区块链中的密码学之数字签名方案(十二)

前言

签名s应当是秘密数字x,消息的哈希值H(m)和随机数字k的一个函数。s=f(x,H(m),k)

我们如何在不知道x和k的情况下验证该等式呢。

我们可以借助于上章学习的离散对数问题。y=g^x mod p 和r=g^k mod p发送给接受者,不用担心x和k的泄露。一般称x为私钥,y为公钥,<r,s>为数字签名。

签名关系F和签名函数f是等价的,而验签关系G是由F决定的。因此关系F是决定签名方案的关键。

我们最容易想到的一种方案是让 中各数字之间有加法运算,如:

s=x+k+H(m)mod(p-1)

所以,G应当为:g^s≡g^(x+k+H(m)) mod p=g^xg^kg^H(m) mod p≡yr g^H(m) mod p

所以,接收方需要验证关系:g^s≡yr * g^H(m) mod p是否成立就可以验证签名了。

但是目前仍然存在问题,即正常的签名是可以通过验证的啊,但是可能被攻击者进行攻击。攻击者很容易在不知晓x和k的情况下,伪造签名r和s。

那么如何进行伪造呢?

攻击者只要先对s任取一值s’,然后通过解方程g^s≡yr * g^H(m) mod p,得到r'≡g^s'/(y * g^H(m)) mod p。

显然满足上述公式的r'和s'也可以验证通过。

所以我们必须修改方案,可以借助上面学习的离散对数问题,可以让验签方案中的s和都出现在指数上,这样攻击者就必须解决离散对数问题,才可能实施攻击。所以我们需要调整验签方案G和签名方案F。

我们可以将签名关系F修改为:sk≡H(m)+xr (mod (p-1)),则签名函数s为s=(H(m)+xr) /k mod(p-1),即k=(H(m)+xr) /s mod(p-1),所以有:r=g^k mod p=g^(H(m)+xr)/s mod p=g^(H(m))/s * g^(r/s) mod p

在该等式的结果中,仅包含签名<r,s>,公钥y和消息m,不会泄露私钥x,k。所以可以使用该等式作为验签关系:

G:r=g^(H(m))/s * g^(r/s) mod p由于r和s都在指数上,所以攻击者无法伪造签名。

总计一下,我们的DSA的签名方案为:

r=g^k mod p;

s=(H(m)+xr) /k mod(p-1)

验签方案为:

r=g^(H(m))/s * g^(r/s) mod p

事实上,上面的方案还是存在着不足,即为了防止离散对数数学问题不被暴力破解,通常素数p的值需要很大,为了减小数字签名的规模,我们需要采取一定的措施:

选择一个相对较小的整数q,使q满足g^q mod p=1,如果 p取1024比特,那么q就取160比特。

这样,s和q修改为相同的规模,r的大小不变。所以我们需要把r缩减为同等规模。即r修改为

r= (g^(H(m)/s * y^(r/s) mod p)) mod q;

到此,我们总结下,DSA的签名方案为:

签名过程:

第一步,生成参数素数p,素数q,底数 g,满足g^q mod p=1;

第二步,对任意消息m,生成随机数 k,1<k<q;

第三步,计算r=(g^k mod p) mod p,若r=0,重复该步骤;

第四步,计算s=(H(m)+xr)/k mod q,若 s=0,重复该步骤;

第五步,令<r,s>为数字签名。

验证过程:

检查该过程是否成立:

  • 0<r<q;
  • 0<s<q;
  • r=(g^(H(m)/s) * y^(r/s) mod p) mod q;

总结:

第一,为了防止泄露私钥 ,只能公开公钥 ;

第二,为了防止伪造签名,必须在验签方案中让签名出现在指数上;

第三,为了减小数字签名规模,为指数选择一个相对较小的模数。

而这一切都建立在素数域GF(p)中的整数加法、乘法、幂和离散对数的运算性质上。

如果将素数域更换为有限域上的椭圆曲线,运算的对象变为椭圆曲线上的点,那么仍然可以定义出具有类似性质的加法、乘法。参照我们的DSA探秘之路,你自己就可以设计出具有更高安全性的椭圆曲线数字签名方案ECDSA,而ECDSA正是比特币体系使用的数字签名方案。

上一篇:数值分析 解线性方程组的编程实现


下一篇:解决图片上传的浏览器兼容问题