Luận văn Nghiên cứu xây dựng thuật toán tấn công hệ mật Rsa

khảo, kế thừa của các tác giả khác đều được trích dẫn đầy đủ. Em xin chịu trách nhiệm về nghiên cứu của mình. Người cam đoan Võ Tá Hoàng iii LỜI CẢM ƠN Học viên trân trọng cảm ơn sự quan tâm, tạo điều kiện và động viên của Lãnh đạo Trường Đại học Thái Nguyên, các thầy cô Khoa Đào tạo sau đại học, các khoa đào tạo và các quý phòng ban Học viện trong suốt thời gian qua. Học viên xin bày tỏ sự biết ơn sâu sắc tới TS. Hồ Văn Canhđã nhiệt tình định hướng, bồi dưỡng, hướng dẫn học viên thực hiện các nội dung khoa học trong suốt quá trình nghiên cứu, thực hiện luận văn. Xin chân thành cảm ơn sự động viên, giúp đỡ to lớn từ phía Cơ quan đơn vị, đồng nghiệp và gia đình đã hỗ trợ học viên trong suốt quá trình triển khai các nội dung nghiên cứu. Mặc dù học viên đã rất cố gắng, tuy nhiên, luận văn không tránh khỏi những thiếu sót. Học viên kính mong nhận được sự đóng góp từ phía Cơ sở đào tạo, quý thầy cô, các nhà khoa học để tiếp tục hoàn thiện và tạo cơ sở cho những nghiên cứu tiếp theo. Xin trân trọng cảm ơn! Hà Nội, tháng năm 2020 Học viên Võ Tá Hoàng iv MỤC LỤC LỜI CAM ĐOAN ................................................................................................... i LỜI CẢM ƠN ...................................................................................................... iii MỤC LỤC ............................................................................................................ iv DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ............................................... vii DANH MỤC HÌNH VẼ, BẢNG BIỂU ............................................................. viii MỞ ĐẦU ............................................................................................................... 1 CHƯƠNG 1: TÌM HIỂU VỀ HỆ MẬT RSA ....................................................... 4 1.1 Hệ mật mã hóa RSA ........................................................................................ 4 1.1.1 Mô tả hệ mật RSA .................................................................................... 4 1.1.2 Thực thi hệ mật RSA ................................................................................ 6 1.1.3 Vấn đề an toàn của hệ mật RSA ............................................................... 6 1.2 Tính an toàn của hệ mật mã RSA .................................................................... 7 1.2.1 An toàn vô điều kiện ................................................................................ 7 1.2.2 An toàn được chứng minh ........................................................................ 7 1.2.3 An toàn tính toán ...................................................................................... 7 1.3 Các kiểu thám mã ............................................................................................ 8 1.3.1 Bài toán thám mã chỉ biết bản mã ............................................................ 9 1.3.2 Bài toán thám mã khi các cặp rõ/ mã đã biết ........................................... 9 1.3.3 Bài toán thám mã với bản rõ lựa chọn ..................................................... 9 1.3.4 Bài toán thám mã với bản mã lựa chọn .................................................... 9 1.4 Tấn công hệ mật RSA lợi dụng những lỗ hổng của chúng ............................. 9 1.4.1 Biết (n) tìm được p, q ........................................................................... 10 1.4.2 Biết số mũ bí mật của RSA .................................................................... 10 1.4.3 Giao thức công chứng ............................................................................ 12 1.4.4 Giao thức module n chung ..................................................................... 14 1.4.5 Giao thức số mũ công khai nhỏ .............................................................. 20 1.4.6 Giao thức số mũ bí mật nhỏ ................................................................... 21 v 1.4.7 Trường hợp các tham số p-1 và q-1 có các ước nguyên tố nhỏ ............. 24 Kết luận Chương 1 .............................................................................................. 26 CHƯƠNG 2: NGHIÊN CỨU MỘT SỐ THUẬT TOÁN TẤN CÔNG HỆ MẬT RSA ..................................................................................................................... 27 2.1 Kiểm tra tính nguyên tố của một số .............................................................. 27 2.1.1 Đặt bài toán ............................................................................................ 27 2.1.2 Các thuật toán kiểm tra tính nguyên tố theo xác suất ............................ 28 2.1.2.1 Thuật toán Fermat ............................................................................... 29 2.1.2.2 Thuật toán Solovay-Strassen ............................................................... 29 2.1.2.3 Thuật toán Miller-Rabin ...................................................................... 30 2.1.2.4 So sánh thuật toán Fermat, Solovay-Strassen và Miller - Rabin ........ 31 2.1.2.5 Kiểm tra tính nguyên tố của số nguyên tố Mersenne .......................... 32 2.1.2.6 Một số thuật toán kiểm tra tính nguyên tố khác .................................. 32 2.2 Các thuật toán phân tích thừa số ................................................................... 34 2.2.1 Thuật toán tìm nhân tử lớn nhất thứ nhất ............................................... 34 2.2.2 Thuật toán phân tích thứ hai ................................................................... 37 2.2.3 Thuật toán phân tích thứ ba .................................................................... 38 Kết luận Chương 2 .............................................................................................. 42 CHƯƠNG 3: ĐỀ XUẤT THUẬT TOÁN TẤN CÔNG RSA KHÔNG CẦN PHÂN TÍCH NHÂN TỬ ..................................................................................... 43 3.1 Mở đầu ........................................................................................................... 43 3.2 Cơ sở toán học của thuật toán ....................................................................... 44 3.2.1 Một số mệnh đề ...................................................................................... 44 3.2.2 Xác định hàm ф(n) ................................................................................. 45 3.3 Đề xuất thuật toán ......................................................................................... 46 3.3.1 Lưu đồ giải thuật .................................................................................... 46 3.3.2 Xây dựng chương trình .......................................................................... 47 3.3.3 Một số ví dụ ............................................................................................ 51 Kết luận Chương 3 .............................................................................................. 53 vi KẾT LUẬN ......................................................................................................... 54 DANH MỤC TÀI LIỆU THAM KHẢO ............................................................ 55 PHỤ LỤC ............................................................................................................ 57 Phụ lục Mã nguồn Chương trình ......................................................................... 57 Phụ lục Thư viện tính toán số lớn ....................................................................... 71 1 Biểu diễn số lớn ................................................................................................ 72 2 Các phép toán với số lớn .................................................................................. 73 vii DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT Ký hiệu, Ý nghĩa viết tắt RSA Rivest - Shamir - Adlemal Hệ mật mã RSA RCT Chinese Remainder Theorem Định lý đồng dư Trung Hoa GCD Greatest Common Divisor Ước chung lớn nhất GF(P) Trường số thực GF(2) Trường nhị phân K Tập hợp khóa mã E Thuật toán mã hóa D Thuật toán giải mã P Tập hợp các bản rõ C Tập hợp các bản mã n Hàm Phi_Ơle p,q Cặp số nguyên tố p và q n Số nguyên dương bất kỳ x Văn bản rõ thuộc y Bản mã thuộc ' k Thành phần khóa công khai '' k Thành phần khóa bí mật s Số nguyên tố Mersenne r Số nguyên lẻ viii DANH MỤC HÌNH VẼ, BẢNG BIỂU Hình 3.1: Lưu đồ thuật toán ................................................................................ 47 Hình 3.2: Giao diện chính của chương trình ...................................................... 48 Hình 3.3: Kiểm tra tính chẵn của số cần phân tích ............................................ 49 Hình 3.4: Kiểm tra tính nguyên tố của số cần phân tích .................................... 49 Hình 3.5: Chức năng phân tích ........................................................................... 50 Hình 3.6: Chức năng dừng trong quá trình phân tích ........................................ 50 Hình 3.7: Chức năng hiển thị kết quả ................................................................. 51 1 MỞ ĐẦU 1. Đặt vấn đề Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len Adleman, công bố lần đầu vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ, được sử dụng trong lĩnh vựcbảo mật và cung cấp cơ chế xác thực của dữ liệu số [3],[17]. Ngày nay, RSA đã được phát triển và ứng dụng rộng rãi trong tất cả các lĩnh vực đời sống, kinh tế xã hội, an ninh quốc phòng, đặc biệt là trong thương mại điện tử. Theo [4],[6] RSA được sử dụng nhiều nhất để trao đổi khóa bí mật và xác thực đối với hệ mật mã đối xứng; sử dụng trên web servers và trên các browsers nhằm đảm bảo an ninh đường truyền, đặc biệt RSA được coi là hạt nhân của hệ thống thanh toán điện tử... Bởi vậy, nghiên cứu phân tích hệ mật RSA luôn thu hút sự quan tâm của nhiều quốc gia, tổ chức, các tập đoàn, công ty và các nhà khoa học đầu tư nghiên cứu [7],[9]. Ở nước ta hiện nay, hầu hết các cơ quan, tổ chức hoạt động trong lĩnh vực bảo mật và các trung tâm nghiên cứu, trường đại học khối kỹ thuật đều có những kết quả nghiên cứu, phân tích hệ số an toàn đối với các tham số hệ mật, từ đó chỉ rõ những mối nguy hiểm tiềm ẩn cần cải thiện hệ mật RSA khi sử dụng [5],[10]. Vấn đề thám mã đối với hệ mật RSA hiện nay đang được các nhà nghiên cứu tập trung khai thác dựa trên các sơ hở của RSA như: tấn công vào số mũ công khai hoặc số mũ bí mật thấp, tấn công vào các tham số nguyên tố p,q bé hoặc cách xa nhau lớn, hoặc họ tập trung vào việc phân tích nhân tử số n (modul của RSA). Trường hợp đối với số lớn, từ n 1024 trở lên thì các phương pháp hiện tại không phát huy được hiệu quả hoặc chạy chậm và không cho quả như mong muốn [3]. Mặt khác về mặt toán học đã chứng minh hiệu quả của việc tấn công hệ mật RSA phụ thuộc vào cách thu hẹp khoảng cách dò tìm số nguyên tố p đối với hệ mật RSA. Do vậy cần có những nghiên cứu tấn công RSA mới mà không cần phân tích nhân tử [4]. 2 Xuất phát từ thực tế đó, luận văn “Nghiên cứu xây dựng thuật toán tấn công hệ mật RSA” mang tính cấp thiết, thực sự có ý nghĩa khoa học và thực tiễn. 2. Đối tượng và phạm vi nghiên cứu - Nghiên cứu về các phương pháp tấn công hệ mật RSA hiện nay và đề xuất một phương pháp tấn công RSA mới. - Sử dụng ngôn ngữ lập trình C để xây dựng chương trình phần mềm được đề xuất. 3. Hướng nghiên cứu của luận văn Nghiên cứu tổng quan về vấn đề an toàn hệ mật RSA, các phương pháp tấn công RSA phổ biến hiện nay. Từ đó đi sâu nghiên cứu đề xuất một phương pháp tấn công RSA mới, không dựa trên bài toán phân tích nhân tử. Nghiên cứu xây dựng phần mềm giải pháp và thực nghiệm, đánh giá. 4. Những nội dung nghiên cứu chính Chương 1: Tổng quan về hệ mật RSA Nghiên cứu mô tả, thực thi hệ mật RSA, vấn đề an toàn và các kiểu, phương pháp tấn công hệ mật RSA phổ biến. Chương 2: Nghiên cứu một số thuật toán tấn công RSA Tập trung nghiên cứu, phân tích một số thuật toán tấn công RSA phổ biến sử dụng chung phương pháp phân tích nhân tử. Nội dung chính của chương trình bày kết quả nghiên cứu các thuật toán kiểm tra số nguyên tố và thuật toán phân tích số nguyên thành tích các thừa số nguyên tố. Chương 3: Nghiên cứu đề xuất thuật toán tấn công RSA Dựa trên cơ sở lý thuyết toán học, nội dung Chương 3 nghiên cứu, tìm hiểu và xây dựng chương trình thuật toán tấn công hệ mật RSA không cần phân tích nhân tử. Việc tính toán, phân tích số nguyên n để xác định các số nguyên tố p,q được thực hiện thông qua tính toán hàm n. Đồng thời đã phân tích, tính toán thực nghiệm để đưa ra một số kết luận. 3 5. Phương pháp nghiên cứu - Nghiên cứu các bài báo khoa học, công trình nghiên cứu trong nước và quốc tế. - Nghiên cứu, phân tích các phương pháp tấn công RSA hiện nay. Từ đó xây dựng thuật toán tấn công RSA mới. - Xây dựng phần mềm ứng dụng và đánh giá. 6. Ý nghĩa khoa học của luận văn Nghiên cứu vấn đề tấn công hệ mật RSA có ý nghĩa và vai trò to lớn trong việc vệ an ninh thông tin. Đây là vấn đề đang được quan tâm, thu hút nhiều quốc gia, tổ chức, cá nhân đầu tư nghiên cứu. Học viên đã nghiên cứu tìm hiểu và xây dựng phần mềm giải pháp tấn công RSA, không cần phân tích nhân tử. Do vậy, luận văn có tính khoa học và ứng dụng thực tiễn. 4 CHƯƠNG 1: TỔNG QUAN VỀ HỆ MẬT RSA 1.1 Hệ mật mã hóa RSA Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir và Len Adleman và được Scientific American công bố lần đầu tiên vào năm 1977 [17]. Hệ mật RSA được sử dụng để bảo mật và đảm bảo tính xác thực của dữ liệu số. Hiện nay RSA được sử dụng trong hệ thống thương mại điện tử, các dịch vụ Web Server và Web Browser. RSA còn được sử dụng để đảm bảo tính xác thực vào bảo mật của Email, đảm bảo an toàn cho các phiên truy cập từ xa và là bộ phận quan trọng của hệ thống thanh toán thẻ tín dụng. Như vậy ta có thể thấy rằng RSA thường được sử dụng trong các ứng dụng cần đảm bảo sự an toàn và bảo mật dữ liệu số cao. 1.1.1 Mô tả hệ mật RSA Định nghĩa hệ mật RSA Hệ mật RSA bao gồm bộ P,C, K, D, E. Trong đó [1]: 1. P là tập các bản rõ. 2. C là tập các bản ký tự mã. 3. K là tập các khóa k , mỗi khóa gồm hai phần: k ' là khóa công khai dành cho việc lập mã, còn k '' là khóa bí mật dành cho việc giải mã. 4. Với mỗi bản rõ xP, thuật toán lập mã E cho ta ký tự mã tương ứng y  Ek ' , xC 5. Với mỗi ký tự mã y thuật toán giải mã D cho ta lại ký tự bản rõ x : Dk '' , y Dk '' , Ek ' , x x Hệ mật RSA sử dụng các tính toán trong Z n trong đó n là tích của hai số nguyên tố lớn phân biệt nhau p,q vàn  p 1q 1. Mô tả hình thức của hệ mật như sau: Cho n  p.q trong đó là các số nguyên tố lớn phân biệt nhau sao cho độ dài của hai số này là gần nhau nhất có thể được. 5 Đặt: P  C  Zn và định nghĩa k  n, p,q,a,b: ab 1modn b - Mã hóa: ek x  x mod n - Giải mã: a dk y y mod n Trong đó xP, yC Các giá trị n,b công khai còn các giá trị p,q,ađược giữ bí mật. Ta sẽ kiểm xem các phép mã hóa và giải mã có phải là các phép toán nghịch đảo của nhau hay không? Vì ab 1modnnên ta có ab  t.n1với một số nguyên bất kỳ t 1. Giả sử có x  Z n khi đó ta sẽ xét hai trường hợp. a.Trường hợp x,n 1 xn mod n 1. Khi đó ta có: t y a mod n  xba mod n  xt. n1 mod n  x n mod n x mod n  1t.xmod n  xmod n b. Trường hợp (x,n)  d 1 d  p hoặc d  q Giả sử d  p , khi đó x  hp với 0  h  q và h,n 1 a Suy ra: y a mod n  xb  mod n  hab mod np ab mod nmod n . Do h,n 1nên hab modn  h. Bên cạnh đó ta lại có: pab mod n  pab modpq  pab mod q  p.pn mod q  p.p p.q   q p.p  p  mod q  p . Vậy ya mod n  hpmod n  hp  x Ví dụ: Giả sử Bob chọn p 101 vàq 113. Khi đó n  pq 11413 và n  p 1q 1 100.112 11200 . Vì 11200 26.52.7nên có thể dùng một số nguyên b khóa công khai có giá trị không chia hết cho 2,5,7. Anh ta kiểm tra điều kiện gcdn,b 1 bằng thuật toán Euclidean. Giả sử Bob chọn b  3533, khi đó theo thuật toán Euclidean mở rộng ta có: 6 b1  6597mod11200 Do vậy số mũ mật (khóa bí mật) để giải mã của Bob sẽ là a  6597. Bob sẽ công bố n 11413 và b  3533. Giả sử Alice muốn gửi bản rõ 9726 đến Bob. Cô ta sẽ tính: 97263533 mod11413 5761 Rồi gửi bản mã 5761 trên kênh truyền. Khi Bob nhận được bản mã 5761 , anh ta sẽ sử dụng khóa bí mật để tính:57616597 mod11413 9726 1.1.2 Thực thi hệ mật RSA Để thiết lập hệ thống, Bob sẽ tuân theo các bước sau: 1. Bob tạo ra hai số nguyên lớn p và q sao cho độ dài của hai số gần bằng nhau nhất có thể được. 2. Bob tính n  p.q và np 1q 1 3. Bob chọn một số ngẫu nhiên b 0  b  n sao cho: gcdb,n 1 4. Bob tính a  b1 modn bằng cách sử dụng thuật toán Euclidean. 5. Bob công bốHình n và 1.b 1trong: Th ựmcộ thit danh hệ m bậạ tvà RSA dùng chúng làn 1.1.3khóa Vấn công đề khai.an toàn của hệ mật RSA Hệ mật RSA chỉ được an toàn khi giữ bí mật khóa giải mã a và thừa số nguyên tố p,q (hay giữ bí mậtn). Trường hợp biết được p,q thì Marvin dễ dàng tính đượcn  p 1q 1 . Khi đó Marvin sẽ sử dụng thuật toán Euclidean mở rộng để tính a . Khi biết a thì toàn bộ hệ thống sẽ bị phá vỡ ngay lập tức. Vì khi biết , toàn bộ khóa K đều được biết và Marvin sẽ giải mã được và sẽ đọc được nội dung của bản rõ, Ngoài ra Marvin có thể lập mã trên văn bản khác là cực kỳ 7 nguy hiểm. Nhất là những thông tin liên quan đến an ninh quốc gia, quân đội, ngân hàng. 1.2 Tính an toàn của hệ mật mã RSA Tính an toàn của một hệ thống mật mã phụ thuộc vào độ khó của bài toán thám mã khi sử dụng hệ mật đó. Người ta đã đề xuất một số cách hiểu cho khai niệm an toàn của hệ thống mật mã, để trên cơ sở các ccách hiểu đó nghiên cứu tính an toàn của nhiều hệ mật khác nhau, sau đây là một vài cách hiểu thông dụng nhất: 1.2.1 An toàn vô điều kiện Giả thiết người thám mã có được thông tin về bản mã. Theo quan niệm lý thuyết thông tin, nếu những hiểu biết về bản mã không thu hẹp được độ bất định về bản rõ đối với người thám mã, thì hệ mật mã là an toàn vô điều kiện, hay theo thuật ngữ của C.Shannon, hệ mật là bí mật hoàn toàn. Như vậy, hệ là an toàn vô điều kiện, nếu độ bất định về bản rõ sau khi người thám mã có được cả thông tin (về bản mã) bằng độ bất định về bản rõ trước đó. Tính an toàn vô điều kiện thường được sử dụng cho các hệ mật mã khó đối xứng. 1.2.2 An toàn được chứng minh Một hệ thống mật mã được xem là có độ an toàn được chứng minh nếu ta có thể chứng minh được bài toán thám mã đối với hệ thống đó “khó tương đương” với một bài toán khó đã biết, thí dụ bài toán phân tích một số nguyên thành tích các thừa số nguyên tố, bài toán tìm lôgarit theo một modul nguyên tố,(“khó tương đương” có nghĩa là nếu bài toán này giải được thì bài toán kia cũng giải được cùng một độ phức tạp như nhau). 1.2.3 An toàn tính toán Hệ mật mã được xem là an toàn về mặt tính toán, nếu mọi phương pháp thám mã đã biết đều đòi hỏi một nguồn năng lực tính toán vượt quá mọi khả năng (kể cả phương tiện thiết bị máy móc) tính toán của một kẻ thám mã. An 8 toàn theo nghĩa này, nói theo ngôn ngữ của lý thuyết về độ phức tạp tính toán là bao hàm cả khái niệm an toàn theo nghĩa “được chứng minh” nói trên. Tính an toàn theo nghĩa được chứng minh hay tính toán được sử dụng nhiều trong công việc nghiên cứu các hệ thống mật mã hiện đại, đặc biệt là các hệ thống mật mã khóa công khai. Các bài toán đó đều có hạt nhân là tính an toàn của các hệ mật mã, góp phần giải quyết các vấn đề an toàn thông tin kể trên. 1.3 Các kiểu thám mã Mật mã được sử dụng trước hết là để đảm bảo tính bí mật cho các thông tin được trao đổi trên các kênh truyền thông công cộng. Do đó bài toán quan trọng nhất của thám mã cũng chính là bài toán phá bỏ tính bí mật đó, tức là: với những bản mã có thể dễ dàng thu được trên các kênh truyền thông công cộng, người thám mã phải tìm ra được nội dung thông tin che dấu bên trong bản mã [8],[17],[18]. Giả thiết chung: Ta luôn coi đối phương biết hệ mã đang dùng. Giả thiết này được gọi là nguyên lý KoreKhoff. Dĩ nhiên nếu đối phương không biết hệ mật được dùng thì nhiệm vụ của anh ta sẽ khó khăn hơn nhiều. Tuy nhiên, ta không muốn độ mật của một hệ thống dựa trên một giả thiết không chắc chắn: đối phương không biết hệ mật đang sử dụng. Vì vậy, mục tiêu trong việc thiết kế một hệ mật là phải đạt được độ mật của giả thiết KoreKhoff. Việc thám mã có thể quy về việc tìm được bản rõ hoặc phát hiện khóa giải mã, khi biết trước hệ mật mã sử dụng. Ngoài việc biết hệ mật mã, người thám mã cần có thông tin về bản rõ và một số phát hiện khác. Tuỳ theo thông tin đó là gì mà ta phân các bài toán thám mã thành 4 loại [2]: - Bài toán thám mã chỉ biết bản mã: Đây là bài toán phổ biến nhất - Bài toán thám mã khi biết cặp rõ/mã. - Bài toán thám mã khi có bản rõ được chọn. - Bài toán thám mã khi có bản mã được chọn. 9 1.3.1 Bài toán thám mã chỉ biết bản mã Đây là bài toán phổ biến nhất. Người thám mã chỉ biết các bản mã c1  ek m1 ,.., ek mi  mà không biết bản rõ tương ứng với những bản mã đó cũng như khóa giải mã. Anh ta cố gắng tìm khóa giải mã, nếu không cần tìm các bản rõ m1m2 ..mi . 1.3.2 Bài toán thám mã khi các cặp rõ/mã đã biết Người thám mã biết các bản mã c1c2 ..ci Như trên, nhưng cũng biết các bản rõ tương ứng m1m2 ..mi . Anh ta cố gắng tìm khóa giải mã a , nếu không thì cố gắng phỏng đoán bản rõ mi1 từ bản mã mới ci1  ek mi1 đã được mã hóa cùng với khóa b . 1.3.3 Bài toán thám mã với bản rõ lựa chọn Người thám mã được quyền truy nhập tạm thời cơ chế mã hóa, nên có thể chọn các bản rõ m1m2 ..mi và có được các bản mã tương ứng c1  ekm1 , c2  ek m2 ,.., ci  ek mi , từ đó anh ta sẽ phỏng đoán khóa giải mã a và có thể tìm được bản rõ mi1 từ một vài bản mã mới ci1  ek mi1  cũng được mã hóa bởi khóa lập mã b . 1.3.4 Bài toán thám mã với bản mã lựa chọn Người thám mã được quyền truy cập tạm thời vào cơ chế giải mã, nên từ các bản mã anh ta nhận được các bản rõ tương ứng . Từ đó anh ta phỏng đoán khóa giải mã và có thể tìm được bản rõ mi1 từ một vài bản mã mới ci1  ek mi1  cũng được mã hóa bởi cùng khóa lập mã . Trong mỗi trường hợp đối tượng cần phải xác định chính là khóa đã sử dụng: Rõ ràng bốn mức tấn công (thám mã) trên đã được liệt kê theo độ tăng dần của sức mạnh tấn công và cách tấn công các bản mã được lựa chọn là thích hợp đối với hệ mật mã hóa công khai. 1.4 Tấn công hệ mật RSA lợi dụng những lỗ hổng của chúng 10 Tính bảo mật của RSA chủ yếu dựa vào việc giữ bí mật số mũ giải mã a và các thừa số p,q của n . Tuy nhiên, điều kiện an toàn trên của hệ mật chỉ là điều kiện chung. Trong thực tế khi thiết kế một giao thức hay một kênh bí mật có sử dụng hệ mật RSA vẫn tồn tại nhiều sơ hở, những sơ hở đó đã được thám mã lợi dụng nhằm phá huỷ giao thức, kênh bí mật, phá vỡ tính an toàn của hệ mật. Trong phần này, sẽ giới thiệu một số sơ hở người thám mã có thể lợi dụng vào đó để phá vỡ hệ mật RSA [5, 8, 13]. 1.4.1 Biết (n) tìm được p, q Người ta có thể xác định được p,q và ngược lại. Biết được người ta có thể dễ dàng tính đượcn. Nếu biết được n ta có thể tìm được bằng cách giải hệ phương trình: p.q  n p.q  n    ( p 1)(q 1)  (n) p  q  n 1(n) Do đó là nghiệm của phương trình bậc 2: 2 x n n1x  n  0 Bởi vậy nếu người thám mã biết được nanh ta có thể phân tích được n và phá được hệ mật. Ngược lại cho trước rõ ràng việc tính nđược thực hiện dễ dàng: n  p 1q 1 1.4.2 Biết số mũ bí mật của RSA Nếu như biết số mũ giải mã a thì coi như đã làm xong việc thám mã, vì vậy việc tìm kiếm là không còn ý nghĩa đối với Marvin (người thám mã) nữa. Tuy nhiên điều này còn có một ý nghĩa quan trọng hơn đó là nếu đối phương biết a thì ta không chỉ phải thay đổi số mũ giải mã mà còn phải chọn modul n khác. Vì khi Marvin biết được d, anh ta cũng có thể tính được . Do đó Marvin sẽ biết cách tìm một khóa bí mật bất kỳ, néu hệ thống vẫn giữ nguyên modul n  p.q . 11 Bây giờ chúng ta sẽ chứng minh rằng: nếu biết số mũ giải a sẽ tìm được các thừa số p,q của n . Thật vậy: Do a.b 1modn nên a.b 1  e.n  k Do n là một số chẵn nên ta có thể viết k dưới dạng. k  2t.r với r là số lẻ vàt 1. Theo định lý ơle: với a : a,n 1a thì an 1. Do đó ta có: k  2 g  Z n  1mod n (do k là bội của và do đó g là căn bậc hai của 1 theo module n . Theo định lý phần dư Trung Hoa, 1 có 4 căn bậc hai module n  p.q . Hai căn bậc 2 là  1, hai căn bậc hai là  xx 1mod p; x  1mod q,1 x  p. Sử dụng một trong hai căn bậc hai không tầm thường này sẽ tìm được trong thời gian đa thức bằng cách tính gcdx 1,n x2 1mod n  x 1x 1 1mod n  x 1x 1: n (1) Đặt x 1,n  d1 và x 1,n  d2 Vì và x  1,0  x  n nên: x 1  0 và 0  x 1 n x 1  0 và 0  x 1 n Suy ra d1 hoặc d 2 phải khác 1 và do nên một trong hai giá trị d1,d2 chính là p hoặc q . Ví dụ: Giả sử n  40313.31. Bốn căn bậc hai của 1 theo modul 403 là: 1,92,311,402. Căn bậc hai 92 nhận được bằng cách giải hệ x 1mod13, x  1mod31theo định lý phần dư China. Nếu tìm được nghiệm không tầm thường này, thì nghiệm không tầm thường kia phải là 403-92=311. Đó là nghiệm của hệ x  1mod13 và x  1mod31. 12 Giả sử x là căn bậc hai không tầm thường của 1 module n . Khi đó ta có: n x 1x 1 Nhưng n không là ước của một nhân tử nào ở vế phải. Điều đó kéo theo gcdx 1,n  p hoặc q (và tương tự gcdx 1, p hoặc q ). Tất nhiên có thể tính ước chung lớn nhất bằng thuật toán Euclidean mà không cần phải phân tích nhâ tử n. Bởi vậy hiểu biết về căn bậc hai không tầm thường 1 module n sẽ làm cho việc phân tích n chỉ cần thực hiện trong thời gian đa thức. Yếu tố quan trọng này là cơ sở của nhiều kết quả trong mật mã. Trong ví dụ trên, gcd93,403  31 và gcd312,403  13 Sau đây là thuật toán phân tích thừa số khi đã biết số mũ giải mã a . 1. Cho w ngẫu nhiên sao cho 1 w  n 1 2. Tính x  gcdw,n 3. If 1 x  n then quit (thanh công: x  p hoặc x  q ) 4. Tính a  Ab 5. Viết ab 1  2s r , với r là số lẻ 6. Tính v  wr modn 7. If v 1modn then quit (không thành công) 8. While v 1modn do 9. v0  v 10. v  v2 modn 11. If v0  1mod n then quit (không thành công) Else Tính x  gcdv0 1,n (thành công: x  p hoặc x  q ) 1 Thuật toán có xác suất thành công tối thiểu là 2 . 1.4.3 Giao thức công chứng 13 Giao thức công chứng là giao thức được thiết kế cho một văn bản sau khi A ký lên đó, người khác có thể xác thực được rằng văn bản này thực sự được ký bởi A (nó cùng giống như như việc công chứng của công chứng viên ký chữ ký của mình lên bản công chứng). Để thiết lập giao thức công chứng, Bob phải chọn các tham số RSA: các số nguyên tố p,q và các số mũ hóa e và khóa giải mã d thỏa mãn e.d 1modn trong đó n  p.q . Các giá trị n,e là công khai, còn p,q,d được Bob giữ bí mất. Để ký một văn bản M, Bob sử dụng số mũ bí mật d để tính chữ ký S  M d modn. Bất cứ ai cũng có thể sử dụng những thông tin công khai của Bob để kiểm tra xem S có thật sựu là chữ ký của Bob trên M hay không bằng cách tính Semodn và so sánh với M . Vì chỉ có Bob biết giá trị , giá trị dùng để tạo ra S . Giao thức công chứng khẳng định rằng chỉ có một mình Bob mới có thể tạo ra S . Tuy nhiên Davida và Denning [6] đã chỉ ra rằng: Có thể tạo ra chữ ký giả mạo của giao thức này. Sau đây là một phương pháp để thực hiện điều đó. Bob có khóa bí mật d và khóa công khai e. Giả sử marvin muốn có được * chữ ký của Bob trên văn bản M  Z n . Khi đó Marvin có thể thực hiện theo cách sau đây: * ' e Lấy một số ngẫu nhiên r  Z n , tính M  r M modn , và đề nghị Bob ký trên M ' . Nếu Bob ký S ' trên M ' thì Marvin có thể dễ dàng tính được chữ ký S của Bob trên M : S  S '.r 1 modn d d Vì S '  M ' mod n  r e M  mod  r edM mod n  r.S mod n  S  r 1S ' mod n S tìm được chính là chữ ký của Bob trên M . ' ed e ' e M  M ' Thật vậy: S  S  mod n  e mod n  e mod n  M mod n r r 14 Kỹ thuật trên được gọi là kỹ thuật che khuất (blinding), kỹ thuật này cho phép Marvin lấy được một chữ ký hợp pháp trên một văn bản anh ta muốn, bằng cách yêu cầu Bob ký trên một văn bản "được che khuất" (blinding) ngẫu nhiên. Bob không có thông tin về văn bản anh ta đang thực sự ký. Kết quả của kỹ thuật này dựa trên một thực tế: RSA sử dụng một hàm toán học (hàm mũ) bảo toàn phép nhân các giá trị đầu vào. Điểm mấu chốt của cách tấn công này là nếu chọn X,M,d và n bất kỳ: d d d XM   X M mod n tức sigk X.M   sigk X .sigk M  Vậy để ngăn cản việc tấn công vào giao thức công chứng bằng kỹ thuật che khuất ta phải huỷ bỏ khả năng sử dụng tính bảo toàn của phép nhân của kẻ định giả mạo chữ ký. Một trong nhiều cách đó là sử dụng hàm “hash một chiều” trên văn bản M trước khi ký và kỹ thuật này được áp dụng trong nhiều ứng dụng thực tế của RSA (ví dụ như thanh toán điện tử ẩn danh). 1.4.4 Giao thức module n chung Tình huống dẫn đến việc sử dụng RSA có số module chung xảy ra như sau: khi trong hệ thống có k người đăng ký sử dụng RSA. Để quản lý, phân phối khóa được đơn giản, trung tâm sẽ tạo ta hai số nguyên tố p,q và tính số modul n  p.q ; sinh ra các cặp khóa mã hóa và giải mã ei ,di , sau đó cấp cho người đ... toán đặt ra: Cho n là số nguyên dương lẻ, d  23 n 1. Nội dung bài toán này là tìm nhân tử lẻ nhỏ nhất f của sao cho d  f  n hoặc khẳng định rằng không tồn tại nhân tử như vậy. Nội dung các bước tiến hành như sau: Thuật toán được thực hiện như sau: Input: Số nguyên dương 38 Output: - Tìm ra nhân tử f - Trả lời “không tìm ra nhân tử nào như vậy” Algorithm: 1. Step 1: Set r  nmodd ; d  23 n1 r'  nmodd  2;  n   n  q  4     ; d  2 d  s   n; 2. Step 2: If d  s thuật toán kết thúc và ta không tìm được nhân tử hay thừa số nào thỏa mãn điều kiện: d  f  n 3. Step 3: Set d  d  2, x  r R  2r  r' ; r'  x Q  q 1, goto step 5 5. Step 4: If r  d , set r  r d Q  q 1, goto step 5(quay lại bước này một lần nữa) 6. Step 5: If r  0 then d là một thừa số của n Và thuật toán kết thúc, ta sẽ thu được f  d Else goto step 2 Như vậy ta thấy rằng thuật toán sẽ quét tất cả các giá trị lẻ nằm trong khoảng 23 n 1, n 2.2.3 Thuật toán phân tích thứ ba Bài toán đặt ra: (giống như thuật toán thứ nhất) cho trước một số lẻ, hãy xác định nhân tử lớn nhất của n mà không vượt qua n Thủ tục này giải bài toán này được tiến hành như sau: 39 Lấy r số nguyên m1,m2 ,.., mr : gcdmi ,m j   1;i, j 1,r Ta lập ma trận (bảng) Sieve si, j với 1 i  r ; 0  j  mi 1 như sau: 2 1 nếu j  n  y(mod mi ) có nghiệm y si, j   0 nếu trái lại Sau khi có bảng si, j ta tiến hành xây dựng thuật giải như sau: Input: Một số nguyên lẻ n  2 Output: các thừa số nguyên tố của n Algorithm: Step1: Đặt x   n và ki   xmod mi , với 1 i  r Step 2: If si,ki 1 For i 1 to r goto Step4 Step 3: đặt x  x 1; ki  ki 1mod mi For i=1 to r goto Step 2 Step 4: đặt y   x 2  n hoặc  x 2  n 4.1. If y2  x2 b thenx  y là một nhân tử cần tìm của và thuật toán kết thúc. 4.2. Else goto Step 3 Trong đó: - x là số nguyên bé nhất mà lớn hơn hoặc bằng x . - x là số nguyên lớn nhất mà nhỏ hơn hoặc bằng x . Thuật toán Pollard p 1 Nguyên tố của nó đều  B . ý chính của thuật toán này là: Giả sử là B-mịn. Ta ký hiệu Q là bội chung nhỏ nhất của tất cả các luỹ thừa của số nguyên tố  B mà bản thân chúng  n . 40 l ln n Nếu q  n thì l ln q  ln n, tức l    với x là số nguyên bé nhất lớn ln q hơn x .  ln    Khi đó ta có:Q   q  lq  qB Trong đó tích lấy theo tất cả các số nguyên tố khác nhau q  B. Nếu p là một thừa số nguyên tố của n sao cho p 1 là B-mịn, thì p 1Q và do đó với mọi a bất kỳ thỏa mãn gcda, p 1, theo định lý Fermat ta có: aQ 1mod p . Vì vậy, nếu lấy d  gcdaQ 1,n thì p d . Nếu d  n , coi như thuật toán không cho ta kết quả mong muốn. Tuy nhiên điều đó chắc không xảy ra nếu có ít nhất hai thừa số nguyên tố khác nhau. Bây giờ chúng ta sẽ xét thuật toán để khẳng định thêm những lập luận ở trên. _Thuật toán Pollard phân tích thành thừa số: Input: Một hợp số không phải là luỹ thừa của một số nguyên tố Output: Một thừa số nguyên tố không tầm thường của Algorithm: 1. Chọn một lần cho độ mịn B 2. Chọn ngẫu nhiên một số nguyên a:2  a  n1 Tính d  gcda,n If d  2then d là kết quả cần tìm. 3. Với mỗi số nguyên tố q  B thực hiện: ln n 3.1. Tính l    ln q l 3.2. Tính a  aq mod n 4. Tính d  gcda 1,n 5. If 1 d  n then cho kết quả 41 6. Else không tìm thấy kết quả nào thỏa mãn. Xét ví dụ sau để hiểu rõ hơn về thuật toán này. Dùng thuật toán cho n 19048567, chọn B 19 và a  3. Ta sẽ tính được gcd3,n 1. Chuyển sang thực hiện bước 3 ta được bảng sau đây(mỗi hàng ứng với giá trị của q ). Q L A 2 24 2293244 3 15 13555889 5 10 16937233 7 8 15214586 11 6 9685355 13 6 13271154 17 5 11406961 19 5 554506 Sau đây là cách tính d  gcd554506 1,19048567   5281 (bước 4) n Vậy ta tìm được một thừa số p  5281, do đó thừa số q   3607 . Cả hai p đều là thừa số nguyên tố. Ta thấy p 1 5281 23.3.5.11, có tất cả các ước nguyên tố đều 19, do đó chắc chắn thuật toán kết thúc sẽ có kết quả. Thuật toán sẽ kết thúc không có kết quả khi độ mịn B được chọn quá bé để không một thừa số nguyên tố p nào của n mà p 1 chỉ chứa các ước số nguyên tố  B . Như vậy, có thể xem p 1_thuật toán Pollard phân tích thành thừa số nguyên tố có hiệu quả đối với những số nguyên là mịn, người ta tính được thời gian cần để thực hiện thuật toán là cỡ vào khoảngOBln n ln B phép nhân theo module. 42 Kết luận Chương 2 Tấn công hệ mật RSA, bản chất là việc phân tích để tìm ra khóa bí mật, hay chính là việc tìm ra cặp số nguyên tố p,q . Nội dung Chương 2 trình bày kết quả tìm hiểu, nghiên cứu các thuật toán kiểm tra tính nguyên tố đối với một số nguyên. Theo đó, đã nghiên cứu tìm hiểu 3 thuật toán phổ dụng nhất là Farmat, Solovay-Strassen và Miller- Rabin, so sánh ưu điểm của 3 thuật toán này để đưa ra một số khuyến cáo trong việc ứng dụng. Đồng thời trình bày kết quả kiểm tra tính nguyên tố đối với số nguyên tố Mersenne, được sử dụng nhiều trong lĩnh vực mật mã hiện nay. Dựa trên các kết quả nghiên cứu về toán học, cùng với một số giả thiết, Chương 2 trình bày tổng quan 3 thuật toán phân tích số nguyên bằng phương 43 pháp phân tích nhân tử được sử dụng phổ biến hiện nay. Các phương pháp phân tích dựa trên phương pháp nhân tử này chỉ khả dụng trong trường hợp n không quá lớn. Do vậy với trường hợp số nguyên lớn cần có một thuật toán phân tích đủ mạnh để giải quyết yêu cầu bài toán đặt ra. CHƯƠNG 3: ĐỀ XUẤT THUẬT TOÁN TẤN CÔNG RSA KHÔNG CẦN PHÂN TÍCH NHÂN TỬ 3.1 Mở đầu Trong chương này, tác giả nghiên cứu và xây dựng phần mềm mô tả thuật toán tấn công hệ mật RSA mà không cần phân tích nhân tử n  p.q của tham số RSA. Như chúng ta đã biết, các thuật toán phân tích nhân tử của tham số RSA đã được trình bày ở chương 2 chỉ có hiệu quả khi tham số n không quá lớn, tức là số n 10100 và với công cụ tính toán hiện đại nhất có thể có hiện tại. Trong khi theo tiêu chuẩn X509 thì tham số phải lớn, cụ thể là n 10150 mới đảm bảo cho hệ mật RSA đủ an toàn. Một ưu điểm của thuật toán sắp được đề xuất là tham số càng lớn càng tốt. 44 3.2 Cơ sở toán học của thuật toán 3.2.1 Một số mệnh đề Cho n là một số nguyên dương, chúng ta cần trả lời câu hỏi “ có phải là tích của 2 số nguyên tố hay không?”Ta có các mệnh đề sau đây: Mệnh đề 1. Giả sử, là một số nguyên dương lẻ, không chính phương (square - free number). Điều kiện cần và đủ để là tích của 2 số nguyên tố là bất đẳng thức kép sau đây được duy trì: 2 n 1  n  n  n 3 . Trong đó n là hàm Phi- Euler (3.1) Chứng minh 1/ Điều kiện đủ: Trước hết ta thấy rằng không phải là số nguyên tố vì nếu là số nguyên tố thì n  n 1. Điều này trái với giả thiết đã cho. Bây giờ, giả sử là tích của 3 số nguyên tố trở lên. Ta ký hiệu p là một số nguyên tố 1 nhỏ nhất và là một nhân tử của . Khi đó, rõ ràng rằng: p  n 3 và do đó, ta có  1 2 n  n1 1   n1 n 3   n  n 3 : trái với giả thiết, vậy điều kiện đủ được  p   chứng minh. 2/ Điều kiện cần:Giả sử n  p.q với p, q là hai số nguyên tố phân biệt, theo tính chất của hàm Phi- Euler ta có: n  p 1q 1  p.q  p  q1 n  p  q1 n 1 1 2 Mặt khác n  p 1q 1  p.q  p  q1  n  2n 2 1  n  n 3 2 Vậy ta có: n 1  n  n  n 3 . Mệnh đề 1 được chứng minh. Mệnh đề 2. Giả sử là tích của 2 số nguyên tố lẻ phân biệt Khi đó: 2 1 n  n 3  n  n  2n 2 1 (3.2) Chứng minh. Đây là hệ quả của chứng minh Mệnh đề 1 Mệnh đề 3. Giả sử n  pq trong đó, p, q là 2 số nguyên tố lẻ phân biệt Khi đó giới hạn 45 lim n 1 n (3.3) n Việc chứng minh Mệnh đề 3 được suy ra từ Mệnh đề 2 Mệnh đề 4. Cho n  pq với p, q là 2 số nguyên tố lẻ phân biệt. Khi đó việc biết được p và q tương đương việc biết được hàm n. Nói chính xác hơn, chúng ta có thể tính được hàm n từ và với Ologn  phép toán bít và có thể tính được và từ hàm vớiOlog3 n phép toán bít. 3.2.2 Xác định hàm ф(n) Để xác định hàmn, ta thiết lập bài toán như sau: Cho trước 2 số nguyên tố lẻ khác nhau p, p . Đặt n = pq.. Ta biết rằng n  p 1q 1. Lúc đó n  n  p  q1  n   p  n 1 (3.4)  p  Hay: pn  n.p  p2  p  n  0 , từ đó có (3.5) p2  n n 1p  n  0 Phương trình bậc 2 ẩn p cho ở (3.5) có dạng p2  Bp  n  0 , trong đó B n n 1 (3.6) Do n là chẵn và n 1 là số tự nhiên chẵn nên ta có thể biến đổi (3.6) như sau: B  2n n 1  2n 1n  2n 1 n   2B ' 2 2  2 2  B'  n'  ' n n'  n 1  ' n  n Với  , 2 và   2 Từ đó, phương trình cho ở (3.5) được viết thành p2  2B' p  n  0 (3.7) Xét biệt số 2 '  B'  n (3.8) 46 p là nghiệm nguyên dương nên căn bậc hai ' phải là giá trị nguyên dương, tức ' phải là số chính phương (perfect square), nghĩa là ' là bình phương đúng của một số nguyên dương. Như vậy, bài toán đặt ra hãy xác định n sao cho ' là số chính phương. Theo mệnh đề 3 ta chỉ cần xác định giá trị : 2   ' n  n 3  2  n  n  n (3.9)    3.3 Nghiên cứu thuật toán 3.3.1 Lưu đồ giải thuật Input: Cho n  p.q , trong đó p, q là hai số nguyên tố lẻ khác nhau n Output: Xác định  ' n hoặc :  ' n  2 Algorithm: n 1 Step 1. Tính n'  ; n 2 Step 2. Đặt b  n'  n ' Step 3. Đặt 1n  b 1, nếu b lẻ ' 1n  b nếu b chẵn ' ' 2 Step 4. Với i 1,2,.. tính i  n n 2i 1  n ' Step 5. Nếu i là số nguyên thì dừng: ' ' ' ' ' ' p  n 1n 2i 1 i ; q  n 1n 2i 1 i là đáp số bài toán Step 6. Trái lại, đặt i  i 1, quay lại Step 4 ' '  n  i n Lưu đồ thuật toán như sau: 47 Hình 3.2: Lưu đồ thuật toán 3.3.2 Xây dựng chương trình Chương trình được viết bằng ngôn ngữ C, sử dụng thư viện số lớn (BigNumber) kiểm tra và phân tích số nguyên n thành số nguyên tố p, q . Đây là phương pháp tấn công hệ mật RSA mà không cần phân tích nhân tử. 3.2.2.1 Giao diện chương trình 48 Chương trình phân tích số nguyên tố được thiết kế giao diện như sau: Hình 3.3: Giao diện chính của chương trình Tại giao diện chính, thao tác nhập số cần phân tích và lựa chọn “phân tích”. Trong quá trình muốn dừng việc phân tích thì clik “dừng”. 3.2.2.2 Một số chức năng chính + Kiểm tra số nhập vào là chẵn hoặc nguyên tố: Sau khi nhập số cần phân tích và thao tác click “Phân tích”. Khi đó, đầu tiên chương trình sẽ tiến hành kiểm tra tính chẵn và tính nguyên tố của số nhập vào. Nếu không thỏa mãn, chương trình sẽ hiển thị thông báo “Số nhập vào là số chẵn, không hợp lệ”và dừng việc phân tích. 49 Hình 3.4: Kiểm tra tính chẵn của số cần phân tích Trường hợp là số nguyên tố, hiển thị “số nhập vào là số nguyên tố, không phân tích được” và dừng việc phân tích. Hình 3.5: Kiểm tra tính nguyên tố của số cần phân tích + Chức năng phân tích:Nếu thỏa mãn tính chẵn và tính nguyên tố, chương trình sẽ tiến hành phân tích theo thuật toán đề xuất. 50 Hình 3.6: Chức năng phân tích + Chức năng dừng trong quá trình phân tích: Khi muốn dừng việc phân tích, tính toán ta sẽ click “Dừng”, chương trình sẽ dừng toàn bộ việc tính toán tại thời điểm yêu cầu. Hình 3.7: Chức năng dừng trong quá trình phân tích 51 + Hiển thị, thông báo kết quả: Hoàn tất quá trình phân tích, chương trình hiển thị thông báo “xong” và kết quả tìm được của p, q cùng toàn bộ các kết quả tính ' . Hình 3.8: Chức năng hiển thị kết quả 3.3.3 Một số ví dụ Ví dụ 1: Cho n 11413, tìm hàm n n'  n 1 n 1  5707 n 106  n Ta có 2 và   . Vậy cận trên của   là 5707106 5601. Vì  ' n là một số chẵn nên ta chọn  ' n  5600 và tính ' ' ' 2 2 2 1  n  n  5707  5600  11413 107 11413  36  6 . ' ' ' Vậy   1 là số chính phương. Do đó  n  5600 là nghiệm cần tìm. Từ đó p 107 6 113 và q 1076 101. Thử lại 101.11311413 n do đó n 100 .112 11200 trùng với kết quả đã tìm được ở trên. Ví dụ 2: Cho n 809009, xác định n n'  n 1  404505 n  899 n'  n  403606 2 ;   do đó   Chọn  ' n  403606 ' ' ' 2 2 Tính 1  n  n  n  404505  403606   809009  808.809 không phải là số chính phương; 52 ' 2 Tính tiếp 2  901 809009  6400  7292 không phải là số chính phương; ' 2 2 Tính tiếp 3  903  809009  6400  80 là số chính phương; Do đó  ' n   ' 809009   n'  903  403602 và n  807204 , số nguyên tố là p,q  823,893  Ví dụ 3: Cho n  92296873, xác định n Ta có  ' n  46148437 ; n'   n 46138830 Chọn  ' n  46138828 ' ' ' 2 2 Tính 1n  n  n  n  9609  92296873  36008 không phải là số chính phương; ' 2 Tính 2  9611 92296873  744448 không phải là số chính phương; ' 2 2 Tiếp tục tính 3  9613 92296873 112896  336 là số chính phương.  ' n92296873  n' 9613  46138824 do đó n 2 ' n 92277648 Từ đó tìm ra được hai số nguyên tố p  9277 và q  9949 Ví dụ 4: Cho n 16111378391, xác định n n 1 Ta có n'   8055689196 và n'  n 8055562266 2 ' Chọn 1 n 8055562264 ' ' ' 2 2 Tính 1n  n 1 n  n 126932 1611137839 1 354233 không phải là số chính phương. ' 2 Tính 2 126934 1611137839 1 852965 không phải số chính phương ' 2 2 Tiếp tục tính 31n 126996 1611137839 1 4075 là số chính phương Do đó,  ' n n' 126996  8055562200 và p 1269964075122921 q 126996 4075131071 Ví dụ 5: Cho n 1152921501922492492471, xác định n Tính n'  n 5764607509 61246209 1073741822  5764607498 87504387 ' ' Chọn 1 n n  n1 53 ' ' ' 2 2 Tính 1n  n 1 n  n 1073741823  n  536870912 không phải số chính phương ' 2 Tính 2 1073741825  n  4831838208 không phải số chính phương ' 2 Tính 134217727  805306368 là số chính phương Do đó  ' n 5764607496 19068930 p 1342177279805306368 536870911 q 1342177279805306368 2147483647 Kết luận Chương 3 54 Dựa trên một số kết quả nghiên cứu chứng minh về mặt toán học, thuật toán phân tích số nguyên n lớn có những ưu điểm nhất định, bởi khi n càng lớn thì n càng tiệm cấn đến n  2 n, nên việc xác định  ' n trở nên thuận lợi. Kết quả thực nghiệm cho thấy việc tính toán trong các vòng lặp đơn giản, mỗi vòng lặp chỉ thực hiện 4 phép tính cộng (+), trừ (-) và bình phương, do vậy việc xây dựng chương trình thuật toán đơn giản. Ví dụ, đối với trường hợp n gồm 19 chữ số thập phân, thuật toán chỉ thực hiện 143217727 vòng lặp, số các phép tính để xác định được giá trị  ' n là 536870908. Chương trình phân tích có giao diện trực quan và các chức năng, thao tác thân thiện người dùng. Một số thực nghiệm thực tế cho kết quả nhanh hơn đối với các thuật toán sử dụng phương pháp nhân tử. Tuy nhiên để có kết luận một cách chính xác hơn, cần có những thực nghiệm so sánh với các thuật toán phân tích hiện có, dựa trên các phân tích, thống kê số liệu khảo sát, tổng hợp làm sở cứ khoa học và thực tiễn chắc chắn, từ đó đưa ra những kết luận, đánh giá chính xác và khuyến cáo phù hợp. Mặt khác, để có thể áp dụng trong thực tế, chúng ta cần xác định cận dưới của hàm một cách tối ưu hơn sao cho khoảng cách giữa cận trên và cận dưới là gần nhau có thể được sao cho xác suất để nằm trong khoảng đó là trên 99% . KẾT LUẬN 55 Luận văn đã tiến hành nghiên cứu tổng quan về hệ mật RSA, phân tích vấn đề an toàn của hệ mật, để làm rõ những điểm yếu, nguy cơ khai thác để tấn công hệ mật hiện nay. Đồng thời đã nghiên cứu những phương pháp, biện pháp phổ biến được sử dụng để tấn công RSA. Trên cơ sở đó, luận văn tìm hiểu nghiên cứu một số thuật toán kiểm tra tính nguyên tố và phân tích số nguyên lớn bằng phương pháp nhân tử, để đưa ra những kết luận, so sánh giữa chúng. Theo đó đã chứng minh được các phương pháp này đều không khả dụng trong trường hợp phân tích các số nguyên lớn. Kế thừa một số kết quả nghiên cứu, chứng minh mới về mặt toán học, luận văn đã đi sâu nghiên cứu thuật toán phân tích số nguyên mới không sử dụng phương pháp nhân tử. Đồng thời đã tiến hành xây dựng Chương trình phân tích một cách trực quan, thân thiện và tổ chức thực nghiệm, đánh giá để rút ra một số kết luận và khuyến cáo trong việc tấn công RSA. Kết quả thực nghiệm ban đầu cho phép khẳng định phương pháp sử dụng có nhiều ưu điểm. Tuy nhiên cần tiếp tục được nghiên cứu, phát triển, tối ưu hóa cận dưới của hàm  ' n. Mặt khác, để đạt hiệu quả phân tích thám mã cao, cần có sự đầu tư nghiên cứu xây dựng hệ thống tính toán lớn, hiệu năng cao sử dụng các công nghệ mới nhất để tăng tốc độ xử lý và tính toán. DANH MỤC TÀI LIỆU THAM KHẢO 56 Tiếng Việt [1] Hồ Văn Canh, Nguyễn Viết Thế, “Phân tích thông tin có bảo mật” NXB Hà Nội T&T, 2010. [2] Lê Công Tuấn Anh, Trịnh Nhật Tiến, “Các phương pháp tấn công chữ ký số: rsa, elgamal, dss”, Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2016. [3] Mai Thị Thúy Hà, Hồ Văn Canh, “Nghiên cứu tấn công hệ mật khóa công khai RSA”, Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2013. [4] Nguyễn Anh Tuấn, Hồ Văn Canh, “Xây dựng thuật toán tấn công RSA không cần phân tích nhân tử”, Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2007. [5] Phan Đình Diệu, “Lý thuyết mật mã và an toàn thông tin”, Đại học Quốc gia Hà Nội, 2002. Tiếng Anh [6] Alfred J. Menezes, Scott A Vanstone, “Handbook of Applied Cryptography”, CRC Press,1996. [7] Abdelhak Azhari1, Samir Bouftass, “On a new fast public key cryptosystem”, 2015. [8] ANSIX9. 44, “Public Key Cryptography Using Reversible Algorithms for the Financial Services Industry: Transport of Symmetric Algorithm Keys Using RSA”, draft, 2004. [9] Caxton Foster, “Cryptanalysis for Microcomputers”, Rochelle Park,1982. [10] D. Boneh, “Twenty Years of Attacks on the RSA Cryptosystems”, Notices of the AMS, 1999. [11] Donal Knut, “The Art of Progamming Computer”, Tom, 2004. [12] I. Anshel, M. Anshel, and D. Goldfeld, “An algebraic method for public-key cryptography”, Methematical Research Letters, 2006. 57 [13] Mark Stamp, Richard, M. Low, “Applied Cryptanalysis”, Wiley - InterScience A. John wiley & Sons, INC Publication, 2007. [14] W. Alext, B. Chor, O. Goldreich, and C.P. Schnor, “RSA and Rabin functions: Certain parts are as hard as the whole”, SIAM Journal on Computing, 2009. Website [15]ố-nguyên-tố [16] [17] [18] PHỤ LỤC Phụ lục Mã nguồn Chương trình 58 using System; using System.Collections.Generic; using System.Linq; using System.Threading.Tasks; using System.Windows.Forms; namespace Phan_Tich_So_Nguyen_To { static class Program { /// /// The main entry point for the application. /// [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new Form1()); } } } -------- namespace Phan_Tich_So_Nguyen_To { partial class Form1 { /// /// Required designer variable. /// private System.ComponentModel.IContainer components = null; /// /// Clean up any resources being used. 59 /// /// true if managed resources should be disposed; otherwise, false. protected override void Dispose(bool disposing) { if (disposing && (components != null)) { components.Dispose(); } base.Dispose(disposing); } #region Windows Form Designer generated code /// /// Required method for Designer support - do not modify /// the contents of this method with the code editor. /// private void InitializeComponent() { System.ComponentModel.ComponentResourceManager resources = new System.ComponentModel.ComponentResourceManager(typeof(Form1)); this.richTextBox1 = new System.Windows.Forms.RichTextBox(); this.textBox1 = new System.Windows.Forms.TextBox(); this.btnAnalysis = new System.Windows.Forms.Button(); this.label1 = new System.Windows.Forms.Label(); this.backgroundWorker1 = new System.ComponentModel.BackgroundWorker(); this.progressBar1 = new System.Windows.Forms.ProgressBar(); this.label2 = new System.Windows.Forms.Label(); this.button1 = new System.Windows.Forms.Button(); this.SuspendLayout(); // // richTextBox1 // 60 this.richTextBox1.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) | System.Windows.Forms.AnchorStyles.Left) | System.Windows.Forms.AnchorStyles.Right))); this.richTextBox1.Font = new System.Drawing.Font("Microsoft Sans Serif", 15.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0))); this.richTextBox1.ForeColor = System.Drawing.Color.ForestGreen; this.richTextBox1.Location = new System.Drawing.Point(0, 58); this.richTextBox1.Name = "richTextBox1"; this.richTextBox1.ReadOnly = true; this.richTextBox1.Size = new System.Drawing.Size(925, 477); this.richTextBox1.TabIndex = 0; this.richTextBox1.Text = ""; // // textBox1 // this.textBox1.AcceptsReturn = true; this.textBox1.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Left) | System.Windows.Forms.AnchorStyles.Right))); this.textBox1.Font = new System.Drawing.Font("Microsoft Sans Serif", 14.25F, System.Drawing.FontStyle.Italic, System.Drawing.GraphicsUnit.Point, ((byte)(0))); this.textBox1.ForeColor = System.Drawing.Color.FromArgb(((int)(((byte)(0)))), ((int)(((byte)(0)))), ((int)(((byte)(192))))); this.textBox1.Location = new System.Drawing.Point(185, 17); this.textBox1.Name = "textBox1"; this.textBox1.ShortcutsEnabled = false; this.textBox1.Size = new System.Drawing.Size(280, 29); this.textBox1.TabIndex = 1; 61 this.textBox1.KeyPress += new System.Windows.Forms.KeyPressEventHandler(this.textBox1_KeyPress); // // btnAnalysis // this.btnAnalysis.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right))); this.btnAnalysis.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0))); this.btnAnalysis.ForeColor = System.Drawing.Color.DarkGreen; this.btnAnalysis.Location = new System.Drawing.Point(471, 14); this.btnAnalysis.Name = "btnAnalysis"; this.btnAnalysis.Size = new System.Drawing.Size(116, 30); this.btnAnalysis.TabIndex = 2; this.btnAnalysis.Text = "Phân tích"; this.btnAnalysis.UseVisualStyleBackColor = true; this.btnAnalysis.Click += new System.EventHandler(this.btnAnalysis_Click); // // label1 // this.label1.AutoSize = true; this.label1.Font = new System.Drawing.Font("Microsoft Sans Serif", 14.25F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0))); this.label1.ForeColor = System.Drawing.Color.Green; this.label1.Location = new System.Drawing.Point(12, 20); this.label1.Name = "label1"; this.label1.Size = new System.Drawing.Size(167, 24); this.label1.TabIndex = 3; this.label1.Text = "Số cần phân tích"; // // backgroundWorker1 62 // this.backgroundWorker1.WorkerReportsProgress = true; this.backgroundWorker1.WorkerSupportsCancellation = true; this.backgroundWorker1.DoWork += new System.ComponentModel.DoWorkEventHandler(this.backgroundWorker1_DoWork); this.backgroundWorker1.ProgressChanged += new System.ComponentModel.ProgressChangedEventHandler(this.backgroundWorker1_Progr essChanged); this.backgroundWorker1.RunWorkerCompleted += new System.ComponentModel.RunWorkerCompletedEventHandler(this.backgroundWorker1_ RunWorkerCompleted); // // progressBar1 // this.progressBar1.Dock = System.Windows.Forms.DockStyle.Bottom; this.progressBar1.Location = new System.Drawing.Point(0, 535); this.progressBar1.Name = "progressBar1"; this.progressBar1.Size = new System.Drawing.Size(925, 23); this.progressBar1.Step = 1; this.progressBar1.TabIndex = 5; // // label2 // this.label2.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right))); this.label2.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F, System.Drawing.FontStyle.Italic, System.Drawing.GraphicsUnit.Point, ((byte)(0))); this.label2.Location = new System.Drawing.Point(697, 4); this.label2.Name = "label2"; this.label2.Size = new System.Drawing.Size(228, 51); this.label2.TabIndex = 6; 63 this.label2.Text = "© All rights reserved by \r\nMr. Hoàng"; this.label2.TextAlign = System.Drawing.ContentAlignment.MiddleCenter; // // button1 // this.button1.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right))); this.button1.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0))); this.button1.ForeColor = System.Drawing.Color.DarkGreen; this.button1.Location = new System.Drawing.Point(593, 14); this.button1.Name = "button1"; this.button1.Size = new System.Drawing.Size(82, 30); this.button1.TabIndex = 2; this.button1.Text = "Dừng"; this.button1.UseVisualStyleBackColor = true; this.button1.Click += new System.EventHandler(this.button1_Click); // // Form1 // this.AcceptButton = this.btnAnalysis; this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F); this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font; this.ClientSize = new System.Drawing.Size(925, 558); this.Controls.Add(this.label2); this.Controls.Add(this.label1); this.Controls.Add(this.button1); this.Controls.Add(this.btnAnalysis); this.Controls.Add(this.textBox1); this.Controls.Add(this.richTextBox1); this.Controls.Add(this.progressBar1); 64 this.ForeColor = System.Drawing.Color.DarkGreen; this.Icon = ((System.Drawing.Icon)(resources.GetObject("$this.Icon"))); this.MaximizeBox = false; this.Name = "Form1"; this.SizeGripStyle = System.Windows.Forms.SizeGripStyle.Hide; this.Text = "Phân tích số nguyên tố"; this.Load += new System.EventHandler(this.Form1_Load); this.ResumeLayout(false); this.PerformLayout(); } #endregion private System.Windows.Forms.RichTextBox richTextBox1; private System.Windows.Forms.TextBox textBox1; private System.Windows.Forms.Button btnAnalysis; private System.Windows.Forms.Label label1; private System.ComponentModel.BackgroundWorker backgroundWorker1; private System.Windows.Forms.ProgressBar progressBar1; private System.Windows.Forms.Label label2; private System.Windows.Forms.Button button1; } } ------------------------------------------ using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading; using System.Threading.Tasks; using System.Windows.Forms; 65 namespace Phan_Tich_So_Nguyen_To { public partial class Form1 : Form { public Form1() { InitializeComponent(); } Int64 tinhN(Int64 thamso) { return (thamso + 1) / 2; } Int64 tinhB(Int64 n, Int64 canN) { if ((n - canN) % 2 == 0) return n - canN; else return n - canN - 1; } Int64 tinhCanN(Int64 thamso) { return (Int64)Math.Sqrt(thamso); } Int64 tinhF(Int64 nPhay, Int64 B, Int64 N) { return (nPhay - B) * (nPhay - B) - N; } bool kiemTraSoChinhPhuong(Int64 N) { try { 66 if (N == 0 || N == 1) { return true; } else { for (double i = 0; i < (Int64)Math.Sqrt(N)+1 ; i++) { if (i * i == N) return true; } } return false; } catch (Exception) { MessageBox.Show("Error here"); return false; } } private void backgroundWorker1_ProgressChanged(object sender, ProgressChangedEventArgs e) { progressBar1.Value = e.ProgressPercentage; //richTextBox1.ScrollToCaret(); } private void backgroundWorker1_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e) { //progressBar1.Hide(); MessageBox.Show("Xong!"); btnAnalysis.Enabled = true; 67 } int validate(string input) { long res=0; if (!Int64.TryParse(input,out res) ) { return 1;//số nhập không hợp lệ } res = Int64.Parse(input); if (res % 2 == 0) { return 2;// số là số chẵn } else if (checkPrime(res) == 2) { return 3;// số nguyên tố } else return 0;// số hợp lệ } int checkPrime(Int64 number) { int count = 0; for (int i = 1; i <= number; i++) { if(number%i==0) count++; if (count > 2) break; } return count; } void AppendTextBox(string Value) { if (InvokeRequired) 68 { this.Invoke(new Action(AppendTextBox), new object[] { Value }); return; } richTextBox1.AppendText(Value); //richTextBox1.ScrollToCaret(); } private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e) { try { if (validate(textBox1.Text)==1) { AppendTextBox("Số nhập vào không hợp lệ \n"); } else if (validate(textBox1.Text)==2) { AppendTextBox("Số nhập vào là số chẵn, không hợp lệ \n"); } else if (validate(textBox1.Text) == 3) { AppendTextBox("Số nhập vào là số