区块链与密码学全民课堂第6-3讲：数字签名算法大合集

导语：本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事，从感兴趣到有乐趣，全民课堂等你来学。这个系列中的课程内容首先从比特币着手进行入门介绍，再延伸至区块链的相关技术原理与发展趋势，然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号，持续进行学习。

6.3 其他数字签名算法

– EIGamal算法 –

数字签名一般利用公钥密码技术来实现，其中私钥用来签名，公钥用来验证签名。ElGamal公钥密码算法是在密码协议中有着重要应用的一类公钥密码算法，其安全性是基于有限域上离散对数学问题的难解性。它至今仍是一个安全性良好的公钥密码算法。它既可用于加密又可用于数字签名的公钥密码体制。

假设p是一个大素数，g是GF(p)的生成元。Alice的公钥为y = g^x mod p, g，p私钥为x。

签名算法：

• Alice用H将消息m进行处理，得h=H(m).

• Alice选择秘密随机数k，满足

0<k< p-1，且(k, p-1)=1

计算

• Alice将(m，r，s)发送给Bob

验证签名过程：

接收方收到M与其签名(r，s)后：

• 计算消息M的Hash值H(M)

• 验证公式

成立则确认为有效签名，否则认为签名是伪造的

上述方案的安全性是基于如下离散对数问题的：已知大素数p、GF(p的生成元g和非零元素y∈GF(p)，求解唯一的整数k, 0≤k≤p – 2，使得y≡g^k (mod p)，k称为y对g的离散对数。

在1996年的欧洲密码学会(Proceedings of EUROCRYPT 96)上，David Pointcheval和Jacques Stern给出一个ElGamal签名的变体，并基于所谓分叉技术证明了在随机预言模型下所给方案是安全的(在自适应选择消息攻击下能抗击存在性伪造)。

– Schnorr算法 –

Schnorr签名方案是一个短签名方案，它是ElGamal签名方案的变形，其安全性是基于离散对数困难性和哈希函数的单向性的。

假设p和q是大素数，是q能被p-1整除，q是大于等于160 bit的整数，p是大于等于512 bit的整数，保证GF(p)中求解离散对数困难；g是GF(p)中元素，且g^q≡1mod p。

密钥生成： 

Alice选择随机数x为私钥，其中1<x<q； 

Alice计算公钥y≡g^x (mod p)

签名算法：

①Alice首先随机数k，这里1<k<q； 

②Alice计算e=h(M, g^k mod p)

③Alice计算s=k–x·e(mod q) 

④Alice输出签名(e, s) 

验证算法：

Bob计算g^kmod p=g^s·y^e mod p 

Bob验证e = h(M, g^k mod p)是否成立，如果成立则输出「Accept」，否则输出「Reject」。

Schnorr签名与ElGamal签名的不同点：

安全性比较：在ElGamal体制中，g为域GF(p)的本原元素；而在Schnorr体制中， g只是域GF(p)的阶为q的元素，而非本原元素。因此，虽然两者都是基于离散对数的困难性，然而ElGamal的离散对数阶为p-1， Schnorr的离散对数阶为q<p-1。从这个角度上说， ElGamal的安全性似乎高于Schnorr。

签名长度比较：Schnorr比ElGamal签名长度短

ElGamal：(m，r，s)，其中r的长度为|p|， s的长度为|p-1|

Schnorr：(m，e，s)，其中e的长度为|q|， s的长度为|q|

– DSA算法 –

1991年，美国政府颁布了数字签名标准(Digital Signature Standard, DSS)，也称为数字签名算法(Digital Signature Algorithm, DSA) 。

和DES一样，DSS也引起了激烈的争论，反对者认为：密钥太短、效率不如RSA高、不能实现数据加密并怀疑NIST在DSS中留有后门。

随后，美国政府对其做了一些改进，目前DSS的应用已经十分广泛，并被一些国际标准化组织采纳为国际标准。2000年，美国政府将RSA和椭圆曲线密码引入到数字签名标准中，进一步丰富了DSA算法。

DSA的主要参数：

全局公开密钥分量，可以为用户公用

p：素数，要求2^L-1<p<2^L,512<=L<1024，且L为64的倍数

q : (p-1)的素因子，2¹⁵⁹<q<2¹⁶⁰，即比特长度为160位

g : =h^(p-1)/q mod p.其中h是一整数，1<h<(p-1)且üh^(p-1)/q mod p>1

用户私有密钥

x：随机或伪随机整数，要求0<x<q

用户公开密钥

y：=g^x mod p 

随机数k  

随机或伪随机整数，要求0<k<q 

DSA签名过程：

• 用户随机选取k

• 计算e=h(M)；

• 计算r=(g^k mod p) mod q 

• 计算s=k^-1(e+x · r) mod q

• 输出(r, s)，即为消息M的数字签名

DSA验证过程：

• 接收者收到M, r, s后，首先验证0<r<q, 0<s<q

• 计算e=h(M)； 

• 计算w=(s)^-1 mod q  

• 计算u₁=e · w mod q 

• 计算u₂=r · w mod q

• 计算①v=[(g^u1 · y^u2) mod p] mod q

• 如果v=r，则确认签名正确，否则拒绝

今天的课程就到这里啦，下一堂课我们将学习基于椭圆曲线的数字签名算法，带大家继续了解数字签名，敬请期待！

同学们可以关注PlatON World，持续学习哦。我们下节课见啦。