現(xiàn)代密碼學(xué)(第五章)課件

數(shù)字簽名一、雜湊函數(shù)二、數(shù)字簽名的基本概念三、幾種常用的數(shù)字簽名四、特殊用途的數(shù)字簽名2023/7/241一、雜湊函數(shù)雜湊函數(shù)又稱為：（1）Hash編碼；（2）Hash函數(shù)；（3）散列編碼：（4）散列函數(shù)；（5）單向壓縮函數(shù)。2023/7/242一、雜湊函數(shù)在公鑰密碼的內(nèi)容中，已經(jīng)介紹了“單向函數(shù)”的概念。而雜湊函數(shù)是一類特殊的單向函數(shù)。設(shè)數(shù)據(jù)文件是任意長度的比特串x

。在密碼應(yīng)用中，希望有這樣的函數(shù)y=H(x)，滿足（1）將x壓縮成為固定長度的比特串y。（2）不同的x一定要生成不同的y。（3）由y的值無法倒算x的值。（這就是說，希望y的作用相當于x

的“身份識別符號”，或者“摘要”。比如人的指紋、DNA、虹膜等。）2023/7/243一、雜湊函數(shù)一個注解對函數(shù)y=H(x)的前兩條希望是互不相容的。這就是說，在要求“將任意長度的比特串x壓縮成為固定長度的比特串y”時，無法做到“不同的x生成不同的y”。

（散列編碼是原始數(shù)據(jù)文件的壓縮，而不是帶格式的文件的壓縮，如ZIP等）例如：y=H(x)，其中設(shè)x的長度在128到256之間；設(shè)y的固定長度為128。（在這里，比特串x是數(shù)據(jù)文件，必須假設(shè)它“可能是任何一個長度在128到256之間的比特串”。）一共有2128+2129+2130+…+2256個不同的x。一共有2128個不同的y。x的個數(shù)多于y的個數(shù)，必然有不同的x壓縮成相同的y。2023/7/244一、雜湊函數(shù)實際性質(zhì)：雜湊函數(shù)函數(shù)y=H(x)滿足（1）將任意長度的比特串x壓縮成為固定長度的比特串y。（2）已知x，計算y=H(x)很容易；已知y，找一個x滿足y=H(x)卻很困難。這一性質(zhì)稱為單向性。（3）找(x1，x2)，x1≠x2，H(x1)=H(x2)，很困難。這一性質(zhì)稱為無碰撞性。這樣的函數(shù)稱為雜湊函數(shù)。2023/7/245一、雜湊函數(shù)（單向性的準確解釋：或許已經(jīng)知道了許多對(x*，y*)，滿足y*=H(x*)；或許一個新的y確實存在一個x滿足y=H(x)；然而實際找到這樣的x卻很困難，在計算上行不通。無碰撞性的準確解釋：或許已經(jīng)知道了許多對(x*，y*)，滿足y*=H(x*)；或許確實存在(x1，x2)滿足：x1≠x2，H(x1)=H(x2)，實際找到這樣的(x1，x2)卻很困難，在計算上行不通。）

2023/7/246一、雜湊函數(shù)雜湊函數(shù)的性質(zhì)（3）強于性質(zhì)（2），即由無碰撞性能夠得到單向性。例如，設(shè)函數(shù)y=H(x)，x的長度固定為N，y的長度為L。設(shè)每個y有2N-L個x使y=H(x)。（均衡函數(shù)）隨機地取m個x值。則P(有個x值滿足H(x)=y’)=1-(1-2-L)m；P(有兩個x值具有相同的H(x)值)=1-(2L)(2L-1)(2L-2)…(2L-m+1)2-Lm=1-(1-0×2-L)(1-1×2-L)(1-2×2-L)…(1-(m-1)×2-L)。2023/7/247一、雜湊函數(shù)（什么樣的函數(shù)能作為雜湊函數(shù)？這個問題的含義非常廣泛。以下僅舉出幾個簡單的例子說明，什么樣的函數(shù)不能作為雜湊函數(shù)。）2023/7/248一、雜湊函數(shù)例1：設(shè)函數(shù)y=H(x)具有可加性：對任意的x1，x2，H(x1)+H(x2)=H(x1+x2)。這樣的函數(shù)不能作為雜湊函數(shù)。取x1并計算y1=H(x1)；取x2并計算y2=H(x2)。記y=y1+y2。求一個x使得y=H(x)，可以取x=x1+x2。例2：設(shè)函數(shù)y=H(x)具有線性：對任意的x，a，aH(x)=H(ax)。這樣的函數(shù)不能作為雜湊函數(shù)。取x1并計算y1=H(x1)。記y=ay1。求一個x使得y=H(x)，可以取x=ax1。2023/7/249一、雜湊函數(shù)例3：設(shè)函數(shù)y=H(x)具有局部置換性：x的第一個比特總等于y的第三個比特，無論x為何值。這樣的函數(shù)不能作為雜湊函數(shù)。取x1并計算y1=H(x1)。取y為將y1改變第三個比特。求一個x使得y=H(x)，可以取為將x1改變第一個比特。例4：設(shè)函數(shù)y=H(x)具有某種連續(xù)性：當y1與y2“距離很近”時，存在x1與x2“距離很近”

，且y1=H(x1)，y2=H(x2)。這樣的函數(shù)不能作為雜湊函數(shù)。取x1并計算y1=H(x1)。取y2與y1“距離很近”。尋找一個x2使y2=H(x2)，只需要在x1的“附近”尋找，搜索量遠遠低于窮舉搜索。2023/7/2410一、雜湊函數(shù)例4：設(shè)函數(shù)y=H(x)，y的固定長度太小。這樣的函數(shù)不能作為雜湊函數(shù)，因為可以用窮舉的方法進行碰撞攻擊。設(shè)y的固定長度為8。注意到不同的y的值的個數(shù)有28=256個。取257個不同的x，并對每個x計算y=H(x)，得到了257個y。這257個y必然有兩個具有相同的值。2023/7/2411一、雜湊函數(shù)由此可見，雜湊函數(shù)y=H(x)不能具有任何“整齊”的性質(zhì)，并且x的任一個比特影響y的每一個比特，就像揉面一樣，達到充分的混淆和擴散。此外，y的長度不能太短，一般在128以上，以防止用窮舉的方法進行碰撞攻擊。我們發(fā)現(xiàn)，雜湊函數(shù)的設(shè)計準則頗像分組密碼的設(shè)計準則。所不同的是，分組密碼不具有壓縮功能。2023/7/2412一、雜湊函數(shù)散列編碼的用途用途一：公平提交方案Alice猜測了一個號碼x1，但不知道中獎號碼x2；Bob設(shè)置了中獎號碼x2，但不知道Alice猜測的號碼x1。Alice希望首先獲得x2，然后重新確定x1使得x1=x2。Bob希望首先獲得x1，然后重新確定x2使得x2≠x1。防止兩人作弊的方案稱為“公平提交方案”。兩人使用一個公開的雜湊函數(shù)y=H(x)。方案如下：2023/7/2413一、雜湊函數(shù)（1）Alice計算y1=H(x1)，并將y1發(fā)送給Bob。（2）Bob計算y2=H(x2)，并將y2發(fā)送給Alice。（3）Alice收到y(tǒng)2后，將x1發(fā)送給Bob。（4）Bob收到y(tǒng)1后，將x2發(fā)送給Alice。（5）Alice收到x2后，檢驗是否y2=H(x2)，若是則x2是真實的中獎號碼。（6）Bob收到x1后，檢驗是否y1=H(x1)，若是則x1是Alice的真實的猜測號碼。2023/7/2414一、雜湊函數(shù)2023/7/2415一、雜湊函數(shù)方案分析：Alice發(fā)送y1給Bob，Bob發(fā)送y2給Alice，這叫做承諾。Alice發(fā)送x1給Bob，Bob發(fā)送x2給Alice，這叫做踐諾。當承諾值確定以后，無法改變踐諾值。當對方發(fā)送來了承諾值以后，己方無法計算出對方的踐諾值，因而無法“隨機應(yīng)變地”確定自己的踐諾值，以重合或避開對方的踐諾值。綜上所述，雜湊函數(shù)阻止了雙方作弊。2023/7/2416一、雜湊函數(shù)用途二：簡易的身份識別設(shè)Bob擁有Alice的身份密號x2

?，F(xiàn)在Alice需要向Bob證明自己的身份，即要向Bob證明自己知道x2

。但必須通過不安全的公共信道來進行證明。這就是說，信道上有攻擊者Eve在截聽。兩人使用一個公開的雜湊函數(shù)y=H(x)。方案如下：2023/7/2417一、雜湊函數(shù)（1）Alice向Bob發(fā)送信息“我是Alice”。（2）Bob收到信息后，向Alice發(fā)送一個隨機的比特串x1。（3）Alice收到x1后，與自己的身份密號x2聯(lián)立，得到x=(x1，x2)。（4）Alice計算y=H(x)，并向Bob發(fā)送y。（5）Bob收到y(tǒng)后，取出Alice的身份密號x2，并與x1聯(lián)立得到x=(x1，x2)，然后驗證是否y=H(x)，若是則認為“Alice”是真正的Alice；若否則認為“Alice”是假冒的Alice。2023/7/2418一、雜湊函數(shù)2023/7/2419一、雜湊函數(shù)方案分析：設(shè)攻擊者Eve截聽到了Alice和Bob之間的證明全過程。這就是說，Eve知道了隨機比特串x1，知道了雜湊函數(shù)值y=H(x1，x2)，但不知道Alice的身份密號x2。根據(jù)雜湊函數(shù)的性質(zhì)，Eve不可能由x1和y計算出x2。那么，Eve在不知道x2的前提下，能否在以后向Bob冒充Alice呢？如果Bob發(fā)送的x1保持不變，則Eve能夠冒充成功。（見方案）。但每次發(fā)送的x1是隨機的，重復(fù)發(fā)送的概率是微乎其微的。2023/7/2420一、雜湊函數(shù)用途三：數(shù)字簽名的輔助函數(shù)使用了散列編碼的數(shù)字簽名將更加安全。（將在以后介紹）2023/7/2421一、雜湊函數(shù)著名的散列編碼函數(shù)SHA-1，美國政府的安全散列編碼算法標準。MD5，由RSA數(shù)據(jù)安全公司研制的散列編碼算法。（2004年5月，中國山東大學(xué)的尚小云教授攻破了MD5。尚小云的攻擊算法可以在幾分鐘內(nèi)找到一批碰撞）2023/7/2422二、數(shù)字簽名的基本概念數(shù)字簽名應(yīng)該具有的性質(zhì)完整性一個被簽了名的消息，無法分割成為若干個被簽了名的子消息。這一性質(zhì)保證了被簽名的消息不能被斷章取義。（這個性質(zhì)的本質(zhì)是：）當一個簽名消息被分割子消息發(fā)送出去，則簽名已經(jīng)被破壞了，收到消息的人會辨認出簽名是無效的（不合法的）。2023/7/2423二、數(shù)字簽名的基本概念身份唯一性（不可偽造性）被Alice簽名的消息只能由Alice生成。（這個性質(zhì)的本質(zhì)是：）Bob在收到一個“被Alice簽名的消息”時，他有辦法檢驗，該簽名是否真的被Alice簽名的消息。或許攻擊者Eve截獲了大量的被Alice簽名的消息，但他仍然不能偽造出一個新的，別人認可的“被Alice簽名的消息”。如果無論Eve截獲多少被Alice簽名的消息，他偽造新的“被Alice簽名的消息”的成功概率仍然沒有絲毫提高，則稱該簽名算法是零知識的。2023/7/2424二、數(shù)字簽名的基本概念不可否認性（公開可驗證性）被Alice簽名的消息，在未來不能被Alice否認。（這個性質(zhì)的本質(zhì)是：）Bob在收到一個被Alice簽名的消息時，他有辦法向第三方證明該簽名是真的被Alice簽名的消息。如果一個數(shù)字簽名具有不可偽造性，則Bob能夠自行驗證簽名消息的真?zhèn)?；而如果一個數(shù)字簽名具有公開可驗證性，則Bob能夠向他人證明簽名消息的真?zhèn)巍?023/7/2425二、數(shù)字簽名的基本概念公鑰密碼的簽名思想既然要求數(shù)字簽名具有這么多的性質(zhì)，怎樣來構(gòu)造數(shù)字簽名？答案是：以公鑰密碼為基礎(chǔ)的數(shù)字簽名算法才能具有如此強大的信息安全功能?；貞浌€密碼：明文m，密文c。Alice的加密密鑰（公鑰）是z，解密密鑰（私鑰）是k。加密方程c=E(m,z)，解密方程m=D(c,k)。2023/7/2426二、數(shù)字簽名的基本概念公鑰密碼的簽名方案（一）Alice欲發(fā)消息m給Bob。（1）Alice用自己的私鑰k對消息m“解密”s=D(m,k)，s就是對消息m的簽名值，(m，s)就是一個簽名消息。（2）Alice將(m，s)發(fā)送給Bob。（3）Bob收到(m，s)后，用Alice的公鑰z，將消息m與簽名s做如下的檢驗：是否m=E(s,z)。若是則(m，s)是Alice發(fā)送的簽名消息。2023/7/2427二、數(shù)字簽名的基本概念在上述方案中，“密文”變成了消息m，“解密方程”變成了簽名方程s=D(m,k)?！懊魑摹弊兂闪撕灻祍，“加密方程”變成了驗證方程m=E(s,z)。任何人只要擁有Alice的公鑰z，都可以對簽名消息(m，s)進行驗證。是否只有Alice自己才能生成自己的簽名消息呢？2023/7/2428二、數(shù)字簽名的基本概念簽名方案（一）的安全性分析：（1）設(shè)Eve知道Alice的公鑰z，選定消息m，對簽名值s進行偽造。要想讓偽造的簽名值s通過檢驗，Eve必須選擇s滿足驗證方程m=E(s,z)。然而在驗證方程中是解不出s的，必須得到Alice的私鑰k，用簽名方程得到s：s=D(m,k)。這就是說，對事先設(shè)定的消息m來說，簽名消息(m，s)具有身份唯一性和不可偽造性。2023/7/2429二、數(shù)字簽名的基本概念（2）設(shè)Eve知道Alice的公鑰z，設(shè)定簽名值s，反過來對消息m進行偽造。此時消息m的內(nèi)容就不能是選定的。Eve選擇一個“簽名值”s，用驗證方程計算“消息”m=E(s,z)。Eve冒充Alice將(m，s)發(fā)送給Bob。Bob用驗證方程檢驗得m=E(s,z)。于是Bob認為(m，s)就是Alice發(fā)送的簽名消息。攻擊成功。為了抵抗這種攻擊，合法簽名消息(m，s)中的消息m必須是有意義的課文，而不是亂碼。2023/7/2430二、數(shù)字簽名的基本概念公鑰密碼的簽名方案（二）額外使用一個公開的雜湊函數(shù)H。

設(shè)Alice欲發(fā)消息m給Bob。（1）Alice用H將消息m進行處理，得h=H(m)。（2）Alice用自己的私鑰k對h“解密”s=D(h,k)，s就是對消息m的簽名值，(m，s)就是一個簽名消息。（3）Alice將(m，s)發(fā)送給Bob。（4）Bob收到(m，s)后，用Alice的公鑰z，將消息m與簽名s做如下的檢驗：是否H(m)=E(s,z)。若是則(m，s)是Alice發(fā)送的簽名消息。2023/7/2431二、數(shù)字簽名的基本概念在上述方案中，簽名方程是s=D(H(m),k)。驗證方程是H(m)=E(s,z)。任何人只要擁有Alice的公鑰z，都可以對簽名消息(m，s)進行驗證。設(shè)攻擊者Eve知道Alice的公鑰z，他試圖偽造一個(m，s)，讓Bob相信(m，s)是Alice的簽名消息。偽造的(m，s)必須滿足驗證方程H(m)=E(s,z)。2023/7/2432二、數(shù)字簽名的基本概念Eve面臨著兩難問題：如果選定消息m，再匹配簽名值s，則在驗證方程H(m)=E(s,z)中無法解出s。（這是公鑰密碼的基本安全性）如果選定簽名值s，再匹配消息m，則在驗證方程H(m)=E(s,z)中能夠解出H(m)，卻無法得到m。（這是雜湊函數(shù)的性質(zhì)）如此看來，簽名方案（二）似乎具有身份唯一性和不可偽造性。2023/7/2433二、數(shù)字簽名的基本概念簽名方案（二）存在的問題（1）如果給Eve更加寬松的條件，設(shè)他不但知道Alice的公鑰z，而且已經(jīng)截獲了許多Alice的簽名消息(m(1)，s(1))，(m(2)，s(2))，…，(m(N)，s(N))。Eve偽造新的Alice的簽名消息(m，s)是否更加容易？如果允許重復(fù)發(fā)送，則Eve的偽造是輕而易舉的，他只需要發(fā)送(m(n)，s(n))即可。此稱為重放攻擊。2023/7/2434二、數(shù)字簽名的基本概念為了使簽名方案（二）抵抗重放攻擊，通常使用兩種方法：Alice已經(jīng)發(fā)送過的簽名消息必須存儲備案，不得再次發(fā)送。一旦發(fā)現(xiàn)有再次發(fā)送，則肯定是重放攻擊。但Eve可以根據(jù)公鑰密碼的結(jié)構(gòu)缺陷來偽造。比如(m，s)=(m(1)m(2)，s(1)s(2))。第一種方法沒有抵抗這種偽造的能力。

Alice的簽名消息中必須含有時戳。一旦發(fā)現(xiàn)發(fā)送時間過于久遠，則肯定是重放攻擊。但“時間過于久遠”的標準很模糊。2023/7/2435二、數(shù)字簽名的基本概念（2）注意到Alice先得到h=H(m)，再計算出s=D(h,k)。這就要求：公鑰密碼對課文h能夠正確進行解密運算。換句話說，對課文h進行解密運算的結(jié)果，再進行加密就得到h

。事實上，許多公鑰密碼具有如下的性質(zhì)：當某個明文加密得到h，則對h解密再加密就得到h；當h是隨意選擇的，則對h解密再加密很難得到h。

比如，NTRU就是這樣的公鑰密碼。因此NTRU無法用簽名方案（二）來構(gòu)造數(shù)字簽名。2023/7/2436三、幾種常用的數(shù)字簽名RSA數(shù)字簽名RSA的密鑰生成：選擇兩個大的素數(shù)p和q。選擇兩個正整數(shù)e和d，滿足：ed是(p-1)(q-1)的倍數(shù)加1。計算n=pq。Alice的公鑰是（n，e），私鑰是d。簽名方案是上述的簽名方案(二)，額外使用一個公開的雜湊函數(shù)H。設(shè)Alice欲發(fā)消息m給Bob。2023/7/2437三、幾種常用的數(shù)字簽名（1）Alice用H將消息m進行處理，得散列值h=H(m)。（2）Alice用自己的私鑰d對h“解密”得s=hd(modn)。（3）Alice將(m，s)發(fā)送給Bob。（4）Bob用Alice的公鑰e，檢驗是否H(m)=se(modn)。若是則(m，s)是Alice發(fā)送的簽名消息。2023/7/2438三、幾種常用的數(shù)字簽名ElGamal數(shù)字簽名ElGamal的密鑰生成：選擇一個大的素數(shù)p。選擇g為域GF(p)的本原元素。選擇正整數(shù)x。計算y=gx(modp)。Alice的公鑰是（p，g，y），私鑰是x。簽名方案是上述的簽名方案(二)，額外使用一個公開的雜湊函數(shù)H。設(shè)Alice欲發(fā)消息m給Bob。2023/7/2439三、幾種常用的數(shù)字簽名（1）Alice用H將消息m進行處理，得h=H(m)。（2）Alice選擇秘密隨機數(shù)k，滿足0<k<p-1，且(k,p-1)=1，計算r=gk(modp)；

s=(h-xr)k-1(mod(p－1))。（3）Alice將(m，r，s)發(fā)送給Bob。（4）Bob用Alice的公鑰，檢驗是否yrrs=gH(m)(

modp)。若是則(m，r，s)是Alice發(fā)送的簽名消息。2023/7/2440三、幾種常用的數(shù)字簽名Schnorr數(shù)字簽名Alice擁有3個正整數(shù)(p，q，g)，向自己的通信伙伴公開。其中：p是模數(shù)（即將要進行(modp)模數(shù)運算），它是一個素數(shù)，值的范圍在2511到2512之間（即p是一個長度為512的比特串）。q也是模數(shù)（即將要進行(modq)模數(shù)運算），它是一個素數(shù)，2159<q

（即q是一個長度不小于160的比特串），并且q是p-1的一個因子。g是域GF(p)的元素，且gq=1(modp)。2023/7/2441三、幾種常用的數(shù)字簽名Alice選擇x，其中1<x<q。Alice計算y=gx(modp)。Alice的公鑰是(p，q，g，y)，Alice的私鑰是x。簽名方案是上述的簽名方案(二)，額外使用一個公開的雜湊函數(shù)H，H的輸出長度是160比特。設(shè)Alice欲發(fā)消息m給Bob。2023/7/2442三、幾種常用的數(shù)字簽名（1）Alice選擇秘密隨機數(shù)k，滿足0<k<q，計算r=gk(modp)；e=H(r,m)；

s=k＋xe(modq)。（3）Alice將(m，e，s)發(fā)送給Bob。（4）Bob用Alice的公鑰，計算r’=gsy-e(modp)。檢驗是否e=H(r’,m)。若是則(m，e，s)是Alice發(fā)送的簽名消息。2023/7/2443三、幾種常用的數(shù)字簽名Schnorr簽名與ElGamal簽名的不同點：

在ElGamal體制中，g為域GF(p)的本原元素；而在Schnorr體制中，g只是域GF(p)的階為q的元素，而非本原元素。因此，雖然兩者都是基于離散對數(shù)的困難性，然而ElGamal的離散對數(shù)階為p-1，Schnorr的離散對數(shù)階為q<p-1。從這個角度上說，ElGamal的安全性似乎高于Schnorr

。2023/7/2444三、幾種常用的數(shù)字簽名簽名長度比較：Schnorr比ElGamal簽名長度短。ElGamal：(m，r，s)，其中r的長度為|p|，s的長度為|p-1|。Schnorr：(m，e，s)，其中e的長度為|q|，s的長度為|q|。在Schnorr簽名中，r=gk(modp)可以預(yù)先計算，k與m無關(guān)，因而簽名只需一次modq乘法及減法。所需計算量少，速度快，適用于靈巧卡采用。2023/7/2445三、幾種常用的數(shù)字簽名數(shù)字簽名算法DSA（DigitalSignatureAlgorithm）1991年8月，美國國家標準研究所(NIST)發(fā)布了其所提議的數(shù)字簽名標準(DSS)，向社會征求意見，該標準定義了數(shù)字簽名算法DSA。經(jīng)過公眾的評議并做了少許改進后，1994年，DSS首次作為聯(lián)邦信息處理標準(FIPS)對外公布。2023/7/2446三、幾種常用的數(shù)字簽名DSA的參數(shù)Alice擁有3個正整數(shù)(p，q，g)，向自己的通信伙伴公開。其中：p是模數(shù)（即將要進行(modp)模數(shù)運算），它是一個素數(shù)，值的范圍在2511到2512之間（即p是一個長度為512的比特串）。q也是模數(shù)（即將要進行(modq)模數(shù)運算），它是一個素數(shù)，2159<q<2160（即q是一個長度為160的比特串），并且q是p-1的一個因子。2023/7/2447三、幾種常用的數(shù)字簽名g是這樣確定的：g=j(p-1)/q(modp)；其中1<j<p，j(p-1)/q(modp)>1。實際上，就是要求g>1，gq(modp)=1。Alice選擇x，其中1<x<q。Alice計算y=gx(modp)。Alice的公鑰是(p，q，g，y)，Alice的私鑰是x。2023/7/2448三、幾種常用的數(shù)字簽名DSA的簽名過程簽名方案是上節(jié)的簽名方案(二)。設(shè)Alice欲發(fā)消息m給Bob。（1）Alice用H將消息m進行處理，得h=H(m)。（2）Alice隨機地選擇一個整數(shù)k(0<k<q)，計算r=(gk(modp))(modq)；s=(k-1(h+xr))(modq)。其中k-1是k的關(guān)于(modq)的逆元，即k-1k(modq)=1，0<k-1

<q。(r,s)就是對消息m的簽名，(m,r,s)就是發(fā)送給Bob的簽名消息。2023/7/2449三、幾種常用的數(shù)字簽名DSA的驗證過程Bob收到(m,r,s)后，用Alice的公鑰(p，q，g，y)，將消息m與簽名(r,s)做如下的檢驗：（1）是否0<r<q，0<s<q。若是則繼續(xù)檢驗，否則拒收簽名。（2）計算h=H(m)，w=s-1(modq)，u1=hw(modq)，u2=rw(modq)，v=(gu1yu2(modp))(modq)。2023/7/2450三、幾種常用的數(shù)字簽名如果v=r，則驗證了簽名是有效的，否則拒收簽名。（一個有效的簽名一定會通過檢驗，而一個偽造的簽名幾乎不可能通過檢驗。）2023/7/2451三、幾種常用的數(shù)字簽名若干說明說明一：關(guān)于(modq)的逆元。因為q是素數(shù)，所以當0<k<q時，有唯一的l滿足：0<l<q，kl(modq)=1。此時稱l為k的關(guān)于(modq)的逆元，記l為k-1。當q很小時，求k的關(guān)于(modq)的逆元只需要窮舉。而當q是一個大素數(shù)時，求k的關(guān)于(modq)的逆元也不是一個困難問題。使用歐幾里德算法（輾轉(zhuǎn)相除法），簡單快速。2023/7/2452三、幾種常用的數(shù)字簽名說明二：關(guān)于隨機選擇的整數(shù)k。Alice在每次生成簽名時，都要臨時隨機地選擇一個整數(shù)k(0<k<q)。k并不發(fā)送給Bob，只是在簽名算法中參加運算，因此可以看作是Alice的另一個私鑰，稱為臨時密鑰。臨時密鑰k為什么要保密？如果臨時密鑰k被公開，則當攻擊者Eve截獲了簽名消息(m,r,s)后，他計算h=H(m)；再從等式s=(k-1(h+xr))(modq)中計算出Alice的私鑰x：x=(sk-h)r-1(modq)

。DSA被攻破。2023/7/2453三、幾種常用的數(shù)字簽名臨時密鑰k為什么要臨時隨機地選擇？設(shè)臨時密鑰k是保密的，但是是固定的。設(shè)攻擊者Eve截獲了兩個簽名消息(m,r,s)和(m’,r’,s’)。Eve能夠計算出h=H(m)，h’=H(m’)。Eve還知道：s=(k-1(h+xr))(modq)，s’=(k-1(h’+xr’))(modq)。這是關(guān)于未知量（k-1，k-1x）的二元一次方程組（只不過是模方程組），可以很簡單地解出（k-1，k-1x），因此解出（k，x）。DSA被攻破。2023/7/2454三、幾種常用的數(shù)字簽名綜上所述，臨時密鑰k應(yīng)該是保密的，且必須臨時隨機選擇。于是會出現(xiàn)以下的現(xiàn)象：Alice在時刻1發(fā)送簽名消息(m,r1,s1)。Alice在時刻2發(fā)送簽名消息(m,r2,s2)。在不同時刻發(fā)送相同的消息m，得到不同的簽名(r1,s1)和(r2,s2)，都是有效簽名。2023/7/2455三、幾種常用的數(shù)字簽名說明三：檢驗過程的合理性（即有效的簽名一定滿足等式v=r）。w=s-1(modq)=(k-1(h+xr))-1(modq)=k(h+xr)-1(modq)。u1=hw(modq)=hk(h+xr)-1(modq)。u2=rw(modq)=rk(h+xr)-1(modq)。所以u1+xu2(modq)=hk(h+xr)-1+xrk(h+xr)-1(modq)=(h+xr)k(h+xr)-1(modq)=k。2023/7/2456三、幾種常用的數(shù)字簽名所以：v=(gu1yu2(modp))(modq)=(gu1gxu2(modp))(modq)=(gu1+xu2(modp))(modq)=(gu1+xu2(modq)(modp))(modq)=(gk(modp))(modq)=r。2023/7/2457三、幾種常用的數(shù)字簽名說明四：偽造簽名的困難性。（如果攻擊者Eve獲得了Alice的私鑰x，則DSA被攻破，Eve可以任意地冒充Alice簽名）設(shè)Eve并不知道x，而試圖偽造Alice的簽名消息(m,r,s)通過檢驗方程v=r，即(gu1yu2(modp))(modq)=r，2023/7/2458三、幾種常用的數(shù)字簽名又即這是一個復(fù)雜的求解離散對數(shù)的問題。2023/7/2459三、幾種常用的數(shù)字簽名公眾對DSA的反應(yīng)：RSADataSecurityInc(DSI)想以RSA算法做為標準，因而對此反應(yīng)強烈。在標準公布之前就指出采用公用?？赡苁拐軌蜻M行偽造簽名。許多大的軟件公司早已得到RSA的許可證而反對DSS。主要批評意見有：①DSA不能用于加密或密鑰分配；②DSA算法中可能設(shè)有陷門；③DSA比RSA慢；④RSA已是一個實際上的標準，而DSS與現(xiàn)行國際標準不相容；⑤DSA未經(jīng)公開選擇過程，還沒有足夠的時間進行分析證明；⑥D(zhuǎn)SA可能侵犯了其它專利（Schnorr簽名算法，Diffie-Hellman的公鑰密鑰分配算法）；⑦由512bit所限定密鑰量太小。現(xiàn)已改為512～1024中可被64除盡的即可供使用。2023/7/2460三、幾種常用的數(shù)字簽名DSA的實現(xiàn)速度

預(yù)計算：隨機數(shù)r與消息無關(guān)，選k預(yù)先計算出其r。