Digital Signature Algorithm (DSA)是Schnorr和ElGamal簽名算法的變種斤寂，被美國(guó)NIST作為DSS(DigitalSignature Standard)拖刃。
(文尾梳理了對(duì)不同消息M,重用k時(shí)候帶來的威脅..)
算法描述:
參數(shù): 全局公鑰為 {p, q, g, y} :
p : L bits長(zhǎng)的素?cái)?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
簽名過程
對(duì)于報(bào)文m, 挑選秘密隨機(jī)數(shù)k: k ∈ (0, q)
r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q
簽名結(jié)果即為(m, r, s)
驗(yàn)算過程
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辟拷，則認(rèn)為簽名有效。
可以代入?yún)?shù)理一下驗(yàn)算過程
ga = g (H(m)*w)mod q mod p
yb = gx*r*w mod q mod p
則上兩式相乘是在mod p條件下的, 指數(shù)是在mod q條件下的,下面省略mod運(yùn)算符
相乘結(jié)果(式一) = g(H(m)*w + x*r*w) = gw*(H(m) + x*r)
因?yàn)?H(m) + x * r = k * s = s * k 所以 式一 又等于 g(w*s*k)
又因?yàn)?w = s-1mod q 所以上式,再加上完整的mod運(yùn)算符,即
g(k mod p) mod q, 亦即v.
代碼實(shí)現(xiàn)
這里只列出簽名函數(shù)的實(shí)現(xiàn). 依賴的庫(kù)是 NTL 庫(kù). 鏈接在此 下載后安裝方法見
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庫(kù), 也有教程,在文檔
* tour-gmp.html
列幾個(gè)這里會(huì)經(jīng)常要查詢的鏈接:
這里我的數(shù)據(jù)存放:
私鑰放在 privateKey.data :
x 988656368...
公鑰放在 publicKey.data :
p 344457347...
q 169861902...
...
即,先是一個(gè)標(biāo)識(shí),后是數(shù)據(jù),方便代碼理解(簡(jiǎn)書不能折疊顯得好冗長(zhǎng)..也沒太多理解的地方..當(dāng)作是熟悉一下NTL...)
SHA-3的接口,項(xiàng)目官網(wǎng)上的嘗試了很久都失敗了..包括make pack等等等等..
最終是改寫了一下這里的SHA-3實(shí)現(xiàn), 得到了一個(gè)能方便#include后調(diào)用返回hash值的函數(shù).
只給出簽名函數(shù)了,因?yàn)楹?jiǎn)單的計(jì)算意義不大,函數(shù)在上面鏈接可查:
void signing(char* fileName) {
string fileDir = "./key/publicKey.data";
fstream pubf(fileDir, ios::in);
/* checkFile是一個(gè)簡(jiǎn)單的封裝的檢查文件狀態(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"
);
}
注意幾個(gè)地方 :
p是一個(gè)大素?cái)?shù),q是p-1的素因子,我選擇的方法是: 先得到一個(gè)素?cái)?shù)q,再去找素?cái)?shù)p. 其次我的q并非160bits, 而是比H(m) 和 x,r都大,即滿足指數(shù)在域內(nèi)可逆的一個(gè)更大的素?cái)?shù).
對(duì)于不同消息M1,M2 重用私密隨機(jī)數(shù)k帶來的威脅
考試的時(shí)候沒寫出來..額..額..額...額! 額..
記錄2種解法(我不...只..搬運(yùn)工):
[1] 解方程法:
對(duì)于報(bào)文m, 挑選秘密隨機(jī)數(shù)k: k ∈ (0, q)
r = ( gk mod p ) mod q
s = ( k-1(H(m) + xr)) mod q
其中x為私鑰. 兩個(gè)消息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
移項(xiàng),提取公因式即可有
x = (s2H(M1) - s1H(M2))(s1 - s2)-1r-1 % q
其中s都已知,H(x)可自行hash計(jì)算,又因?yàn)?q是素?cái)?shù),且s1 != s2, 所以(s1-s2)-1是存在的(域的性質(zhì),封閉性).當(dāng)然,r-1也存在.所以上式右邊式子所有元素均已知或者可計(jì)算,私鑰x將會(huì)暴露.
[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的表達(dá)式
同解法一理,右邊各元素均可求/已知,所以私鑰x將會(huì)暴露.
按理說,到這里就該狼狽溜了..
再貼一個(gè)小工具吧,挺方便的.解決命令行的參數(shù)交互問題. 省得自己寫一堆分支和判斷..
相關(guān)博客 寫得挺通俗易懂
大概用起來會(huì)是這樣:
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;
}
