一.ElGamal数字签名方案
1.1 知识引用
ElGamal数字签名使用私钥进行加密,使用公钥进行解密。
基本元素是p和α,α是p的原根,用户产生私钥/公钥对的方法如下。
数字签名的过程为:
(1) 选择随机整数K,K和q-1互素。
(2)S1=α^Kmod(q)
(3) 计算K^-1mod(q-1)
(4) S2=K^-1(m-XAS1)mod(q-1)。m=H(M),是M在哈希函数H下的哈希值,满足0<=m<=q-1的整数
(5) (S1,S2)为签名
验证签名的方法为:
证明为:
1.2 例题
ElGamal数字签名方法:模数q=19,选取随机数K=11,对消息m=4的签名(S1,S2)=(2,4)。
(1)若敌手知晓K=11,请写出计算出私钥XA的过程。
由前文数字签名的过程(4)
即得到
4=5×(4-2×XA) mod (18) XA 取值在1和18之间
XA=7
PS:
求K逆的过程比较简单的可以使用欧几里得除法,如本题可求得为5
(2)若敌手不知晓K,但敌手截获另一也选取同一随机数K的对m'=17的签名(2,15),则其也可以计算出私钥XA,请写出计算过程
解得XA=(18n-8)/22,XA=7.
二、ElGamal公钥密码算法描述
2.1算法介绍
1. 选取一个大素数p,使离散对数问题在有限域GF(p)上是难解的,选取g∈Z是一个本原元。
2. 随机选取整数x,1≤x≤p-2,计算y=g^x(mod p); y是公开的加密密钥,而x是保密的脱密密钥。
3. 明文空间为Z,密文空间为Z×Z。
4. 加密变换:对任意明文m∈Z,秘密地随机选取一个整数k,1≤k≤p-2,于是可得密文为:
c=(c1,c2)
其中
c1=g^k(mod p) , c2=my^k(mod p)
5. 脱密变换:对任意密文c=(c1,c2)∈Z×Z,明文为:
m=c2×(c1^x)^-1(mod p)
证明:
c2×(c1^x)^-1(mod p)=my^k(g^(kx))^-1 (mod p)
=mg^kx × g^(-kx) (mod p)=m (mod p)
2.2算法例题
Alice的私钥XA=11,公开参数q=19,α=5。
(1)计算Alice的公钥YA
这里介绍一种模重复平方计算法,计算过程如下:
结果是6
(2)选取k=3,计算对M=7用Alice的公钥加密后得到的密文。
(3)Alice收到密文C=(4,7),用私钥对密文解密,求其得到的明文。文章来源:https://www.toymoban.com/news/detail-793830.html
文章来源地址https://www.toymoban.com/news/detail-793830.html
到了这里,关于ElGamal算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!