【文章內(nèi)容簡介】 s.此時(shí) ,因?yàn)橛? 所以攻擊者 E必須計(jì)算離散對數(shù)。 .m o dlo g,m o dp sp gryrM ygrMsr??????(2) 攻擊者已知消息 M,選擇一個(gè)值 s,再求另一個(gè)值 r. 此時(shí) , 他必須從同余方程 中求出 r。這是一個(gè)到目前為止還沒有可行方法求解的方程，甚至也看不出它與離散對數(shù)問題有沒有關(guān)系。 pgry Msr m o d ??35 ElGamal數(shù)字簽名的安全性 ? 1．不知道私鑰的攻擊 ?(3) 攻擊者已知消息 M，同時(shí)求 (r,s). 即他必須從同余方程 中同時(shí)求出 (r,s)?，F(xiàn)在人們對這個(gè)方程的認(rèn)識幾乎是一無所有，既沒有人發(fā)現(xiàn)解這個(gè)問題的方法，也沒有人能夠證明不能解這個(gè)問題。 pgry Msr m o d ??? (4)攻擊者選擇數(shù)據(jù)對 (r,s)，求消息 M。此時(shí)必須計(jì)算離散對數(shù) .m o dlo g pM sr ryg ??36 ElGamal數(shù)字簽名的安全性 ? 1．不知道私鑰的攻擊 ?(5)攻擊者同時(shí)選擇數(shù)據(jù) M， r和 s，使得 (r, s)是 M的簽名。這種攻擊方法可能獲得成功。攻擊者首先選擇整數(shù) i和 j， 0≤i, j≤p?2， gcd( j, p?1)=1，計(jì)算 成立，所以 (r, s) 是消息 M的有效簽名 ?該攻擊方法屬于存在性偽造。因此，在使用 ElGamal數(shù)字簽名方案時(shí)，不要直接對消息進(jìn)行簽名，而應(yīng)該對消息的 Hash值進(jìn)行簽名。 p gg ygyygyry p jirM p jrs p ygr Mi r jri r jrrjjirsrjim o d)().1(m o d),1(m o d,m o d11111?????????????????????????????由于37 ElGamal數(shù)字簽名的安全性 ? 1．不知道私鑰的攻擊 ?例 設(shè) p=467， g=2是 Z467*的本原元，簽名者公鑰y=132。攻擊者選擇整數(shù) i=99， j=179，計(jì)算 ,467m o d3032,467m o d303117132.331466m o d15199117,41466m o d151117,117467m o d1322,151466m o d1793 3 1411 1 71 7 99911 g ry M s r j Msr??????????????????????由于所以（ 117， 41）是消息 M =331的有效簽名。 38 ElGamal數(shù)字簽名的安全性 ? 2．已知消息攻擊 ?假設(shè)攻擊者 E知道 (r, s)是消息 M的簽名 ,則 E可利用它來偽造其它消息的簽名 . 選擇整數(shù) l, i, j,0?l, i, j ? p?2， gcd(lr?js, p?1)=1,計(jì)算 .m o d)(,m o dm o d).1(m o d)()(),1(m o d)(,m o d1111111111)()(}))((1{)()()()()()()()(11p ggy gy gry ygryuyp gyr p gryp sjrlsiMluW p sjrlusv p ygru WjslrulMisjslrjslrujslrM l ujslri s ujslrr l ujslrj s uujslri s ujslrh s ujslrj s uujslrsujiluvuMrsMsrjil???????????????????????????????????????????????????????????????????，所以由于 可見 (u, v)是消息 W的有效簽名。 ?該攻擊方法屬于存在性偽造 ?使用對消息的 Hash值進(jìn)行簽名的方式 ,可以抵抗這類攻擊 . 39 ElGamal數(shù)字簽名的安全性 ? 使用 ElGamal數(shù)字簽名方案的安全措施 ?(1) 不要泄露隨機(jī)數(shù) k ).1(m o d)(),1(m o d)(11???????????p rksMx p krxMs 可計(jì)算出私鑰否則，根據(jù)?(2) 不要使用同一個(gè)隨機(jī)數(shù) k給兩個(gè)不同的消息簽名 設(shè)（ r， s）是消息 M的簽名，（ u， v）是消息 W的簽名，使用的是同一個(gè)隨機(jī)數(shù) k，則 可求出私鑰 。 40 ElGamal簽名體制的變形 ? ElGamal數(shù)字簽名算法有多種變形 ?設(shè)大素?cái)?shù) p是模數(shù)， g是一個(gè)模 p的本原元， x為簽名者的私鑰， k為隨機(jī)數(shù)， m為待簽名的消息，（ r， s）是對 M的簽名。簽名值的分量 r=gk mod p, 分量 s由簽名算法確定。 ElGamal數(shù)字簽名各種變形的簽名算法和驗(yàn)證算法見下表。 41 ElGamal簽名體制的變形 42 第 6章 數(shù)字簽名 ? 數(shù)字簽名概念 ? RSA數(shù)字簽名體制 ? ElGamal數(shù)字簽名體制 ? 其它數(shù)字簽名方案 ? 數(shù)字簽名標(biāo)準(zhǔn) ? 應(yīng)用 43 Fiat?Shamir數(shù)字簽名 ? Fiat?Shamir數(shù)字簽名由 A. Fiat和 A. Shamir提出，有時(shí)簡記為 FS數(shù)字簽名。與 RSA數(shù)字簽名相比較， FS數(shù)字簽名的主要優(yōu)勢是速度快，它僅需要 RSA的 1%?4%的模乘法。FS數(shù)字簽名的理論基礎(chǔ)是大整數(shù)素因子分解的困難性。 ? 1．參數(shù)生成 : 選取兩個(gè)大素?cái)?shù) p、 q，令 n=p?q。 n是公開參數(shù)， p和 q是管理中心 CA掌握的密鑰。設(shè) h是一個(gè)公開的Hash函數(shù)， k是一個(gè)固定的正整數(shù)。 ?管理中心 CA為用戶 A產(chǎn)生 k個(gè)公開密鑰： yi (i =1,2,…, k) 是模 n的平方剩余 ?再為用戶 A產(chǎn)生 k個(gè)私鑰（保密） .m o d, . . . ,m o d,m o d 1122111 nyxnyxnyx kk ??? ???44 Fiat?Shamir數(shù)字簽名 ? : 為了對消息 m進(jìn)行簽名 ,用戶 A執(zhí)行以下步驟 ?（ 1）隨機(jī)選取一個(gè)正整數(shù) t。 ?（ 2）在 1和 n之間隨機(jī)選取 t個(gè)正整數(shù) rj (j =1,2,…, t)，并計(jì)算 ).,...,2,1(m o d2 tjnrR jj ?? ?（ 3）計(jì)算 Hash函數(shù)值 h (m|| R1|| R2||…|| Rt)，依次取出其前 k?t個(gè)比特值，記為 ?（ 4）計(jì)算 )., . . . ,2,1。, . . . ,2,1( tjkib ij ?? ).,. ..,2,1(m od1tjnxrs kibijjij ?? ?? ?用戶 A對消息 m的數(shù)字簽名為 )., . . . ,2,1。, . . . ,2,1(}{},{ tjkisb jij ?? 簽名者將數(shù)據(jù)（ m， {bij}， {sj}）發(fā)送給接收者 B 45 Fiat?Shamir數(shù)字簽名 ? 3．驗(yàn)證算法 : 接收方 B收到簽名數(shù)據(jù)（ m,{bij},{sj}）后 , 按以下步驟進(jìn)行驗(yàn)證： ?（ 1）利用 A的公鑰計(jì)算 ?（ 2）計(jì)算 Hash函數(shù)值 依次取出其前 k?t個(gè)比特值，記為 ?（ 3）比較等式 是否成立。如果 k?t個(gè)等式全部成立，則數(shù)字簽名有效。否則，數(shù)字簽名無效。 ).,.. .,2,1(m od12 tj n ysRkibij39。jij ?? ??),||. . .||||||( 21 39。t39。39。 RRRmh)., .. .,