DSA 数字签名算法

Digital Signature Algorithm (DSA)是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(DigitalSignature Standard)。

(文尾梳理了对不同消息M,重用k时候带来的威胁..)

算法描述:

参数: 全局公钥为 {p, q, g, y} :

p : L bits长的素数.L是64倍数,范围[512, 1024]
q : p - 1的160bits素因子
g : g = h^((p-1)/q) mod p
  其中 h满足h < p - 1, h^((p-1)/q) mod p > 1
x : x < q, x 为私钥
y : y = g^x mod p

签名过程

对于报文m, 挑选秘密随机数k: k ∈ (0, q)
r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q
签名结果即为(m, r, s)

验算过程

w = s^(-1)mod q
a = ( H( m ) * w ) mod q
b = ( r * w ) mod q
v = (( g^a * y^b ) mod p ) mod q
若v = r，则认为签名有效。

可以代入参数理一下验算过程
g^a = g ^{(H(m)*w)mod q} mod p
y^b = g^{x*r*w mod q} mod p
则上两式相乘是在mod p条件下的, 指数是在mod q条件下的,下面省略mod运算符
相乘结果(式一) = g^{(H(m)*w + x*r*w)} = g^{w*(H(m) + x*r)}
因为 H(m) + x * r = k * s = s * k 所以 式一 又等于 g^(w*s*k)
又因为 w = s^-1mod q 所以上式,再加上完整的mod运算符,即
g^{(k mod p)} mod q, 亦即v.

代码实现

这里只列出签名函数的实现. 依赖的库是 NTL 库. 链接在此下载后安装方法见

For a detailed guide to installation, please see the appropriate documentation: 
   * doc/tour-unix.html for unix systems
   * doc/tour-win.html for Windows and other systems
一般NTL又需要gmp库, 也有教程,在文档
   * tour-gmp.html

列几个这里会经常要查询的链接:

这里我的数据存放:
私钥放在 privateKey.data :
x 988656368...
公钥放在 publicKey.data :
p 344457347...
q 169861902...
...
即,先是一个标识,后是数据,方便代码理解(简书不能折叠显得好冗长..也没太多理解的地方..当作是熟悉一下NTL...)
SHA-3的接口,项目官网上的尝试了很久都失败了..包括make pack等等等等..
最终是改写了一下这里的SHA-3实现, 得到了一个能方便#include后调用返回hash值的函数.
只给出签名函数了,因为简单的计算意义不大,函数在上面链接可查:

void signing(char* fileName) {
    string fileDir = "./key/publicKey.data";
    fstream pubf(fileDir, ios::in);
    /* checkFile是一个简单的封装的检查文件状态的函数*/
    if (!checkFile(pubf, fileDir))
        return;

    fileDir = "./key/privateKey.data";
    fstream prif(fileDir, ios::in);
    if (!checkFile(prif, fileDir))
        return;
    
    pubf.seekg(0);
    prif.seekg(0);
    char tmp;
    pubf >> tmp >> p >> tmp >> q >> tmp >> g >> tmp >> y;
    prif >> tmp >> x;

    pubf.close();
    prif.close();

    ZZ k, r, s, hm;
    hm = getHash(fileName);
    /*k -> (0, q - 1)*/
    k = RandomBnd(q - 1) + 1;            
    r = PowerMod(g, k, p) % q;
    s = (InvMod(k, q) * (hm + x * r)) % q;

    fileDir = "./signatureResult.data";
    fstream resf(fileDir, ios::out);
    if (!resf.is_open()) {
        cerr << "create ./signatureResult.data failed" << endl;
        return;
    }

    resf << "r " << r << "\n"
        << "s " << s << "\n";
    resf.close();
    fprintf(stdout,
            "----------------------------------------\n"
            " digital signature done ! \n"
            " in file : ./signatureResult.data \n"
            "----------------------------------------\n"
           );
}

注意几个地方 :
p是一个大素数,q是p-1的素因子,我选择的方法是: 先得到一个素数q,再去找素数p. 其次我的q并非160bits, 而是比H(m) 和 x,r都大,即满足指数在域内可逆的一个更大的素数.

对于不同消息M1,M2 重用私密随机数k带来的威胁

OTZ

考试的时候没写出来..额..额..额...额! 额..

记录2种解法(我不...只..搬运工):
[1] 解方程法:
对于报文m, 挑选秘密随机数k: k ∈ (0, q)
r = ( g^{k mod p} ) mod q
s = ( k^-1(H(m) + xr)) mod q
其中x为私钥. 两个消息M1 M2, 即有
{M1, r, s1}, 其中s1 = k^-1(H(M1)+xr) % q
{M2, r, s2}, 其中s2 = k^-1(H(M2)+xr) % q 则有
式2 : ks1 = H(M1)+xr % q
式3 : ks2 = H(M2)+xr % q
式2 * s2 = 式3 * s1 = ks1s2
即 s1H(M2) + s1xr = s2H(M1) +s2xr
移项,提取公因式即可有
x = (s2H(M1) - s1H(M2))(s1 - s2)^-1r^-1 % q
其中s都已知,H(x)可自行hash计算,又因为 q是素数,且s1 != s2, 所以(s1-s2)^-1是存在的(域的性质,封闭性).当然,r^-1也存在.所以上式右边式子所有元素均已知或者可计算,私钥x将会暴露.

[2] 求k再直接通过s求x痛苦没想出来法
s1 - s2 = k^-1(H(M1) - H(M2)) % q
k = (H(M1) - H(M2)) * (s1 - s2)^-1
这里得到了k
又由 s1 = ( k^-1(H(M1) + xr)) mod q
有式子x = (ks1 - H(M1)) r^-1
也可以用s2来得x的表达式
同解法一理,右边各元素均可求/已知,所以私钥x将会暴露.

按理说,到这里就该狼狈溜了..
再贴一个小工具吧,挺方便的.解决命令行的参数交互问题. 省得自己写一堆分支和判断..
相关博客写得挺通俗易懂
大概用起来会是这样:

int main(int argc, char* argv[]) {
    int users_option;
    puts("");
    if (argc == 1) usage();
    while ((users_option = getopt(argc, argv, "s:v:gh")) != -1) {
        switch (users_option) {
            case 's' :
                signing(optarg); break;
            case 'v' :
                verifying(optarg); break;
            case 'g' :
                generate_key(); break;
            case 'h' :
            case '?' :
                usage(); break;
        }
    }
    return 0;
}