Luận văn Một số ứng dụng của số học trong lý thuyết mật mã

Trước những năm 70 của thế kỷ XX, Số học thường được xem là một trong những ngành toán học thuần tuý, chỉ có ý nghĩa lý thuyết. Đối tượng nghiên cứu của Số học là các quy luật trong tập hợp số, giả thuyết lớn tồn tại trong Số học là các giả thuyết số nguyên tố. Thậm chí, có những nhà toán học cho rằng vẻ đẹp của Số học có được nhờ sự xa rời thực tiễn của nó! (theo câu nói của G.H. Hardy, A Mathematician's Apology, 1940). Vμo những n ̈m đầu thế kỷ XX hệ mã mới có tính bảo mật cao hơn được xuất hiện với sự ra đời của hệ mã British Playfair n ̈m 1910, đó lμ mã khối thông qua phép thay thế theo chìa. Song song với qu ̧ trình ph ̧t triển của lịch sử vμ nhu cầu về bảo mật thông tin tran nhiều lĩnh vực đã thúc đẩy c ̧c hệ mã mới ra đời có tính bảo mật ngμy cμng cao, như hệ mã mũ của Pohlig vμ Hellman (n ̈m 1978), tiếp theo lμ giao thức trao đổi chìa kho ̧ của Diffie- Hellman, sau nữa lμ hệ mã ElGamal. Một nét chung của hai hệ mã tran lμ cho phép công bố công khai một phần thông tin cho việc lập mã gọi lμ ho ̧ với kho ̧ công khai, mã một mô hình hoμn hảo cho hệ mã kiểu nμy được công bố bởi Rivest, Shamir vμ Adleman vμo n ̈m 1978, mang tan RSA. Hệ mã RSA vẫn đang lμ một th ̧ch thức lớn đối với những nhμ th ̧m mã. Mục đích của bản luận v ̈n nμy nhằm trình bμy cơ sở của việc ̧p dụng lý thuyết số vμo mật mã, đặc biệt lμ mã ho ̧ RSA vμ một số thuật to ̧n phân tích số nguyan đang sử dụng trong th ̧m mã. Luận v ̈n gồm hai chương. Chương I trình bμy c ̧c kiến thức chuẩn bị phục vụ cho chương sau như c ̧c kh ̧i niệm về thuật to ̧n, độ phức t1p của thuật to ̧n, c ̧c kiến thức về đồng dư vμ phân số lian tục. Chương II trình bμy một số hệ mã đơn giản, hệ mã thông dụng, hệ mã RSA vμ ứng dụng của số học vμo mật mã kho ̧ công khai như phân tích Fecmat, phân tích Fecmat mở rộng, phân tích sử dụng phân số lian tục, phân tích dùng phương ph ̧p của Pollard. Từ đó viết một số thủ tục phân tích số, thủ tục lập mã vμ giải mã ch1y tran Maple. Mục lục Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Một số kiến thức cơ bản 1.1 2 5 Thuật to ̧n vμ độ phức t1p của thuật to ̧n . . . . . . . . . . . . . . . . . . . . 5 1.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 1.2 Kh ̧i niệm: Độ phức t1p của thuật to ̧n . . . . . . . . . . . . . . . . . . . . . . . . 7 Phép tính đồng dư vμ c ̧c vấn đề lian quan . . . . . . . . . . . . . . . . . . . 1.2.1 1.2.2 Thuật to ̧n Euclid vμ mở rộng 10 . . . . . . . . . . . . . . . 10 . . . . . . . . . . . . . . . . . . . . . . 11 1.2.3 Phi - hμm Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.4 Phép tính đồng dư vμ phương trình đồng dư . . . . . . . . . . . . . . 13 1.2.5 Định lý Fermat vμ c ̧c mở rộng . . . . . . . . . . . . . . . . . . . . . 14 1.2.6 Tính to ̧n với đồng dư của luỹ thừa bậc lớn . . . . . . . . . . . . . . . 15 1.2.7 1.3 Số nguyan tố vμ định lý cơ bản của số học Thặng dư bình phương vμ ký hiệu Legendre . . . . . . . . . . . . . . . 16 Phân số lian tục 1.3.1 1.3.2 2 Kh ̧i niệm. Tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Một số ứng dụng của số học trong lý thuyết mật mã 2.1 21 Hệ mã Ceasar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 Hệ Mã Khối . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Một số hệ mã mũ thông dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.1 Hệ mã mũ của Pohligvμ Hellman 26 2.2.2 Giao thức trao đổi chìa kho ̧ của Diffie - Hellman . . . . . . . . . . . 29 2.2.3 Hệ mã ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2.4 Hệ mã RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Phân tích ra thừa số nguyan tố . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.1 Phân tích Fermat vμ mở rộng của nó . . . . . . . . . . . . . . . . . . 35 2.3.2 Phân tích sử dụng lian phân số. . . . . . . . . . . . . . . . . . . . . . 40 2.3.3 2.3 21 2.1.1 2.2 Nguyan t3⁄4c chung vμ một số hệ mã đơn giản . . . . . . . . . . . . . . . . . . Phân tích dùng phương ph ̧p của Pollard . . . . . . . . . . . . . . . . . 43 . . . . . . . . . . . . . . . . . . . . Tμi liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46