ElGamal加密

• 一种概率加密方案。
• 如果判定Diffie–Hellman问题难以求解，就可以提供IND-CPA (INDistinguishability under Chosen-Plaintext Attack) 安全性。

给定$g, g^a, g^b$和$X$，判断$X$是$g^{ab}$还是$g^c$，其中c是随机值。

• $E_{K_{pub}}(M_1) \cdot E_{K_{pub}}(M_2) = E_{K_{pub}}(M_1 \cdot M_2)$
  通过通用变换，可以提供IND-CCA2 (INDistinguishability under Chosen-Ciphertext Attack) 安全性。

• 密钥生成
  1. 选择素数$p$。
  2. 在$\mathbb{Z}_p^*$的子群$\mathbb{G}$中，选择生成元$g$。
     • 该子群的阶为$q$。
  3. 从$\mathbb{Z}_q$中选择随机元素$x$，并计算$X = g^x \pmod{q}$。
  4. 输出公钥$\text{pk} = (p, q, g, X)$和私钥$\text{sk} = x$。
• 加密
  1. 从$\mathbb{Z}_q$中选择随机元素$r$。
  2. 计算$C_1 = g^r$和$C_2 = M \cdot X^r$，然后输出密文$CT = (C_1, C_2)$。
• 解密
  1. 给定私钥$\text{sk} = x$和密文$CT = (C_1, C_2)$，
  2. 计算$C_2 / (C_1)^x (= M \cdot X^r / (g^r)^x = M)$，输出明文$M$。

• 公钥：$\text{pk} = (23, 11, 2, 8)$，私钥：$\text{sk} = 6$。
• 加密
  • 当$r = 3$时，
  • $C_1 = 2^3 = 8$
  • $C_2 = 9 \cdot 8^3 = 9 \cdot 512 = 4608$
• 解密
  • $M = 4608 / 8^6 = 9$