简述
ElGamal算法，是由T.Elgamal于1984年提出的公钥密码体制和椭圆曲线加密体系。既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题即CDH假设。在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K，其实现依据是求解离散对数是困难的，而其逆运算指数运算可以应用快速幂的方法有效地计算。也就是说，在适当的群G中，指数函数是单向函数。
用于签名
- 生成密钥:确定一个大素数$p$和它的一个原根$g$，在$Z_p$域上选择一个随机数$x$作为密钥，并计算$$y=g^x\ mod\ p$$
$(p,g,y)$作为公钥。
- 签名算法:用$m$表示待签名信息，在$Z_p$域上选择一个与$p-1$互质的数$k$，并计算$$C_1=g^k\ mod\ p$$
再运用Ext_Euclidean算法求出$C_2$，使其满足：$$m\equiv ax+C_2k\ \ mod\ p-1$$
3. 输出签名:$(C_1,C_2)$.
4. 验证签名:验证下式$$y^{C_1}\cdot \ C_1^{C_2}\equiv\ g^m\ mod\ p$$ $$C_1\in Z_p$$
5. 原理:这里应用了欧拉定理。
用于加密
- 生成密钥：确定一个大素数$p$和它的一个原根$g$，在$Z_p$域上选择一个随机数$x$作为密钥，并计算$$y=g^x\ mod\ p$$
$(p,g,y)$作为公钥。 - 加密算法：用$m$表示待加密信息，在$Z_p$域上选择一个与$p-1$互质的数$k$，并计算$$C_1=g^k\ mod\ p$$
$$C_2=y^k\cdot m\ \ mod\ p$$ - 输出密文$(C_1,C_2)$
- 解密算法:计算下式$$m=C_2\cdot(C_1^x)^{-1}\ \ mod\ p$$
这里需运用Ext_Euclidean算法求乘法逆元。