III. Mật mã RSA - Thực hiện (Tiếp)

4. Tạo số nguyên tố trong Python

Để tạo ra một cặp khóa công khai và khóa bí mật trong mật mã RSA, bước đầu tiên là chọn hai số nguyên tố (p, q). Chúng là nền tảng chính cho tất cả các bước tạo khóa tiếp theo. Vậy, làm thế nào để tạo ra một cặp số nguyên tố (p, q)?

Trước đây, người ta đã sử dụng sàng Eratosthenes để lưu trữ các số nguyên tố bằng cách loại bỏ các hợp số.

Trong Python, bạn có thể sử dụng hàm getPrime() từ module Crypto.Util.number trong thư viện PyCryptodome:

getPrime(N:int, randfunc:callable) -> long

Hàm này sẽ trả về một số nguyên tố ngẫu nhiên có độ dài N bytes.

5. Sử dụng Module trong Python

Để thực hiện các phép toán mã hóa và giải mã trong RSA, Python cung cấp hàm pow(base, exponent, modulus). Hàm này thực hiện tính toán đồng dư, như sau:

• base: giá trị cơ số.
• exponent: giá trị số mũ.
• modulus: giá trị module.

Ví dụ, để tính kết quả 3718 ≡ ? (mod 912), bạn có thể viết chương trình như sau:

ans = pow(37, 18, 912)
print(ans)

Nếu không cung cấp аргумента thứ ba (modulus), hàm pow() sẽ chỉ tính lũy thừa thường. Tuy nhiên, nếu bạn cần tốc độ cao hơn cho các dữ liệu lớn, hãy dùng math.pow().

6. Tìm số nghịch đảo module

Khóa bí mật d cũng cần được xác định để giải mã thông điệp RSA. Mối quan hệ giữa e và d là:

de ≡ 1 (mod ϕ(n)).

Câu hỏi đặt ra là, liệu có tồn tại d cho mọi e và ϕ(n)? Câu trả lời là có, với điều kiện ƯCLN(e, ϕ(n)) = 1. Hay nói cách khác, bạn có thể sử dụng phương trình này để tìm d.

Việc tìm d cộng thông qua vòng lặp thử từng giá trị có thể mất thời gian khi n lớn, vì vậy thay vào đó bạn có thể sử dụng hàm pow() với exponent=-1:

d = pow(e, -1, phi)

Bài tập cho bạn đọc

Cho cặp số nguyên tố (p, q) = (53, 71), số mũ công khai e = 65537, hãy mã hóa m = 102.

IV. Một số Kỹ thuật Tấn công RSA

Điểm yếu chính của RSA là chỉ có hai phần chính là khóa công khai (n, e). Nếu kẻ tấn công muốn giải mã thông điệp, họ cần giá trị bí mật d và ϕ(n). Chúng tôi sẽ thảo luận về cách tìm ra ϕ(n).

1. Vấn đề khi chọn số nguyên tố nhỏ

Số n nhỏ dẫn tới khả năng mật mã không an toàn. Điều này có nghĩa là nếu chọn cặp số nguyên tố nhỏ, không gian thông điệp có thể mã hóa cũng bị giới hạn. Hơn nữa, việc lựa chọn số nguyên tố nhỏ làm tăng khả năng kẻ tấn công tìm ra p và q.

Bạn có thể tham khảo các công cụ trực tuyến sau để phân tích các số nguyên lớn:

• http://factordb.com/
• https://www.alpertron.com.ar/
• https://www.wolframalpha.com/

Tài liệu tham khảo

• https://en.wikipedia.org/wiki/RSA_(cryptosystem)
• https://www.amsi.org.au/teacher_modules/pdfs/Maths_delivers/Encryption5.pdf
• https://sites.math.washington.edu/~morrow/336_09/papers/Yevgeny.pdf
• https://vi.wikipedia.org/wiki/Giải_thuật_Euclid_mở_rộng
• https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
• https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
  source: viblo