ElGamal加密算法|ElGamal签名算法|公钥密码|数字签名|密码学|信息安全
ElGamal签名算法
密钥产生
- 确定一个大素数p
- 取p的一个本原根g
- 在Zp域上选择一个随机数x
- y = gx%p
- (y, g, p)为公钥,x为私钥
签名算法
设待签名的消息为m
- C1=gk%p
- C2=(H(m)-x*C_1) * k-1%(p-1)
- 输出签名(C1,C2)和消息m
验证算法
-
y
C
1
∗
C
1
C
2
=
H
(
m
)
y^{C_1}*C_1^{C_2}=H(m)
正确性证明
ElGamal加密算法
简单介绍
-
EIGamal密码是除了RSA密码之外最有代表性的公开密钥密码
-
EIGamal是建立在离散对数的困难问题上的一种公钥体制密码
密钥产生
- 选一个素数
p
,以及小于p
的两个随机数g
和x
- 计算
y
=
g
x
y = g^x
- 公钥为
(y, g, p)
,私钥为x
算法加密过程
M
为明文
- 选取一个与
p-1
互素的整数k
-
C
1
=
g
k
C_1=g^k
-
C
2
=
y
k
M
C_2=y^kM
-
(
C
1
,
C
2
)
(C_1,C_2)
算法解密过程
解密方法:
C
2
C
1
x
frac{C_2}{C_1^x}
C1xC2%p
证明:
EIGamal 密码体制安全性
由于私钥x是通信双方共享的,别人不知道
所以,当加密完了以后的密文(y, g, p)
被别人盗取后,想获取明文M
,只能通过
C
2
=
y
k
M
C_2=y^kM
C2=ykM%p来获得,这里面只有k
和M
是不知道的,所以只要获得了k
就能获得M
,而想获得k
,只有通过
C
1
=
g
k
C_1=g^k
C1=gk%p来获取,这里面虽然只有k
是未知数,但是求离散对数的过程是很困难的,尤其是对p很大的情,所以EIGamal密码体制很安全
举个例子
- 取p=11, g=5, x=2
- 则 y = g x%p = 3
- 取 k 为 7, m为10
- 则C1 = gk%p = 3
- C2 = yk*m % p = 2
- 则C1x%p= 9
- 9在模11下的逆元为5
- 所以
C
2
C
1
x
=
2
∗
5
frac{C_2}{C_1 ^x}=2 * 5
ElGamal签名算法
密钥产生
- 确定一个大素数p
- 取p的一个本原根g
- 在Zp域上选择一个随机数x
- y = 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
验证算法
-
y
C
1
∗
C
1
C
2
=
g
H
(
m
)
y^{C_1}*C_1^{C_2}=g^{H(m)}
正确性证明
举个例子
- p = 11
- g = 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
- 验证:计算
y
C
1
∗
C
1
C
2
y^{C_{1}} * C_{1}^{C_2}
- 计算Hg%p=1
- 所以验证成功