IX. Vấn đề an toàn trong xây dựng thuật toán RSA

RSA vốn là một loại mật mã an toàn, tuy nhiên quá trình sinh khóa phụ thuộc nhiều vào yếu tố lựa chọn từ con người: Bao gồm việc chọn cặp số $(p, q)$ và số mũ công khai $e$, cùng với cách thức vận dụng quy trình mã hóa đã mang lại các kẽ hở cho kẻ tấn công có thể khai thác. Bởi vậy, để đảm bảo vấn đề bảo mật, an toàn trong việc truyền thông điệp mã hóa bằng thuật toán RSA, bên cạnh việc vận hành thuật toán an toàn thì chúng ta cũng cần đảm bảo các tham số $n, d, e$ được lựa chọn phù hợp.

1. Nguyên tắc lựa chọn số $n$

Yếu tố được xét tới đầu tiên khi đánh giá một thuật toán mã hóa RSA có an toàn hay không chính là khả năng phân tích số $n$ ra tích hai thừa số nguyên tố cao hay thấp. Bởi vậy việc lựa chọn số $n$ an toàn đóng vai trò quan trọng trong sự an toàn của thuật toán.

Nguyên tắc đầu tiên và dễ thấy nhất đó chính là giá trị của số $n$ cần được đảm bảo đủ lớn. Với sự phát triển nhanh chóng của công nghệ, hệ thống tính toán thì các số $n$ với giá trị nhỏ đều có thể dễ dàng bị phân tích. Hiểu một cách đơn giản bước đầu là số $n$ càng lớn thì thuật toán càng an toàn. Nên lựa chọn số $n$ có độ dài từ $1024$ đến $2048$ bit, sẽ khó có thể bị tấn công thành công trong tương lai gần.

Về bản chất, số $n$ được tạo thành từ tích của hai thừa số nguyên tố $p$ và $q$, nên bên cạnh việc đảm bảo số $n=p\times q$ đủ lớn thì cách lựa chọn cặp số nguyên tố $(p, q)$ cũng cần lưu ý. Cùng nhớ lại các phần bài viết về phương thức tấn công, việc lựa chọn cặp số $(p, q)$ có giá trị quá gần nhau hoặc quá xa đều tồn tại điểm yếu nhất định.

Xét thao tác liên tục nâng lên lũy thừa bậc $e$ của phương trình $c \equiv m^e \pmod {n}$, dừng lại cho tới khi thu được kết quả bằng $c$, giả sử sau $t$ lần nâng lên lũy thừa ta có:

$$m^e \equiv c \pmod {n}\\ m^{e^2} \equiv c^e \pmod {n}\\ ...\\ m^{e^{t+1}} \equiv c^{e^{t}} \equiv c \pmod {n}\\$$

Suy ra $m^{e^{t+1}} \equiv m^e \pmod {n}$, dẫn tới $m^{e^{t+1}-e} \equiv 1 \pmod {n}$. (các điều kiện nguyên tố cùng nhau hầu như thỏa mãn hoàn toàn do $n$ đủ lớn). Một trường hợp số $t$ thỏa mãn theo định lý Euler là khi $e^{t+1}-e\equiv 0 \pmod {\phi(n)}$, hay $e^{t}\equiv 1 \pmod {\phi(n)}$ (Do $e$ và $\phi(n)$ nguyên tố cùng nhau).

Tiếp tục sử dụng định lý Euler ta có thể chọn $t=\phi(\phi(n))$, như vậy nếu $t$ đủ nhỏ, ta có thể tính ngược lại quá trình trên và tìm ra $\phi(n)$ - đe dọa tới tính an toàn của thuật toán. Khi $GCD(p-1, q-1)$ nhỏ, sẽ dẫn tới $\phi(\phi(n))$ lớn, từ đó $t$ lớn, làm giảm đi tính hiệu quả của phương pháp trên.

Số nguyên tố được chọn cần là "số nguyên tố mạnh", tức cần thỏa mãn đồng thời:

• Điều kiện $1$: tồn tại hai số nguyên tố lớn $p_1$, $p_2$ sao cho $(p-1)\ \vdots\ p_1$ và $(p+1)\ \vdots\ p_2$
• Điều kiện $2$: tồn tại bốn số nguyên tố lớn $r_1, r_2, s_1, s_2$ sao cho $(p_1 - 1)\ \vdots\ r_1$, $(p_1 + 1)\ \vdots\ s_1$, $(p_2 - 1)\ \vdots\ r_2$, $(p_2 + 1)\ \vdots\ s_2$

Tóm lại việc chọn số $n$ an toàn chính là chọn hai số nguyên tố $p$, $q$ thỏa mãn đồng thời:

• Số $p$ và $q$ đủ lớn
• Đảm bảo hai số nguyên tố có khoảng cách đủ lớn và vừa phải.
• $GCD(p-1, q-1)$ nhỏ.
• Là các "số nguyên tố mạnh".

2. Nguyên tắc lựa chọn số $e$

Số mũ công khai $e$ được chọn sao cho thỏa mãn $GCD(e, \phi(n))=1$, do có nhiều giá trị thỏa mãn nên cần chú ý lựa chọn sao cho phù hợp. Việc lựa chọn số $e$ quá nhỏ mang lại nhiều tiềm ẩn bị tấn công kết hợp với phương thức vét cạn giá trị hoặc vận dụng định lý Thặng dư Trung Hoa. Để chống lại sự tấn công, chúng ta nên lựa chọn số $e$ sao cho tồn tại $i$ thỏa mãn:

$$e^i \equiv 1 \pmod {\phi(n)}, \text{với } i \geq \frac{\phi(n)}{2}$$

3. Nguyên tắc lựa chọn số $d$

Mặc dù số mũ bí mật $d$ được tính toán phụ thuộc vào các giá trị khác mà không được chọn trực tiếp, nhưng nó lại đóng vai trò quan trọng nhất trong việc giải mã ngược lại thông điệp gốc. Do đó chúng ta cũng cần đảm bảo số $d$ thu được cần đáp ứng tính an toàn.

Khi số $d$ thu được có độ dài không đủ lớn, mặc dù có lợi cho tốc độ tính toán mã hóa, nhưng sẽ làm giảm đáng kể tính an toàn của thuật toán. Một trong những cách làm phổ biến của kẻ tấn công là sử thông một thông điệp $m$ tự sinh rồi thực hiện mã hóa rồi so sánh và tìm ra $d$. Độ dài của $d$ càng nhỏ thì không gian dự đoán càng nhỏ, dẫn tới tỉ lệ đoán đúng càng lớn. Bên cạnh đó kẻ tấn công cũng có thể sử dụng Wiener's attack cũng mang lại hiểu quả lớn trong trường hợp này.

Chúng ta nên đảm bảo số mũ bí mật $d$ sau khi được sinh ra thỏa mãn:

$$d \geq N^{\frac{1}{4}}$$

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