ElGamal加密算法
简单介绍
EIGamal密码是除了RSA密码之外最有代表性的公开密钥密码
EIGamal是建立在离散对数的困难问题上的一种公钥体制密码
密钥产生
选一个素数p
,以及小于p
的两个随机数g
和x
计算 y=gxy = g^xy=gx%p公钥为(y, g, p)
,私钥为x
算法加密过程
M
为明文
选取一个与p-1
互素的整数k
C1=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}C1xC2%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 * 5C1xC2=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签名算法|公钥密码|数字签名|密码学|信息安全》对你有帮助,请点赞、收藏,并留下你的观点哦!