Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Sư phạm Nghiên cứu xây dựng thuật toán tấn công hệ mật rsa...

Tài liệu Nghiên cứu xây dựng thuật toán tấn công hệ mật rsa

.PDF
90
56
112

Mô tả:

i ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG VÕ TÁ HOÀNG NGHIÊN CỨU XÂY DỰNG THUẬT TOÁN TẤN CÔNG HỆ MẬT RSA LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Thái Nguyên – 2020 ii LỜI CAM ĐOAN Học viên xin cam đoan luận văn này là công trình nghiên cứu thực sự của bản thân, dưới sự hướng dẫn khoa học của TS. Hồ Văn Canh. Các số liệu, kết quả trong luận văn là trung thực và chưa từng được công bố dưới bất cứ hình thức nào. Tất cả các nội dung tham 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 P y Bản mã thuộc 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 k 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 đó p, q 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  Z n và định nghĩa k  n, p, q, a, b : ab  1mod  n - Mã hóa: ek x   x b mod n - Giải mã: d k  y   y a 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  1 vớ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ó:   y a mod n  xb mod n  x t . n 1 mod n  x n  mod n x mod n  1t.xmod n   xmod n  a t 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 Suy ra: y a mod n  x b  mod n  h ab mod n  p ab mod n mod n . Do h, n  1 nên a h ab mod n  h . Bên cạnh đó ta lại có: p ab mod n  p ab mod  pq  p ab mod q  p. p n  mod q  p. p  p . q    p. p   p     mod q  p . Vậy  q y a mod n  hp mod 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.7 nê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  6597 mod11200 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.1: b trong mộtthidanh bạ và dùng chúng làn Thực hệ mật RSA khóa công 1.1.3 Vấn đề 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 a , 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ã c1c2 ..ci anh ta nhận được các bản rõ tương ứng m1m2 ..mi . Từ đó anh ta 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 cùng khóa lập mã b . 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 p, q người ta có thể dễ dàng tính được  n  . Nếu biết được  n  ta có thể tìm được p, q 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 đó p, q là nghiệm của phương trình bậc 2: x 2  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 p, q 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 p, q 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 p, q . 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ó: g  Z n  1 mod n (do k là bội của  n  và do đó g 2 là căn bậc hai của 1 k 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 p, q trong thời gian đa thức bằng cách tính gcdx  1, n x 2  1 mod n  x  1x  1  1 mod n  x  1x  1 : n (1) Đặt x  1, n  d1 và x  1, n  d 2 Vì n  p.q 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  p.q nên một trong hai giá trị d1 , d 2 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  2 s 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  v 2 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 ) Thuật toán có xác suất thành công tối thiểu là 1 2 . 1.4.3 Giao thức công chứng
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng