前言

签名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正是比特币体系使用的数字签名方案。