Thuật toán mã hóa RSA

Trong bài viết Tổng Quan Về Public-Key Cryptography Và Cryptocurrency, bạn Linh có đề cập tới Mã hóa bất đối xứng (asymmetric cryptography). Trong bài viết này, tôi sẽ giới thiệu với các bạn về một trong những thuật toán đó, mà cụ thể là thuật toán mã hóa RSA.

Thuật toán mã hóa RSA (Rivest–Shamir–Adleman) do ba nhà toán học và khoa học máy tính Ron Rivest, Adi ShamirLeonard Adleman công bố lần đầu năm 1978.

Trước tiên, chúng ta xem xét một vài định nghĩa và định lý cơ bản: (chứng minh của các định lý này các bạn có thể tìm thấy dễ dàng trên Internet)

Định nghĩa 1:
Gọi \mathbb{Z} là tập các số nguyên \{0, 1, -1, 2, -2, \ldots\}.
Cho a, b \in \mathbb{Z}. Nếu \exists \, c \in \mathbb{Z}: b = ac, ta nói a là ước của bb là bội của a, ký hiệu a \vert b.

Định nghĩa 2:

  • c \in \mathbb{Z} được gọi là ước chung của a, b \in \mathbb{Z} nếu c \vert ac \vert b.
  • d \in \mathbb{Z} được gọi là ước chung lớn nhất của a, b \in \mathbb{Z}, ký hiệu d = \gcd(a,b) hay d = a \wedge b, nếu d là bội của mọi ước của ab; (c \in \mathbb{Z}, c \vert a, c \vert b \Rightarrow c \vert d).

Định nghĩa 3:
Hai số nguyên a, b \in \match{Z} được gọi là nguyên tố cùng nhau, ký hiệu a \perp b hay (a,b) = 1, nếu a \wedge b = 1.

Định nghĩa 4:
Cho x, y \in \mathbb{Z}, m \in \mathbb{N}^* = \{n \in \mathbb{Z}; n \geq 1\}.
x được gọi là đồng dư của y theo modulo m, ký hiệu:

    \[ x \equiv y \pmod m \]

nếu m là ước của x - y, hay nói cách khác là xy có cùng số dư khi chia cho m. m được gọi là modulo của phép đồng dư.
Ví dụ: 260 \equiv 4 \pmod{256}

Định nghĩa 5 (hàm phi-Euler (đọc là phi-ơ-le)):
Cho n \geq 1. Hàm phi-Euler của n, ký hiệu \varphi(n) là tập hợp tất cả các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n.

    \[ \varphi(n) = \{k \in \mathbb{N}^*; 1 \leq k \leq n, k \perp n \} \]

Ví dụ: \varphi(1) = 1, \varphi(2) = 1, \varphi(3) = 2, \varphi(57) = 56

Định lý 1:
Nếu n = p \cdot q, trong đó pq là các số nguyên tố, thì \varphi(n) = (p-1)(q-1).
Ví dụ: Cho n = 35 = 5 \times 7. Vậy \varphi(35) = (5-1)(7-1) = 24.
Cụ thể \varphi(35) = \{1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34\}

Định lý 2 (Định lý Euler):
a^{\varphi(n)} \equiv 1 \pmod{n}

OK, sơ sơ như vậy là ta đã đủ lý thuyết để chiến với thuật toán mã hóa RSA rồi đấy (cũng khá đơn giản phải không nào :D)

Quy trình phát sinh khóa công khai (public key) và khóa cá nhân (private key):

  1. Chọn 2 số nguyên tố lớn ngẫu nhiên (trên 1024 bits), pq.
  2. Tính n = p \cdot q
  3. Chọn e là một số nguyên tố cùng nhau với (p-1)(q-1). Điều này đảm bảo cho d ở bước 4 luôn tồn tại.
  4. Tìm d sao cho ed \equiv 1 \pmod{(p-1)(q-1)} (ta có thể tính được d sử dụng thuật toán Euclide mở rộng).
  5. Cặp (e, n) chính là public key, (d, n) chính là private key. Bây giờ ta không còn cần dùng tới 2 số p, q nữa và có thể xóa bỏ chúng.

Quy trình mã hóa:
Giả sử An muốn gửi cho Bình một thông điệp M, thông điệp này trước hết phải được chuyển thành các blocks, mỗi block tương ứng với một số m \le n. Ví dụ, với binary data, mỗi block sẽ chứa \log_2 n bits. An sẽ mã hóa thông điệp này sử dụng khóa cá nhân của mình và gửi cho Bình.

    \[ s = m^d \pmod{n} \]

Quy trình giải mã:
Sau khi nhận được thông điệp mã hóa từ An, Bình tiến hành giải mã sử dụng khóa công khai của An.

    \[ s' = s^e \pmod{n} \]

Chứng minh:

    \begin{align*} s' &= s^e \pmod{n} \\ &= (m^d)^e \pmod{n} \\ &= m^{de} \pmod{n}\\ &= m^{k(p-1)(q-1)+1} \pmod{n} \qquad \qquad \text{(theo bước 4)}\\ &= m^{k\varphi(n) + 1} \pmod{n} \qquad \qquad \text{(theo định lý 1)}\\ &= (m^{\varphi(n)})^km \pmod{n}\\ &= m \qquad \qquad \text{(theo định lý 2)} \end{align*}

Ví dụ:
An chọn p = 17, q = 23.
Tính n = 17 \cdot 23 = 391.
Trong ví dụ này, để đơn giản nên tôi chọn các số p, q nhỏ, trong thực tế p, q là các số nguyên tố rất lớn nên việc tìm ra p, q từ n là gần như không thể.
Tính \varphi(n) = (17-1)(23-1) = 352
Chọn e = 5. Chọn d = 141. (ed = 5 \cdot 141 = 705 \equiv 1 \pmod{352}).
Bây giờ, giả sử An muốn gửi cho Bình thông điệp m = 89.
An tính: 89^5 \mod{391} = 378. An gửi giá trị này cho Bình.
Bình giải mã: 378^{141} \mod{391} = 89.
Dĩ nhiên giá trị 378^{141} đối với chúng ta là rất lớn, nhưng đối với máy tính thì là “chuyện nhỏ”. Bạn nào thích có thể kiểm chứng lại giống như hình bên dưới.

Tham khảo:
https://www.cs.bham.ac.uk/~mdr/teaching/modules06/netsec/lectures/blind_sigs.html
https://kipalog.com/posts/Cac-giai-thuat-tinh-nghich-dao-modulo

Để lại một bình luận

Địa chỉ email của bạn sẽ không được công bố.