Tìm hiểu về hệ mật mã RSA và vai trò của nó trong cuộc sống (phần 1)

Lời mở đầu

Hệ mật mã khóa công khai RSA (Rivest–Shamir–Adleman) là một trong những hệ mật mã được sử dụng rộng rãi nhất hiện nay. RSA được sử dụng trong nhiều mục đích khác nhau, ví dụ như:

Bảo mật email

Bảo mật các giao dịch ngân hàng

Bảo mật dữ liệu trong các tổ chức và cơ quan Chính phủ

Phân phối khóa an toàn cho các hệ mật mã đối xứng

Mặc dù RSA có những hạn chế nhất định, nhưng RSA vẫn là hệ mật mã rất quan trọng, RSA đã được tiêu chuẩn hóa và được công nhận bởi ANSI (American National Standards Institute — Viện tiêu chuẩn và quốc gia Hoa Kỳ) và một số tổ chức uy tín khác. Trong loạt bài viết này chúng ta sẽ tìm hiểu chi tiết về hệ mật mã RSA, cách thức hoạt động của nó, vai trò của nó trong cuộc sống cũng như các phương pháp để tấn công nó.

Bàn luận về sự ra đời của RSA

☝️

Phần bàn luận về sự ra đời của RSA có những kiến thức cơ bản về lịch sử phát triển mật mã và các loại mã hóa, nếu độc giả chỉ muốn tìm hiểu về cơ chế hoạt động của RSA, vui lòng bỏ qua phần này.

Hệ mật mã đối xứng

Bài toán phân phối khóa

Hệ mật mã bất đối xứng

Một số kiến thức toán học cần biết

Hệ mật mã RSA

Hiện nay RSA đã trở thành tiêu chuẩn và được công bố tại [2] với nhiều cải tiến và bổ sung nhằm tăng tính bảo mật cho hệ mã này. Tuy nhiên để thuận tiện cho độc giả có thể hiểu rõ về cơ chế hoạt động của hệ mật mã RSA, chúng ta chỉ bàn luận đến phiên bản lúc sơ khai (Textbook RSA) để độc giả có thể dễ dàng tiếp cận loại mật mã này.

Quy tắc mã hóa và giải mã trong RSA

Bước 1: Sinh khóa RSA

Trước khi bắt đầu quá trình mã hóa và giải mã, chúng ta cần tạo một cặp khóa bao gồm khóa công khai (Public Key) được công khai cho mọi người được sử dụng để mã hóa và khóa bí mật (Private Key) cần được giữ kín và được sử dụng để giải mã thông tin.

Bước 2: Mã hóa và giải mã

Chúng ta ký hiệu thông điệp cần mã hóa là

m

, hàm mã hóa là

E_k

, hàm giải mã là

D_k

, ta có

\begin{align*} E_k(m) &= m^e\;(\bmod\,N)=x \\ D_k(x) &= D_k(E_k(m))=x^d\;(\bmod\,N)=m \end{align*}

Chúng ta cùng xem xét bồ để sau để hiểu rõ hơn về tính đúng đắn cũng như hiểu được sao

x^d \,(\bmod\,N )

lại có thể bằng

m

Độ an toàn của RSA

Độ an toàn của RSA dựa trên khẳng định sau: nếu không biết chìa khóa bí mật, kẻ xấu không thể đảo ngược được hàm

E_k(m)=m^e\;(\bmod\;N)

trong thời gian đa thức (polynomial-time). Có nghĩa rằng an toàn của RSA có liên quan mật thiết tới bài toán tìm căn bậc

e

của một số bất kì theo module

N

Phương pháp để đảo ngược được hàm

E_k(m)

chính là tìm giá trị của hàm

\varphi(N)

, nếu tính được

\varphi(N)

chúng ta có thể tìm được khóa bí mật

d

bằng cách giải hệ 2 phương trình sau:

\begin{cases} (p-1)\cdot(q-1)&=\varphi(N)\\ p\cdot q&=N \end{cases}

Tuy nhiên để tính được

\varphi(N)

khi không biết

p

và

q

ở thời điểm hiện tại là không thể, bởi vì

\begin{align*} \varphi(N) &= \vert \mathbb{Z}_{N}\backslash \{0,p,2\cdot p,...,(q-1)\cdot p,q,2\cdot q, (p-1)\cdot q\} \vert \\ & = N-q-(p-1)=(p-1)\cdot (q-1 ) \end{align*}

Với số lượng nhiều kinh khủng khiếp như vậy, cách này là không khả thi ở thời điểm hiện tại.

Tuy nhiên nếu chúng ta có thể phân tích được

N

ra các thừa số nguyên tố, ta có thể dễ dàng tính được

\varphi(N)

(vì thế hàm

E_k

còn được gọi là hàm trapdoor 1 chiều - Trapdoor one-way function) và thể giải mã được thông điệp được mã hóa bởi RSA, ở rất nhiều tài liệu và các giáo trình đều bắt đầu với bài toán phân tích số

N

ra thừa số nguyên tố, tuy nhiên bản chất độ khó RSA chính là bài toán giải căn bậc

e

của một số nguyên theo modulo

N

tuy vậy 2 bài toán này lại tương đương với nhau (có nghĩa là nếu tìm được cách giải bậc

e

của một số nguyên theo modulo

N

đồng nghĩa với việc tìm được cách phân tích số

N

ra thừa số các số nguyên tố và ngược lại) [3] vậy nên, người ta đã đi theo một hướng dễ dàng hơn đó chính là phân tích số

N

thành các thừa số nguyên tố.

Độ dài bit của

N

được khuyến nghị là ít nhất 2048 bit để bảo đảm tính bảo mật.

Cách RSA giải quyết vấn đề phân phối khóa

Vậy RSA đã giải quyết được vấn đề khó khăn của mật mã đối xứng đó chính là vấn đề phân phối khóa, (về mặt lý thuyết) An sẽ mã hóa thông tin và gửi cho Bình qua đường truyền Internet, sau đó Bình sẽ gửi cho An khóa công khai của của mình, An mã hóa chìa khóa bằng thuật toán RSA sử dụng khóa công khai của Bình và Bình sử dụng khóa bí mật của mình giải mã và nhận được chìa khóa mã hóa từ An.

Có vẻ phức tạp nhỉ? Chúng ta sẽ cụ thể hóa vấn đề trên bằng giao thức (protocol) sau:

Bước 1: An → Bình: Thông tin được mã hóa bằng chìa khóa $h$

Bước 2: Bình sinh ra khóa công khai $(N,e)$ và $(p,q,d)$ .

Bước 3: Bình → An : cặp khóa công khai $(N,e)$ .

Bước 4: An mã hóa khóa $h$ bằng hàm $E_k(h)=h^{e} \;(\bmod\;N) =x$ .

Bước 5: An → Bình: $x$ .

Bước 6: Bình giải mã $x$ bằng hàm $D_k(x)=x^d = h^ {e\cdot d} \;(\bmod\;N)=h$ .

Bước 7: Bình dùng khóa h để giải mã thông điệp được gửi bởi An.

Ta sẽ xem xét ví dụ cụ thể sau để hiểu rõ được RSA được sử dụng như thế nào trong thực tế

Bước 1: An → Bình: Thông tin được mã hóa bằng chìa khóa $h=11$ .

Bước 2: Bình sinh ra các khóa của mình như sau:

$p=17,q=23$

$N=p\cdot q=391, \varphi(N) = (p-1) \cdot (q-1)= 16 * 22 = 352$

Chọn ngẫu nhiên $e$ trong khoảng từ 3 tới 352, $e=3$

Tìm $d$ bằng giải thuật Euclid mở rộng, ta tính được $d=235$

Các khóa của Bình sẽ là: khóa công khai $(391,3)$ , khóa bí mật $17,23,235$ .

Bước 3: Bình → An : cặp khóa công khai $(391,3)$ .

Bước 4: An mã hóa $h=11$ và ra kết quả sau $h ^ {e} \;(\bmod\;391)=11^ {3} \; (\bmod\;391) = 158$ .

Bước 5: An → Bình: $x=158$ .

Bước 6: Bình giải mã $x$ như sau $x^ {d} \; (\bmod\;N)=158 ^ {235} \;(\bmod\;391)= 11=h$ .

Bước 7: Bình dùng khóa $h=11$ để giải mã thông điệp được gửi bởi An.

Ở phần tiếp theo chúng ta sẽ tìm hiểu những ứng dụng của RSA trong cuộc sống cũng như các phương pháp để tấn công hệ mật mã RSA.

Tài liệu tham khảo

R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public key cryptosystems, Commun. ACM 21 (1978), 120–126.

RSA Laboratories. PKCS #1 v2.2: RSA Cryptography Standard October, 2012

May A. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis. University of Paderborn. 2003.

👌

Tìm hiểu về hệ mật mã RSA và vai trò của nó trong cuộc sống (Phần 2)