Homomorphic Encryption

💡

Nếu bạn đã từng say mê bộ truyện Harry Potter thì chắc các bạn chẳng xa lạ gì với cái tên của “Kẻ mà ai cũng biết là ai đấy” - Chúa tể hắc ám Voldemort. Hắn đã chia linh hồn mình ra làm 7 cái trường sinh linh giá. Muốn tiêu diệt hắn, phải tiêu diệt toàn bộ 7 cái trường sinh linh giá này. Bài viết này, chúng ta sẽ quan sát câu chuyện của Voldemort dưới lăng kính của mật mã, thông qua kỹ thuật mã hóa đồng cấu (homomorphic encryption).

!!! Disclaimer 1: Việc cố gán ghép một chi tiết trong truyện thần thoại vào khoa học kỹ thuật đôi khi không hoàn toàn phù hợp về tính chất cốt lõi. Ở đây, mình chỉ muốn tiếp cận vấn đề một cách gần gũi và dễ hiểu với các bạn. Vì vậy, nếu cảm thấy đây là ví dụ chưa thực sự phù hợp, xin bạn niệm tình bỏ qua.

!!! Disclaimer 2: Thực ra, theo mình, kỹ thuật chia nhỏ bí mật của Shamir (Shamir’s Secret Sharing) sẽ phù hợp hơn cho vấn đề của Voldemort*.*

Mã hóa đồng cấu (Homomorphic Encryption)

Mã hóa đồng cấu là một dạng mã hóa cho phép thực hiện các phép tính trực tiếp trên dữ liệu đã được mã hóa (ciphertext), mà không cần giải mã nó. Kết quả của các phép tính trên dữ liệu mã hóa, khi được giải mã, sẽ khớp với kết quả của các phép tính được thực hiện trên dữ liệu gốc (plaintext).

Cho một hệ mã hóa gồm:

Thông điệp $m$
Một cặp khóa gồm khóa công khai $pk$ và khóa bí mật $sk$

Hàm mã hóa $E(m)$
Hàm giải mã $D(M)$ với $M=E(m)$

Một hệ mã hóa được gọi là đồng cấu nếu với mọi dữ liệu $m_1, m_2$ và phép toán $*$, tồn tại một phép toán $\circ$ sao cho:

$$D(E(m_1)*E(m_2)) = m_1 \circ m_2$$

Trường hợp cụ thể với hệ mã hóa RSA

Nhắc lại mã hóa RSA:

$E(m) = m^e \mod n$
$D(E(m)) = E(x)^d \mod n = (m^{e})^d \mod n= m$ (vì $e.d \equiv 1 \mod \phi(n)$ - Fermat nhỏ)

Giả sử thông điệp $m$ được chia làm $k$ phần sao cho $m = \prod_{i=1}^k m_i$. Ta có:

$$\begin{align*} E(m_1)E(m_2) \dots E(m_k) &= m_1^em_2^e \dots m_k^e \\ &= (m_1m_2\dots m_k)^e \\ &=E(m_1m_2\dots m_k) & (\mod n) \end{align*}$$

Và nếu giải mã …

$$\begin{align*} D(E(m_1)E(m_2)\dots E(m_k)) &= D((m_1m_2\dots m_k)^e \mod n) \\ &= ((m_1m_2\dots m_k)^e)^d \mod n \\ &= m_1m_2\dots m_k \mod n\\ &= m \mod n \end{align*}$$

Như vậy, chúng ta có thể thấy mã hóa đồng cấu cho phép ta thay vì mã hóa thông điệp gốc $m$, nếu chúng ta có thể chia $m$ thành nhiều phần $m_i$, mã hóa các $m_i$ riêng lẻ, rồi gộp lại và vẫn khôi phục nguyên vẹn lại thông điệp gốc $m$ khi giải mã.

Điểm đặc biệt của phương pháp này là cần phải có đủ các thành phần $E(m_i)$ mới khôi phục lại được $m$. Bạn có thể lợi dụng phương pháp này để chia nhỏ mật mã ra nhiều phần nhằm tăng tính bảo mật hơn cho ứng udjng của bạn như ví điện tử chẳng hạn. Đây cũng chính là ý tưởng của MPC (Multi-party Computing) Wallet.

Ví dụ đơn giản

Giả sử bạn có số bí mật là $s=21$, và tách làm 2 phần $s_1 = 3, s_2 = 7$: $s=s_1 \times s_2$.

Khởi tạo mã hóa RSA với $p=31, q=19$. Khóa công khai $pk = (n,e) = (589,7)$, khóa bí mật $sk=(n,d)=(589,463)$.

Tính $E(s_1) = s_1^e \mod n = 3^7 \mod 589 = 420$
Tính $E(s_2) = s_2^e \mod n = 7^7 \mod 589 =121$
Tính $E(s_1)E(s_2) = 420*121 = 50820$
Tính $D(E(s_1)E(s_2)) = D(50820) = 50820^{463} \mod 589 = 21 (= s_1\times s_2) \checkmark$

💡

Nếu bạn gặp khó khăn với tính toán, bạn có thể cuộn lên header của bài viết và dùng các công cụ tính toán ở tab số 2 “Discrete Math Evaluator - Modulo” để kiểm chứng nhé!

Làm sao tách một thông điệp $m$ bất kỳ thành $k$ phần ?

Sử dụng phép toán trên trường hữu hạn $\mathbb F_p$, ta có:

$$\begin{align*} m. m^{-1} &= 1 (\mod p)\\ m = m_1.m_2 &\implies m_2=m.m_1^{-1} (\mod p) \end{align*}$$

Với $m_1^{-1}$ là phần tử nghịch đảo của $m_1$ trong $\mathbb F_p$.

Giả sử bạn có thông điệp $m$ và muốn chia thành 2 phần:

Chọn một giá trị bất kỳ $m_1 \in \mathbb F_p$
Tính $m_2 = m.m_1^{-1} (\mod p)$

Tổng quát, muốn chia thành $k$ phần:

Chọn ngẫu nhiên $m_1,m_2,\dots,m_{k-1} \in \mathbb F_p$
Tính $m_k = m.(m_1m_2\dots m_{k-1})^{-1}$

Ví dụ: Bạn có số bí mật là $s=151$ và muốn chia làm $k=4$ phần, trên trườn hữu hạn $\mathbb F_p, p = 191$

Chọn ngẫu nhiên $s_1 = 14, s_2 = 21,s_3=178$
Tính $s_1s_2s_3 = 14.21.178 \mod 191 = 189$
Tính $(s_1 s_2 s_3)^{-1} =189^{-1} =95 (\mod 191)$
Tính $s_4 = s.95 \mod 191 = 151.95 \mod 191 = 20$

Vậy 4 phần chia lần lượt sẽ là: $s_1 = 14, s_2=21, s_3=178, s_4=20$.

Bạn có thể kiểm tra lại bằng cách tính$s_1s_2s_3s_4 = 14.21.178.20 \mod 191 = 1046640 \mod 191 = 151 = s$

Các loại mã hóa đồng cấu

Mã hóa đồng cấu một phần (Partially Homomorphic Encryption - PHE):

Hỗ trợ một loại phép toán đồng cấu (cộng hoặc nhân)
Ví dụ: RSA hỗ trợ nhân đồng cấu, Paillier hỗ trợ cộng đồng cấu. Bạn có thể vào trang web interactive.skyglab.tech của mình để thử nghiệm

Mã hóa đồng cấu từng phần (Somewhat Homomorphic Encryption - SWHE):

Hỗ trợ cả cộng và nhân
Nhưng giới hạn số lần phép toán.

Mã hóa đồng cấu hoàn toàn (Fully Homomorphic Encryption - FHE)

Hỗ trợ cả cộng và nhân
Không giới hạn số lần phép toán
Đây là một lĩnh vực rất hot hiện nay!!!

Hormomophic Encryption - 7 trường sinh linh giá của Chúa Tể Voldemort

Mã hóa đồng cấu (Homomorphic Encryption)

Trường hợp cụ thể với hệ mã hóa RSA

Ví dụ đơn giản

Làm sao tách một thông điệp \(m\) bất kỳ thành \(k\) phần ?

Các loại mã hóa đồng cấu