Tài liệu 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 QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Anh Tuấn XÂY DỰNG THUẬT TOÁN TẤN CÔNG RSA KHÔNG CẦN PHÂN TÍCH NHÂN TỬ Ngành : Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60.48.05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN: TS. HỒ VĂN CANH Hà Nội – 2007 1 Mục lục LỜI NÓI ĐẦU ....................................................................................................... 3 Chƣơng 1 - TỔNG QUAN VỀ MẬT MÃ VÀ MÃ THÁM ................................. 5 1.1. Mã truyền thống. ........................................................................................ 5 1.1.1. Mã apphin. ............................................................................................ 5 1.1.2. Mã thay thế (substitution cipher). .......................................................... 6 1.1.3. Mã chuyển dịch (shift cipher) ................................................................ 6 1.1.4. Mã hoán vị. ............................................................................................ 6 1.1.5. Mã Vigenère. ......................................................................................... 7 1.1.6. Mã Hill. ................................................................................................. 7 1.2. Mã đối xứng. ............................................................................................... 8 1.2.1. Mã theo dòng. ........................................................................................ 8 1.2.2. Mã chuẩn DES. ...................................................................................... 9 1.3. Mã bất đối xứng. ....................................................................................... 10 1.4. Vấn đề thám mã. ....................................................................................... 16 Chƣơng 2 - TỔNG KẾT NHỮNG KẾT QUẢ TẤN CÔNG VÀO HỆ MẬT RSA TRONG NHỮNG NĂM QUA ................................................................... 19 2.1. Một số giả thiết ngầm định. ...................................................................... 19 2.2. Phân tích các số nguyên lớn. .................................................................... 20 2.2.1. Modul chung ........................................................................................ 20 2.2.2. Mù (Blinding) ...................................................................................... 20 2.3. Số mũ riêng bé (Low Private Exponnent) ............................................... 21 2.3.1. Độ lớn e. .............................................................................................. 22 2.3.2. Sử dụng CRT........................................................................................ 22 2.4. Số mũ công khai bé (Low public Exponent) ............................................ 22 2.4.1. Hastad's Broadcast Attack. .................................................................. 23 2.4.2. Franklin-Reiter Related Message Attack. ............................................. 24 2.5. Thành phần công khai bé ......................................................................... 24 2.5.1. Coppersmith's Short Pad Attack. ......................................................... 24 2.5.2. Tấn công bằng khóa riêng. .................................................................. 25 2.6. Cài đặt các tấn công. ................................................................................. 26 2.6.1. Tấn công dựa trên thời gian. ................................................................ 26 2.6.2. Tấn công dựa trên các lỗi ngẫu nhiên. ................................................. 28 2.6.3. Tấn công của Bleichenbacher trên PKCS 1 ......................................... 29 2.8. Một số tấn công bằng nhân tử hóa số N với số N lớn. ............................. 29 2.8.1. Tìm nhân tử lớn nhất thứ nhất  N .................................................... 30 2.8.2. Phân tích thứ hai. ................................................................................ 30 2.8.3. Phân tích thứ ba. ................................................................................. 31 2.8.4. Thuật toán Pollard (p-1). ..................................................................... 32 Chƣơng 3 - THƢ VIỆN TÍNH TOÁN SỐ LỚN ................................................ 34 2 3.1. Biểu diễn số lớn. ........................................................................................ 34 3.2. Các phép toán trong số lớn ...................................................................... 35 3.2.1. So sánh hai số. ..................................................................................... 35 3.2.2. Cộng hai số lớn dương......................................................................... 36 3.2.3. Trừ hai số lớn dương ........................................................................... 37 3.2.4. Phép nhân hai số lớn. .......................................................................... 37 3.2.5. Phép chia hai số lớn dương. ................................................................ 39 3.2.6. Lũy thừa............................................................................................... 41 3.2.7. Ước chung lớn nhất. ............................................................................ 41 3.2.8. Phép nhân theo module p. .................................................................... 42 3.2.9. Tính căn của số nguyên lớn. ................................................................ 43 3.2.10. Tìm phần từ nghịch đảo theo module p .............................................. 43 3.2.11. Phép cộng có dấu............................................................................... 44 3.2.12. Phép trừ có dấu. ................................................................................ 45 3.2.13. Phép nhân có dấu. ............................................................................. 45 Chƣơng 4 - PHƢƠNG PHÁP TẤN CÔNG RSA KHÔNG CẦN PHÂN TÍCH NHÂN TỬ ............................................................................................................ 46 4.1. Mở đầu ...................................................................................................... 46 4.2. Cơ sở toán học. .......................................................................................... 47 4.2.1. Bổ đề 1................................................................................................. 47 4.2.2. Bổ đề 2................................................................................................. 48 4.2.3. Bổ đề 3................................................................................................. 48 4.2.4. Bổ đề 4................................................................................................. 48 4.3. Các thuật toán ........................................................................................... 51 4.4. Các ví dụ: .................................................................................................. 54 KẾT LUẬN .......................................................................................................... 62 3 LỜI NÓI ĐẦU 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ỹ. Hệ mật sử dụng trong lĩnh vự đảm bảo tính riêng tư và cung cấp cơ chế xác thực của dữ liệu số. Ngày nay, RSA đã được phát triển ứng dụng rộng rãi trong thương mại điện tử. Nó được sử dụng trên Web servers và trên các Browsers nhằm đảm bảo an ninh đường truyền, được sử dụng trong việc tạo khóa và xác thực của mail, trong truy cập từ xa…, và đặc biệt nó là hạt nhận của hệ thống thanh toán điện tử. Tóm lại, RSA được ứng dụng rộng rãi trong các lĩnh vực nơi mà an ninh an toàn thông tin được đòi hỏi. Ngay từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ số an toàn bởi nhiều nhà nghiên cứu. Mặc dầu đã trải qua nhiều năm nghiên cứu và đã có một số cuộc tấn công ấn tượng nhưng không mang lại kết quả là phá hủy. Đa phần họ mới chỉ ra được những mỗi nguy hiểm tiềm ẩn của RSA mà khi sử dụng RSA người dùng cần cải thiện. Thực tế vấn đề thám mã đối với hệ mật RSA hiện tại đang được các nhà nghiên cứu tập trung khai thác 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). Tuy nhiên đối với số n lớn, chẳng hạ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à tỏ ra không có kết quả như mong muốn. Xuất phát từ thực tế đó, em đã phân tích về mặt toán học hệ mật để tìm cách thu hẹp khoảng cách mà thuật toán phải dò tìm số nguyên tố p kết hợp đưa ra một thuật toán tấn công vào RSA mà không phải phân tích nhân tử. Và qua nghiên cứu cài đặt phương pháp tổng hợp này tỏ ra có hiệu quả cao hơn các thuật toán đã được công bố mới đây. Nội dụng của phương pháp này sẽ được em trình bày trong chương cuối của luận văn. Để phục vụ cho việc phân tích các tính chất của hệ mật RSA, em đã trình bày tổng quan về mật mã và thám mã trong chương I – “Tổng quan về mật mã và thám mã”. Ở chương này, em trình bày chi tiết về lịch sử cũng như các khái niệm về các hệ mã thuộc dòng mã truyền thống cũng như dòng mã đối xứng, mã bất đối xứng giúp giúp chúng ta hiểu cơ sở lý thuyết về các hệ mật mã. Vấn đề thám mã nói 4 chung và thám mã đối với hệ mật RSA cũng được em trình bày kỹ trong chương này. Trên cơ sở hiểu các hệ mật được trình bày ở chương I, để có cái nhìn tổng quan về vấn đề thám mã đối với hệ mật RSA trong những năm qua, em đã tổng kết lại các phương pháp và kết quả đã được công bố trong chương II của luận văn – “Tổng kết những kết quả tấn công vào hệ mật RSA trong những năm qua”. Trong chương này em đã trình bày chi tiết các thuật toán tấn công vào hệ mật RSA như: các tấn công cơ bản – modul chung, mù; tấn công vào số mũ công khai hoặc số mũ bí mật thấp; tấn công dựa trên thời gian hay dựa trên các lỗi ngẫu nhiên… Ngoài ra, em cũng trình bày các thuật toán tấn công RSA bằng nhân tử hóa số n với số n lớn như thuật toán Pollard, tuy nhiên các thuật toán được giới thiệu ở đây mới chỉ giải quyết cho modul N của RSA có độ dài hạn chế, còn modulus N có độ dài lớn thì cho đến nay chưa có phương pháp khả thi nào được công bố. Qua nghiên cứu các thuật toán đã được công bố, em đề xuất phương pháp tấn công RSA mà không cần phần tích nhân tử, phương pháp này tỏ ra có hiệu quả đối với hệ RSA có số n lớn. Để thực hiện phương pháp này, em xin phép được trình bày thư viện các phép toán đối với số lớn trong chương III – “Thư viện tính toán số lớn”. Các thuật toán biểu diễn cũng như tính toán cộng, trừ, nhân, chia…phục vụ cho việc xây dựng giải pháp tấn công RSA mà không phân tích nhân tử. Các thuật toán đã được trình bày ở chương II chủ yếu là dò tìm 1 số nguyên tố p(giả sử p < q). Trên cơ sở đó nếu xác định được một nhân tử nguyên tố p của n thì có thể từ đó suy ra được ngay nhân tử kia bằng cách lấy số n chia cho p: q= n p tuy nhiên với số lớn việc xác định p và q như vậy là không hiệu quả. Qua nghiên cứu, em đưa ra phương pháp tấn công RSA bằng cách rút ngắn khoảng cách dò tìm số nguyên tố p đồng thời không phải tìm một nhân tử nguyên tố bé của n. Phương pháp này được trình bày chi tiết ở chương IV – “Phương pháp tấn công RSA không cần phân tích nhân tử” . 5 Chƣơng 1 - TỔNG QUAN VỀ MẬT MÃ VÀ MÃ THÁM 1.1. Mã truyền thống. Mã truyền thống hay còn gọi là mã cổ điển là một dạng của mật mã đã được sử dụng trong lịch sử phát triển của loài người nhưng ngày nay đã trở nên lạc hậu do các phương thức mã hóa này quá đơn giản và những kẻ tấn công có thể dễ dàng bẻ khóa thông qua nhiều phương thức như tấn công vét cạn, hay dựa trên tấn công thống kê (dựa trên tần suất xuất hiện của các chữ cái). Nhìn chung, mã truyền thống hoạt động trên cơ sở bảng chữ cái (chẳng hạn các ký tự từ "A" tới "Z" trong tiếng Anh), và chúng được thực hiện bằng tay hay một số máy móc cơ khí đơn giản. Các phương thức mã hóa truyền thống chủ yếu dựa trên mật mã hóa hoán vị và mật mã hóa thay thế. Trong mật mã hóa thay thế, các ký tự (hoặc nhóm ký tự) được thay thế một cách có quy luật trong toàn bộ thông điệp bằng các ký tự khác (hoặc nhóm ký tự), sau đó các ký tự còn lại trong bảng chữ cái được thay thế theo một quy luật nào đó xác định trước. Trong phương thức mật mã hóa hoán vị thì các ký tự được giữ không đổi, nhưng trật tự của chúng trong bản tin lại thay đổi theo một quy luật nào đó. Cụ thể một số hệ mã truyền thống như: 1.1.1. Mã apphin. Sơ đồ các hệ mật mã apphin được định nghĩa như sau: S = (P , C , K , E , D ) , trong đó P =C = Z26 , K = { (a,b)  Z26 x Z26  gcd(a, 26) = 1} , các ánh xạ E và D được cho bởi: Ek(x ) = ax + b mod26, Dk(y ) = a-1(y - b) mod26, với mọi x  P , y  C , k = (a, b)  K . K là tập các khóa, k  K là một khóa cụ thể nào đó trong K. 6 1.1.2. Mã thay thế (substitution cipher). Sơ đồ các hệ mật mã thay thế được định nghĩa như sau: S = (P , C , K , E , D ) , trong đó P = C = Z26 , K là tập hợp tất cả các phép hoán vị trên Z26 các ánh xạ E và D được cho bởi: e ( x)   ( x), với mọi x d ( y )   1 ( y ),  P , y  C ,   K là một phép hoán vị trên Z26 . Ta thường đồng nhất Z26 với bảng ký tự tiếng Anh, do đó phép hoán vị trên Z26 cũng được hiểu là một phép hoán vị trên tập hợp các ký tự tiếng Anh, 1.1.3. Mã chuyển dịch (shift cipher) Hệ mã dùng phép chuyển dịch, ta dùng bảng ký tự gồm có 26 ký tự, được đánh số từ 0 đến 25, ta có thể đồng nhất nó với tập Z26. Như vậy, sơ đồ các hệ mật mã chuyển dịch được định nghĩa như sau: S = (P , C , K , E , D ) , trong đó P = C = K = Z26 , các ánh xạ E và D được cho bởi: với mọi k, x , y  Z26 : E (k, x) = x + k mod26, D (k, y) = y - k mod26. Các hệ mật mã được xác định như vậy là đúng đắn, vì với mọi k, x , y  Z26 ta đều có:   DkEk(x) = (x + k ) - k mod26 = x vì x  a, z Các hệ mật mã chuyển dịch đã được sử dụng từ rất sớm, theo truyền thuyết, hệ mã đó với k =3 đã được dùng bởi J. Caesar từ thời đế quốc La mã, và được gọi là hệ mã Caesar. 1.1.4. Mã hoán vị. Các hệ mã hoán vị cũng được thực hiện trên từng bộ m ký tự liên tiếp, nhưng bản mật mã chỉ là một hoán vị của các ký tự trong từng bộ m ký tự của bản rõ. Ta ký hiệu Sm là tập hợp tất cả các phép hoán vị của tập hợp { 1,2, ... ,m }. Sơ đồ các phép mã hoán vị được cho bởi 7 S = (P , C , K , E , D ) , trong đó P Ek(x1,..., =C xm ) = Z 26m , K = Sm , các ánh xạ E và D được cho bởi: = ( x (1) ,..., x ( m) ), Dk(y1,..., ym ) = ( y 1 (1) ,..., y 1 ( m) ), với mọi x =(x1,..., xm )  P , y =(y1,..., ym )  C , K =  Sm ,  -1 là hoán vị nghịch đảo của  . 1.1.5. Mã Vigenère. Sơ đồ mật mã này lấy tên của Blaise de Vigenère, sống vào thế kỷ 16. Khác với các hệ mật mã đã kể trước, các hệ mật mã Vigenère không thực hiện trên từng ký tự một, mà được thực hiện trên từng bộ m ký tự (m là số nguyên dương). Sơ đồ các hệ mật mã Vigenère được định nghĩa như sau: S = (P , C , K , E , D ) , P trong đó = C =K = Z 26m , các ánh xạ E và D được cho bởi: Ek(x1,..., xm ) = ( x1+k1,...., xm+km ) mod26 Dk(y1,..., ym ) = ( y1-k1 ,..., ym-km ) mod26 với mọi x =(x1,..., xm )  P , y =(y1,..., ym )  C , k = (k1,...,km) K . Sơ đồ mã Vigenère có thể được xem là mở rộng của sơ đồ mã chuyển dịch, nếu mã chuyển dịch thực hiện việc chuyển dịch từng ký tự một thì mã Vigenère thực hiện đồng thời từng bộ m ký tự liên tiếp. 1.1.6. Mã Hill. Sơ đồ mật mã này được đề xuất bởi Lester S. Hill năm 1929. Cũng giống như sơ đồ mã Vigenère, các hệ mã này được thực hiện trên từng bộ m ký tự liên tiếp, điều khác là mỗi ký tự của bản mã được xác định bởi một tổ hợp tuyến tính (trên vành Z26) của m ký tự trong bản rõ. Như vậy, khoá sẽ được cho bởi một ma trận cấp m, tức là một phần tử của K  Z m xm. Để phép biến đổi tuyến tính xác định bởi ma trận K có phép nghịch đảo, bản thân ma trận K cũng phải có ma trận nghịch đảo K -1 theo mod26; mà điều kiện cần và đủ để K có nghịch đảo là định thức của nó, ký hiệu detK, nguyên tố với 26. Vậy, sơ đồ mật mã Hill được định nghĩa là sơ đồ 8 S = (P , C , K , E , D ) , trong đó P = Z 26m , K = K  Z26mm : gcd(det K , 26)  1 , = C các ánh xạ E và D được cho bởi: Ek(x1,..., xm ) = (x1,..., xm ).K mod26, Dk(y1,..., ym ) = (y1,..., ym ). K -1 mod26 với mọi x =(x1,..., xm )  P , y =(y1,..., ym )  C , k  K . 1.2. Mã đối xứng. Mã đối xứng (symmetric-key algorithms) là hệ mã mà người gửi và người nhận cùng có một khóa chung K . K được giữ như bí mật riêng của hai người, K dùng cả cho lập mật mã và giải mã nên có thể dễ dàng tìm được một khóa nếu biết khóa kia. Nhiều thuật ngữ khác dành cho việc mã hóa dùng chìa khóa đối xứng bao gồm các phương pháp mã hóa đơn khóa (single-key), phương pháp mã hóa một khóa (one-key) và phương pháp mã hóa khóa cá nhân (private-key). Thuật toán đối xứng có thể được chia ra làm hai thể loại, mã luồng (stream ciphers) và mã khối (block ciphers). Mã luồng mã hóa từng bit của thông điệp trong khi mã khối gộp một số bit lại và mã hóa chúng như một đơn vị. Cỡ khối được dùng thường là các khối 64 bit. Thuật toán tiêu chuẩn mã hóa tiên tiến (Advanced Encryption Standard), được NIST công nhận tháng 12 năm 2001, sử dụng các khối gồm 128 bit, 192 bít hoặc 256 bít tùy người gửi/nhận thống nhất với nhau. Mã đối xứng nhìn chung có tốc độ tính toán nhanh. Điển hình như: 1.2.1. Mã theo dòng. Với cách lập mã theo dòng, ta còn cần có một bộ sinh dòng khoá để với mỗi mầm khoá s cho trước nó sinh ra một dòng khoá K1K2K3..., mỗi Ki dùng để lập mã cho khối xi của văn bản. Mỗi từ khoá Ki , ngoài việc phụ thuộc vào mầm khoá s còn có thể phụ thuộc vào đoạn từ khoá K1...Ki-1 đã được sinh ra trước đó và cả vào các yếu tố khác, chẳng hạn như đoạn văn bản x1...xi-1 đã được lập mã trước đó. Như vậy, ta có thể định nghĩa lại như sau: Một sơ đồ hệ mã theo dòng được cho bởi một bộ S = (P , C , R, K , F, E , D ) thỏa mãn các điều kiện sau đây: (1) 9 P là một tập hữu hạn các ký tự bản rõ, C là một tập hữu hạn các ký tự bản mã, R là một tập hữu hạn các mầm khoá, K là một tập hữu hạn các khóa, F = { f1, f 2,....}là bộ sinh dòng khoá, trong đó mỗi fi là một ánh xạ từ R K i- 1 P i- 1 vào K , E là một ánh xạ từ K xP vào C ,, được gọi là phép lập mật mã; và D là một ánh xạ từ K x C vào P , được gọi là phép giải mã. Với mỗi k K , ta định nghĩa Ek : P C , Dk :C P là hai hàm cho bởi :  x P : Ek(x) = E (k,x) ;  y C : Dk(y) = D (k,y). Ek vàDk được gọi lần lượt là hàm lập mã và hàm giải mã ứng với khóa mật mã K. Các hàm đó phải thỏa mãn hệ thức:  x P : Dk(Ek(x)) = x. Khi cho trước mầm khoá rR , với mỗi bản rõ x = x1x2....xm  P * , ta có bản mật mã tương ứng là y = y1 y2.... ym , với yi = E (Ki ,xi ) , trong đó Ki = fi (r, K1,...,Ki- 1, x1x2....xi- 1), (i =1,2,...,m). Điều đó có nghĩa là từ mầm khoá r và bản rõ x sinh ra được dòng khoá K1K2...Km , và với dòng khoá đó lập được bản mã y theo từng ký tự một. Nếu bộ sinh dòng khoá không phụ thuộc vào văn bản rõ, tức là nếu mỗi fi là một ánh xạ từ R xK i- 1 vào K , thì ta gọi bộ sinh dòng khoá đó là đồng bộ ; dòng khoá chỉ phụ thuộc vào mầm khoá và là như nhau đối với mọi văn bản rõ. Một dòng khóa K =K1K2K3.. được gọi là tuần hoàn với chu kỳ d nếu có số nguyên N sao cho Ki+d = Ki với mọi i  N . Chú ý rằng mã Vigenère với độ dài khóa m có thể được coi là mã dòng với dòng khoá có chu kỳ m, và có các phép lập mã và giải mã theo mã chuyển dịch. 1.2.2. Mã chuẩn DES. Hệ mã DES là một hệ mật mã theo khối, mỗi khối bản rõ là một từ 64 bit, tức là một phần tử thuộc Z 264 , và các khối bản mã cũng là các từ 64 bit, như vậy P = C 10 = Z 264 . DES có tập khoá K = Z 256 , tức mỗi khoá là một từ 56 bit. Với mỗi khoá K và bản rõ x, quá trình lập mã diễn ra như sau: Bước đầu, dùng một phép hoán vị ban đầu IP, từ x 64 bit sẽ biến thành một từ mới IP (x ), từ này được chia thành hai nửa L0 và R0 , mỗi nửa là một từ 32 bit. Bước tiếp theo, ta sẽ dùng 16 lần những phép toán giống nhau để liên tiếp được các cặp (L1,R1 ),...., (L16 ,R16 ), sau đó dùng phép hoán vị nghịch đảo IP -1 cho từ đảo ngược R16L16 ta sẽ được bản mã y tương ứng. 1.3. Mã bất đối xứng. Sự ra đời của khái niệm hệ mã bất đối xứng là một tiến bộ có tính chất bước ngoặt trong lịch sử mật mã nói chung, gắn liền với sự phát triển của khoa học tính toán hiện đại. Mã hóa bất đối xứng là một dạng mật mã hóa cho phép người sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí mật trước đó. Điều này được thực hiện bằng cách sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân (hay khóa bí mật). Trong mã bất đối xứng, khóa cá nhân phải được giữ bí mật trong khi khóa công khai được phổ biến công khai. Trong 2 khóa, một dùng để mã hóa và khóa còn lại dùng để giải mã. Điều quan trọng đối với hệ thống là khó có thể tìm ra khóa bí mật nếu chỉ biết khóa công khai. Hệ thống mã bất đối xứng có thể sử dụng với các mục đích như:  Mã hóa: giữ bí mật thông tin và chỉ có người có khóa bí mật mới giải mã  được. Tạo chữ ký số: Việc kiểm tra một chữ ký nào đó dễ dàng được thực hiện nhờ khóa công khai cho trước.    Thỏa thuận khóa: cho phép thiết lập khóa dùng để trao đổi thông tin mật giữa 2 bên. Phân phối khóa: Phân phối khóa được định nghĩa là một cơ chế theo đó một bên chọn khóa bí mật và sau đó truyền nó tới một hoặc nhiều bên khác nhau. Thỏa thuận khóa để chỉ một giao thức theo đó hai (hoặc nhiều hơn) bên cùng thiết lập khóa bí mật bằng cách liên lạc trên kênh công cộng Các kỹ thuật mã bất đối xứng đòi hỏi khối lượng tính toán nhiều hơn các kỹ thuật mã hóa khóa đối xứng nhưng những lợi điểm mà chúng mang lại khiến cho 11 chúng được áp dụng trong nhiều ứng dụng. Các hệ mã bất đối xứng dựa trên tính chất của các bài toán cơ bản như: Bài toán phân tích số nguyên (thành thừa số nguyên tố): Cho số nguyên dương n , tìm tất cả các ước số nguyên tố của nó, hay là tìm dạng phân tích chính tắc của n = p1 . p2 ... pk , trong đó pi là các số nguyên tố từng 1 2 k cặp khác nhau và các i  1. Bài toán này có liên hệ mật thiết với các bài toán thử tính nguyên tố hay thử tính hợp số của một số nguyên, nhưng với những gì mà ta biết đến nay, nó dường như khó hơn nhiều so với hai bài toán thử tính nguyên tố và tính hợp số. Bài toán RSA (Rivest-Shamir-Adleman) : Cho số nguyên dương n là tích của hai số nguyên tố lẻ khác nhau, một số nguyên dương e sao cho gcd(e, (n)) =1, và một số nguyên c ; tìm một số nguyên m sao cho me  c (mod n) . Điều kiện gcd(e, (n)) =1 bảo đảm cho việc với mỗi số nguyên c  0,1,...,n -1 có đúng một số m  0,1,...,n -1 sao cho me  c (mod n) . Dễ thấy rằng nếu biết hai thừa số nguyên tố của n, tức là biết n =p.q thì sẽ biết  (n) = (p -1)(q -1), do gcd(e, (n)) =1 sẽ tìm được d =e -1mod (n), và do đó sẽ tìm được m =c d modn. Như vậy, bài toán RSA có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Bài toán thặng dư bậc hai : Giả sử cho trước một hợp số nguyên lẻ và một số nguyên a Jn , tập tất cả các số a có ký hiệu Jacobi. Hãy quyết định xem a có là thặng dư bậc hai theo modn hay không? Trong lý thuyết mật mã, bài toán này cũng thường được xét với trường hợp n là số nguyên Blum, tức n là tích của hai số nguyên tố p và q , n =p.q. Ta chú ý rằng trong trường hợp này, nếu a Jn , thì a là thặng dư bậc hai theo modn, điều này có thể thử được dễ dàng vì nó tương đương với điều kiện a (p -1)/2 1 (modp). Như vậy, trong trường hợp này, bài toán thặng dư bậc hai có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Mặt khác, nếu không biết cách phân tích n thành thừa số nguyên tố thì cho đến nay, không có cách nào giải được bài toán 12 thặng dư bậc hai trong thời gian đa thức. Điều đó củng cố thêm niềm tin rằng bài toán thặng dư bậc hai và bài toán phân tích số nguyên là có độ khó tương đương nhau. Bài toán tìm căn bậc hai modn : Định nghĩa thặng dư bậc 2: Giả sự a,n là số nguyên n  1 và (a,n) = 1. Khi đó a được gọi là thặng dư bậc 2 theo module n nếu và chỉ nếu tồn tại x nguyên sao cho: x2  a modn (1) Nếu a không thỏa mãn phương trình (1) thì a được gọi là không thặng dư bậc 2 theo module n. Tập tất cả các số nguyên a là thặng dư bậc 2 theo module n được ký hiệu là Qn. Tập tất cả các số nguyên không thặng dư bậc 2 theo module n được ký hiệu bằng Qn . Cho một số nguyên lẻ n là hợp số Blum, và một số a Qn (Qn là tập tất cả các thặng dư bậc 2 theo modul n) tức a là một thặng dư bậc hai theo modn . Hãy tìm một căn bậc hai của a theo modn, tức tìm x sao cho x 2 a (modn). Nếu biết phân tích n thành thừa số nguyên tố, n =p.q , thì bằng cách giải các phương trình x 2 a theo các modp và modq, rồi sau đó kết hợp các nghiệm của chúng lại theo định lý số dư Trung quốc ta sẽ được nghiệm theo modn , tức là căn bậc hai của a theo modn cần tìm. Vì mỗi phương trình x 2 a theo modp và modq có hai nghiệm (tương ứng theo modp và modq ), nên kết hợp lại ta được bốn nghiệm, tức bốn căn bậc hai của a theo modn. Người ta đã tìm được một số thuật toán tương đối đơn giản (trong thời gian đa thức) giải phương trình x 2 a (modp) với p là số nguyên tố. Như vậy, bài toán tìm căn bậc hai modn có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Ngược lại, nếu có thuật toán  giải bài toán tìm căn bậc hai modn thì cũng có thể xây dựng một thuật toán giải bài toán phân tích số nguyên như sau: Chọn ngẫu nhiên một số x với gcd(x,n) =1, và tính a =x2modn. Dùng thuật toán  cho a để tìm một căn bậc hai modn của a. Gọi căn bậc hai tìm được đó là y. Nếu y  x (modn), thì phép thử coi như thất bại, và ta phải chọn tiếp một số x khác. còn nếu y  x (modn), thì gcd(x-y, n) chắc chắn là một ước số không tầm thường của n, cụ thể là p hay là q. Vì n có 4 căn bậc hai modn nên xác suất của thành công ở mỗi lần thử là 1/2, và do đó số trung bình (kỳ vọng toán học) các phép thử để thu được một thừa số p hayq của n là 2, từ đó ta thu 13 được một thuật toán giải bài toán phân tích số nguyên (Blum) với thời gian trung bình đa thức. Tóm lại, theo một nghĩa không chặt chẽ lắm, ta có thể xem hai bài toán phân tích số nguyên và tìm căn bậc hai modn là khó tương đương nhau. Bài toán lôgarit rời rạc : Cho số nguyên tố p, một phần tử nguyên thuỷ  theo modp (hay  là phần tử nguyên thuỷ của Z p ), và một phần tử   Z p .Tìm số nguyên x (0 x  p - 2) sao cho  x   (modp). Ta đã biết rằng trong trường hợp chung, cho đến nay chưa có một thuật toán nào giải bài toán này trong thời gian đa thức. Bài toán này cũng được suy rộng cho các nhóm cyclic hữu hạn như sau: Bài toán lôgarit rời rạc suy rộng : Cho một nhóm cyclic hữu hạn G cấp n, một phần tử sinh (nguyên thuỷ)  của G, và một phần tử  G. Tìm số nguyên x (0 x  n - 1) sao cho  x = . Cho Zn = {0,1,…,n-1}. Trên Zn ta định nghĩa hai phép toán là cộng (+) và phép nhân (.) theo module n nói chung không phải là một trường. Z n là một trường khi và chỉ khi n là số nguyên tố. Trong trường hợp n là số nguyên tố thì Zn* = Zn/{0}. Các nhóm được quan tâm nhiều nhất trong lý thuyết mật mã là: nhóm nhân của trường hữu hạn GF (p)- đẳng cấu với nhóm Z p của trường Zp, nhóm nhân F2 m của trường hữu hạn GF (2m), nhóm nhân: Zn  a :0  a  n  1,gcd(a, n)  1 của trường Zn, nhóm gồm các điểm trên một đường cong elliptic xác định trên một trường hữu hạn, v.v... Bài toán Diffie-Hellman : Cho số nguyên tố p, một phần tử nguyên thuỷ  theo modp (tức phần tử sinh của Z p ), và các phần tử  a mod p và  b mod p . Hãy tìm giá trị  ab mod p . Có thể chứng minh được rằng bài toán Diffie-Hellman qui dẫn được về bài toán lôgarit rời rạc trong thời gian đa thức. Thực vậy, giả sử có thuật toán  giải bài toán lôgarit rời rạc. Khi đó, cho một bộ dữ liệu vào của bài toán Diffie-Hellman 14 gồm p,  ,  a mod p và  b mod p ; trước hết dùng thuật toán  cho (p,  ,  a mod p ) ta tìm được a , và sau đó tính được :  ab mod p  ( b )a mod p. Người ta cũng chứng minh được hai bài toán lôgarit rời rạc và Diffie-Hellman là tương đương về mặt tính toán trong một số trường hợp, ví dụ p -1 là B-mịn với B = O ((lnp)c ),c là hằng số. Tương tự như với bài toán lôgarit rời rạc, ta cũng có thể định nghĩa các bài toán Diffie-Hellman suy rộng cho các nhóm cyclic hữu hạn khác. Bài toán tổng tập con (hay bài toán KNAPSACK) : Cho một tập các số nguyên dương a1 , a2 ,..., an  và một số nguyên dương s. Hãy xác định xem có hay không một tập con các aj mà tổng của chúng bằng s. Một cách tương đương, hãy xác định xem có hay không các xi 0,1 (1 i  n) sao cho  n a x  s. i 1 i i Bài toán này là một bài toán NP - đầy đủ, tức là thuộc lớp những bài toán khó mà cho đến nay chưa tìm được thuật toán giải chúng trong thời gian đa thức ! Bài toán giải mã đối với mã tuyến tính : Mã tuyến tính là một lớp mã truyền tin có tính chất tự sửa sai được sử dụng trong kỹ thuật truyền tin số hoá. Ta phát biểu bài toán giải mã đối với mã tuyến tính như sau: Cho một ma trận cấp n xm A=(aij) gồm các thành phần là 0 hoặc 1, một vectơ y =(y1,y2,...,ym) các giá trị 0 và 1, và một số nguyên dương K. Hỏi: có hay không một vectơ x =(x1,x2,...,xn) gồm các số 0 hoặc 1 và có không nhiều hơn K số 1 sao cho với mọi j (1 j  m): n  x .a i 1 i ij  y j (mod 2) ? Chú ý rằng ở đây, x là vectơ thông tin, và y là vectơ mã, phép giải mã là tìm lại x khi nhận được y, bài toán này tiếc thay lại là một bài toán khó; Berlekamp, McEliece và Tilborg năm 1978 đã chứng minh nó thuộc lớp các bài toán Np đầy đủ ! Dựa trên các bài toán số học nêu trên, nhiều hệ mã bất đối xứng đã ra đời, trong khuôn khổ luận văn này chúng ta đi sâu nghiên cứu hệ mật RSA. Hệ mật 15 RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len Adleman [18], được đưa ra công khai lần đầu tiên vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ. Hệ mật thường sử dụng cho việc cung cấp sự riêng tư và bảo đảm tính xác thực của dữ liệu số. Sơ đồ chung của hệ mã khoá công khai được cho bởi : S = (P , C , K , E , D ) trong đó P là tập ký tự bản rõ, C là tập ký tự bản mã, K là tập các khoá K , mỗi khoá K gồm có hai phần K =(K’,K''), K' là khoá công khai dành cho việc lập mật mã, còn K'' là khoá bí mật dành cho việc giải mã. Với mỗi ký tự 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 , và với ký tự mã y thuật toán giải mã D sẽ cho ta lại ký tự bản rõ x : D (K'', y) = D (K'', E (K', x)) =x. Để xây dựng một hệ mã khoá công khai RSA, ta chọn trước một số nguyên n =p.q là tích của hai số nguyên tố lớn, chọn một số e sao cho gcd(e,  (n)) =1, và tính số d sao cho e.d  1(mod (n)). Mỗi cặp K =(K’,K''), với K' =(n,e) và K'' = d sẽ là một cặp khoá của một hệ mật mã RSA cụ thể cho một người tham gia. Như vậy, sơ đồ chung của hệ mật mã RSA được định nghĩa bởi danh sách (1), trong đó: P = C = Zn , trong đó n là một số nguyên Blum, tức là tích của hai số nguyên tố; K = {K =(K’,K''): K' =(n,e) và K'' = d, gcd(e,  (n)) =1, e.d  1(mod (n))}; E và D được xác định bởi: E (K', x) = xe modn, với mọi x P , D (K'', y) = yd modn, với mọi y C . Để chứng tỏ định nghĩa trên là hợp thức, ta phải chứng minh rằng với mọi cặp khoá K =(K' ,K'' ), và mọi x P , ta đều có D (K'', E (K', x)) = x . Thực vậy, do e.d  1(mod (n)) ta có thể viết e.d = t . (n) +1. Nếu x nguyên tố với n , thì dùng định lý Euler (xem 2.1.3) ta có 16 D (K'', E (K', x)) = xed  xt ( n)1  xt ( n) .x (mod n)  x. Nếu x không nguyên tố với n , thì do n =p.q , hoặc x chia hết cho p và nguyên tố với q, hoặc x chia hết cho q và nguyên tố với p, và  (n) =(p -1).(q -1),trong cả hai trường hợp ta đều có xt ( n ) 1  x (mod p), xt ( n ) 1  x (mod q); từ đó suy ra xt ( n) 1  x (mod n), tức D (K'', E (K', x)) =x. Tính bảo mật của RSA có độ khó tương đương với bài toán phân tích số nguyên (Blum) thành thừa số nguyên tố. Do đó, giữ tuyệt mật khoá bí mật d, hay giữ tuyệt mật các thừa số p,q , là có ý nghĩa rất quyết định đến việc bảo vệ tính an toàn của hệ mật mã RSA. 1.4. Vấn đề thám mã. Từ khi ra đời các kỹ thuật bảo mật thông tin thì đồng thời nó cũng ra đời các kỹ thuật thám mã, tức là các kỹ thuật với chúng cho phép người ta đọc được nội dung thông tin đã mật mã hóa mà không cần cho trước khóa mã. Rõ ràng việc thám mã khó khăn hơn nhiều lần việc giải mã vì người thám mã chỉ có trong tay bản mã và không có bất cứ một thông tin nào khác. Đúng như Edgar Poe – nhà nghiên cứu lâu đời về mã thám người Pháp đã tầng nói: “Khó ai có thể tin rằng: Trí tuệ con người lại có thể sinh ra một bí ẩn (mật mã - người dịch) mà cũng chính trí tuệ con người lại không khám phá được bí ẩn đó sau mỗi lao động chuyên cần thích đáng” (1968). Dù khó khăn là vậy, như chủ tịch Hồ Chí Minh của chúng ta đã dạy: “Biết địch, biết mình trăm trận đánh, trăm trận thắng”. Biết mình đã khó nhưng biết địch càng khó khăn gấp bội. Tình báo điện tử nói chung, mã thám nói riêng là một biện pháp nghiệp vụ để biết địch. Chính vì vậy song song với sự phát triển của kỹ thuật mật mã là kỹ thuật thám mã. Tất cả các nước tiên tiến đều có các cơ quan tình báo điện tử (Bao gồm thu tin và thám mã). Ở Mỹ, cơ quan an ninh quốc gia NSA (The nationnal Security Agency) được thành lập ngày 04/11/1952 theo chỉ thị của tổng thống Truman. Theo con số mới nhất (năm 2001) thì hàng năm ngân sách chi cho NSA xấp xỉ 15 tỷ USA. Ở Nga, trước đây là KGB sau đó đổi thành Fapxi, trong đó cục 16 trực thuộc tổng thống làm nhiệm vụ thu tin thám các loại điện mật trên thế 17 giới mà họ quan tâm. Các nước Trung Quốc, Đức, Anh, Pháp v.v..đều có cơ quan thám mã, có điều kết quả thám mã của họ được giữ bí mật tuyệt đối, do đó mà những thông tin về kỹ thuật mã thám cụ thể không được đăng trên bất cứ tạp chí nào. Ở Việt Nam, công tác tình báo điện tử ra đời từ 1954 và đã có nhiều kết quả cực kỳ quan trọng, góp phần làm nên chiến thắng lẫy lầng miền Nam và bảo vệ miền Bắc Xã hội chủ nghĩa thống nhất đất nước. Nếu nói mật mã là một khoa học thì thám mã là một khoa học và nghệ thuật. Nó đòi hỏi người mã thám không những cần công cụ tính toán vượt trội mà điều căn bản ở họ cần có lòng say mê nghề nghiệp và phải học tập suốt đời. Như vậy, công việc thám mã không phải do các Hackers thực hiện mà do một tổ chức Nhà nước đảm nhiệm; Ở đó phải có sự đầu tự thích đáng về người và kinh phí, đồng thời với sự hợp tác đăc lực của nhiều cơ quan nghiên cứu khoa học và các trường đại học lớn thì mới có hy vọng thành công. Ngày nay, mật mã và mã thám là một bộ môn rất quan trọng của An toàn thông tin. Xét trong phạm vi của một quốc gia thì hai lĩnh vực mật mã và mã thám bổ sung cho nhau cùng nhau phát triển, mặc dù chúng hoàn toàn độc lập đối với nhau. Chính vì vậy việc nghiên cứu thám mở một hệ mật nào đó có ý nghĩa quan trong ở chỗ là không những tìm ra được những thông tin mật mà còn bổ sung nhằm hoàn thiện hơn cho các hệ mật mà cơ quan chức năng về mật mã đang nghiên cứu ứng dụng. Sở dĩ đề tài “Nghiên cứu thám mã hệ mật RSA mà không phải phân tích nhân tử nguyên tố của module n RSA” được chọn làm mục tiêu nghiên cứu là vì đây là một hệ mật mã khóa công cộng được sử dụng rộng rãi nhất (như trong PKI, trong một số hệ điều hành, trong các thiết bị tự động ATM v.v..). Tuy nhiên việc nghiên cứu tấn công hệ mật RSA là một vấn đề rất lớn mà nhiều nhà khoa học trên thế giới đã tập trung tìm hiểu và đã cho nhiều kết quả quan trọng. Ở chương II chúng ta sẽ tìm hiểu những kết quả chính đạt được qua hơn 20 năm về tấn công RSA trên thế giới. Quá trình nghiên cứu, chúng ta sử dụng Alice và Bob để biểu thị cho hai phía muốn truyền thông lẫn nhau. Chúng ta coi Marvin là kẻ gian muốn tấn công nghe lén hay lấy trộm thông tin giữa Alice và Bob. Ta mô tả một phiên bản được đơn giản hóa của hệ mật RSA: Giả sử N=pq là tích của hai số nguyên tố lớn cùng kích 18 thước (mỗi số n/2 bít). Số N với kích thức 1024 bit, nghĩa là 309 số thập phân. Mỗi một nhân tử là 512 bit. Giả sử e, d là hai số nguyên thỏa mãn ed = 1 mod  (N) với điều kiện  (N) = (p − 1)(q − 1) là cấp của nhóm nhân trên Z*N. Chúng ta gọi N là modul RSA, e là số mũ mã hóa và d là số mũ giải mã. Cặp (N,e) là khóa công khai. Cặp (N,d) được gọi là khóa bí mật hay còn gọi là khóa riêng và chỉ có người nhận mới được biết. Khóa bí mật dùng để giải mã bản mã. Một thông điệp (message) là một số nguyên M  Z*N . Để mã hóa M, người ta tính C=Me mod N. Để giải mã bản mã, cần tính Cd mod N. Tức là: Cd = Med = M (mod N) (1) Ở đây phương trình (1) được chỉ ra bởi định lý Euler. Người ta xác định (hay định nghĩa) hàm RSA là một ánh xạ f: x  xe mod N. Nếu d cho trước, hàm đó có thể dễ dàng nghịch đảo được bằng cách dùng phương trình trên. Chúng ta coi d như là một cửa sập (trapdoor) để nghịch đảo hàm f. Bản chất của việc tấn công là nghiên cứu độ khó của hàm ngược (nghịch đảo) RSA khi không cho trước của sập d. Nói chính xác hơn, cho trước bộ 3 (N,e,C), chúng ta muốn biết được độ khó của việc tìm căn bậc e của C theo mod N (N = p.q) như thế nào khi chưa biết nhân tử của N. Vì ZN* là một tập hợp hữu hạn nên người ta có thể liệt kê (đếm) được tất cả các phần tử của Z*N cho đến khi tìm được đúng số nguyên (bức thông điệp) M cần tìm. Rất tiếc là thời gian thực hiện của thuật toán để tìm được đúng số M có cấp N, nghĩa là kích cỡ đầu vào có cấp số mũ thì thời gian chạy có cấp log2N. Chúng ta quan tâm đến thuật toán có thời gian bé hơn, tính bậc của n c điều kiện n=log2N và c là một hằng số nhỏ (bé hơn 5), thực tế thuật toán tốt hay không phụ thuộc vào kích thước đầu vào. Trong luận văn này chúng ta quan tâm đến thuật toán được coi là có hiệu quả. Chúng ta không tập trung chủ yếu vào nghiên cứu hàm ngược của RSA để tấn công vào RSA. Việc khó khăn của tính hàm ngược RSA chính là từ đầu vào ngẫu nhiên, được cho bởi (N,e,C), một kẻ tấn công khó có thể tìm ra bản rõ M. Nếu cho trước (N,e,C), rất khó để tìm ra thông tin về M. Điều này được biết trong lý thuyết an ninh an toàn. Chúng ta chỉ ra rằng RSA được mô tả ở trên là không an toàn: nếu cho (N,e,C), chúng ta có thể dẽ dàng suy diễn ra một vài thông tin của bản rõ M (ví dụ, ký tự Jacobi của M trên N được dễ dàng suy ra từ C). RSA có thể được an toàn ngữ nghĩa bằng việc thêm các bít ngẫu nhiên vào quá trình xử lý mã 19 hóa. Hàm RSA x  xe mod N là một ví dụ về hàm của sập một chiều (trapdoor one-way function). Nó có thể được tính toán dẽ dàng, nhưng như chúng ta đã biết không thể tính ngược hiệu quả nếu không có (cửa sập) d ngoại trừ một vài trường hợp đặc biệt. Chƣơng 2 - TỔNG KẾT NHỮNG KẾT QUẢ TẤN CÔNG VÀO HỆ MẬT RSA TRONG NHỮNG NĂM QUA 2.1. Một số giả thiết ngầm định. 1) N – RSA modulus 2) e – số mũ mã hóa (encryption exponent) 3) d – số mũ giải mã (decryption exponent) 4) M – Thông điệp số nguyên (message integer), M  Z*N 5) Hàm mã hóa RSA là một hàm: f(x) = xemod N = y và hàm giải mã là: g(x) = yd mod N = x. Hàm f và g có quan hệ với nhau: gf(x) = x  x  Z*N Hàm g(.) được gọi là hàm nghịch đảo của hàm f(.) trong hệ mật RSA. Nếu biết trước d thì việc tìm x rất dẽ dàng khi biết y = f(x). Nhưng nếu d không biết trước thì việc tìm hàm x khi cho trước y là một bài toán NP-Khó. Do đó số mũ d được gọi là một “cửa sập” (trapdoor). 6) Chúng ta nghiên cứu độ khó của hàm ngược (nghịch đảo) RSA khi không cho trước của sập d và nghiên cứu phương pháp tấn công RSA trong trường hợp này. 7) Về mặt lý thuyết, nếu cho trước (N,e,C), rất khó để tìm ra thông tin về M. 8) Tấn công vét cạn (brute-force attack) bằng cách phân tích các modulus, thời gian chạy với số nguyên n-bít là: exp((c + o(1))n1/3log2/3n) trong đó c < 2 .