基于素数群的 EIGamal 加密
系统参数：素数群 $G$ 的阶为 $p$，生成元为 $g$
密钥生成：选择随机数 $\alpha \in Z_p$，计算 $g_1=g^{\alpha}$，则私钥和公钥为 $(\alpha, g_1)$
加密：将消息编码为群元素 $m \in G$，公钥 $g_1$，选择随机数 $r \in Z_p$，计算密文 $C_1=g^r, C_2=g_1^r \cdot m$
解密：对于密文 $(C_1, C_2)$，使用私钥 $\alpha$ 计算 $m=C_2 \cdot C_1^{-\alpha}$
推导：$C_2 \cdot C_1^{-\alpha}=(g_1^r\cdot m)(g^r)^{\alpha}=m$
基于椭圆曲线群的 EIGamal 加密
系统参数：椭圆曲线群 G 的阶为 $p$，生成元为 $G$
密钥生成：选择随机数$\alpha \in Z_p$，计算 $G_1=\alpha \cdot G$，则私钥和公钥分别为 $(\alpha, G_1)$
加密：将消息编码到椭圆曲线群，得到 $M \in G$，公钥 $G_1$，选择随机数 $r \in Z_p$，计算密文
$$ \begin{align} &C_1 = r \cdot G \\ &C_2 = M + r \cdot G_1 \end{align} $$
解密：对于密文 $(C_1, C_2)$，使用私钥 $\alpha$，计算 $M=C_2 - \alpha \cdot C_1$
推导：$C_2 - \alpha \cdot C_1 = (M + r \cdot G_1) - \alpha r \cdot G = M$
安全性分析：基于 DDH 困难问题，即已知 $G, a \cdot G, b \cdot G, Z \in G$，无法判定 $Z = ab \cdot G$ 是否成立
ECIES 加密
系统参数：椭圆曲线群 G 的阶为 $n$，生成元为 $G$。$h$ 为余因子常量。KDF 为密钥派生函数。
密钥生成：选择随机数 $d \in Z_p$，计算 $Q = d \cdot G$，则私钥和公钥分别为 $(d, Q)$
加密：选择随机数 $k \in [1, n-1]$，计算 $R=k \cdot G$，$Z=hk \cdot Q$（对 $Q$ 做倍点运算后，还是椭圆曲线上的点）。取 $Z$ 的横坐标为 $x_z$，计算两个随机数 $(k_1, k_2)=KDF(x_z, R)$。使用 CTR-AES 加密模式对任意长消息 $m \in \left\{0, 1\right\}^*$ 加密
$$ \begin{align} &C=CTR\_AES\_Enc_{k_1}(m)\\ &t = MAC_{k_2}(C) \end{align} $$
密文为 $(R, C, t)$，其中，$t$ 用于校验密文的完整性。
解密：使用私钥 $d$ 计算 $Z'=hd \cdot R$。取 $Z'$ 的横坐标 $x_z'$，计算两个随机数 $(k_1', k_2')=KDF(x_z', R)$。计算 $t'=MAC_{k_2'}(C)$，校验 $t'=t$，然后 CTR-AES 解密 $m=CTR\_AES\_Dec_{k_1'}(C)$
推导过程：$Z = hk \cdot Q = hkd \cdot G = hd \cdot R = Z'$
没有评论