RSA - Kỹ thuật mã hóa khóa công khai

Con người đã sử dụng mã hóa từ hàng ngàn năm trước, ví dụ như mã Caesar cách đây hơn 2000 năm. Tuy nhiên, các phương pháp cổ điển chỉ dùng một khóa cho cả mã hóa và giải mã, gây bất tiện và thiếu an toàn. Ví dụ như trong chiến tranh do phải chuyển khóa cho người nhận, khóa dễ bị đánh cắp hoặc thất lạc. Năm 1977, ba nhà khoa học máy tính là Ron Rivest, Adi Shamir và Leonard Adleman phát minh thuật toán RSA – mã hóa bất đối xứng với hai khóa: khóa công khai (public key) để mã hóa và khóa bí mật (private key hay secret key) để giải mã. RSA đánh dấu bước tiến lớn trong mật mã học, đặt nền tảng cho bảo mật internet như HTTPS, chữ ký số (digital signature) và VPN.

Ý tưởng chủ đạo

Từ một thông điệp gốc $m$ cần được mã hóa, bản mã $M$ được tạo ra bằng cách

Sau đó $M$ lại được giải mã đề trờ về thông điệp ban đầu $m$ bằng cách:

Nghĩa là $M^{\text{decryption factor}} = m^{\text{encryption factor * decryption factor}} \mod k= m$, suy ra:

Từ đây, chúng ta có thể dùng “encryption factor“ trở thành khóa công khai và “decryption factor“ trở thành khóa bí mật. Tuy nhiên, làm cách nào để xác định chúng?

Định lý Euler

Cho $a,n \in \mathbb{N}, \gcd(a,m)=1$, ta luôn có $a^{\phi(n)} \equiv 1 \quad (\mod{m})$ với $\phi(m)$ là hàm đếm tổng các số tự nhiên nhỏ hơn và nguyên tố cùng nhau với $m$:

Hàm $\phi(m)$ có vài tính chất sau:

• $\phi(1)=1$

• Nếu $\gcd(a,b)=1$ thì $\phi(a)*\phi(b)=\phi(a*b)$

• Nếu $p$ là số nguyên tố, thì $\phi(p)=p-1$

Mình xin giới thiệu một chứng minh đơn giản của định lý này như sau:

Gọi $S=\{x_1,x_2,\dots,x_{\phi(m)}\}$ với $x_i \lt m, \gcd(x_i,m)=1$. Rõ ràng, theo định nghĩa thì tập hợp này có đúng $\phi(m)$ phần tử.

Xét tập hợp $S'=\{ax_1,ax_2,\dots,ax_{\phi(m)}\}$, vì $\gcd(x_i,m)=1$ và $\gcd(a,m)=1$ nên $\gcd(ax_i,m)=1$. Hơn nữa nếu $ax_i \equiv ax_j \pmod m$ thì $x_i \equiv x_j \pmod m$ vì $\gcd(a,m)=1$.

Do đó các phần tử của $S'$ khi lấy dư cho $m$ sẽ đôi một khác nhac và vẫn nguyên tố cùng như với $m$. Vì thế ta có thể kết luận là $S'$ modulo $m$ là một hoán vị của tập hợp $S$.

Xét tích của tất cả các phần tử trong tập hợp $S'$ và $S$ (đều modulo với $m$) , ta có:

điều phải chứng minh.

Áp dụng Định lý Euler để xây dựng lược đồ mã hóa

Nếu xem thông điệp cần mã hóa $m$ với vai trò như $a$ ở định lý trên, ta cần tìm $n$ sao cho:

• $\gcd(a,n) = 1$, nếu tìm được $n$ thỏa, thì theo định lý Euler bên trên ta có $a^{\phi(n)} \equiv 1 (\mod n)$

• Để ý rằng theo công thức đồng dư, nếu: $a \equiv b (\mod m)$ thì $a^k \equiv b^k (\mod n)$ do đó nếu $a^{\phi(n)} \equiv 1 (\mod n)$thì $(a^{\phi(n)})^t \equiv 1^t (\mod n)$ tương đương với $a^{t.\phi(n)}) \equiv 1 (\mod n)$. Như vậy vấn để là ta cần tìm một số nguyên $t \gt 0$ để xây dựng: $\text{encryption factor}\times\text{decryption factor} = t\times \phi(n) + 1$

Đó là ý tưởng chính của thuật toán. Dưới đây là các bước của thuật toán.

Thuật toán RSA

• Chọn 2 số nguyên tố: $p,q$

• Tính $n=p.q, \phi(p)=p-1, \phi(q)=q-1 \implies \phi(n)=(p-1)(q-1)$

• Chọn $d,e \in \mathbb{N}$ sao cho: $d.e=1+t.\phi(n), \forall t > 0, t \in \mathbb{N}$. Thực ra, đây là thứ mình diễn giải để tiện cài đặt từ nguyên văn thuật toán:

  • Chọn $1 < e < \phi(n)$ sao cho $\gcd(e, \phi(n)) = 1$, thực ra ở bước này, bạn có thể tìm một số nguyên tố bất kỳ bé hơn $\phi(n)$ là đảm bảo tính chất

  • Chọn $d$ sao cho $d.e \equiv 1 (\mod \phi(n))$, để tính chúng ta có thể dùng thuật toán Euclide mở rộng (Extented Euclide Algorithm). Demo này mình chọn brute force cho đơn giản.

• Khóa công khai (public key) là $pk=(n,e)$, và khóa bí mật (secret key) là $sk = (d,n)$

• Từ đó, ta có:

  • Mã hóa $M = m^e \mod n$

  • Giải mã $m=M^d \mod n$

Demo

Các bạn chú ý nhập $p,q$ sao cho $n=p.q \gt 128$ để tránh lỗi do mất mát thông tin nhé!