Luận văn: Thuật toán tấn công RSA không cần phân tích nhân tử

Chuyên khảo kỹ thuật phân tích Luận vă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ử, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Tác giả: Nguyễn Anh Tuan
• Người hướng dẫn: TS. Hồ Văn Canh
• Trường học: Trường Đại học Công nghệ
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Xây dựng thuật toán tấn công RSA không cần phân tích nhân tử
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2007
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1 - TỔNG QUAN VỀ MẬT MÃ VÀ MÃ THÁM
• 1.1. Mã truyền thống hay còn gọi là mã cổ điển
• 1.2. Sơ đồ các hệ mật mã apphin
• 1.3. Mã thay thế (substitution cipher)
• 1.4. Mã chuyển dịch (shift cipher)
• 1.5. Mã hoán vị
• 1.6. Mã Vigenère
• 1.7. Mã Hill
• 1.8. Mã đối xứng (symmetric-key algorithms)
• 1.9. Mã theo dòng
• 1.10. Mã chuẩn DES
• 1.11. Mã bất đối xứng
• 1.12. Bài toán phân tích số nguyên
• 1.13. Bài toán RSA
• 1.14. Bài toán thặng dư bậc hai
• 1.15. Bài căn bậc hai modn
• 1.16. Bài toán logarit rời rạc suy rộng
• 2. CHƯƠNG 2 - TỔNG KẾT MẬT RSA TRONG NHỮNG NĂM QUA
• 2.1. Một số giả thiết ngầm định
• 2.2. Phân tích các số nguyên lớn
• 2.3. Số mũ riêng bé(Low Private Exponnent
• 2.4. Số mũ công khai bé(Low public Exponent)
• 2.5. Hastad's Broadcast Attack
• 2.6. Franklin-Reiter Related Message Attack
• 2.7. Thành phần công khai bé
• 2.8. Coppersmith's Short Pad Attack
• 2.9. Tấn công bằng khóa riêng
• 2.10. Cài đặt các tấn công
• 2.11. Tấn công dựa trên thời gian
• 2.12. Tấn công dựa trên các lỗi ngẫu nhiên
• 2.13. Tấn công của Bleichenbacher trên PKCS I
• 2.14. Một số tấn công bằng nhân tứ hóa số N với s lớn
• 2.15. Tìm nhân tử lên nhất thú nhất
• 2.16. Phân tích thứ hai
• 2.17. Phân tích thứ ba
• 2.18. Thuật toán Pollard (p-1)
• 3. CHƯƠNG 3 - THƯ VIỆN TÍNH TOÁN SỐ LỚN
• 3.1. Biểu diễn số lớn
• 3.2. Các phép toán trong số lớn
• 3.3. So sánh hai số
• 3.4. Cộng hai số lớn dương
• 3.5. Trừ hai số lớn dương
• 3.6. Phép nhân hai số lớn
• 3.7. Phép chia hai số lớn dương
• 3.8. Ước chung lớn nhất
• 3.9. Phép nhân theo module p
• 3.10. Tính căn của số nguyên lắm
• 3.11. Tìm phần tử nghịch đảo theo module p
• 3.12. Phép cộng có dấu
• 3.13. Phép trừ có dấu
• 4. CHƯƠNG 4 - PHƯƠNG PHÁP TẤN CÔNG RSA KHÔNG CẦN PHÂN TÍCH NHÂN TỬ

Tóm tắt

I. Khám phá tấn công RSA Điểm yếu ngoài phân tích nhân tử

Hệ mật RSA, nền tảng của an toàn thông tin hiện đại, xây dựng sức mạnh dựa trên một giả định cốt lõi: độ khó của bài toán phân tích một số nguyên lớn thành các thừa số nguyên tố. Tuy nhiên, việc chỉ tập trung vào thách thức này đã vô tình bỏ qua nhiều vectơ tấn công tiềm tàng khác. Bài viết này sẽ đi sâu vào các phương pháp tấn công RSA không cần phân tích nhân tử, một lĩnh vực quan trọng trong mật mã học và an toàn thông tin. Các phương pháp này không cố gắng phá vỡ modul N, mà thay vào đó, chúng khai thác các điểm yếu trong quá trình lựa chọn tham số hoặc các lỗ hổng trong quá trình triển khai hệ thống. Hiểu rõ các kỹ thuật này không chỉ giúp nhận diện các mối đe dọa thực tế mà còn là chìa khóa để xây dựng các ứng dụng thuật toán RSA an toàn hơn, từ chữ ký số RSA đến các giao thức mã hóa phức tạp. Nội dung sẽ bao quát từ các cuộc tấn công kinh điển dựa trên tham số yếu đến các kỹ thuật hiện đại khai thác kênh phụ, cung cấp một cái nhìn toàn diện về các mối nguy hiểm tiềm ẩn của hệ mật mã khóa công khai phổ biến nhất thế giới.

1.1. Nền tảng bảo mật RSA và bài toán phân tích nhân tử

Bảo mật của thuật toán RSA phụ thuộc trực tiếp vào độ khó tính toán của việc phân tích số nguyên N thành hai thừa số nguyên tố p và q. N được gọi là modul, là một phần của khóa công khai. Trong khi đó, p và q được giữ bí mật và dùng để tính ra khóa bí mật d. Về mặt lý thuyết, nếu một kẻ tấn công có thể phân tích được N, họ sẽ dễ dàng tính được φ(N) = (p-1)(q-1), từ đó tìm ra khóa bí mật d từ khóa công khai e. Đây là lý do tại sao các khóa RSA hiện đại thường có độ dài 2048-bit hoặc 4096-bit, khiến việc phân tích nhân tử bằng các thuật toán hiện tại như sàng số trường tổng quát (GNFS) trở nên bất khả thi về mặt thời gian. Tuy nhiên, sự phụ thuộc vào một điểm yếu duy nhất này lại chính là khởi nguồn cho các hướng tấn công khác. Các nhà nghiên cứu nhận ra rằng, thay vì đối đầu trực tiếp với bài toán phân tích số nguyên lớn, việc tìm kiếm các 'lối tắt' thông qua các lỗi triển khai hoặc lựa chọn tham số sai lầm sẽ hiệu quả hơn nhiều.

1.2. Các lỗ hổng triển khai RSA và vai trò của thám mã

Một hệ mật mã có thể an toàn về mặt lý thuyết nhưng lại trở nên yếu ớt khi triển khai trong thực tế. Lỗ hổng triển khai RSA là những sai sót phát sinh không phải từ bản chất thuật toán, mà từ cách nó được lập trình, cấu hình và sử dụng. Những lỗ hổng này tạo ra các kênh thông tin rò rỉ mà kẻ tấn công có thể khai thác. Vai trò của thám mã trong bối cảnh này là tìm ra và khai thác chính những kẽ hở đó. Thay vì giải bài toán toán học khó, người thám mã phân tích các yếu tố như thời gian thực thi, mức tiêu thụ điện năng, thông báo lỗi của hệ thống, hoặc các điểm yếu khi các tham số khóa công khai và bí mật được chọn một cách bất cẩn. Chính vì vậy, việc nghiên cứu các phương pháp tấn công RSA không cần phân tích nhân tử có ý nghĩa thực tiễn cực kỳ quan trọng, giúp các nhà phát triển và quản trị hệ thống nhận thức được mối nguy và áp dụng các biện pháp phòng thủ thích hợp, đảm bảo an toàn cho toàn bộ hệ thống.

II. Top phương pháp tấn công RSA dựa vào các tham số yếu

Việc lựa chọn tham số trong RSA không phải là một công việc tùy ý; nó đòi hỏi sự tuân thủ nghiêm ngặt các nguyên tắc toán học để đảm bảo an ninh. Khi các tham số này được chọn một cách cẩu thả, hệ thống sẽ mở ra những cánh cửa cho các cuộc tấn công mạnh mẽ. Phần này sẽ phân tích chi tiết các phương pháp tấn công RSA không cần phân tích nhân tử phổ biến nhất, nhắm vào việc khai thác các tham số yếu. Chúng ta sẽ khám phá tấn công Wiener, một kỹ thuật kinh điển hoạt động hiệu quả khi khóa bí mật d nhỏ. Tiếp theo là tấn công Hastad, cho thấy sự nguy hiểm của việc sử dụng số mũ công khai e nhỏ và gửi cùng một thông điệp đến nhiều người nhận. Cuối cùng, tấn công mô-đun chung sẽ minh họa tại sao việc chia sẻ cùng một modul N giữa nhiều người dùng lại là một sai lầm chết người về mặt bảo mật. Hiểu rõ các kỹ thuật này là bước đầu tiên để tránh những lỗi sơ đẳng khi thiết lập một hệ thống mã hóa RSA.

2.1. Phân tích tấn công Wiener với khóa bí mật d nhỏ

Tấn công Wiener là một phương pháp tấn công hiệu quả khi khóa giải mã (khóa bí mật) d được chọn với giá trị quá nhỏ, cụ thể là khi d < (1/3) * N^(1/4). Mục đích của việc chọn d nhỏ là để tăng tốc độ giải mã, nhưng điều này lại tạo ra một lỗ hổng nghiêm trọng. Cuộc tấn công này dựa trên mối quan hệ ed ≡ 1 (mod φ(N)), có thể viết lại thành ed - kφ(N) = 1 với k là một số nguyên nào đó. Từ đó suy ra |e/φ(N) - k/d| là một giá trị rất nhỏ. Mặc dù kẻ tấn công không biết φ(N), họ có thể dùng N để xấp xỉ vì φ(N) rất gần N. Do đó, k/d là một xấp xỉ rất tốt của e/N. Kỹ thuật phân số liên tục (continued fractions) được sử dụng để tìm tất cả các phân số tối giản k/d xấp xỉ e/N. Bằng cách thử từng cặp (k, d) tìm được, kẻ tấn công có thể nhanh chóng khôi phục khóa bí mật d. Luận văn của Nguyễn Anh Tuấn trích dẫn định lý của M. Wiener, nhấn mạnh rằng kẻ tấn công có thể tìm d một cách hiệu quả chỉ với thông tin công khai (N, e).

2.2. Kỹ thuật tấn công Hastad khi số mũ công khai e nhỏ

Tấn công Hastad, hay còn gọi là Hastad's Broadcast Attack, khai thác trường hợp khi cùng một thông điệp M được mã hóa và gửi đến nhiều người nhận khác nhau (ví dụ k người), mỗi người sử dụng một modul N_i khác nhau nhưng lại dùng chung một số mũ công khai e nhỏ (ví dụ e=3). Kẻ tấn công sẽ thu thập k bản mã C_i, trong đó C_i ≡ M^e (mod N_i). Với hệ phương trình đồng dư này, kẻ tấn công có thể sử dụng Định lý phần dư Trung Hoa (Chinese Remainder Theorem - CRT) để tìm ra một giá trị X duy nhất sao cho X ≡ M^e (mod N_1*N_2*...*N_k). Nếu k ≥ e, thì M^e sẽ nhỏ hơn N_1*N_2*...*N_k. Điều này có nghĩa là X = M^e. Khi đó, kẻ tấn công chỉ cần tính căn bậc e của X là có thể khôi phục được thông điệp gốc M mà không cần phải phân tích bất kỳ modul N_i nào. Đây là một lời cảnh báo mạnh mẽ về việc sử dụng số mũ e nhỏ một cách thiếu cân nhắc.

2.3. Hiểm họa từ tấn công mô đun chung Common Modulus Attack

Tấn công mô-đun chung (Common Modulus Attack) xảy ra khi một modul N được sử dụng chung cho nhiều người dùng, mỗi người có một cặp khóa công khai/bí mật (e_i, d_i) riêng. Giả sử người dùng 1 có khóa công khai (N, e_1) và người dùng 2 có khóa (N, e_2), với gcd(e_1, e_2) = 1. Nếu một thông điệp M được mã hóa bằng cả hai khóa công khai này và gửi đi, kẻ tấn công sẽ chặn được hai bản mã: C_1 ≡ M^(e_1) (mod N) và C_2 ≡ M^(e_2) (mod N). Vì gcd(e_1, e_2) = 1, kẻ tấn công có thể sử dụng thuật toán Euclid mở rộng để tìm hai số nguyên r và s sao cho r*e_1 + s*e_2 = 1. Từ đó, họ có thể tính toán (C_1^r * C_2^s) mod N ≡ (M^(e_1))^r * (M^(e_2))^s mod N ≡ M^(r*e_1 + s*e_2) mod N ≡ M^1 mod N. Kết quả chính là thông điệp gốc M. Simmons đã chỉ ra rằng, modul RSA không bao giờ được dùng chung, vì bất kỳ người dùng nào trong hệ thống cũng có thể phân tích N từ khóa riêng của mình và từ đó phá vỡ khóa của tất cả những người khác.

III. Hướng dẫn tấn công RSA qua kênh phụ và lỗi hệ thống

Các cuộc tấn công tinh vi nhất không nhắm vào thuật toán mà vào quá trình triển khai vật lý của nó. Đây là lĩnh vực của các cuộc tấn công kênh phụ (side-channel attack), nơi thông tin về khóa bí mật bị rò rỉ qua các kênh không chủ định như thời gian xử lý, năng lượng tiêu thụ, hoặc thậm chí là các thông báo lỗi. Phần này sẽ phân tích các phương pháp tấn công này một cách chi tiết. Chúng ta sẽ bắt đầu với tấn công thời gian (timing attack), một kỹ thuật do Kocher phát hiện, cho thấy sự chênh lệch nhỏ trong thời gian giải mã có thể tiết lộ từng bit của khóa bí mật. Tiếp theo, bài viết sẽ trình bày về cách khai thác các lỗi ngẫu nhiên trong quá trình tính toán, đặc biệt khi hệ thống sử dụng Định lý Phần dư Trung Hoa để tăng tốc. Cuối cùng, cuộc tấn công của Bleichenbacher trên PKCS#1 sẽ là một ví dụ điển hình về việc một thông báo lỗi tưởng chừng vô hại lại có thể bị lợi dụng để giải mã hoàn toàn một bản tin.

3.1. Phân tích tấn công thời gian Timing Attack của Kocher

Tấn công thời gian (Timing Attack), do Paul Kocher đề xuất, là một dạng tấn công kênh phụ kinh điển. Kỹ thuật này không khai thác điểm yếu toán học của RSA mà dựa vào việc đo lường chính xác thời gian cần thiết để thực hiện một phép toán giải mã hoặc tạo chữ ký. Thuật toán tính lũy thừa theo mô-đun (ví dụ: bình phương và nhân lặp lại) thường có thời gian thực thi phụ thuộc vào các bit của số mũ bí mật d. Cụ thể, nếu một bit của d là '1', một phép nhân bổ sung sẽ được thực hiện, làm tăng một chút thời gian xử lý so với khi bit đó là '0'. Bằng cách gửi một lượng lớn các bản mã ngẫu nhiên đến thiết bị (ví dụ: smartcard) và đo thời gian phản hồi, kẻ tấn công có thể thực hiện phân tích thống kê để suy ra từng bit của khóa d. Để phòng chống, các hệ thống cần đảm bảo thời gian thực thi là hằng số (constant-time execution) hoặc sử dụng kỹ thuật làm mờ (blinding) để ngẫu nhiên hóa phép tính, khiến cho thời gian không còn tương quan với khóa bí mật.

3.2. Khai thác lỗi ngẫu nhiên với Định lý Phần dư Trung Hoa

Để tăng tốc độ giải mã và ký số, nhiều hệ thống RSA sử dụng Định lý Phần dư Trung Hoa (CRT). Thay vì tính M ≡ C^d (mod N), hệ thống sẽ tính M_p ≡ C^(d_p) (mod p) và M_q ≡ C^(d_q) (mod q), sau đó kết hợp kết quả để ra M. Boneh, DeMillo, và Lipton đã chỉ ra rằng nếu một lỗi phần cứng ngẫu nhiên (ví dụ: bit-flip) xảy ra trong quá trình tính toán, chẳng hạn làm sai kết quả của M_p nhưng M_q vẫn đúng, chữ ký tạo ra (S') sẽ bị lỗi. Chữ ký này sẽ không hợp lệ, tức S'^e ≠ M (mod N). Tuy nhiên, nó vẫn thỏa mãn S'^e ≡ M (mod q) nhưng S'^e ≠ M (mod p). Do đó, p sẽ là một ước của N và S'^e - M, trong khi q thì không. Kẻ tấn công có thể tính gcd(S'^e - M, N) để tìm ra thừa số nguyên tố p một cách dễ dàng, từ đó phá vỡ hoàn toàn hệ thống. Đây là một ví dụ về tấn công lỗi (fault injection attack).

3.3. Tấn công Bleichenbacher trên PKCS 1 Lỗi từ thông báo

Tấn công của Bleichenbacher là một dạng chosen ciphertext attack (CCA) nhắm vào chuẩn PKCS#1 phiên bản 1.5. Chuẩn này yêu cầu thông điệp trước khi mã hóa phải được đệm (padding) theo một định dạng cụ thể, bắt đầu bằng hai byte 0x00 0x02. Khi một máy chủ nhận được một bản mã, nó sẽ giải mã và kiểm tra xem phần đệm có hợp lệ không. Nếu không, nhiều hệ thống sẽ trả về một thông báo lỗi. Bleichenbacher đã chứng minh rằng thông báo lỗi này hoạt động như một 'oracle', cho phép kẻ tấn công biết được bản rõ sau khi giải mã có tuân thủ định dạng hay không. Bằng cách tạo ra hàng ngàn bản mã biến thể từ bản mã gốc và gửi đến máy chủ, dựa vào việc máy chủ có báo lỗi hay không, kẻ tấn công có thể dần dần thu hẹp khoảng giá trị của thông điệp gốc và cuối cùng khôi phục hoàn toàn nó. Lỗ hổng này cho thấy tầm quan trọng của việc không để lộ bất kỳ thông tin nào về quá trình xử lý nội bộ, kể cả qua các thông báo lỗi.

IV. Sáng kiến tấn công RSA Rút ngắn khoảng dò tìm nhân tử

Bên cạnh việc khai thác các lỗi đã biết, các nghiên cứu trong lĩnh vực thám mã luôn tìm kiếm những phương pháp mới để tấn công RSA hiệu quả hơn. Luận văn của Nguyễn Anh Tuấn đề xuất một hướng tiếp cận độc đáo, một thuật toán tấn công RSA không cần phân tích nhân tử theo cách truyền thống. Thay vì chạy các thuật toán phân tích số phức tạp, phương pháp này tập trung vào việc rút ngắn khoảng không gian tìm kiếm cho thừa số nguyên tố nhỏ hơn (p). Dựa trên các bổ đề toán học vững chắc, thuật toán này chứng minh rằng nhân tử p luôn nằm gần giá trị căn bậc hai của N hơn so với nhân tử q. Sáng kiến này không chỉ mang tính học thuật mà còn có tiềm năng ứng dụng thực tế, đặc biệt khi đối mặt với các modul N lớn mà các phương pháp phân tích nhân tử hiện tại tỏ ra chậm chạp. Phần này sẽ trình bày chi tiết cơ sở toán học và các bước thực hiện của thuật toán đề xuất, mở ra một góc nhìn mới về việc phá vỡ RSA.

4.1. Cơ sở toán học Bổ đề về khoảng cách nhân tử p q

Cơ sở của thuật toán đề xuất trong tài liệu nghiên cứu là Bổ đề 1, phát biểu rằng: Với N = p*q và p < q, thì nhân tử nhỏ hơn p sẽ gần với sqrt(N) hơn so với nhân tử lớn hơn q. Chứng minh điều này khá trực quan: nếu p = sqrt(N) - α và q = sqrt(N) + β (với α, β > 0), thì N = (sqrt(N) - α)(sqrt(N) + β) = N + (β-α)sqrt(N) - αβ. Điều này dẫn đến (β-α)sqrt(N) = αβ. Vì α, β, sqrt(N) đều dương, suy ra β - α cũng phải dương, tức là β > α. Điều này có nghĩa là khoảng cách từ q đến sqrt(N) lớn hơn khoảng cách từ p đến sqrt(N). Bổ đề này tuy đơn giản nhưng lại là một phát hiện quan trọng, vì nó cho phép giới hạn phạm vi tìm kiếm p trong một khoảng hẹp hơn nhiều bên dưới sqrt(N), thay vì phải tìm kiếm từ các số nguyên tố nhỏ nhất. Điều này giúp giảm đáng kể thời gian tính toán cho thuật toán dò tìm.

4.2. Xây dựng thuật toán dò tìm p mà không cần phân tích N

Dựa trên các cơ sở toán học đã chứng minh, thuật toán được đề xuất hoạt động bằng cách tìm kiếm số nguyên tố p trong một khoảng xác định hẹp hơn. Thay vì sử dụng các phương pháp phân tích nhân tử phức tạp như thuật toán Pollard (p-1) hay sàng bình phương, thuật toán này tập trung vào việc tìm kiếm lùi từ giá trị floor(sqrt(N)). Thuật toán sẽ kiểm tra các số lẻ giảm dần từ floor(sqrt(N)) và thử xem chúng có phải là ước của N hay không. Mặc dù đây vẫn là một dạng của phép chia thử (trial division), nhưng nhờ việc rút ngắn đáng kể khoảng tìm kiếm dựa trên các bổ đề toán học, hiệu quả của nó được cải thiện rõ rệt so với việc chia thử từ các số nguyên tố nhỏ. Phương pháp này tỏ ra hiệu quả cao hơn các thuật toán đã được công bố, đặc biệt đối với các máy tính cá nhân thông thường khi xử lý các số N có độ dài lớn, nơi mà các thuật toán phân tích nhân tử tiêu chuẩn trở nên quá chậm. Các công cụ như RsaCtfTool cũng thường tích hợp các phương pháp tương tự để tự động hóa quá trình này.

V. Bí quyết phòng chống các kỹ thuật tấn công RSA hiệu quả

Hiểu rõ các phương pháp tấn công là điều kiện tiên quyết để xây dựng một hệ thống phòng thủ vững chắc. Việc bảo vệ một hệ thống RSA không chỉ dừng lại ở việc chọn một modul N đủ lớn. Nó đòi hỏi một cách tiếp cận toàn diện, từ việc lựa chọn cẩn thận các tham số, sử dụng các tiêu chuẩn đã được kiểm chứng, đến việc gia cố quá trình triển khai để chống lại các cuộc tấn công tinh vi. Phần cuối cùng này sẽ tổng hợp các biện pháp phòng chống hiệu quả nhất đối với các kỹ thuật tấn công RSA không cần phân tích nhân tử đã được trình bày. Chúng ta sẽ thảo luận về tầm quan trọng của việc lựa chọn tham số an toàn, vai trò của các sơ đồ đệm (padding) hiện đại trong việc ngăn chặn các cuộc tấn công dựa trên tương tác, và các kỹ thuật lập trình phòng thủ để giảm thiểu rò rỉ thông tin qua các kênh phụ. Đây là những kiến thức thiết yếu cho bất kỳ ai làm việc trong lĩnh vực an toàn thông tin và mật mã học.

5.1. Lựa chọn tham số an toàn Độ dài khóa và giá trị e d

Để chống lại các cuộc tấn công dựa trên tham số yếu, việc lựa chọn tham số phải tuân thủ các khuyến nghị an toàn. Đầu tiên, modul N phải đủ lớn (khuyến nghị tối thiểu 2048-bit). Hai số nguyên tố p và q phải được chọn ngẫu nhiên, có độ dài xấp xỉ nhau (ví dụ, cùng n/2 bit) để ngăn chặn các thuật toán phân tích nhân tử hiệu quả khi một thừa số quá nhỏ. Để chống lại tấn công Wiener, khóa bí mật d không được quá nhỏ; nó phải có độ dài bit tương đương với N. Ngược lại, để chống tấn công Hastad, số mũ công khai e không nên quá nhỏ. Giá trị thường được khuyến nghị là e = 65537 (2^16 + 1), đủ lớn để chống lại các tấn công đơn giản nhưng vẫn đủ nhỏ để tính toán hiệu quả. Quan trọng nhất, không bao giờ được sử dụng chung một modul N cho nhiều người dùng để tránh common modulus attack.

5.2. Áp dụng các sơ đồ đệm Padding an toàn như OAEP

Các cuộc tấn công như của Bleichenbacher đã cho thấy sự nguy hiểm của việc mã hóa trực tiếp thông điệp (textbook RSA). Để ngăn chặn các cuộc tấn công chosen ciphertext attack (CCA), cần phải sử dụng các sơ đồ đệm (padding schemes) an toàn. Sơ đồ đệm phổ biến và an toàn nhất hiện nay là Optimal Asymmetric Encryption Padding (OAEP). OAEP thêm các yếu tố ngẫu nhiên và cấu trúc vào thông điệp trước khi mã hóa. Điều này đảm bảo rằng cùng một thông điệp khi được mã hóa nhiều lần sẽ cho ra các bản mã khác nhau, làm mất tính xác định (deterministic) của RSA. Quan trọng hơn, OAEP được chứng minh là an toàn dưới mô hình random oracle, khiến cho việc khai thác các thông báo lỗi để suy ra thông tin về bản rõ trở nên bất khả thi. Việc chuyển từ các chuẩn cũ như PKCS#1 v1.5 sang OAEP là một bước đi thiết yếu để bảo vệ hệ thống RSA khỏi các cuộc tấn công tương tác.

5.3. Các biện pháp chống tấn công kênh phụ và kiểm tra chữ ký

Để chống lại tấn công kênh phụ (side-channel attack), cần áp dụng các biện pháp ở cấp độ triển khai. Đối với tấn công thời gian, kỹ thuật RSA-blinding là một giải pháp hiệu quả. Trước khi giải mã, bản mã C được nhân với một số ngẫu nhiên r^e, tạo thành C' = (rM)^e. Hệ thống sẽ giải mã C' để được rM, sau đó nhân với nghịch đảo của r để có M. Vì r là ngẫu nhiên, thời gian giải mã không còn phụ thuộc vào khóa bí mật. Để chống lại tấn công lỗi, hệ thống phải luôn kiểm tra tính hợp lệ của chữ ký hoặc kết quả giải mã trước khi gửi đi. Ví dụ, sau khi tạo chữ ký S, hệ thống nên tính S^e mod N và so sánh với thông điệp gốc M. Nếu kết quả khớp, chữ ký mới được coi là hợp lệ. Biện pháp đơn giản này ngăn chặn hiệu quả việc rò rỉ thông tin từ một chữ ký bị lỗi.

Trích đoạn nội dung tài liệu

chương I— “Tổng quam vé một mã và thám ma”. © chung này, em trình bày chỉ 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 L để có cái nhìn tổng quan về van để 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ả đã dược công bố trong chương II của luận văn — “Tổng kết những két qua tan công vào hệ một SA trong những năm qua".

Trang chương nảy cm đã trình bày chỉ tiết các thuật toán tắn công vào hệ mật R8A như. các tin gông cơ bản — modul chung, mủ, tấn công vào số mũ công khai hoặc số mũ bi 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 RA bằng nhân tử hóa số n với số n lớn như thuật toán Pallard, 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ó độ đài hạn chế, còn modulus N có độ đài lớn thì cho đến nay chưa có phương pháp khã thị nào được công bố Qua nghiên cứu oáo thuật toán đã được công bố, em để xuất phương pháp tân công R8A mả không cần phần tích nhân tử, phương phản này tỏ ra có hiệu quả đối với hệ RRA có số n lớn Để thực hiện phương pháp này, em xin phép được trình bay thư viện các phép toán đối với số lớn trong chương II “7ñ 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. cho việc xây dựng giải pháp tấn công R5.A 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à đỏ 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 thi co thể từ đó suy ra được ngay nhân tử kia bằng cách lây số n chia cho p: qt 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 bing cách rút ngắn khoảng cách đò 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 chỉ 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ử” “ Chuong 1 - TONG QUAN VE MAT MA VA MA THAM 1. 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 dã trở nên lạc hậu do các phương thức mã hóa này quá dơn giãn và những kể tấn công có thể để 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ại động trên cơ sở bảng chữ cái (chẳng hạn các ky ur từ "A" tới "Z" trong tiếng Anh), và chúng dược thực hiện bằng tay hay một số máy móc cư khí dơ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 vi va mat ma 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 Irong loan bộ thông điệp bằng các ký Lự 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. Irong 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. Sơ đồ các hệ mật mã apphin được dịnh nghĩa như sau: §=(ể.#— { (ab) 6 Z2sxZs Ì goả(s, 26)— 1}, các ánh xạ và 2 được cho bởi: $x) = axy ! b mod26, Bly = aly - 6) mod26, với mọi x €. # la lap cae khoa, ke_#lA mdl khda cu thể nào đó trong _#ˆ 1. Ma thay thé (substitution cipher).

Sơ đỗ các hệ mật mã thay thê được định nghĩa như sau §=(Z.9), trong dé # = = Log, % 1a tap hop tat cd các phép hoán vị trén 245 các ánh xạ #và. được cho bởi #,(3)— z@, voi moix afy)— 70), c #,vc #, zc _ là một phép hoán vị trên Z;s. Ta thường đồng nhất Z;s với bang ký tự tiếng Anh, do đó phép hoán vị trên Z;s 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. Ma chuyén dich (shift cipher) lIệ mã dùng phép chuyển dich, ta ding bing ky 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 Z;s.

Như vậy, sơ đồ các hệ mật mã chuyển dịch được định nghĩa như sau S= (PEELE. yg, cic anh xa ¥va Dduoe cho bởi với mọi k x, ÿ C Lhe # & xv) = x Ik mod26, LK vy y¥-k mod26. Các hệ mật mã dược xác định như vậy là dúng dẫn, vì với mọi k, x, y £ Z2 ta đều có 4œ) — œ~—k)-k mod26 ~ xvìx € faz} Các hệ mật mã chuyển dịch dã dược sử dụng từ rất sớm, theo truyền huyết, hệ mã đó với k =3 đã dược dùng bởi J. Cacsar tir thoi dé quắc La mã, va dược gọi là hệ mã Caesar, 1.

AAã hoán vị. Các hệ mã hoán vị cũng được thực hiện lrê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ộ z¡ ký tự của bản rõ. Ta ký higu Sm 1a tap hợp tất cả các phép hoán vị của tập hợp { 1,2,. Sơ đồ các phép mã hoán vị được cho bởi Ñ- (#V.

8), trong đó #" = = £3, = Sm, cdc anh xa # va BD duge cho béi: BG. xm ) = Crete) Bie yer) = Ope Fertig) vai moi x =(%,. pm) ee , B= cấu, 8` là hoán vị nghịch dảo của z 1. Sơ đồ mật mã này lấy tên của Blaise de Vigenére, séng vào thé ky 16.

Khác với các hệ mật mã đã kế trước, các hệ mật mã Vigonẻrc không thực hiện trên Lừng ký tư một, mả dược thực hiện trên từng bộ m ký tự (m là số nguyên đương) So dé cde hé lật mã Vigenere được định nghĩa như sau: S= (PP HED), trong dG .# = % = = 2%, cac anh xa và 5Ø được cho bởi tiỚm,., xe) — (xi lẫu,., xml em ) mod26 0n., yH-lom) mol26 voi molx ~Éx¡,. kim)c 7 Sơ đồ mã Vigenẻre có thể được xem là mở rộng của sơ để mã chuyển địch, nếu mã chuyển dich thực hiện việc chuyển địch từng ký tự một thì mã Vigenere thực hiện dẳng thời từng bộ „ ký tự liên tiếp 1. Äđã HH Sơ đề mật mã này được đề xuất bởi Lester 8. Cũng giống như sơ đồ mã Vigendro, các hộ mã nảy được thực hiện trên từng bộ ø ký tự liên tiếp, diều khác lả mỗi ký tự của bản mã được xác định bởi một tổ hợp Luyễn tính (trên vành Zz«) của zz ký tự trong bản rõ.

Như vậy, khoá sẽ được cho bởi một ma trận cấp m, Lức là mat phan tit cilia 4% Z""™ ĐỀ phép biến đổi tuyến tỉnh xác định bởi ma trận _#€ó phép nghịch đảo, bản thân ma trận K cũng phải có ma trận nghịch đảo _2ˆ' theo mod26; mà điều kiện cần và di để K có nghịch đảo là định thức của nó, ký hiệu đetK, nguyên. Vậy, sơ đổ mật mã IHII được định nghĩa là sơ đô S- (FC.#= ÍK Z4 ":ged(datK,26 —1}, các ánh xạ và 2 được cho bởi. Z2 mod26, PY YO) = Oe YE). Mã đối xứng (gmmetrio-key algorithms) là hệ mã mà người gửi và người nhận củng có một khóa chung _#7 _# được giữ như bí mật riêng của hai người, _Z” dùng cả cho lập mật mã và giải mã nên có thể 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 dối xứng bao gồm các phương pháp mã hỏa đơn khóa (singie-#ey), 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 (privz/e-kep). Thuật toán đối xứng có thể dược chia ra lam hai thể loại, mã luồng (siream ciphers) va ma khdi (block ciphers). Mã luồng mã hóa từng bịt của thông diệ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 bịt.

Thuật toán tiêu chuẩn mã hóa tiên tiến (1#wanced DncrypHon Standard), được NIST công nhận tháng 12 năm 2001, sử dụng các khối gồm 128 bít, 192 bít hoặc 256 bít tủy người pửi/nhận thống nhất với nhau. MIã đổi xứng nhìn chung có tốc dộ tỉnh toán nhanh. Điển hình như: 1.1, MG theo dong. 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á 2C%0%., mdi 4 dùng để lập mi cho khối xi của văn bản.

Mỗi từ khoá .2, ngoài việc phụ thuộc vào mẫm khoá s con có thể phụ thuộc vào doạn từ khoá .Zˆ 27 dã dược sinh ra trước đó vả cả vào các yếu tổ khác, chẳng hạn như đoan văn bản xị.xi\ đã được lập mã trước đó. Hư vậy, ta có thê định nghĩa lại như sau: Miệt sơ đỗ hệ mã theo động được cho bởi một bộ S= (AC RX LE BD) qd) 4n mãn cá điều Lid 5 thỏa mãn các điều kiện sau đây: 9 @ Ja mot tập hữu hạn các ký Lự bản rỡ, *£ là một tập hữu hạn các ký tự bản mã, R la mot tap hitu hạn các mẫm khoá, 7a mét Vip hitu han cdc khóa, #ˆ'— {ñ. Hà bộ sinh đòng khoá, trong đó mỗifi là một ánh xạ từ R 3K. “isp * yao K, t# lá một ảnh xạ từ _Š%? vào 'Z,, được gọi là phép lập mật mã, và 2 là một ảnh xạ từ /#ˆx v2 vào .##, được gọi lả phép giải mã.#; ta định nghia &: % Ww , Gi, +6’ > la hai him cho bởi 3x eX :Gx)- 8x); Ive: Aly) - Pky).