Tài liệu Phân tích thừa số nguyên tố và ứng dụng trong mật mã

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ———————o0o——————– KHÓA LUẬN TỐT NGHIỆP PHÂN TÍCH THỪA SỐ NGUYÊN TỐ VÀ ỨNG DỤNG TRONG MẬT MÃ Chuyên ngành: TOÁN ỨNG DỤNG Giảng viên hướng dẫn: Sinh viên: Trần Vĩnh Đức Đặng Kiều Trang Lớp: K37-sp Toán HÀ NỘI, 5/2015 LỜI CẢM ƠN Bài khóa luận này được hoàn thành dưới sự hướng dẫn nhiệt tình của thầy giáo T.S Trần Vĩnh Đức. Qua đây em xin gửi lời cảm ơn sâu sắc tới các thầy cô trong tổ Toán ứng dụng và các thầy cô trong khoa Toán trường ĐHSP Hà Nội 2 đã giúp đỡ em trong quá trình học tập để thuận lợi cho việc nghiên cứu. Đặc biệt, em xin gửi lời cảm ơn chân thành tới thầy giáo T.S Trần Vĩnh Đức người đã dành cho em sự hướng dẫn nhiệt tình, chu đáo và chỉ bảo cho em trong suốt quá trình học tập nghiên cứu và thực hiện khóa luận. Dù đã hết sức cố gắng, nhưng do đây là lần đầu tiên làm quen với việc nghiên cứu khoa học và do năng lực còn hạn chế nên khó tránh khỏi những sai sót. Em mong muốn nhận được sự chỉ bảo, đóng góp của quí thầy cô để cho bài khóa luận được tốt hơn. Em xin chân thành cảm ơn! Hà Nội, tháng 05 năm 2015 Sinh viên Đặng Kiều Trang LỜI CAM ĐOAN Sau một thời gian nghiên cứu với sự cố gắng, nỗ lực của bản thân cùng sự hướng dẫn nhiệt tình chỉ bảo của thầy giáo T.S Trần Vĩnh Đức em đã hoàn thành bài khóa luận của mình. Em xin cam đoan bài khóa luận là do bản thân nghiên cứu cùng với sự hướng dẫn của thầy giáo T.S Trần Vĩnh Đức không hề trùng với bất cứ đề tài nào. Hà Nội, tháng 05 năm 2015 Sinh viên Đặng Kiều Trang MỤC LỤC Lời cảm ơn 1 Lời cam đoan 2 1 Phân tích thừa số nguyên tố và ứng dụng trong mật mã 1.1 Công thức Euler . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Hệ mật mã khóa công khai RSA . . . . . . . . . . . . . . . 1.3 Kiểm tra tính nguyên tố . . . . . . . . . . . . . . . . . . . 1.4 Thuật toán phép nhân tử hóa Pollard p-1 . . . . . . . . . 1.5 Phân tích thừa số qua hiệu của các bình phương . . . . . . 2 Số 2.1 2.2 2.3 trơn, sàng và xây Số trơn . . . . . . Sàng bậc hai . . . Sàng trường số . Tài liệu tham khảo dựng quan hệ cho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . phép nhân . . . . . . . . . . . . . . . . . . . . . tử . . . . . . RSA . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 10 14 19 23 hoá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 33 34 41 . . . . . . . . . . . . . . . . . . . . . . . . . 46 CHƯƠNG 1 PHÂN TÍCH THỪA SỐ NGUYÊN TỐ VÀ ỨNG DỤNG TRONG MẬT MÃ RSA 1.1 Công thức Euler Phương pháp thay đổi khóa Diffie-Hellman và hệ thống mật mã khóa công khai ElGamal đã nghiên cứu dựa trên thực tế thì nó rất dễ để tính lũy thừa an mod p, nhưng rất khó để tìm lại các số mũ n nếu ta chỉ biết giá trị của a và an mod p. Một kết quả quan trọng mà chúng ta sử dụng để phân tích tính đúng đắn của Diffie-Hellman và ElGamal là Định lý Fermat nhỏ, ap−1 ≡ 1(mod p) với mọi a 6≡ 0 (mod p). Định lý Fermat nhỏ thể hiện một tính chất tốt của các số nguyên tố. Nó cho ta biết điều gì sẽ xảy ra nếu thay p bằng số m không phải là số nguyên tố, tức là am−1 ≡ 1 (mod p) có đúng không? Ta thấy câu trả lời là không. Trong phần này ta đi tìm hiểu khái quát tính đúng đắn của Định lý Fermat nhỏ khi m = pq là tích của hai số nguyên tố phân biệt, vì đây là trường hợp quan trọng nhất trong các ứng dụng mã hóa. Ta bắt đầu với một ví dụ. Với lũy thừa modun 15 sẽ làm như thế nào? Nếu ta thực hiện bảng của lũy thừa bậc 2 và bậc 3 mod 15, chúng trông không thật thú vị, nhưng nhiều lũy thừa bậc 4 đồng dư với 1 mod 15. Cụ thể, ta thấy rằng a4 ≡ 1 (mod 15) với a = 1, 2, 4, 7, 8, 11, 13 và 14; a4 6≡ 1 (mod 15) với a = 3, 5, 6, 9, 10 và 12. Vậy sự khác nhau giữa dãy các số 1, 2, 4, 7, 8, 11, 13, 14 với dãy các số 3, 5, 6, 9, 10, 12, 15 là gì? Ta thấy, mỗi số 3, 5, 6, 9, 10, 12, 15 đều có một bội chung 15, còn các số 4 1, 2, 4, 7, 8, 11, 13, 14 là các số nguyên tố cùng nhau với 15. Điều này cho thấy rằng một số phiên bản của Định lý nhỏ Fermat cũng đúng nếu số a là số nguyên tố cùng nhau với modun m, nhưng số mũ không nhất thiết phải là m − 1. Cho m = 15 ta thấy số mũ đúng là 4. Tại sao là 4? Ta có thể dễ dàng kiểm tra với mỗi giá trị của a, nhưng có một thuật toán cụ thể sẽ tốt hơn. Để chứng minh a4 ≡ 1 (mod 15) ta cần kiểm tra 2 đồng dư thức Từ (1.1) ta thấy a4 ≡ 1 (mod 3) và a4 ≡ 1 (mod 5). (1.1) . . a4 − 1 .. 3 và a4 − 1 .. 5 . Do đó a4 − 1 .. 15. Hai đồng dư thức trong (1.1) là nguyên tố theo modun nên ta có thể sử dụng Định lý Fermat nhỏ để kiểm tra chúng là đúng. Thật vậy a4 = (a2)2 = (a(3−1))2 ≡ 12 ≡ 1 (mod 3), a4 = a5−1 ≡ 1 (mod 5). Nếu quan sát hai đồng dư thức này, ta sẽ thấy các tính chất thiết yếu của lũy thừa 4 đó là p − 1 là bội của 4 với p = 3 và p = 5. Bằng việc quan sát này, ta sẽ có các công thức cơ bản làm nền tảng cho các hệ thống mật mã khóa công khai RSA. Định lí 1.1.1 (Công thức Euler cho pq). Cho p và q là 2 số nguyên tố khác nhau và cho Khi đó g = UCLN(p − 1, q − 1). a(p−1)(q−1)/g ≡ 1 (mod pq) ∀a thỏa mãn UCLN(a, pq) = 1. Đặc biệt, nếu p và q là các số nguyên tố lẻ, thì a(p−1)(q−1)/2 ≡ 1 (mod pq) ∀a thỏa mãn UCLN(a, pq) = 1. . . Chứng minh. Theo giả thiết ta thấy p 6 .. a và g .. q − 1, nên ta có thể tính a(p−1)(q−1)/g = (a(p−1))(q−1)/g vì (q − 1)/g là một số nguyên, ≡ 1(q−1)/g (mod p) vì ap−1 ≡ 1 (mod p) theo Định lý Fermat nhỏ, ≡ 1 (mod p) vì 1 lũy thừa luôn bằng 1! 5 Tương tự, thay đổi vai trò của p và q, ta có a(p−1)(q−1)/g ≡ 1 (mod q). Như vậy a(p−1)(q−1)/g − 1 chia hết cho cả p và q, do đó nó chia hết cho pq. Ta được điều phải chứng minh. Phương pháp thay đổi khóa Diffie-Hellman và hệ thống mật mã khóa công khai ElGamal phụ thuộc vào những khó khăn khi giải phương trình dạng ax ≡ b (mod p). Trong đó a, b và p là các số đã biết, p là số nguyên tố, và x là ẩn. Hệ thống mật mã khóa công khai RSA mà chúng ta nghiên cứu trong phần tiếp theo phụ thuộc vào độ khó của việc giải phường trình dạng xe ≡ c (mod N), Với e, c và N là các số đã biết và x là ẩn. Nói cách khác, việc bảo mật của RSA dựa trên giả thiết là nó rất khó để tính căn bậc e modun N. Đây có phải là một giả thuyết hợp lý? Nếu modun N là số nguyên tố thì sẽ tương đối dễ dàng trong việc để tính căn bậc e modun N, như được trình bày trong các mệnh đề dưới đây. Mệnh đề 1.1.2. Cho p là một số nguyên tố và e ≥ 1 là một số nguyên thỏa mãn UCLN(e, p − 1) = 1. Ta thấy rằng e có modun nghịch đảo p − 1, ta nói de ≡ 1 (mod p − 1). Khi đó đồng dư thức xe ≡ c (mod p). có nghiệm duy nhất x ≡ cd (mod p). Chứng minh. Nếu c ≡ 0 (mod p), thì x ≡ 0 (mod p) là nghiệm duy nhất mà ta cần tìm. Giả sử c 6≡ 0 (mod p). Đồng dư thức de ≡ 1 (mod p − 1) có nghĩa là tồn tại một số nguyên k sao cho de = 1 + k(p − 1). 6 Bây giờ ta kiểm tra cd là một nghiệm của phương trình xe ≡ c (mod p) : (cd )e ≡ cde (mod p) ≡ c1+k(p−1) (mod p) ≡ c(cp−1)k (mod p) ≡ c · 1k (mod p) ≡ c (mod p). luật số mũ, vì de = 1 + k(p − 1), luật số mũ, từ Định lý Fermat nhỏ, Như vậy x = cd là một nghiệm của xe ≡ c (mod p). Để chứng minh nghiệm đó là duy nhất, ta giả sử x1 và x2 là hai nghiệm của đồng dư thức 1.1.2. Ta chỉ cần chứng minh z de ≡ z (mod z) với z bất kỳ, ta thấy x1 ≡ x1 de ≡ (x1e )d ≡ cd ≡ (x2e)d ≡ x2de ≡ x2 (mod p). Vậy Mệnh đề 1.1.2 có nghiệm duy nhất. Ví dụ 1.1.3. Giải đồng dư thức sau x1583 ≡ 4714 (mod 7919), Với modun p = 7919 là số nguyên tố. Theo Mệnh đề 1.1.2, đầu tiên ta cần giải đồng dư thức 1583d ≡ 1 (mod 7918). Để tìm d ta sử dụng thuật toán Euclide mở rộng, ta tìm được d ≡ 5277 (mod 7981). Từ Mệnh đề 1.1.2 ta thấy x ≡ 47145277 ≡ 6059 (mod 7919) là nghiệm của x1583 ≡ 4714 (mod 7919). Mệnh đề 1.1.2 cho thấy rằng rất dễ để tính nghệm nếu modun p là một số nguyên tố. Trong trường hợp cho modun N là một hợp số thì sẽ có một sự khác biệt rất quan trọng. Nếu chúng ta biết phân tích N thì lại dễ dàng để tính nghiệm. Các mệnh đề sau đây trình bày phương pháp làm trong trường hợp N = pq là tích của hai số nguyên tố. Các trường hợp tổng quát được để lại xem như Bài tập. 7 Mệnh đề 1.1.4. Cho p và q là các số nguyên tố khác nhau và e ≥ 1 thỏa mãn UCLN(e, (p − 1)(q − 1)) = 1. Ta thấy e có modun nghịch đảo là (p − 1)(q − 1), ta nói de ≡ 1 (mod (p − 1)(q − 1)). Khi đó đồng dư thức xe ≡ c (mod pq), có nghiệm duy nhất x ≡ cd (mod pq). (1.2) Chứng minh. Giả sử UCLN(c, pq) = 1, (làm tương tự cho các trường hợp khác). Chứng minh của Mệnh đề 1.1.4 tương tự như phần chứng minh của Mệnh đề 1.1.2, nhưng thay vì sử dụng định lý Fermat nhỏ, ta sử dụng công thức Euler (Định lý 1.1.1). Các đồng dư thức de ≡ 1 (mod (p − 1)(q − 1)) có nghĩa là tồn tại số nguyên k sao cho de = 1 + k(p − 1)(q − 1). Bây giờ ta kiểm tra cd là nghiệm của xe ≡ c (mod pq) : (cd )e ≡ cde (mod pq) ≡ c1+k(p−1)(q−1) (mod pq) ≡ c(cp−1 )k (mod pq) ≡ c.1k (mod pq) ≡ c (mod pq). luật số mũ, vì de = 1 + k(p − 1)(q − 1), luật số mũ, từ công thức Euler (Định lý 1.1.1), Do đó x = cd là nghiệm của đồng dư thức (1.2). Ta đi chứng minh nghiệm này là duy nhất. Giả sử x = u cũng là nghiệm của (1.2), khi đó u ≡ ude−k(p−1)(q−1) vì de = 1 + k(p − 1)(q − 1). ≡ (ue)d .(u(p−1)(q−1))−k ≡ (ue)d .1−k (mod pq) sử dụng công thức Euler (Định lý 1.1.1) ≡ cd (mod pq) vì u là nghiệm của (1.2) Do đó, tất cả nghiệm của (1.2) đều đồng dư với cd (mod pq), như vậy đó là nghiệm duy nhất. 8 Nhận xét 1.1.5. Mệnh đề 1.1.4 đưa ra một thuật toán để giải xe ≡ c(mod pq). Đầu tiên là giải de = 1(mod (p − 1)(q − 1)), rồi tính cd (mod pq). Ta có thể làm cho các tính toán nhanh hơn bằng cách sử dụng một giá trị nhỏ hơn d. Cho g = UCLN(p − 1, q − 1) và giả sử ta giải đồng dư thức sau với d :   (p − 1)(q − 1) de ≡ 1 mod . g Từ công thức Euler (Định lý 1.1.1) ta có a(p−1)(q−1)/g ≡ 1 (mod pq). Do đó như trong chứng minh của Mệnh đề 1.1.4, nếu ta viết de = 1 + k(p − 1)(q − 1)/g, thì (cd )e = cd e = c1+k(p−1)(q−1)/g = c.(c(p−1)(q−1))k ≡ c (mod pq). Vì vậy sử dụng giá trị nhỏ hơn này của d, ta vẫn thấy rằng cd mod pq là nghiệm của xe ≡ c (mod pq). Ví dụ 1.1.6. Giải đồng dư thức x17389 ≡ 43927 (mod 64349), với modun N = 64 · 349 = 229 · 281 là tích của hai số nguyên tố p = 229 và q = 281. Bước đầu tiên là giải đồng dư thức 17389 ≡ 1 (mod 63840), với 63840 = (p − 1)(q − 1) = 228 · 280. Giải đồng dư thức, ta được d = 53509 (mod 63840). Sau đó, từ Mệnh đề 1.1.4 ta có x ≡ 4391253509 ≡ 14458 (mod 64349), là nghiệm của x17389 ≡ 43927 (mod 64349). Ta có thể giảm đi một chút công việc bằng cách sử dụng các ý tưởng được trình bày trong Nhận xét 1.1.5. Ta có g = UCLN(p − 1)(q − 1) = UCLN(228, 280) = 4. Dó đó (p − 1)(q − 1)/g = (228)(280)/4 = 15960, từ đây ta có thể tìm được một giá trị của d bằng cách giải đồng dư thức 17389 ≡ 1 (mod 15960), 9 có nghiệm là d ≡ 5629 (mod 15960), và do đó x ≡ 439275629 ≡ 14458 (mod 64349), là nghiệm của x17389 ≡ 14458 (mod 64349). Chú ý rằng ta cũng có những nghiệm tương tự, nhưng ta chỉ cần nâng 43927 lên lùy thừa 5629th, trong khi sử dụng Mệnh đề 1.1.4 yêu cầu trực tiếp ta nâng 43927 lên lũy thừa 53509th. Cách làm này tiết kiệm thời gian, mặc dù không phải là nhiều. Bob Plice Tạo khóa Chọn số nguyên tố bí mật p và q. Chọn số mũ mã hóa e với UCLN(e, (p − 1)(q − 1)) = 1. Cho biết N = pq và e. Mã hóa Chọn bản rõ m. Sử dụng khóa công khai của Bob (N,e) để tính c ≡ me (mod N). Gửi bản mã cho Bob. Giải mã Tính d thỏa mãn ed ≡ 1 (mod (p − 1)(q − 1)). Tính m′ ≡ cd (mod N) khi đó m′ là bản rõ m. Bảng 1.1: Thành lập khóa RSA, mã hóa và giải mã 1.2 Hệ mật mã khóa công khai RSA Bob và Alice có những vấn đề thông thường của việc trao đổi thông tin bí mật trên một đường dây thông tin liên lạc an toàn. Bob và Alice có nhiều cách 10 khác nhau thực hiện công việc này, phụ thuộc vào độ khó của việc giải quyết các bài toán logarit rời rạc. Trong phần này chúng ta trình bày các hệ thống mật mã khóa công khai RSA là hệ thống phát minh đầu tiên và tất nhiên được biết đến nhiều nhất. RSA được đặt tên theo những nhà phát minh ra nó là Ron Rivest, Adi Shamir và Leonard Adleman. Việc bảo mật RSA phụ thuộc vào phép lưỡng phân sau • Thiết lập. Cho p và q là số nguyên tố lớn, cho N = pq, và cho e và c là các số nguyên. • Bài toán. Giải đồng dư thức xe ≡ c (mod N) với ẩn x. Thuận lợi. Bob, người biết được các giá trị của p và q, có thể dễ dàng tìm x như trình bày trong Mệnh đề 1.1.4. Khó khăn. Eve, người không biết giá trị của p và q, không thể dễ dàng tìm x. Phép lưỡng phân. Giải xe ≡ c (mod N) là dễ dàng cho người có thêm thông tin bổ sung, nhưng nó dường như là khó khăn cho tất cả những người khác. Hệ thống mật mã khóa công khai RSA được tóm tắt trong Bảng 1.1. Khóa bí mật của Bob là một cặp số nguyên tố lớn p và q. Khóa công khai của ông là cặp (N, e) gồm tích N = pq và một số mũ mã hóa e nguyên tố cùng nhau. Alice có bản rõ của mình và biến đổi nó thành số nguyên m trong khoảng từ 1 đến N. Cô mã hóa m bằng cách tính đại lượng c ≡ me (mod N). Số nguyên c là bản mã của cô, mà cô gửi cho Bob. Bob dễ dàng giải đồng dư thức xe ≡ c (mod N) để phục hồi thông tin m của Alice, vì Bob đã biết phân tích thừa số N = pq. Mặt khác, Eve có thể chặn được bản mã c nếu cô ấy biết phân tích N, cô có lẽ đã gặp khó khăn khi giải xe ≡ c (mod N). Ví dụ 1.2.1. Có thể minh họa hệ mật khóa công khai RSA với một ví dụ bằng số nhỏ. Tất nhiên, ví dụ này là không an toàn, vì con số này là quá nhỏ nên Eve sẽ dễ phân tích được N. Việc triển khai an toàn của RSA sử dụng modun N với hàng trăm chữ số. Sự Thành Lập Khóa K 11 • Bob chọn hai số nguyên tố bí mật p = 1223 và q = 1987. Bob tính modun chung của chúng N = p.q = 1223.1987 = 2430101. • Bob chọn một số mũ mã hóa công khai e = 948.047 với tính chất UCLN(e, (p − 1), (q − 1)) = UCLN(94807, 2426892) = 1. Mã Hóa RSA • Alice chuyển đổi bản rõ cô thành một số nguyên m = 1070777 thỏa mãn 1 ≤ m < N. • Alice sử dụng khóa công khai của Bob (N, e) = (2430101, 948047) để tính c ≡ me (mod N), c ≡ 107077794807 ≡ 1473513 (mod 2430101). • Alice gửi bản mã c = 1473513 đến Bob. Giải Mã RSA Bob có (p − 1)(q − 1) = 1222.1986 = 2426892, giải ed ≡ 1 (mod (p − 1)(q − 1)), 94807 ≡ 1 (mod 2426892), với d và thấy rằng d = 1051235. Bob lấy bản mã c = 1473513 và tính cd (mod N), 14735131051235 ≡ 1070777 (mod 2430101). Giá trị mà ông tính chính là thông điệp m = 1070777 của Alice. Nhận xét 1.2.2. Các số N và e hình thành khóa công khai của Bob được gọi tương đương với modun và số mũ mã hóa. Số d mà Bod sử dụng giải mã thông tin của Alice mà d thỏa mãn ed ≡ 1 (mod (p − 1)(q − 1)), (1.3) được gọi là chỉ số mã hóa. Rõ ràng là mã hóa sẽ hiệu quả hơn nếu chỉ số mã hóa e là một số nhỏ và tương tự như vậy thì giải mã sẽ hiệu quả hơn nếu chỉ số giải mã d là số nhỏ. Tất nhiên, Bob không thể chọn cả mã hóa và giải mã đều là giá trị nhỏ vì khi một trong hai được lựa chọn thì cái còn lại sẽ được coi là đồng dư thức (1.3). 12 Chú ý rằng Bob không thể lấy e = 2 vì ông cần e là số nguyên tố cùng nhau với (p − 1)(q − 1). Do đó, giá trị nhỏ nhất có thể của e là e = 3. Như chúng ta biết, khi lấy e = 3 thì an toàn như là lấy giá trị lớn hơn của e dù cho vẫn có một số điểm không thỏa đáng. Những ai muốn nhanh chóng mã hóa nhưng lại lo ngại với e = 3 quá nhỏ, khi đó thường lấy e = 216 + 1 = 65537, vì nó chỉ mất bốn phép bình phương và một phép nhân để tính m65537 Một cách khác cho Bob là sử dụng một giá trị nhỏ cho d và sử dụng đồng dư thức (1.3) để xác định e, nên e sẽ lớn. Tuy nhiên, điều này lại có thể dẫn đến phiên bản không an toàn của RSA. Chính xác hơn là nếu d nhỏ hơn N 1/4 , thì lý thuyết liên phân số cho phép Eve phá vỡ RSA. Nhận xét 1.2.3. Thuật toán mã hóa công khai số N = pq, là tích của hai số nguyên tố bí mật p và q. Mệnh đề 1.1.4 cho biết nếu Eve biết giá trị (p−1)(q−1), thì bà có thể giải xe ≡ c (mod N), và dó đó có thể mã hóa những thông tin được gửi cho Bob. Khai triển hệ thức (p − 1)(q − 1) ta được (p − 1)(q − 1) = pq − p − q + 1 = N − (p − q) + 1. (1.4) Bob đã công bố giá trị N, vì vậy Eve bây giờ đã biết N. Do đó, nếu Eve có thể xác định giá trị của tổng p + q thì (1.4) sẽ cho bà biết giá trị (p − 1)(q − 1) có thể giúp bà mã hóa những thông tin. Thực tế, nếu Eve biết các giá trị p + q và pq, thì sẽ rất dễ để tính giá trị của p và q. Bà chỉ cần sử dụng công thức bậc hai để tìm ra những nghiệm của đa thức X 2 − (p − q)X + pq, vì phân tích đa thức thành nhân tử bằng (X − p)(X − q), nên các nghiệm của nó là p và q. Do đó, khi Bob đưa ra giá trị N = pq thì sẽ chẳng dễ dàng cho Eve khi tìm ra giá trị của (p − 1)(q − 1) hơn là khi tìm p và q. Chúng ta minh họa bằng ví dụ sau. Giả sử Eve biết rằng: N = pq = 66240912547 và (p − 1)(q − 1) = 66240396760. Đầu tiên bà sử dụng (1.4) để tính p + q = N + 1 − (p − 1)(q − 1) = 515788. 13 Sau đó bà sử dụng công thức bậc hai để phân tích đa thức thành nhân tử: X 2 − (p + q)X + N = X 2 − 515788X + 66240912547 = (X − 241511)(X − 274277). Phép tính này cho bà phân tích thừa số N = 66240912547 = 241511 · 274277. Nhận xét 1.2.4. Chúng ta có đã cho thấy rằng Eve sẽ chẳng thấy dễ dàng khi xác định (p − 1)(q − 1) hơn là bà phân tích N. Nhưng lại không chứng minh được Eve buộc phải phân tích N để giải mã những thông tin của Bob. Vấn đề là những gì Eve cần làm để giải những đồng dư thức dạng xe ≡ c (mod N), và nhận thức được rằng có thuật toán hiệu quả để giải những đồng dư thức như vậy mà không cần tìm giá trị của (p − 1)(q − 1). Không ai tìm ra phương pháp nào như vậy tồn tại dù gợi ý rằng tính những nghiệm modun N có thể đơn giản hơn phân tích N. 1.3 Kiểm tra tính nguyên tố Bob đã đọc xong các phần trên và bây giờ sẵn sàng truyền thông tin cho Alice bằng cách dùng cặp khóa công khai/bí mật RSA của ông. Để tạo ra cặp khóa mã hóa RSA, Bob cần chọn hai số nguyên tố rất lớn là p và q. Ông không chọn được hai số nguyên tố đủ lớn nhưng có thể là hợp số, đó là những số p và q. Trước hết, nếu p và q không phải là số nguyên tố thì Bob sẽ cần phải biết cách phân tích chúng để giải mã thông tin của Alice. Nhưng thậm chí tệ hơn, nếu p và q là những số nguyên tố nhỏ, thì Eve có thể sẽ phân tích được pq và phá vỡ hệ thống của Bob. Do đó, Bob cần phải tìm ra những số nguyên tố lớn hơn. Chính xác hơn là ông cần một cách nào đó để phân biệt số nguyên tố và hợp số vì nếu ông tìm ra cách làm này, thì ông có thể chọn ngẫu nhiên những số cho tới khi ông thấy nó là số nguyên tố. Chúng ta sẽ thảo luận về vấn đề khả năng số được chọn ngẫu nhiên là số nguyên tố sau này, nhưng bây giờ thì ông đã có cơ hội tốt để thành công. Do đó, những gì Bob thực sự cần là một cách hiệu quả để xác định một số rất lớn là số nguyên tố. 14 Ví dụ, giả sử như Bob chọn số lớn có giá trị: n = 31987937737479355332620068643713101490952335301 và ông muốn biết số n có là số nguyên tố hay không. Đầu tiên Bob tìm những phép phân tích nhỏ nhưng ông lại thấy n không chia hết cho bất kì số nguyên tố nào nhỏ hơn 1000000. Vì vậy, ông bắt đầu nghi ngờ liệu n là số nguyên tố hay không. Tiếp theo, ông tính 2n−1 mod n và ông thấy rằng 2n−1 ≡ 1281265953551359064133601216247151836053160074 (mod n). (1.5) Đồng dư thức (1.5) cho Bob biết rằng n là hợp số dù cho nó không cho ông bất kỳ dấu hiệu nào về cách phân tích n. Tại sao? Xem lại định lý Fermat, nếu p là số nguyên tố thì ap−1 ≡ 1 (mod p) (trừ trương hợp a chia hết cho p). Do đó, nếu n là số nguyên tố, thì vế phải của (1.5) có thể đồng dư với 1, vì nếu không đồng dư với 1 thì Bob kết luận n không là số nguyên tố. Trước khi tiếp tục phần trước đây liên quan đến sự tìm kiếm của Bob về những số nguyên tố lớn, chúng ta phát biểu phiên bản thuận tiện của Định lý Fermat nhỏ, mà không có điều kiện nào ở a. Định lí 1.3.1 (Đinh lý Fermat, phiên bản 2). Cho p là số nguyên tố. Khi đó ap ≡ a (mod p) với mọi số nguyên a. (1.6) Chứng minh. Nếu p ∤ a, thì bản đầu tiên của Định lý Fermat cho thấy ap−1 ≡ 1 (mod p). Khi nhân cả hai vế với a ta chứng minh được (1.6) là đúng. Mặt khác, nếu p|a thì cả hai vế của (1.6) đồng dư với 0 modun p. Quay lại với sự tìm kiếm của Bob, ta thấy ông ấy chẳng có chút lo ngại nào khi ngẫu nhiên chọn một số lớn khác, n = 2967952985951692762820418740138329004315165131. (1.7) Sau khi kiểm tra tính chia hết bởi những số nguyên tố nhỏ, Bob tính 2n mod n và tìm được 2n ≡ 2 (mod n). (1.8) 15 Từ (1.8) kết hợp với Định lý Fermat (1.3.1) có chứng minh được n là số nguyên tố hay không? Câu trả lời là không! Định lý Fermat chỉ làm việc theo một chiều: Nếu p là số nguyên tố, thì ap ≡ a (mod p). Chẳng có gì để cản trở tính đồng dư (1.8) là đúng với các giá trị hợp số của n, và thực tế nghiên cứu cơ bản đưa ra những ví dụ như: 2341 ≡ 2 (mod 341) với 341 = 11.31. Tuy nhiên, khi 2n ≡ 2 (mod n) sẽ có nhiều khả năng n là số nguyên tố, vì nếu giá trị của 2n mod n ra khác thì n là hợp số. Điều này dẫn đến định nghĩa sau đây. Định nghĩa 1.3.2. Số nguyên n cố định. Ta nói số nguyên a là chứng thực (cho tính hợp số) của n nếu an 6≡ a (mod n). Mệnh đề 1.3.3. Cho p là số nguyên tố lẻ và viết: p − 1 = 2k q với q lẻ. Cho a là số bất kì không chia hết cho p, khi đó một trong hai điều kiện sau đây là đúng: (i) aq đồng dư với 1 modun p. (ii) Một trong những aq , a2q , a4q , ..., a2 k−1 q , đồng dư với 1 modun p. Chứng minh. Định lý Fermat nhỏ cho ta biết rằng ap−1 ≡ 1 (mod p). Quan sát dãy số: k−1 k aq , a2q , a4q , ..., a2 q , a2 q , ta biết rằng số cuối cùng trong dãy số là ap−1 , đồng dư với 1 modun p. Hơn nữa, mỗi số trong dãy trên là bình phương của số trước. Do đó, một trong những khả năng sau đây buộc phải xảy ra: (i) Số đầu tiên trong dãy đồng dư với 1 modun p. (ii) Vài số trong dãy không đồng dư với 1 modun p nhưng khi nó được bình phương, nó sẽ đồng dư với 1 modun p. Nhưng số duy nhất thỏa mãn cả hai điều kiện: b 6≡ 1 (mod p) và b2 ≡ 1 (mod p) 16 là −1, vì vậy một trong những số trong dãy là đồng dư với −1 modun p. Điều này hoàn tất chứng minh của Mệnh đề 1.3.3 Đưa vào. Số nguyên n được kiểm tra, số nguyên a như là chứng thực tiềm năng. 1. Nếu n chẵn hoặc 1 < UCLN(a, n) < n, trả lại Hợp số. 2. Viết n − 1 = 2k q với q lẻ. 3. Đặt a = aq (mod n). 4. Nếu a ≡ 1 (mod n), trả lại Kiểm tra thất bại. 5. Vòng lặp i = 0, 1, 2, ..., k − 1. 6. Nếu a ≡ −1 (mod n), trả lại Kiểm tra thất bại. 7. Đặt a = a2 mod n. 8. Tăng dần i và lặp lại từ Bước 5. 9. Trả lại Hợp số. Bảng 1.2: Kiểm tra Miller–Rabin cho hợp số Định nghĩa 1.3.4. Cho n là số lẻ và viết n − 1 = 2k q với q lẻ. Số nguyên a mà thỏa mãn UCLN(a, n) = 1 được gọi là chứng thực Miller-Rabin cho hợp số của n nếu cả hai điều kiện sau đây đều đúng: (a) aq 6≡ 1 (mod n). i (b) a2 q 6≡ −1 (mod n) với mọi i = 0, 1, 2, ..., k − 1. Nó tuân theo Mệnh đề 1.3.3, đó là nếu tồn tại một số a mà chứng thực MillerRabin với n thì n chắc chắn là hợp số. Phương pháp kiểm tra Miller-Rabin cho hợp số được trình bày ở Bảng 1.2. Bây giờ, giả sử rằng Bob muốn kiểm tra số lớn n có thể là số nguyên tố không? Để làm điều này, ông đã làm phương pháp kiểm tra Miller-Rabin sử dụng một loạt những giá trị được lựa chọn ngẫu nhiên của a. Tại sao điều này lại tốt hơn việc dùng phương pháp kiểm tra định lí Fermat nhỏ? Câu trả lời là không có số nào giống như Carmichael cho phương pháp kiểm tra Miller-Rabin và thực tế mỗi hợp số đều có rất nhiều chứng thực Miller-Rabin như được trình bày ở mệnh đề sau đây. 17 Mệnh đề 1.3.5. Cho n là hợp số lẻ. Khi đó ít nhất 75% những số giữa 1 và n − 1 là chứng thực cho n. Chứng minh. Việc chứng minh này không khó, chúng ta sẽ không chứng minh ở đây. Bây giờ hãy xem xét những tìm kiếm của Bob để tìm những số nguyên tố lớn. Ông lấy số nguyên tố n và thực hiện phương pháp kiểm tra Miller-Rabin cho n với 10 giá trị khác nhau của a. Nếu bất kỳ giá trị a nào là phương pháp chứng minh Miller-Rabin với n thì Bob suy ra n là hợp số. Mệnh đề 1.3.5 cho thấy nếu n là hợp số thì mỗi lẫn Bob thử một giá trị cho a, ít nhất ông đã có 75% cơ hội chứng minh được nó. Vì Bob không tìm được chứng minh nào trong 10 lần thử đó, nên hợp lý khi kết luận rằng xác suất n là hợp số có ít nhất (25%)10, xấp xỉ với 10−6. Và nếu không đủ thì Bob có thể sử dụng 100 giá trị khác nhau của a và nếu không giá trị nào chứng minh n là hợp số thì xác suất n là hợp số sẽ ít hơn (25%)100 ≈ 10−60. Ví dụ 1.3.6. Chúng ta minh họa phương pháp kiểm tra Miller-Rabin với a = 2 và n = 561 trong đó, bạn có thể nhớ lại định nghĩa về số Carmichael.Ta phân tích n − 1 = 560 = 24.35 và sau đó tính 235 ≡ 263 (mod 561), 22.35 ≡ 2632 ≡ 166 (mod 561), 24.35 ≡ 1662 ≡ 67 (mod 561), 28.35 ≡ 672 ≡ 1 (mod 561). Số đầu tiên 235 modun 561 không đồng dư với 1 hoặc −1 và những số khác trong dãy này cũng không đồng dư với −1, vì vậy, 2 là chứng thực Miller-Rabin so với thực tế là 561 là hợp số. Ví dụ 1.3.7. Ta thực hiện ví dụ thứ hai, lấy n = 172947529 và phân tích n − 1 = 172947528 = 23 .21618441. 18 Áp dụng phương pháp kiểm tra Miller-Rabin với a = 17 và tìm được: 1721618441 ≡ 1 (mod 172947529). Do đó, 17 không phải là phương pháp chứng thực Miller-Rabin cho n. Tiếp theo, ta thử a = 3 nhưng: 321618441 ≡ −1 (mod 172947529), vì vậy 3 cũng lại không phải là phương pháp Miller-Rabin. Từ đây ta có thể nghi ngờ n là số nguyên tố nhưng nếu ta thử với một giá trị khác, cho a = 23, thấy rằng 2321618441 ≡ 40063806 (mod 172947529), 2321618441 ≡ 2257065 (mod 172947529), 2321618441 ≡ 1 (mod 172947529). Do đó, 23 là witness Miller-rabin và n thực sự là hợp số. 1.4 Thuật toán phép nhân tử hóa Pollard p-1 Chúng ta đã thấy là tương đối dễ để kiểm tra một số lớn liệu có phải là số nguyên tố không. Điều này là tốt vì hệ thống mã hóa RSA cần những số nguyên tố lớn để thực hiện. Ngược lại, tính bảo mật của RSA dựa trên độ khó rõ ràng trong việc tính toán với những số lớn. Nghiên cứu về phép nhân tử hóa đã có từ thời kỳ Hy Lạp cổ đại nhưng nó chỉ dành cho máy tính khi mà mọi người bắt đầu phát triển những thuật toán có khả năng phân tích những số lớn. Nghịch lý RSA là để khiến RSA hoạt động hiệu quả hơn, chúng ta muốn dùng modun N = pq càng nhỏ càng tốt. Mặt khác, nếu nếu đối phương có thể có phân tích N thì thông tin được mã hóa của chúng ta sẽ không còn bảo mật. Do vậy rất quan trọng khi hiểu được khó khăn như thế nào để phân tích những số lớn, và đặc biệt là để hiểu được tiềm năng của những thuật toán khác nhau mà hiện nay được dùng để phân tích thừa số. Trong vài phần tiếp theo chúng ta sẽ thảo luận một cách chi tiết hơn về một số phương pháp được biết đến để phân tích những số nguyên lớn. 19