2.DSS，即DSA，當初的設(shè)計是用于數(shù)字簽名而不用于密鑰交換的算法，最初的設(shè)計是用來替換RSA的，是在ElGamal和Schorr數(shù)字簽名方案的基礎(chǔ)上設(shè)計的，這里不詳細介紹這兩個算法，有興趣的同學可以自己去找找相關(guān)資料。與DH一樣的密碼數(shù)學基礎(chǔ)，即素數(shù)域上中的模冪運算，最重要的區(qū)別構(gòu)造p(大素數(shù))時要使p-1可以被另一個稱作q的素數(shù)除盡。與RSA不同的是，DSA簽名結(jié)果是由兩個值r和s(160位)組成。

算法原理：

1）參數(shù)介紹

p：L bits長的素數(shù)。L是64的倍數(shù)，范圍是512到1024；

q：p - 1的160bits的素因子；

g：g = h^((p-1)/q) modp，h滿足h < p - 1, h^((p-1)/q)mod p > 1；

x：x <q，x為私鑰；

y：y = g^x mod p ，( p, q, g, y )為公鑰；

以上參數(shù)中p, q, g以及y為公匙，x為私匙必須保密!任何第三方用戶想要從Y解密成X 都必須解決整數(shù)有限域離散對數(shù)難題。

注：

a)、整數(shù)p, q,g 可以公開，也可僅由一組特定用戶共享。

b)、私鑰x 和 公鑰 y 稱為一個密鑰對 (x,y) ，私鑰只能由簽名者本人獨自持有，公鑰則可以公開發(fā)布。密鑰對可以在一段時間內(nèi)持續(xù)使用。

2）簽名過程

P產(chǎn)生隨機數(shù)k，k < q；

P計算r = ( g^k mod p ) modq

s = ( k^(-1) (H(m) + xr)) modq

簽名結(jié)果是( m, r, s)。

注：

a)、k^(-1) 表示整數(shù)k關(guān)于某個模數(shù)的逆元，并非指k 的倒數(shù)。k在每次簽名時都要重新生成。逆元：滿足(a*b) mod m =1的a和b互為關(guān)于模數(shù)m 的逆元，表示為 a=b^(-1)或 b=a^(-1) ,如 (2*5) mod 3 = 1， 則 2 和 5 互為 模數(shù)3 的逆元。BTW:有興趣實現(xiàn)的童鞋，可以參照GNUMP, 求k的模數(shù)逆元可以用GNU MP的mpz_invert函數(shù).

b)、SHA(M)：M的Hash值，M為待簽署的明文或明文的Hash值。SHA是Oneway-Hash函數(shù)，DSS中選用SHA1( FIPS180: Secure Hash Algorithm)，此時SHA(M) 為160bits長的數(shù)字串（16進制），可以參與數(shù)學計算（事實上SHA1函數(shù)生成的是字符串，因此必須把它轉(zhuǎn)化為數(shù)字串）。

c)、最終的簽名就是整數(shù)對( r , s )，它們和 M一起發(fā)送到驗證方。

d)、盡管r 和 s 為 0 的概率相當小，但只要有任何一個為0, 必須重新生成 k，并重新計算 r和 s 。

3）驗證過程

w =s^(-1)mod q

u1 = (H( m ) * w ) mod q

u2 = (r * w ) mod q

v = ((g^u1 * y^u2 ) mod p ) mod q

若v = r，則認為簽名有效。

注：

a)、驗證通過說明：簽名( r, s )有效，即(r , s , M )確為發(fā)送方的真實簽名結(jié)果，真實性可以高度信任，M 未被竄改，為有效信息。

b)、驗證失敗說明：簽名( r , s )無效，即(r, s , M) 不可靠，或者M被竄改過，或者簽名是偽造的，或者M的簽名有誤，M 為無效信息。

舉個簡單的例子：

參數(shù)選?。?/b>

1)取p=23，q=11是(p-1)=22的素因子。(p-1)/q=2(這兩個數(shù)基本上是符合條件的比較小數(shù)字了，如果q取的太小，后面很多地方取值就體現(xiàn)不出來了))

2)g =h^((p-1)/q) mod p。取h=12，g=12^2 mod 23 =6<>1，滿足條件，生成Zp*中唯一的q階循環(huán)了群。

3)選擇x=8，滿足1<8<q

4)計算y= g^x mod p=6^8 mod 23 = 1679616 mod 23 = 18

所以公鑰p=23,q=11,g=6,y=18

簽名過程：

1)選擇隨機數(shù)k=7, 滿足k<q

2)計算 r = ( g^k mod p ) mod q = (6^7 mod 23) mod 11 = 3 mod 11 =3

3)計算k^(-1) mod q=8

4)為了方便計算，隨便取h(m)=10

5)s=k^(-1)(h(m)+xr) mod q =8*(10+8*3) mod 11 = 8

所以消息m的簽名值r=3,s=8

驗證過程：

1)計算w = (s^-1) mod q = 7

2)計算 u1 = (h(m)*w) mod q = 10*7 mod 11 = 4

3)計算 u2 = ( r * w ) mod q = 3*7 mod 11 = 10

4)計算v = (( g^u1 * y^u2 ) mod p ) mod q = ((6^4*18^10) mod23)mod11=3 mod 11 = 3

最后判斷v是否與r相等，以決定是否通過了驗證

證明公式：

因為：r=(g^k mod p) mod q;

s=(h(m)+xr)k^(-1) mod q;

w=s^(-1) mod q

u1 =(h(m)*w) mod q

u2 = (r * w ) mod q

v = ((g^u1 * y^u2 ) mod p ) mod q

所以：v = (( g^u1 * y^u2 ) mod p ) mod q

= ((g^(h(m)*w) * y^(r*w) mod p ) mod q

= ((g^(h(m)*w) * g^(x*r*w) mod p ) mod q mod p ) mod q

= ((g^((h(m)+(x*r)*w) mod p ) mod q mod p ) mod q

= ((g^(s*k*w) mod p ) mod q mod p ) mod q

= ((g^k mod p ) mod q mod p ) mod q

= r

所以，最后驗證的時候只要v=r的時候，即可認為通過驗證，這個推理等式用到了費爾馬定理：

安全性分析：

DSA只能與SHA-1一起使用，而RSA可以與任何摘要算法一起使用。DSA簽名不包括摘要標識符，所以如果允許多種摘要算法就會使DSA遭受前面RSA里面介紹的那種替換攻擊。DSA主要依賴于整數(shù)有限域離散對數(shù)難題。素數(shù)P 必須足夠大，且p-1至少包含一個大素數(shù)因子以抵抗Pohlig &Hellman算法的攻擊。M一般都應采用信息的HASH值(官方推薦為SHA算法)。DSA的安全性主要依賴于p和g，若選取不當則簽名容易偽造，應保證g對于p-1的大素數(shù)因子不可約。DSA算法在破解時關(guān)鍵的參數(shù)就是X 根據(jù) Y = G^X mod P 只要知道 P，G，Y，Q 且能分解出 X 就可以偽造R，S寫出KeyGen了。個人觀點DSA的安全性要次于ECC 與RSA不相上下。但是有一點，就是DSA算法的驗證過程R，S 是以明文形式出現(xiàn)的，這點很容易被利用。

BTW:與RSA不同的是，RSA是對簽名數(shù)據(jù)“解密”后再比對摘要值，而DSA中摘要值是需要參與計算的。