密码学之公钥密码体系(3):ElGamal算法
密码学之公钥密码体系(3):ElGamal算法
文章目录
1. ElGamal算法
ElGamal算法是基于离散对数求解困难的加密体系。与RSA算法一样,都能用于数据加密和数据签名。但是两者的原理不一样,ELGmal算法基于离散对数问题,而RSA算法基于大数分级困难问题。此外,对于ElGamal算法对于使用相同的私钥,对相同的明文进行加密,每次得到的加密结果却不一样,这是ElGamal算法另一个重要特征。
2. ElGamal算法基本原理
2.1 ElGamal密钥生成
- 随机选择一个大素数
p
p
p
−
1
p-1
p
p
g
g
p
p
g
g
- 随机选择一个整数
x
x
2
≤
x
≤
p
−
2
2≤x≤ p-2
- 计算
y
=
g
x
m
o
d
p
y=g^x mod p
取y
y
2.2 ElGamal加密过程
- 对明文
M
M
k
k
2
≤
k
≤
p
−
2
2≤k≤p-2
k
k
p
−
1
p-1
- 计算:
a
=
g
k
m
o
d
p
a=g^k mod p
b
=
M
∗
y
k
m
o
d
p
b=M*y^k mod p
- 密文对为
(
a
,
b
)
(a,b)
2.3 ElGamal解密过程
- 由密文可得明文
M
M
M
=
b
/
a
x
m
o
d
p
M=b/a^x mod p
其中x
x
- 解密过程和Diffie-Hellman密钥交换过程极为类似。
- 下面给出了加密和解密过程
2.4 ElGamal签名过程
2.4.1 签名:
- 对消息
M
M
k
k
k
k
p
−
1
p-1
- 计算:
a
=
g
k
m
o
d
p
a=g^kmodp
- 利用扩展欧几里得算法,求出
b
b
M
=
(
x
a
+
k
b
)
m
o
d
(
p
−
1
)
M=(xa+kb)mod(p-1)
- 签名结果为(a,b)。需要注意的是,k需要保密。
2.4.2 验签:
- 需要验证下面公式成立:
y
a
a
b
m
o
d
p
=
g
M
m
o
d
p
y^aa^bmodp=g^Mmodp
- 下面给出签名和验签的大致流程
- 需要注意的是,在每次使用ElGamal算法进行签名时,都需要更新随机数k。
2.4.3 具体案例:
- 选择
p
=
11
,
g
=
2
p=11,g=2
x
=
8
x=8
y
=
g
x
m
o
d
p
=
>
y
=
2
8
m
o
d
11
=
3
y=g^xmodp => y=2^8 mod 11 = 3
- 因此,公开秘钥是
y
=
3
,
g
=
2
,
p
=
11
y=3,g=2,p=11
- 对消息
M
=
5
M=5
k
=
9
k=9
g
c
d
(
9
,
10
)
=
1
gcd(9,10)=1
a
=
g
k
m
o
d
p
=
2
9
m
o
d
11
=
6
a=g^kmodp=2^9mod11=6
利用欧几里得算法求b
b
M
=
(
a
x
+
k
b
m
o
d
(
p
−
1
)
)
M=(ax+kbmod(p-1))
5
=
(
8
∗
6
+
9
∗
b
)
m
o
d
10
5=(8*6 + 9*b)mod10
求解得到b
=
3
b=3
(
a
,
b
)
(a,b)
(
6
,
3
)
(6,3)
- 验签上述签名的正确性,只需要验证下面:
y
a
a
b
m
o
d
p
=
g
M
m
o
d
p
y^aa^bmodp=g^Mmodp
3
6
6
3
m
o
d
11
=
2
5
m
o
d
11
3^66^3mod11=2^5mod11
2.5 ElGamal算法软件算法实现的快慢
具有
160
b
i
t
160 bit
160bit的指数的ElGamal算法对不同模数长度的快慢表