ElGamal加密算法

简单介绍

EIGamal密码是除了RSA密码之外最有代表性的公开密钥密码

EIGamal是建立在离散对数的困难问题上的一种公钥体制密码

密钥产生

选一个素数p，以及小于p的两个随机数g和x计算 y=gxy = g^xy=gx%p公钥为(y, g, p)，私钥为x

算法加密过程

M为明文

选取一个与p-1互素的整数kC1=gkC_1=g^kC1​=gk%pC2=ykMC_2=y^kMC2​=ykM%p(C1,C2)(C_1,C_2)(C1​,C2​)即为密文

算法解密过程

解密方法：C2C1x\frac{C_2}{C_1^x}C1x​C2​​%p

证明：

EIGamal 密码体制安全性

由于私钥x是通信双方共享的，别人不知道

所以，当加密完了以后的密文(y, g, p)被别人盗取后，想获取明文M,只能通过 C2=ykMC_2=y^kMC2​=ykM%p来获得，这里面只有k和M是不知道的，所以只要获得了k就能获得M，而想获得k，只有通过 C1=gkC_1=g^kC1​=gk%p来获取，这里面虽然只有k是未知数，但是求离散对数的过程是很困难的，尤其是对p很大的情，所以EIGamal密码体制很安全

举个例子

取p=11, g=5, x=2则 y = g x%p = 3取 k 为 7， m为10则C1 = gk%p = 3C2 = yk*m % p = 2则C1x%p= 99在模11下的逆元为5所以 C2C1x=2∗5\frac{C_2}{C_1 ^x}=2 * 5C1x​C2​​=2∗5%10 =10，所以解密成功

ElGamal签名算法

密钥产生

确定一个大素数p取p的一个本原根g在Zp域上选择一个随机数xy = gx%p(y, g, p)为公钥，x为私钥

签名算法

设待签名的消息为m

取一个与p-1互质的k

C1=gk%p

C2=(H(m)-x*C1) * k-1%(p-1)

输出签名(C1,C2)和消息m

验证算法

yC1∗C1C2=gH(m)y^{C_1}*C_1^{C_2}=g^{H(m)}yC1​∗C1C2​​=gH(m)%p

正确性证明

举个例子

p = 11g = 2,(注意必须取p的一个生成元)x = 6计算y = gx%p = 9取 k = 7计算C1=gk%p = 7利用扩展欧几里得计算k在模p-1意义下的逆元k-1= 3假设需要验证的消息m经过哈希后的结果是H = 10则计算C2 = ((H - x * C1) * k-1 ) % (p-1) = 4验证：计算yC1∗C1C2y^{C_{1}} * C_{1}^{C_2}yC1​∗C1C2​​%p = 1计算Hg%p=1所以验证成功

如果觉得《ElGamal加密算法｜ElGamal签名算法｜公钥密码｜数字签名｜密码学｜信息安全》对你有帮助，请点赞、收藏，并留下你的观点哦！