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

Thực ra, mình đã viết một version bằng tiếng Anh về bài này khá lâu trước đây, các bạn có thể tham khảo tại bài viết này.

Ý 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

$$M = m^{\text{encryption factor}} \mod k$$

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

$$m = M^{\text{decryption factor}} \mod k$$

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

$$m^{\text{encryption factor * decryption factor} - 1} \equiv 1 (\mod k)$$

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,n)=1\), ta luôn có \(a^{\phi(n)} \equiv 1 \quad (\mod{n})\) với \(\phi(n)\) là hàm đếm tổng các số tự nhiên nhỏ hơn và nguyên tố cùng nhau với \(n\):

$$\phi(n)=|\{0\lt x \lt n, \gcd(n,x)=1\}|$$

Hàm \(\phi(n)\) 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\)

Á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 \(d\) chúng ta có thể dùng thuật toán Euclide mở rộng (Extented Euclide Algorithm) mà hy vọng sẽ có một bài viết khác mình sẽ giới thiệu về thuật toán này. 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é!