Digital Signature Algorithm (DSA)是Schnorr和ElGamal簽名算法的變種，被美國NIST作為DSS(DigitalSignature Standard)。

(文尾梳理了對不同消息M,重用k時候帶來的威脅..)

算法描述:

參數(shù): 全局公鑰為 {p, q, g, y} :

p : L bits長的素數(shù).L是64倍數(shù),范圍[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, 挑選秘密隨機數(shù)k: k ∈ (0, q)
r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q
簽名結(jié)果即為(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，則認為簽名有效。

可以代入?yún)?shù)理一下驗算過程
g^a = g ^{(H(m)*w)mod q} mod p
y^b = g^{x*r*w mod q} mod p
則上兩式相乘是在mod p條件下的, 指數(shù)是在mod q條件下的,下面省略mod運算符
相乘結(jié)果(式一) = 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.

代碼實現(xiàn)

這里只列出簽名函數(shù)的實現(xiàn). 依賴的庫是 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

列幾個這里會經(jīng)常要查詢的鏈接:

• 大數(shù)ZZ文檔
• 基本使用演示
• 總的幫助文檔

這里我的數(shù)據(jù)存放:
私鑰放在 privateKey.data :
x 988656368...
公鑰放在 publicKey.data :
p 344457347...
q 169861902...
...
即,先是一個標識,后是數(shù)據(jù),方便代碼理解(簡書不能折疊顯得好冗長..也沒太多理解的地方..當作是熟悉一下NTL...)
SHA-3的接口,項目官網(wǎng)上的嘗試了很久都失敗了..包括make pack等等等等..
最終是改寫了一下這里的SHA-3實現(xiàn), 得到了一個能方便#include后調(diào)用返回hash值的函數(shù).
只給出簽名函數(shù)了,因為簡單的計算意義不大,函數(shù)在上面鏈接可查:

void signing(char* fileName) {
    string fileDir = "./key/publicKey.data";
    fstream pubf(fileDir, ios::in);
    /* checkFile是一個簡單的封裝的檢查文件狀態(tài)的函數(shù)*/
    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是一個大素數(shù),q是p-1的素因子,我選擇的方法是: 先得到一個素數(shù)q,再去找素數(shù)p. 其次我的q并非160bits, 而是比H(m) 和 x,r都大,即滿足指數(shù)在域內(nèi)可逆的一個更大的素數(shù).

對于不同消息M1,M2 重用私密隨機數(shù)k帶來的威脅

OTZ

考試的時候沒寫出來..額..額..額...額! 額..

記錄2種解法(我不...只..搬運工):
[1] 解方程法:
對于報文m, 挑選秘密隨機數(shù)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是素數(shù),且s1 != s2, 所以(s1-s2)^-1是存在的(域的性質(zhì),封閉性).當然,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將會暴露.

按理說,到這里就該狼狽溜了..
再貼一個小工具吧,挺方便的.解決命令行的參數(shù)交互問題. 省得自己寫一堆分支和判斷..
相關(guān)博客 寫得挺通俗易懂
大概用起來會是這樣:

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;
}