Đề tài Các phương pháp tấn công rsa

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ------------------ Bùi Tuấn Anh CÁC PHƯƠNG PHÁP TẤN CÔNG RSA KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành : Công Nghệ Thông Tin HÀ NỘI – 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ------------------ Bùi Tuấn Anh CÁC PHƯƠNG PHÁP TẤN CÔNG RSA KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành : Công Nghệ Thông Tin Cán bộ hướng dẫn: TS. Hồ Văn Canh HÀ NỘI – 2009 LỜI CÁM ƠN Để thực hiện hoàn thành luận văn “ Các phương pháp tấn công RSA” em đã nhận được sự hướng dẫn và giúp đỡ nhiệt tình của nhiều tập thể và cá nhân Trước hết, em xin bày tỏ lòng biết ơn chân thành đến ban lãnh đạo cùng quý thầy cô trong khoa Công nghệ thông tin - Trường Đại học Công nghệ, Đại học quốc gia Hà Nội đã tận tình dạy dỗ, truyền đạt kiến thức, kinh nghiệm quý báu và tạo điều kiện thuận lợi cho em trong suốt thời gian học tập và thực hiện đề tài. Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dẫn TS. Hồ Văn Canh, người đã tận tình hướng dẫn, giúp đỡ em trong suốt quá trình thực hiện đề tài. Xin trân trọng gửi đến gia đình, bạn bè và người thân những tình cảm tốt đẹp nhất đã giúp đỡ động viên em trong suốt quá trình học tập cũng như thực hiện và hoàn thành luận văn. Hà Nội, ngày 15/05/2009 Sinh viên Bùi Tuấn Anh TÓM TẮT NỘI DUNG 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. Hệ mật sử dụng trong lĩnh vực đả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ử và đặc biệt nó là hạt nhân của hệ thống thanh toán điện tử. 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ù đã 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á huỷ. Đ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 tập trung vào việc phân tích nhân tử số n(modul của RSA). Luận văn của em sẽ trình bày các phương pháp tấn công RSA trong vòng 20 năm trở lại đây và lựa chọn môt phương pháp tấn công phổ biến để demo. Mục lục MỞ ĐẦU ................................................................................................................. 1 Chương 1. CÁC KHÁI NIỆM CƠ BẢN ............................................................. 2 1.1 Một số khái niệm toán học ........................................................................ 2 1.1.1 Số nguyên tố và nguyên tố cùng nhau................................................. 2 1.1.2 Đồng dư thức ...................................................................................... 2 1.1.3 Không gian Zn và Zn*........................................................................... 3 1.1.4 Phần tử nghịch đảo ............................................................................. 3 1.1.5 Khái niệm nhóm, nhóm con, nhóm Cyclic .......................................... 4 1.1.6 Hàm Ф Euler....................................................................................... 4 1.1.7 Các phép toán cơ bản trong không gian modulo................................ 5 1.1.8 Độ phức tạp tính toán ......................................................................... 5 1.1.9 Hàm một phía và hàm một phía có cửa sập........................................ 6 1.2 Vấn đề mã hóa............................................................................................ 7 1.2.1 Giới thiệu về mã hóa........................................................................... 7 1.2.2 Hệ mã hóa ........................................................................................... 7 1.2.3 Những tính năng của hệ mã hóa ......................................................... 8 Chương 2. TỔNG QUAN VỀ MÃ HOÁ CÔNG KHAI MÃ THÁM ................ 9 2.1 Mã hoá khoá công khai ............................................................................. 9 2.1.1 Đặc điểm của Hệ mã khoá công khai ................................................. 9 2.1.2 Nơi sử dụng Hệ mã hóa khoá công khai.......................................... 10 2.2 Các bài toán liên quan đến hệ mã hoá khoá công khai...................... 10 2.2.1 Bài toán phân tích số nguyên thành thừa số nguyên tố ................... 11 2.2.2 Bài toán RSA (Rivest-Shamir-Adleman) .......................................... 11 2.2.3 Bài toán thặng dư bậc hai................................................................ 11 2.2.4 Bài toán tìm căn bậc hai mod n ....................................................... 12 2.2.5 Bài toán lôgarit rời rạc.................................................................... 13 2.2.6 Bài toán lôgarit rời rạc suy rộng ..................................................... 13 2.2.7 Bài toán Diffie-Hellman................................................................... 13 2.2.8 Bài toán giải mã đối với mã tuyến tính............................................ 14 2.3 Vấn đề thám mã ....................................................................................... 16 Chương 3. 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 3.1 Một số giả thiết ngầm định ..................................................................... 19 3.2 Phân tích các số nguyên lớn................................................................... 19 3.3 Các tấn công cơ bản ............................................................................... 20 3.3.1 Modul chung ..................................................................................... 20 3.3.2 Mù (Blinding)................................................................................... 21 3.4 Số mũ riêng bé (Low Private Exponnent) ............................................ 21 3.4.1 Độ lớn e............................................................................................. 22 3.4.2 Sử dụng CRT .................................................................................... 22 3.5 Số mũ công khai bé (Low public Exponent) ........................................ 23 3.5.1 Hastad's Broadcast Attack. .............................................................. 23 3.5.2 Franklin-Reiter Related Message Attack. ........................................ 24 3.6 Thành phần công khai bé....................................................................... 24 3.6.1 Coppersmith's Short Pad Attack. ..................................................... 25 3.6.2 Tấn công bằng khóa riêng. .............................................................. 25 3.7 Cài đặt các tấn công. .............................................................................. 26 3.7.1 Tấn công dựa trên thời gian. ............................................................ 27 3.7.2 Tấn công dựa trên các lỗi ngẫu nhiên. ............................................ 28 3.8 Một số tấn công bằng nhân tử hóa số N với số N lớn .......................... 29 3.8.1 Tìm nhân tử lớn nhất thứ nhất N≤ ............................................... 29 3.8..2 Phân tích thứ hai............................................................................. 30 3.8.3 Phân tích thứ ba............................................................................... 31 3.8.4 Thuật toán Pollard (p-1) ................................................................... 32 3.9 Kết luận ................................................................................................... 33 Chương 4. THƯ VIỆN TÍNH TOÁN SỐ LỚN ................................................. 34 4.1 Biểu diễn số lớn. ....................................................................................... 34 4.2 Các phép toán trong số lớn ..................................................................... 35 4.2.1 So sánh hai số ................................................................................... 35 4.2.2 Cộng hai số lớn dương...................................................................... 36 4.2.3 Trừ hai số lớn dương ........................................................................ 36 4.2.4 Phép nhân hai số lớn. ....................................................................... 37 4.2.5 Phép chia hai số lớn dương. ............................................................. 38 4.2.6 Lũy thừa ............................................................................................ 40 4.2.7 Ước chung lớn nhất........................................................................... 41 4.2.8 Phép nhân theo module p.................................................................. 42 4.2.9 Tìm phần từ nghịch đảo theo module p ............................................ 42 4.2.10 Phép cộng có dấu............................................................................ 43 4.2.11 Phép trừ có dấu............................................................................... 44 4.3.12 Phép nhân có dấu............................................................................ 44 Chương 5. PHƯƠNG PHÁP TẤN CÔNG BẰNG ............................................ 45 NHÂN TỬ HOÁ SỐ N SỬ DỤNG ĐỊNH LÝ FERMAT ................................. 45 5.1 Bổ đề 1....................................................................................................... 45 5.2 Định lý Fermat........................................................................................... 45 KẾT LUẬN ........................................................................................................... 48 1 MỞ ĐẦU Hệ mật mã khoá công khai RSA được sử dụng phổ biến trong lĩnh vực đả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 và ứng dụng rộng rãi trong thương mại điện tử, được sử dụng trong việc tạo khoá 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ử. 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. Chính vì lý do được sử dụng rộng rãi trong thương mại điện tử cũng như có độ an toàn cao mà đã có rất nhiều sự nhòm ngó cũng như các cuộc tấn công nhằm phá vỡ sự an toàn của hệ mật RSA. 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ù 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á huỷ. Đa phần họ mới chỉ ra được những mối nguy hiểm tiềm ẩn của RSA. Để 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 các khái niệm cơ bản liên quan đến toán học, mật mã và thám mã , trình bày tổng quan về hệ mã hoá khoá công khai, các bài toán liên quan đến hệ mã hoá khoá công khai Trên cơ sở hiểu các khái niệm cơ bản, các cơ sở toán học, để 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 tấn công vào hệ mật RSA và kết quả thu được 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 vào 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ử hoá 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 mudul 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ố. 2 Chương 1 - CÁC KHÁI NIỆM CƠ BẢN 1.1 Một số khái niệm toán học 1.1.1 Số nguyên tố và nguyên tố cùng nhau Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, 17, … Hệ mật mã thường sử dụng các số nguyên tố ít nhất là lớn hơn 10150. Hai số m và n được gọi là nguyên tố cùng nhau, nếu ước số chung lớn nhất của chúng bằng Ký hiệu: gcd (m, n) = 1. Ví dụ: 9 và 14 là hai số nguyên tố cùng nhau. 1.1.2 Đồng dư thức Cho a và b là các số nguyên n là số nguyên dương. Khi đó a được gọi là đồng dư với b theo modulo n, ký hiệu là a ≡ b (mod n), nếu a, b chia cho n có cùng số dư. n được gọi là modulo của đồng dư. Kí hiệu: a ≡ b (mod n) Ví dụ: 5 ≡ 7 mod 2 vì: 5 mod 2 = 1 và 7 mod 2 = 1 Tính chất của đồng dư: Cho a, a1, b, b1, c ∈ Z. Ta có các tính chất sau: - a ≡ b mod n nếu và chỉ nếu a và b có cùng số dư khi chia cho n - Tính phản xạ: a ≡ a mod n - Tính đối xứng: Nếu a ≡ b mod n thì b ≡ a mod n - Tính giao hoán: Nếu a ≡ b mod n và b ≡ c mod n thì a ≡ c mod n - Nếu a ≡ a1 mod n, b ≡ b1 mod n thì a + b ≡ (a1+b1) mod n và ab ≡ a1 b1 mod n Lớp tương đương: Lớp tương đương của số nguyên a là tập hợp các số nguyên đồng dư với a theo modulo n. 3 Cho n cố định đồng dư với n trong không gian Z vào các lớp tương đương. Nếu a = qn + r, trong đó 0 ≤ r ≤ n thì a ≡ r mod n. Vì vậy mỗi số nguyên a là đồng dư theo modulo n với duy nhất một số nguyên trong khoảng từ 0 đến n-1 và được gọi là thặng dư nhỏ nhất của a theo modulo n. Cũng vì vậy, a và r cùng thuộc một lớp tương đương. Do đó r có thể đơn giản được sử dụng để thể hiện lớp tương đương. 1.1.3 Không gian Zn và Zn* Không gian Zn (các số nguyên theo modulo n) Không gian các số nguyên theo modulo n: Zn là tập hợp các số nguyên không âm nhỏ hơn n. Tức là: Zn = {0, 1, 2, … n-1}. Tất cả các phép toán trong Zn đều được thực hiện theo modulo n. Ví dụ: Z11 = {0, 1, 2, 3, …, 10} Trong Z11: 6 + 7 = 2, bởi vì 6 + 7 = 13 ≡ 2 (mod 11). Không gian Zn* Là tập hợp các số nguyên p ∈ Zn, nguyên tố cùng n. Tức là: Zn* = { p ∈ Zn | gcd (n, p) = 1}, Ф(n) là số phần tử của Zn* Nếu n là một số nguyên tố thì: Zn* = { p ∈ Zn | 1 ≤ p ≤ n – 1} Ví dụ: Z2 = {0, 1} thì Z2* = {1} vì gcd (1, 2) = 1. 1.1.4 Phần tử nghịch đảo Định nghĩa: Cho a ∈ Zn. Nghịch đảo của a theo modulo n là số nguyên x ∈ Zn sao cho ax ≡ 1(mod n). Nếu x tồn tại thì đó là giá trị duy nhất, và a được gọi là khả nghịch. Nghịch đảo của a ký hiệu là a-1. Tính chất: • Cho a, b ∈ Zn. Phép chia a cho b theo modulo n là tích của a và b theo modulo n, và chỉ được xác định khi b có nghịch đảo theo modulo n. • Cho a ∈ Zn, a là khả nghịch khi và chỉ khi gcd (a, n) = 1. 4 • Giả sử d = gcd (a, n). Phương trình đồng dư ax = b mod n có nghiệm x nếu và chỉ nếu d chia hết cho b, trong trường hợp các nghiệm d nằm trong khoảng 0 đến n – 1 thì các nghiệm đồng dư theo modulo n/d. Ví dụ: 4-1 = 7 (mod 9) vì 4.7 ≡ 1 (mod 9) 1.1.5 Khái niệm nhóm, nhóm con, nhóm Cyclic Nhóm là bộ các phần tử (G, *) thỏa mãn các tính chất sau: • Tính chất kết hợp: ( x * y ) * z = x * s ( y * z ) • Tính chất tồn tại phần tử trung gian e ∈ G: e * x = x * e = x , ∀ x ∈ G • Tính chất tồn tại phần tử nghịch đảo x’ ∈ G: x’ * x = x * x’ = e Nhóm con là bộ các phần tử (S, *) là nhóm thỏa mãn các tính chất sau: • S ∈ G, phần tử trung gian e ∈ S • x, y ∈ S Î x * y ∈ S Nhóm Cyclic: Là nhóm mà mọi phần tử x của nó được sinh ra từ một phần tử đặc biệt g ∈ G. Phần tử này được gọi là phần tử nguyên thủy, tức là: Với ∀ x ∈ G: ∃ n ∈ N mà gn = x. Ví dụ: (Z+, *) là một nhóm cyclic có phần tử sinh là 1 1.1.6 Hàm Ф Euler Định nghĩa: Cho n ≥ 1. Ф (n) được định nghĩa là các số nguyên trong khoảng từ [1, n] nguyên tố cùng nhau với n. Hàm Ф được gọi là hàm phi Euler. Tính chất: - Nếu p là số nguyên tố thì Ф (n) = p - 1. - Hàm phi Euler là hàm có tính nhân: - Nếu (m, n) = 1 thì Ф (m*n) = Ф (m) Ф (n). - Nếu n = p1e1p2e2…pkek là thừa số nguyên tố của n thì : Ф(n) = n ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − 1 11 p ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − 2 11 p … ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − np 11 5 1.1.7 Các phép toán cơ bản trong không gian modulo Cho n là số nguyên dương. Như trước, các phần tử trong Zn được thể hiện bởi các số nguyên {0, 1, 2,…, n - 1}. Nhận xét rằng: nếu a, b ∈ Zn thì: (a + b) mod n = ⎩⎨ ⎧ ≥+−+ <++ nbaifnba nbaifba Vì vậy, phép cộng modulo (và phép trừ modulo) có thể được thực hiện mà không cần thực hiện các phép chia dài. Phép nhân modulo của a và b được thực hiện bằng phép nhân thông thường a với b như các số nguyên bình thường, sau đó lấy phần dư của kết quả sau khi chia cho n. Phép tính nghịch đảo trong Zn có thể được thực hiện nhờ sử dụng thuật toán Euclidean mở rộng như mô tả sau: Nếu b=0 thì đặt d: =a; x: =1; y: =0; return (d; x; y) ; Đặt x2 :=1; x1 :=0 ; y2 : =0 ; y1 : =1 ; Khi b>0 thực hiện: q: = [a/b]; r = a-qb; x: = x2-px1; y: = y2 - py1 ; a : =b; r: =b; x1:=x2; x1:=x; y2:=y1; y1:=y ; d:=a ; x:=x2 ; y:=y2 ; return(d, x, y) ; 1.1.8 Độ phức tạp tính toán Lý thuyết thuật toán và các hàm tính được ra đời từ những năm 30 của thế kỉ 20 đã đặt nền móng cho việc nghiên cứu các vấn đề “tính được”, “giải được” trong toán học. Tuy nhiên từ cái “tính được” đến việc tính toán thực tế là một khoảng cách rất lớn. Có rất nhiều vấn đề được chứng minh là có thể “tính được” nhưng không tính được trong thực tế cho dù có sự hỗ trợ của máy tính. Vào những năm 1960, lý thuyết độ phức tạp tính toán được hình thành và phát triển một cách nhanh chóng, cung cấp nhiều hiểu biết sâu sắc về bản chất phức tạp của các thuật toán và các bài toán, từ những bài toán thuần túy lý thuyết đến những bài toán thường gặp trong thực tế. Độ phức tạp tính toán (về không gian hay thời gian) của một tiến trình tính toán là số ô nhớ được dùng hay số các phép toán sơ cấp được thực hiện trong tiến trình tính toán 6 đó. Dữ liệu đầu vào đối với một thuật toán thường được biểu diễn qua các từ trong một bảng ký tự nào đó. Độ dài của một từ là số ký tự trong từ đó. Cho một thuật toán A trên bảng ký tự Z (tức là có các đầu vào là các từ trong Z). Độ phức tạp tính toán của thuật toán A được hiểu như một hàm số fa(n) sao cho với mỗi số n thì fa(n) là số ô nhớ, hay số phép toán sơ cấp tối đa mà A cần để thực hiện tiến trình tính toán của mình trên các dữ liệu vào có độ dài nhỏ hơn hoặc bằng n. Ta nói: thuật toán A có độ phức tạp thời gian đa thức, nếu có một đa thức P(n) sao cho với mọi n đủ lớn ta có: fa(n) ≤ p(n), trong đó fa(n) là độ phức tạp tính toán theo thời gian của A. Bài toán P được gọi là “giải được” nếu tồn tại thuật toán để giải nó, tức là thuật toán làm việc có kết thúc trên mọi dữ liệu đầu vào của bài toán. Bài toán P được gọi là “giải được trong thời gian đa thức” nếu có thuật toán giải nó với độ phức tạp thời gian đa thức. 1.1.9 Hàm một phía và hàm một phía có cửa sập Hàm một phía: Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhưng rất khó để tính ngược lại. Ví như : Biết giả thiết x thì có thể dễ dàng tính ra f(x), nhưng nếu biết f(x) thì rất khó tính ra được x. Trong trường hợp này “khó” có nghĩa là để tính ra được kết quả thì phải mất rất nhiều thời gian để tính toán. Ví dụ: Tính y = f(x) = αx mod p là dễ nhưng tính ngược lại x = logα y là bài toán “khó” (bài toán logarit rời rạc) Hàm một phía có cửa sập: F(x) được gọi là hàm một phía có cửa sập nếu tính xuôi y = f (x) thì dễ nhưng tính ngược x = f - 1(y) thì khó tuy nhiên nếu có “cửa sập” thì vấn đề tính ngược trở nên dễ dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính ngược. Ví dụ: 7 y = f (x) = xb mod n tính xuôi thì dễ nhưng tính ngược x = ya mod n thì khó vì phải biết a với a * b ≡ 1 (mod (Ф (n)) trong đó Ф(n) = (p-1)(q-1). Nhưng nếu biết cửa sập p, q thì việc tính n = p * q và tính a trở