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