ElGamal

ElGamal算法

此时有一个需被加密的消息x。

密钥生成：

随机取一个大素数p，并取Z_p^*的一个本原元作为α，再从{2,…,p-2}中随机取一个数作为d,计算β ≡ α^d mod p 。({d}为私钥，{p,α,β}为公钥。)

加密：

再次从{2,…p-2}中随机取一个数作为r,计算k_r≡α^r mod p。计算k_m≡β^r mod p。

计算y≡k_m*x mod p，y就是加密出的密文。

解密：

计算x≡（k_r^d )^-1*y mod p 得出x。

ElGamal协议

ElGamal协议是对ElGamal方案的正式定义。

为了方便描述，我们先假设有Alice和Bob这两个人。

为了保证消息的私密性，二人决定对传递的消息加密。

首先，Bob随机取一个大素数p，并取Z_p^*的一个本原元作为α，在从{2,…,p-2}中随机取一个数字作为d,并计算β≡α^d mod p。

Bob将p和α对外公开，并将（p,α,β）作为公钥k_pub发送给Alice。

Alice从{2,…,p-2}中选择一个数作为r,计算k_r ≡ α^r mod p。计算k_m ≡ β^r mod p。

并将消息x（x的长度必须小于p）通过y≡x*k_m mod p加密成y。最后，Alice将(k_r,y)发送给Bob。

Bob通过k_m ≡ k_r^d mod p 计算出掩码密钥k_m，而后再通过计算x ≡ y*k^-1 mod p得到x。

ElGamal协议的验证

Alice需加密的消息为x=11。

Bob生成一个素数P=13，取α=2。选择d=8，则可以计算出β=9。而后Bob将（p,α,β）作为k_pub发送给Alice。

Alice选择r=5,计算出k_r=α^r ≡ 6 mod 13,再计算出k_m=β^r ≡ 3 mod 13,再对消息x进行加密，计算y=x*k_m ≡ 7 mod 13。而后再将（k_r , y)发送给Bob。

Bob通过k_m=k_r^d ≡ 3 mod 13,得到了k_m，最后只要计算x=y*k_m^-1 ≡ 11 mod 13，便成功还原出了消息x。

ElGamal加密和解密的代码的简单实现

这里我直接将加密和解密的代码写在一起，方便验证其正确性。代码中的P是提前生成的大素数，af是Z_p^*的一个本原元。（代码是用Python写的。）

from Crypto.Util.number import bytes_to_long,long_to_bytes
import gmpy2 as gp
x=bytes_to_long(bytes(input("please input:"),encoding="utf-8"))
p=25123340539613169448341086263083665422339746291241104014172083032815449631995806048303663356814273919781597336198663028438720363603452541021888997965977983
af=2
d=5#从零到p-2中取随机取一个数，这里直接取5
b=pow(af,d,p)
r=67#从零到p-2中随机去一个数，这里取67
km=b**r%p#计算加密的密钥
y=km*x%p#得出密文
print("密文为：",y)
#*************
#下面这部分是解密代码
#*************
kr=pow(af,r,p)#这里才计算kr是因为只有解密时才需要kr
km=pow(kr,d,p)#计算解密所需密钥
k=gp.invert(km,p)#计算解密的密钥的逆元
dx=y*k%p
print("明文为：",long_to_bytes(dx))