Bà GIÁO DĀC VÀ ĐÀO T¾O TR¯äNG Đ¾I HàC QUÀN LÝ VÀ CÔNG NGHà HÀI PHÒNG ----------------------------------- Đâ ÁN TàT NGHIàP NGÀNH : CÔNG NGHà THÔNG TIN Sinh viên : Đß Hoàng Anh GiÁng viên h°ãng d¿n : TS Hã Văn Canh HÀI PHÒNG – 2023 Bà GIÁO DĀC VÀ ĐÀO T¾O TR¯äNG Đ¾I HàC QUÀN LÝ VÀ CÔNG NGHà HÀI PHÒNG ----------------------------------- PH¯¡NG PHÁP NHÀN BI¾T Sà NGUYÊN Tà 2N-1 Đâ ÁN TàT NGHIàP Đ¾I HàC Hà CHÍNH QUY NGÀNH: CÔNG NGHà THÔNG TIN Sinh viên : Đß Hoàng Anh GiÁng viên h°ãng d¿n : TS Hã Văn Canh HÀI PHÒNG – 2023 Bà GIÁO DĀC VÀ ĐÀO T¾O TR¯äNG Đ¾I HàC QUÀN LÝ VÀ CÔNG NGHà HÀI PHÒNG -------------------------------------- NHIàM VĀ ĐÀ TÀI TàT NGHIàP Sinh viên: Đß Hoàng Anh Mã SV: 1812101004 Lãp : CT2201C Ngành : Công nghá thông tin Tên đÁ tài: Ph°¢ng pháp nhÁn biÁt sá nguyên tá d¿ng 2n-1 NHIàM VĀ ĐÀ TÀI 1. Mô tÁ tóm tÃt đÁ tài: - Tìm hiáu vß vai trò cÿa sá nguyên tá trong an toàn b¿o mÁt thông tin - Tìm hiáu các ph°¢ng pháp nhÁn biÁt sá nguyên tá d¿ng 2n-1 - Cài đÁt ch°¢ng trình thā nghiám.Các tài liáu cÅn thi¿t [1] Hồ Văn Canh, Lê Danh C°ßng (2018): MÁt mã và an toàn thông tin: Lý thuyÁt và āng dāng. NXB: Thông tin và Truyßn thông – 8/2018. Van Oorschot, S cott A.
Vanstone (1999): Handbook of Applied Cryptography. CRC Press: Boca Raton, New York, London, Tokyo. [3] Neal Koblitz (2000): A Course in Number Theory and Cryptography. Springer-Verlag Press: New York, Berlin Heidelberg, London, Pái, and Tokyo (2000).
[4] Phan Đình Diáu (2002): MÁt mã và an toàn thông tin. NXB Đ¿i hác Quác gia Hà Nái năm 2002 .[5] Trßnh NhÁt TiÁn ( 2003): MÁt mã và an toàn CSDL. NXB ĐHQG Hà Nái năm 2003.Đßa điÃm thực tÁp tát nghiáp Công ty cổ phần đầu t° tài chính và công nghá Datatech CÁN Bà H¯âNG D¾N ĐÀ TÀI TàT NGHIàP Há và tên : Hồ Văn Canh Hác hàm, hác vß : Đ¿i Tá-TiÁn Sĩ C¢ quan công tác : Hác Vián Kỹ ThuÁt MÁt Mã Nái dung h°ãng d¿n: Nái dung dự kiÁn - Mát sá khái niám c¢ b¿n trong sá hác, đ¿i sá. - Mát sá ph°¢ng pháp kiám tra sá nguyên tá.
- Āng dāng cÿa sá nguyên tá và thā nghiám ch°¢ng trình. Đß tài tát nghiáp đ°ÿc giao ngày 17 tháng 4 năm 2023 Yêu cầu ph¿i hoàn thành xong tr°ớc ngày 17 tháng 6 năm 2023 Đã nhÁn nhiám vā ĐTTN Đã giao nhiám vā ĐTTN Sinh viên Gi¿ng viên h°ớng d¿n Đß Hoàng Anh TS. Hã Văn Canh Hải Phòng, ngày 8 tháng 6 năm 2023 TR¯æNG KHOA CàNG HÒA Xà HàI CHĂ NGH)A VIàT NAM Đác lÁp - Tự do - H¿nh phúc PHI¾U NHÀN XÉT CĂA GIÀNG VIÊN H¯âNG D¾N TàT NGHIàP Há và tên gi¿ng viên: Hồ Văn Canh Đ¢n vß công tác: Cāc Kỹ thuÁt Nghiáp Vā-CBA Há và tên sinh viên: Đß Hoàng Anh Ngành: Công nghá thông tin Đß tài tát nghiáp: Ph°¢ng pháp nhÁn biÁt sá nguyên tá d¿ng 2n-1. Tinh thÅn thái đá căa sinh viên trong quá trình làm đÁ tài tát nghiáp &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 2.
Đánh giá chÃt l°ÿng căa đã án/khóa luÁn(so vãi nái dung yêu cÅu đã đÁ ra trong nhiám vā Đ.N trên các lý luÁn, thực tißn, tính toán sá liáu…) &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 3. Ý ki¿n căa giÁng viên h°ãng d¿n tát nghiáp Đ¿t Không đ¿t Điám:&&&&&&&&&&&&&. Hải Phòng, ngày 8 tháng 6 năm 2023 GiÁng viên h°ãng d¿n (Ký và ghi rõ họ tên) CàNG HÒA Xà HàI CHĂ NGH)A VIàT NAM Đác lÁp - Tự do - H¿nh phúc PHI¾U NHÀN XÉT CĂA GIÀNG VIÊN CHÂM PHÀN BIàN Há và tên gi¿ng viên: Đ¢n vß công tác: Há và tên sinh viên: Đß Hoàng Anh Ngành: Công nghá thông tin Đß tài tát nghiáp:. PhÅn nhÁn xét căa giÁng viên chÃm phÁn bián &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 2.
Những mặt còn h¿n ch¿ &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 3. Ý ki¿n căa giÁng viên chÃm phÁn bián Đ°ÿc b¿o vá Không đ°ÿc b¿o vá Điám&&&& H¿i Phòng, ngày 13 tháng 6 năm 2023 GiÁng viên chÃm phÁn bián (Ký và ghi rõ há tên) LäI CÀM ¡N Lßi đầu tiên, em xin gāi lßi c¿m ¢n chân thành đÁn các Thầy Cô trong Khoa Công Nghá Thông, Tr°ßng Đ¿i hác Qu¿n Lý và Công Nghá H¿i Phòng đã gi¿ng d¿y, chỉ b¿o cho em kiÁn thāc và kinh nghiám quý báu trong suát 4 năm hác t¿i tr°ßng đá em có thá thực hián đồ án tát nghiáp này. ĐÁc biát em xin gāi lßi c¿m ¢n sâu sắc tới Thầy Hồ Văn Canh ng°ßi đã trực tiÁp h°ớng d¿n và tÁn tình giúp đỡ em hoàn thành tát đồ án tát nghiáp cÿa mình. Em cũng xin c¿m ¢n Cô Nguyßn Thß Xuân H°¢ng – Lãnh đ¿o Khoa Công Nghá Thông Tin đã luôn t¿o đißu kián cho em và các b¿n trong suát quá trình hác cũng nh° thực hián các công tác tát nghiáp.
Em xin trân tráng c¿m ¢n Ban lãnh đ¿o, các Thầy Cô á các phòng ban cÿa Tr°ßng ĐH Qu¿n Lý và Công Nghá H¿i Phòng đã cho em môi tr°ßng hác tÁp tát nhÁt có thá tÿ khi em bắt đầu đÁt chân vào gi¿ng đ°ßng và cho đÁn khi hoàn thành đồ án tát nghiáp quan tráng nhÁt trong cuác đßi sinh viên. Trong quá trình thực tÁp, cũng nh° là trong quá trình làm đồ án tát nghiáp em không tránh khßi những thiÁu sót vß trình đá lý luÁn cũng nh° kinh nghiám thực tißn nên em rÁt mong sự đóng góp ý kiÁn và chỉ b¿o tÿ Thầy, Cô đá em tiÁn bá h¢n và có thêm nhißu kinh nghiám và kiÁn thāc đá có thá góp ích cho những công viác sau này. Em xin chân thành cÁm ¢n! LäI CAM ĐOAN Em xin cam đoan rằng đß tài này đ°ÿc tiÁn hành mát cách minh b¿ch, công khai. Mái thā đ°ÿc dựa trên sự cá gắng cũng nh° sự nß lực cÿa b¿n thân cùng với sự giúp đỡ cÿa thầy Hồ Văn Canh.
Các sá liáu và kÁt qu¿ nghiên cāu đ°ÿc đ°a ra trong đồ án là trung thực và không sao chép hay sā dāng kÁt qu¿ cÿa bÁt kỳ đß tài nghiên cāu nào t°¢ng tự. NÁu nh° phát hián rằng có sự sao chép kÁt qu¿ nghiên cāu đß những đß tài khác b¿n thân em xin chßu hoàn toàn trách nhiám. H¿i Phòng, ngày 13 tháng 6 năm 2022 Sinh viên (Ký và ghi rõ há tên) MĀC LĀC LäI CÀM ¡N. 1 DANH MĀC VI¾T TÂT.
1 CH¯¡NG I: CÁC KHÁI NIàM C¡ BÀN .MàT Sà KHÁI NIàM TRONG Sà HàC, Đ¾I Sà. Khái niám trong sá hác .Khái niám trong đ¿i sá .MàT Sà THUÀT TOÁN. Error! Bookmark not defined.ThuÁt toán tính °ớc chung lớn nhÁt. Error! Bookmark not defined.ThuÁt toán tính phần tÿ nghßch đ¿o theo Modulo.
Error! Bookmark not defined.ThuÁt toán phân tích mát sá ra các thÿa sá nguyên tá. Error! Bookmark not defined. Đà PHĀC T¾P TÍNH TOÁN. Error! Bookmark not defined.
Khái niám vß đá phāc t¿p tính toán. Error! Bookmark not defined. Error! Bookmark not defined. Hàm mát phía và cāa sÁp mát phía.
Error! Bookmark not defined. Error! Bookmark not defined. CH¯¡NG 2: MàT Sà PH¯¡NG PHÁP KIÂM TRA Sà NGUYÊN Tà. Error! Bookmark not defined.
Sà NGUYÊN Tà .Khái niám sá nguyên tá. Tính chÁt cÿa sá nguyên tá.4: Sự phân bá cÿa sá nguyên tá. Sà NGUYÊN Tà CÓ D¾NG ĐÀC BIàT. Error! Bookmark not defined.
Error! Bookmark not defined. Sá nguyên tá Lucas-Lehmer. Error! Bookmark not defined.Sá nguyên tá d¿ng Fermat. Error! Bookmark not defined.
MàT Sà PH¯¡NG PHÁP KIàM TRA Sà NGUYÊN Tà. Error! Bookmark not defined.1 Ph°¢ng pháp cổ đián. Error! Bookmark not defined.2 Ph°¢ng pháp xác suÁt. Error! Bookmark not defined.
Error! Bookmark not defined. CH¯¡NG 3: ĄNG DĀNG CĂA Sà NGUYÊN Tà VÀ THĈ NGHIàM CH¯¡NG TRÌNH. THĀ NGHIàM CH¯¡NG TRÌNH. Error! Bookmark not defined.
CÁu hình há tháng. Error! Bookmark not defined. Chāc năng chính. Error! Bookmark not defined.
Cài đÁt há tháng. Error! Bookmark not defined. 46 TÀI LIàU THAM KHÀO. 54 DANH MĀC HÌNH Hình 1.1: Mô t¿ quá trình tính toán cÿa thuÁt toán Euclid.
Error! Bookmark not defined.2: Mô t¿ quá trình tính toán cÿa thuÁt toán Euclid má ráng. Error! Bookmark not defined.1: ThuÁt toán phân tích thÿa sá n-1. Error! Bookmark not defined.3: ThuÁt toán phân tích thÿa sá(cho tr°ớc sá mũ gi¿i mã a). Error! Bookmark not defined.4: ThuÁt toán phân tích cổ đián.
Error! Bookmark not defined.2: Đồ thß biáu dißn các chā sá cÿa sá nguyên tá Mersenne lớn nhÁt đã biÁt theo tÿng năm cÿa kỳ nguyên đián tā. Error! Bookmark not defined.3 Kiám tra sá nguyên tá 2,5000. Error! Bookmark not defined.4 KÁt qu¿ tr¿ vß cÿa ch°¢ng trình sá nguyên tá 2n -1, cÿa 2,11213. Error! Bookmark not defined.5 KÁt qu¿ nhÁn đ°ÿc sau khi liát kê tÿ 1 -> 5000.
Error! Bookmark not defined.5 Phân tích thÿa sá nguyên tá 27,102,1001,5000. Error! Bookmark not defined. DANH MĀC TĆ VI¾T TÂT Tć vi¿t tÃt Ti¿ng Anh Ti¿ng Viát Ged Greatest Common Divisor ¯ớc sá chung lớn nhÁt Lcm Least Common Multiple Bái sá chung nhß nhÁt Mod Modulo Mæ ĐÄU Ta biÁt rằng sá nguyên tá và đÁt biát là sá nguyên tá lớn đóng vai trò rÁt quan tráng trong nhißu lĩnh vực vß an toàn – b¿o mÁt thông tin nh°: Trong h¿ tần c¢ sá khóa công khai, trong các há mÁt mã RSA, Elgamal, trong xác thực và chữ ký đián tā, vv. Tuy nhiên mát vÁn đß đÁt ra là làm thÁ nào đá khẳng đßnh mát sá nguyên d°¢ng N nào đó là sá nguyên tá hay hÿp sá? Ta biÁt rằng sá nguyên tá là mát sá chia hÁt cho mát và chính nó.
Nh° vÁy sá nguyên tá là mát sá nguyên (d°¢ng) lẻ? Vì nÁu nó là sá ch¿n thì nó s¿ chia hÁt cho 2 và nh° vÁy, nó không ph¿i là mát sá nguyên tá. VÁy sá nguyên tá (trÿ sá 2) là mát sá lẻ. Nh°ng sá lẻ ch°a hẳn đã là sá nguyên tá. ví dā: Sá 9 là sá lẻ nh°ng không ph¿i là sá nguyên tá.
Sá 15 là sá lẻ nh°ng cũng không ph¿i là sá nguyên tá. Sá 2047 cũng không ph¿i là sá nguyên tá vì (2047 = 23.89) VÁy cho mát sá nguyên lẻ n bÁt kỳ làm thá nào đá nhÁn biÁt đ°ÿc n là sá nguyên tá (chỉ chia hÁt cho 1 và chính nó)? ĐÁn nay đã có nhißu tài liáu nghiên cāu vß vÁn đß này chẳng h¿n trong Knut(2004):= The Artof Programming Computer= (TÁp II- 2004): < chẳng h¿n thuÁt toán sàng bình ph°¢ng < (Quadratic Sieve algerithin) [1: Alfred J.van Oorschot and Scott A.Vanstone (1998) CRC press: Boca Raton. Newyork, London and Tokyo(1998) ]. CÁC KHÁI NIàM C¡ BÀN 1.
MàT Sà KHÁI NIàM TRONG Sà HàC, Đ¾I Sà 1. Khái niám trong sá hác 1). Ký hiáu chia h¿t Cho a và b là hai sá nguyên d°¢ng. Sá a chia hÁt cho sá b ký hiáu là a b Tồn t¿i n þ N sao cho: a=b*n Khi đó ng°ßi ta nói b là °ớc cÿa a và ký hiáu: b | a.