chap10-2：密碼協(xié)議基本理論

密碼協(xié)議基本理論密碼協(xié)議是指使用密碼技術(shù)的信息交換協(xié)議。所謂協(xié)議，就是兩個或者兩個以上的參與者為完成某項(xiàng)特定的任務(wù)而采取的一系列步驟。包含三層含義：協(xié)議自始至終是有序的過程，在前一步?jīng)]有執(zhí)行之前，后面的步驟不能執(zhí)行；協(xié)議至少需要兩個參與者；通過協(xié)議必須能夠完成某項(xiàng)任務(wù)。密碼協(xié)議的基本概念算法、協(xié)議、密碼協(xié)議算法：一系列步驟，完成一項(xiàng)任務(wù)。協(xié)議：一系列步驟，它包括兩方或多方，設(shè)計(jì)它的目的是要完成一項(xiàng)任務(wù)。協(xié)議中的每個參與者都必須了解協(xié)議，并且預(yù)先知道所要完成的步驟協(xié)議中的每個參與者都必須同意并遵循該協(xié)議協(xié)議必須是清楚的，每一步必須明確定義，并且不會引起誤解協(xié)議必須是完整的，對每種可能的情況必須規(guī)定具體的動作密碼協(xié)議(CryptographicProtocol)：是使用密碼技術(shù)的協(xié)議協(xié)議的參與者可能是朋友和完全信任的人，或者也可能是敵人和互相完全不信任的人包含某種密碼算法，但通常協(xié)議的目的不僅僅是為了簡單的秘密性參與協(xié)議的各方可能為了計(jì)算一個數(shù)值想共享他們的秘密部分、共同產(chǎn)生隨機(jī)系列，確定互相的身份或者同時簽署合同等等使用密碼的目的是防止或發(fā)現(xiàn)竊聽者和欺騙密碼協(xié)議的目的是運(yùn)用密碼學(xué)技術(shù)保證安全系統(tǒng)的安全性和保密性。但是，如果密碼協(xié)議設(shè)計(jì)得不合理，則相當(dāng)于設(shè)計(jì)者暴露了安全系統(tǒng)中的漏洞，攻擊者根本不用去攻擊安全的密碼算法就能夠達(dá)到入侵系統(tǒng)的目的。密碼協(xié)議研究的主要領(lǐng)域包括：網(wǎng)絡(luò)安全協(xié)議的設(shè)計(jì)和分析、密鑰管理協(xié)議的設(shè)計(jì)與分析以及與它們相關(guān)領(lǐng)域的研究，如零知識證明、身份認(rèn)證、密鑰協(xié)商、秘密共享等。密碼協(xié)議的分類系統(tǒng)通信中的密碼協(xié)議按功能可以分成三類身份認(rèn)證協(xié)議數(shù)字簽名協(xié)議密鑰分配協(xié)議

身份認(rèn)證協(xié)議在安全系統(tǒng)中進(jìn)行通信時，為了保證安全性，通信的一方需要知道另一方的身份，這就需要使用身份認(rèn)證協(xié)議。在身份認(rèn)證體系中被鑒別的消息是相對固定的，通信一方聲稱的身份可以立即被另一方確認(rèn)或否認(rèn)。數(shù)字簽名協(xié)議數(shù)字簽名協(xié)議和身份認(rèn)證協(xié)議相似，但復(fù)雜的多。在數(shù)字簽名協(xié)議中，消息是易變的，且具有生命期。數(shù)字簽名在信息安全領(lǐng)域有很多應(yīng)用，如公鑰證書、數(shù)據(jù)完整性和匿名性等。

密鑰分配協(xié)議密鑰分配協(xié)議是指為了在通信中達(dá)到保密的目的，要求參與通信的兩個或者多個實(shí)體之間具有會話密鑰的一致性。這種協(xié)議可以采用對稱密碼體制（如DES等），也可以采用非對稱密碼體制（例如Diffie-Hellman公鑰交換等）。密碼協(xié)議的安全性目前許多密碼協(xié)議都存在安全缺陷，造成協(xié)議存在安全缺陷的原因主要有兩個：協(xié)議設(shè)計(jì)者誤解或者采用了不恰當(dāng)?shù)拿艽a技術(shù)；協(xié)議設(shè)計(jì)者對整體系統(tǒng)的安全需求考慮不足。密碼協(xié)議的安全性是一個很難解決的問題，許多廣泛應(yīng)用的密碼協(xié)議后來都被發(fā)現(xiàn)存在安全缺陷。因此，從安全性角度來看，在設(shè)計(jì)密碼協(xié)議時應(yīng)當(dāng)對協(xié)議的安全性做出認(rèn)真的分析。密碼協(xié)議的分析目前，對密碼協(xié)議進(jìn)行分析的方法主要有兩大類攻擊檢驗(yàn)方法：使用目前已知的所有的有效攻擊方法，對密碼協(xié)議進(jìn)行攻擊，檢驗(yàn)密碼協(xié)議是否能夠抵抗這些攻擊。在分析的過程中，主要使用自然語言和示意圖對密碼協(xié)議所交換的消息進(jìn)行分析。當(dāng)能夠恰當(dāng)?shù)倪x擇攻擊方法時，這種分析方法往往是非常有效的，但這一要求很難滿足。形式化的分析方法：指采用各種形式化的語言對密碼協(xié)議進(jìn)行描述，并按照規(guī)定的假設(shè)和分析、驗(yàn)證方法證明協(xié)議的安全性。目前，形式化的分析方法是研究的熱點(diǎn)，但是就其實(shí)用性來說，還沒有什么突破性的進(jìn)展。由于密碼協(xié)議本身的復(fù)雜性，目前并沒有一種方法能夠?qū)γ艽a協(xié)議的安全性進(jìn)行充分必要的理論證明。每一類方法都有不同的側(cè)重點(diǎn)，或者說或多或少存在不足之處，在使用上述方法分析安全協(xié)議的時候，應(yīng)當(dāng)仔細(xì)分析協(xié)議的特點(diǎn)、應(yīng)用環(huán)境和需求，綜合使用這些分析方法，以得到較為合理的結(jié)果。主要內(nèi)容身份認(rèn)證協(xié)議數(shù)字簽名協(xié)議密鑰分配協(xié)議分類口令鑒別挑戰(zhàn)-響應(yīng)式認(rèn)證基于零知識證明的身份鑒別身份認(rèn)證協(xié)議分類口令鑒別挑戰(zhàn)-響應(yīng)式認(rèn)證基于零知識證明的身份鑒別身份認(rèn)證協(xié)議在密碼學(xué)中，挑戰(zhàn)-響應(yīng)式協(xié)議的思想是指一個實(shí)體通過知識證明來向另一個實(shí)體證明其身份。在此類協(xié)議中，挑戰(zhàn)一般是一個隨機(jī)值或秘密值，當(dāng)攻擊者竊聽通信信道時，由于每次挑戰(zhàn)值都不同，所以對挑戰(zhàn)的響應(yīng)不會暴露秘密信息。身份認(rèn)證協(xié)議

采用分組密碼技術(shù)的挑戰(zhàn)-響應(yīng)式認(rèn)證

采用公鑰密碼技術(shù)的挑戰(zhàn)-響應(yīng)式認(rèn)證身份認(rèn)證協(xié)議采用分組密碼技術(shù)認(rèn)證方案此時認(rèn)證的發(fā)起者和驗(yàn)證者間需要有共享密鑰，在系統(tǒng)用戶較少時，此要求容易滿足，用戶較多的情況下，需要使用可信的第三方。基于時間戳的單向認(rèn)證基于隨機(jī)數(shù)的單向認(rèn)證基于隨機(jī)數(shù)的雙向認(rèn)證采用分組密碼技術(shù)的認(rèn)證方案基于時間戳的單向認(rèn)證驗(yàn)證方接受發(fā)起方傳送的信息并對其解密，對解密后的消息進(jìn)行驗(yàn)證，檢驗(yàn)時間戳是否合法可以防止攻擊者對傳送消息的重用。分析：需要防止對時鐘的惡意修改，在分布式環(huán)境下很難保證。同時，對已用時間戳的保存會浪費(fèi)大量的存儲空間。采用分組密碼技術(shù)的認(rèn)證方案基于隨機(jī)數(shù)的單向認(rèn)證首先驗(yàn)證方向發(fā)起方傳送隨機(jī)數(shù)，發(fā)起方對身份信息和隨機(jī)數(shù)進(jìn)行加密并送出，最后驗(yàn)證方解密得到消息并驗(yàn)證隨機(jī)數(shù)。為防止選擇明文攻擊，發(fā)起方可在發(fā)送的消息中加入另一隨機(jī)數(shù)。采用分組密碼技術(shù)的認(rèn)證方案基于隨機(jī)數(shù)的雙向認(rèn)證協(xié)議中，驗(yàn)證方首先向發(fā)起方送出隨機(jī)數(shù)r1，然后發(fā)起方選擇另一隨機(jī)數(shù)r2，并對身份信息和隨機(jī)數(shù)r1、r2進(jìn)行加密，然后送出。驗(yàn)證方解密得到的消息后，驗(yàn)證隨機(jī)數(shù)r1，驗(yàn)證通過后，將隨機(jī)數(shù)r1、r2加密后送給發(fā)起方，最后發(fā)起方通過驗(yàn)證隨機(jī)數(shù)r1、r2來驗(yàn)證對方的身份。采用公鑰密碼技術(shù)的認(rèn)證方案在利用公鑰密碼技術(shù)進(jìn)行認(rèn)證時，發(fā)起者通過兩種方法來證明其身份：

對用其公鑰加密過的隨機(jī)數(shù)進(jìn)行解密；

對隨機(jī)數(shù)進(jìn)行簽名。為了保證安全性，認(rèn)證協(xié)議的公私鑰對不能在其他應(yīng)用中使用；同時，協(xié)議還應(yīng)能夠抵抗選擇密文攻擊。采用公鑰密碼技術(shù)的認(rèn)證方案簡單的認(rèn)證協(xié)議：認(rèn)證方B選擇隨機(jī)數(shù)r，計(jì)算x=h(r)，e=PA(r，B)，（其中：h是哈希函數(shù)，PA是發(fā)起方A的公鑰）；B向A發(fā)送(x，B，e)；A對接受到的信息進(jìn)行解密得到r’和B’，并驗(yàn)證r’=r，B’=B；若通過驗(yàn)證，則A向B發(fā)送r；最后，B對r進(jìn)行驗(yàn)證?；陔S機(jī)數(shù)的單方公鑰認(rèn)證。認(rèn)證方B選擇隨機(jī)數(shù)rB，并將其發(fā)送給發(fā)起方A；A在接收到rB之后，選取另一隨機(jī)數(shù)rA，將(rA，B，SA(rA，rB，B))發(fā)送給B，（SA是A的私鑰）；B對接受到的信息進(jìn)行解密并進(jìn)行驗(yàn)證，這里，rA可用來防止選擇消息攻擊。采用公鑰密碼技術(shù)的認(rèn)證方案主要內(nèi)容身份認(rèn)證協(xié)議數(shù)字簽名協(xié)議密鑰分配協(xié)議數(shù)字簽名協(xié)議身份唯一性（不可偽造）被Alice簽名的消息只能由Alice生成。其本質(zhì)是：Bob在收到一個“被Alice簽名的消息”時，他有辦法檢驗(yàn)，該簽名是否真的被Alice簽名的消息?；蛟S攻擊者Eve截獲了大量的被Alice簽名的消息，但他仍然不能偽造出一個新的，別人認(rèn)可的“被Alice簽名的消息”。如果無論Eve截獲多少被Alice簽名的消息，他偽造新的“被Alice簽名的消息”的成功概率仍然沒有絲毫提高，則稱該簽名算法是零知識的。不可否認(rèn)性（公開可驗(yàn)證）被Alice簽名的消息，在未來不能被Alice否認(rèn)。其本質(zhì)是：Bob在收到一個被Alice簽名的消息時，他有辦法向第三方證明該簽名是真的被Alice簽名的消息。如果一個數(shù)字簽名具有不可偽造性，則Bob能夠自行驗(yàn)證簽名消息的真?zhèn)?；而如果一個數(shù)字簽名具有公開可驗(yàn)證性，則Bob能夠向他人證明簽名消息的真?zhèn)?。?shù)字簽名協(xié)議公鑰密碼的簽名思想既然要求數(shù)字簽名具有這么多的性質(zhì)，怎樣來構(gòu)造數(shù)字簽名？以公鑰密碼為基礎(chǔ)的數(shù)字簽名算法。公鑰密碼：明文m，密文cAlice的加密密鑰(公鑰)是z，解密密鑰(私鑰)是k加密方程c=E(m,z)，解密方程m=D(c,k)數(shù)字簽名協(xié)議消息的數(shù)字簽名就是指依賴于簽名者私有信息的有關(guān)被簽署消息的數(shù)字符號。在信息安全領(lǐng)域數(shù)字簽名有很多應(yīng)用，如公鑰證書、數(shù)據(jù)完整性和匿名性等。

數(shù)字簽名體系可分為兩大類：消息附屬(appendix)數(shù)字簽名：在簽名驗(yàn)證階段需要原始的消息。較為典型的有DSA、ElGamal和Schnorr簽名體系。消息自恢復(fù)數(shù)字簽名：在簽名驗(yàn)證階段不需要原始的消息。較為典型的有RSA、Rabin和Nyberg-Rueppel公鑰簽名體系。數(shù)字簽名協(xié)議按照明、密文的對應(yīng)關(guān)系劃分，上面每一類又可分為兩個子類：一類是確定性數(shù)字簽名，其明文與密文一一對應(yīng)；另一類是隨機(jī)數(shù)字簽名，它對同一消息的簽名是隨機(jī)變化的。數(shù)字簽名體系的分類消息認(rèn)證可以保護(hù)信息交換不受第三方的攻擊，但不能處理通信雙方自身發(fā)生的攻擊。數(shù)字簽名提供了這種能力:驗(yàn)證簽名者、簽名的日期和時間認(rèn)證消息內(nèi)容可由第三方仲裁，以解決爭執(zhí)因此，數(shù)字簽名具有認(rèn)證功能數(shù)字簽名應(yīng)滿足的條件簽名值必須依賴于所簽的消息產(chǎn)生簽名比較容易識別和驗(yàn)證簽名比較容易偽造數(shù)字簽名在計(jì)算上是不可行的。包括已知數(shù)字簽名，偽造新的消息已知消息，偽造數(shù)字簽名保存數(shù)字簽名的拷貝是可行的公鑰密碼的簽名方案（一）Alice發(fā)消息m給BobAlice用自己的私鑰k對消息m“解密”s=D(m,k)，s是對消息m的簽名值，(m，s)是一個簽名消息。Alice將(m，s)發(fā)送給Bob。Bob收到(m，s)后，用Alice的公鑰z，將消息m與簽名s做如下的檢驗(yàn)：是否m=E(s,z)。若是則(m，s)是Alice發(fā)送的簽名消息。在上述方案中：“密文”變成了消息m，“解密方程”變成了簽名方程s=D(m,k)?！懊魑摹弊兂闪撕灻祍，“加密方程”變成了驗(yàn)證方程m=E(s,z)。任何人只要擁有Alice的公鑰z，都可以對簽名消息(m，s)進(jìn)行驗(yàn)證。是否只有Alice自己才能生成自己的簽名消息呢？安全性分析（1）：設(shè)Eve知道Alice的公鑰z，選定消息m，對簽名值s進(jìn)行偽造。要想讓偽造的簽名值s通過檢驗(yàn)，Eve必須選擇s滿足驗(yàn)證方程m=E(s,z)。然而在驗(yàn)證方程中是解不出s的，必須得到Alice的私鑰k，用簽名方程得到s：s=D(m,k)。這就是說，對事先設(shè)定的消息m來說，簽名消息(m，s)具有身份唯一性和不可偽造性。安全性分析（2）：設(shè)Eve知道Alice的公鑰z，設(shè)定簽名值s，反過來對消息m進(jìn)行偽造。此時消息m的內(nèi)容就不能是選定的。Eve選擇一個“簽名值”s，用驗(yàn)證方程計(jì)算“消息”m=E(s,z)。Eve冒充Alice將(m，s)發(fā)送給Bob。Bob用驗(yàn)證方程檢驗(yàn)得m=E(s,z)。于是Bob認(rèn)為(m，s)就是Alice發(fā)送的簽名消息。攻擊成功。為了抵抗這種攻擊，合法簽名消息(m，s)中的消息m必須是有意義的，而不是亂碼。使用一個公開的雜湊函數(shù)H

設(shè)Alice欲發(fā)消息m給BobAlice用H將消息m進(jìn)行處理，得h=H(m)。Alice用自己的私鑰k對h“解密”s=D(h,k)，s就是對消息m的簽名值，(m，s)就是一個簽名消息。Alice將(m，s)發(fā)送給Bob。Bob收到(m，s)后，用Alice的公鑰z，將消息m與簽名s做如下的檢驗(yàn)：是否H(m)=E(s,z)。若是則(m，s)是Alice發(fā)送的簽名消息。公鑰密碼的簽名方案（二）在上述方案中：簽名方程是s=D(H(m),k)驗(yàn)證方程是H(m)=E(s,z)任何人只要擁有Alice的公鑰z，都可以對簽名消息(m，s)進(jìn)行驗(yàn)證設(shè)攻擊者Eve知道Alice的公鑰z，他試圖偽造一個(m，s)，讓Bob相信(m，s)是Alice的簽名消息。偽造的(m，s)必須滿足驗(yàn)證方程H(m)=E(s,z)安全性分析：如果選定消息m，再匹配簽名值s，則在驗(yàn)證方程H(m)=E(s,z)中無法解出s。（公鑰密碼的基本安全性）如果選定簽名值s，再匹配消息m，則在驗(yàn)證方程H(m)=E(s,z)中能夠解出H(m)，卻無法得到m。（雜湊函數(shù)的性質(zhì)）如此看來，簽名方案（二）似乎具有身份唯一性和不可偽造性。重放攻擊：如果給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))即可。抵抗重放攻擊，通常使用兩種方法：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ā)送時間過于久遠(yuǎn)，則肯定是重放攻擊，但“時間過于久遠(yuǎn)”的標(biāo)準(zhǔn)很模糊。RSA簽名體系RSA簽名體系的消息空間和密文空間都是Zn={0,1,2,…,n?1}，n=p×q。這種簽名體系是確定性的數(shù)字簽名體系。1.RSA簽名體系的密鑰產(chǎn)生每個實(shí)體A進(jìn)行以下操作：隨即選擇兩個大素?cái)?shù)p和q；計(jì)算n=p×q和

Φ(n)=(p?1)(q?1)；隨即選擇e，滿足1＜e＜Φ(n)，gcd(e,Φ(n))=1；用歐幾里得算法計(jì)算d，滿足1＜d＜Φ(n)，ed=1mod(n)。設(shè)A的公鑰為(n，e)，私鑰為(n，d)。2.簽名算法計(jì)算s=mdmodn；發(fā)送(m，s)。3.驗(yàn)證算法（1）計(jì)算m′=semodn；（2）驗(yàn)證m′是否等于m，若不等于，則拒絕；4.安全性分析如果攻擊者能夠進(jìn)行模n的大整數(shù)分解，則它可計(jì)算Φ(n)，從而利用歐幾里得算法得到簽名者的私鑰。所以簽名者必須小心地選擇p和q。Rabin簽名體系Rabin簽名與RSA簽名很相似，但其使用了一個偶數(shù)公鑰參數(shù)e。為了使驗(yàn)證更簡單，Rabin簽名設(shè)定e=2。1.Rabin簽名體系的密鑰產(chǎn)生每個實(shí)體A進(jìn)行以下操作：（1）隨即選擇兩個大素?cái)?shù)p和q；（2）計(jì)算n=p×q和

Φ(n)=(p?1)(q?1)。設(shè)A的公鑰為n，私鑰為(p，q)。2.簽名算法（1）計(jì)算s，使s2=mmodn；（2）發(fā)送(m，s)。3.驗(yàn)證算法（1）計(jì)算m′=s2modn；（2）驗(yàn)證m′是否等于m，若不等于，則拒絕。4.安全性分析攻擊者選一個x，求出x2=m′modn，并送給簽名者。簽名者將簽名s送給攻擊者。若s≠±x，則攻擊者有1/2的機(jī)會分解n，從而可破解此系統(tǒng)。但RSA只是“相信等于”大整數(shù)分解的困難性（無法證明），因而無上述缺點(diǎn)。ElGamal簽名方案ElGamal簽名是一種隨機(jī)附屬簽名機(jī)制，它可以對任意長度的二進(jìn)制消息格式進(jìn)行簽名。1.ElGamal簽名體系的密鑰產(chǎn)生每個實(shí)體A進(jìn)行以下操作：隨機(jī)選擇大素?cái)?shù)p和上的本原元g；選擇隨機(jī)整數(shù)x，1≤x≤p－2；計(jì)算y=gxmodp設(shè)A的公鑰為(p,g,y)A的私鑰為xElGamal簽名方案2.簽名算法選擇隨機(jī)數(shù)k，1≤k≤p-2且gcd(k,p-1)=1；計(jì)算r=gkmodp；計(jì)算k-1modp-1；計(jì)算s=k-1(h(m)-xr)modp-1；m的簽名為(r,s)。ElGamal簽名方案3.驗(yàn)證算法驗(yàn)證1≤r≤p-1，若不滿足則拒絕；計(jì)算v1=yrrsmodp；計(jì)算h(m)和v2=gh(m)modp；若v1=v2，則接收簽名，否則拒絕。其中，s=k-1(h(m)-xr)modp-1，可得ks=(h(m)-xr)modp-1，即h(m)=(ks+xr)modp-1，從而有g(shù)h(m)＝gks+xr＝(gx)r˙rsmodp，因此有v1=v2。安全性分析攻擊者要偽造簽名就要確定s的值，離散對數(shù)問題是困難問題，則攻擊者正確選擇s的概率為1/p，當(dāng)p足夠大時，這個概率可忽略；每次簽名時必須選擇不同的k，否則，簽名者的私鑰有可能暴露。假設(shè)s1=k-1{h(m1)-xr}modp-1，s2=k-1{h(m2)-xr}modp-1，則(s1-s2)k={h(m1)-h(m2)}modp-1，若s1-s2≠0modp-1，則k=(s1-s2)-1{h(m1)-h(m2)}modp-1，這時計(jì)算x是方便的。ElGamal簽名方案Schnorr簽名方案參數(shù)設(shè)定：大素?cái)?shù)p，2511<p<2512大素?cái)?shù)q，2159<q，q|(p-1)g是域GF(p)的元素，且gq=1(modp)。用戶私鑰x：隨機(jī)或偽隨機(jī)整數(shù),其中0<x<q公鑰y=gxmodp簽名：消息m，簽名者選取隨機(jī)整數(shù)k，0<k<q，且k與p-1互素r=gkmodpe=h(r,m)s=k＋xe(modq)(m，e，s)即為消息m的數(shù)字簽名。Schnorr簽名方案驗(yàn)證：r’=gsy-e(modp)若e=h(r’,m)成立則接受，否則拒絕Schnorr簽名方案Elgamal方案與Schnorr方案的比較g在ElGamal體制中，g為域GF(p)的本原元在Schnorr體制中，g只是域GF(p)的階為q的元素，而非本原元安全性兩者都是基于離散對數(shù)問題的困難性，然而ElGamal的離散對數(shù)階為p-1，Schnorr的離散對數(shù)階為q<p-1。從這個角度上說，ElGamal的安全性高于Schnorr。Schnorr簽名方案Elgamal方案與Schnorr方案的比較簽名長度ElGamal：(m，r，s)，其中r的長度為|p|，s的長度為|p-1|。Schnorr：(m，e，s)，其中e的長度為|q|，s的長度為|q|。計(jì)算速度在Schnorr簽名中，r=gk(modp)可以預(yù)先計(jì)算，k與m無關(guān)，因而簽名只需一次modq乘法和減法。所需計(jì)算量更少，速度更快。Schnorr簽名方案DigitalSignatureStandard（DSA）1.數(shù)字簽名算法(DSA)1991年8月，美國國家標(biāo)準(zhǔn)技術(shù)研究所(NIST)公布了一種數(shù)字簽名算法(DSA)，之后，DSA成為了美國聯(lián)邦信息處理標(biāo)準(zhǔn)DSS(FIPS186)，并成為第一個經(jīng)過各國政府驗(yàn)證的數(shù)字簽名方案。DSA是ElGamal簽名方案的變種，它使用了安全哈希函數(shù)(SHA-1)。DSA美國政府的簽名方案由NIST和NSA，在20世紀(jì)90年代設(shè)計(jì)1991年，作為FIPS-186發(fā)布1993，1996，2000進(jìn)行了修改采用SHAhash算法

DSS是標(biāo)準(zhǔn)DSA算法。FIPS186-2(2000)包括可選的RSA和橢圓曲線簽名算法DSA可以提供512-1024bit的安全性比RSA小且快僅是一個數(shù)字簽名方案（不能用于加密）安全性依賴于計(jì)算離散對數(shù)的困難性是ElGamal和Schnorr方案的變體參數(shù)設(shè)定：大素?cái)?shù)p，2L-1<p<2L，512<L<1024，且L為64的倍數(shù)：即比特長度在512到1024之間，長度增量為64比特。素?cái)?shù)q，q|(p-1)，且2159<q<2160g=h(p-1)/qmodp,h為整數(shù),1<h<(p-1),h(p-1)/q(modp)>1用戶私鑰x：隨機(jī)或偽隨機(jī)整數(shù),其中0<x<p-1公鑰y=gxmodpDSS簽名：對明文m(1,q)，簽名者選取隨機(jī)整數(shù)k，1≤k≤p-2且k與p-1互素，計(jì)算r=(gkmodp)modqs=k-1(H(m)+xr)modq其中kk-1modq≡1(r，s)即為消息m的數(shù)字簽名。DSS驗(yàn)證：計(jì)算w=s-1modqu1=H(m)wmodqu2=rwmodqv=[(gu1yu2)modp]modq檢驗(yàn)v=r是否成立。DSSDSS系統(tǒng)構(gòu)造：q=101，p=78*q+1=7879，3為GF(7879)中的一個本原元取g=378mod7879=170為模p的q次單位根，假設(shè)用戶私鑰x=75，則y=gx(mod7879)=4567簽名者對消息m=1234簽名：簽名者選擇隨機(jī)數(shù)k=50，得k-1(mod101)=99計(jì)算簽名：r=(17050(mod7879))(mod101)=2518(mod101)=94s=(1234+75*94)99(mod101)=97簽名為(1234,94,97)DSS驗(yàn)證：

w=s-1

modq=97-1

mod101=25

u1=H(m)wmodq=1234*25mod101=45

u2=rwmodq=94*25mod101=27v=[(gu1yu2)modp]modq=(17045*456727(mod7879))(mod101)

=2518(mod101)=94=r因此該簽名是有效的。DSS4）安全性分析DSA的安全依賴于兩種不同的離散對數(shù)問題：一種是在上的離散對數(shù)問題，另一種是在階為q的循環(huán)子群上的離散對數(shù)問題。DSSDSA不能用于加密或密鑰分配DSA算法中可能設(shè)有陷門，DSA未經(jīng)公開選擇過程，還沒有足夠的時間進(jìn)行分析證明DSA比RSA慢，RSA已是一個實(shí)際上的標(biāo)準(zhǔn)，而DSS與現(xiàn)行國際標(biāo)準(zhǔn)不相容DSA可能侵犯了其它算法的專利由512位所限定密鑰量太小?，F(xiàn)已改為512～1024中可被64除盡的即可供使用。DSSGroupsignature-群簽名群簽名在群管理員及一組群成員的參與下，使得每個群成員能夠匿名的代表群生成簽名，簽名驗(yàn)證方僅能驗(yàn)證該簽名的有效性及確實(shí)來自該群體，但無法確知（包括其他群成員）具體的簽名人是哪一個群成員；發(fā)生糾紛的情況下，群管理員能夠打開群簽名的匿名性，找到生成簽名的群成員。群簽名若干用戶組成一個群體，使用相關(guān)的簽名方案群中心負(fù)責(zé)為群管理員和群成員分配密鑰，群管理員則在必要的時候打開簽名確定簽名者的身份可用在電子投票、電子拍賣等領(lǐng)域群簽名性質(zhì)只有群成員能夠代表群進(jìn)行簽名；群成員能夠代表群進(jìn)行匿名地簽名；區(qū)分兩個不同的群簽名在計(jì)算上是不可行的；如果發(fā)生爭執(zhí)，群管理員可以打開簽名來決定簽名者的真實(shí)身份；群簽名其他群成員、其他群成員的勾結(jié)或其他群成員與群管理員的勾結(jié)都不能偽造一個群成員的合法簽名。匿名性、可追蹤性、無關(guān)聯(lián)性、不可偽造性、不可鏈接性、防陷害攻擊、動態(tài)群簽名等。群簽名方案舉例密鑰生成群中心隨機(jī)地生成兩個大素?cái)?shù)p，q，計(jì)算n=pq，選擇公開hash函數(shù)h()。選擇，并求d，使隨機(jī)選擇,使

選擇素?cái)?shù),且,將()送給用戶

做密鑰；

Ui

驗(yàn)證，以確信消息是群中心送來的；密鑰生成群中心將()送給群管理員，其中是群成員的身份；

設(shè)系統(tǒng)有k個成員，群中心利用中國剩余定理，可求同余方程組：

的解c；

群中心將（n,e,c）作為公鑰，（d,p,q）為群中心的私鑰。簽名

群成員

要對消息m簽名：首先計(jì)算h(m)；再計(jì)算；則即為Ui

生成的簽名。驗(yàn)證

若Bob要對

的簽名

進(jìn)行驗(yàn)證，Bob利用群公鑰e計(jì)算：

，

得到，然后驗(yàn)證：

是否成立。若成立，簽名合法，否則拒絕。群管理員通過

對應(yīng)的IDi確定簽名者的身份。成員的加入

在有成員加入時，群中心只需重新求解c的值并公布出去，而不必改變其他群成員的秘鑰。群中心偽造群成員的簽名顯然，該方案中群中心知道所有的群成員的簽名密鑰，因此一個不誠實(shí)的群中心可以偽造其他群成員的合法簽名而不能被檢測。可能遭受的攻擊聯(lián)合攻擊假設(shè)群成員

聯(lián)合起來攻擊方案，他們分別掌握

，

可知為和的公因子；聯(lián)合成員越多，成功的可能越大也可以通過自己多次加入群實(shí)現(xiàn)可能遭受的攻擊研究點(diǎn)群公鑰的長度依賴于群的大小；群簽名的長度依賴于群的大?。辉黾有鲁蓡T需要重新啟動整個系統(tǒng),或者更改所有原有成員的密鑰以及改變?nèi)汗€；撤銷群成員需更改群公鑰及所有成員的密鑰；不能抵抗聯(lián)合攻擊；具有聯(lián)結(jié)性（可以從兩個不同的群簽名來區(qū)分是否來自于同一個簽名者）或廣義偽造性（任何人可以對任意消息進(jìn)行簽名）。Ringsignature-環(huán)簽名環(huán)簽名是一類特殊的無條件匿名方案,因?yàn)槠浜灻[含的某個參數(shù)按照一定的規(guī)則組成環(huán)狀而得名。而在之后提出的許多方案中不要求簽名的構(gòu)成結(jié)構(gòu)成環(huán)形，只要簽名的形成滿足自發(fā)性、匿名性和群特性，也稱之為環(huán)簽名。環(huán)簽名不同于群簽名,一方面,簽名者指定自己的匿名范圍,該范圍內(nèi)的非簽名者可能意識不到自己包含其中;另一方面,由于不設(shè)置管理員,簽名接收者只能驗(yàn)證簽名的有效性,而無法追蹤簽名者的身份,即環(huán)簽名能實(shí)現(xiàn)無條件匿名。環(huán)簽名性質(zhì)無條件匿名性。攻擊者即使非法獲取了所有可能簽名者的私鑰，他能確定出真正的簽名者的概率不超過1/n，這里n為環(huán)成員（可能簽名者）的個數(shù)。不可偽造性。外部攻擊者在不知道任何成員私鑰的情況下，即使能夠從一個產(chǎn)生環(huán)簽名的隨機(jī)預(yù)言者那里得到任何消息m的簽名，他成功偽造一個合法簽名的概率也是可以忽略的。環(huán)簽名具有良好的特性：可以實(shí)現(xiàn)簽名者的無條件匿名；簽名者可以自由指定自己的匿名范圍；構(gòu)成優(yōu)美的環(huán)形邏輯結(jié)構(gòu)；可以實(shí)現(xiàn)群簽名的主要功能但無需可信第三方或群管理員等。RST環(huán)簽名方案參數(shù)選取：

E：對稱加密算法，如AES；

H：安全Hash函數(shù)。一組用戶B1，B2，……，Bn。用戶Bi的RSA公私鑰（ei,di）,模數(shù)ni。設(shè)簽名驗(yàn)證環(huán)簽名的應(yīng)用環(huán)簽密；匿名泄漏信息一個公司經(jīng)常要征求員工的意見或建議，為提高員工反饋意見的可靠性，往往需要多個員工聯(lián)合提出意見或建議才生效。與此同時，為了防止上司的報(bào)復(fù)行為，保護(hù)提意見的員工，在獲得員工反饋信息的同時還不能暴露員工的真實(shí)身份。這時就可以使用門限環(huán)簽名方案，即達(dá)到某個門限值的員工以聯(lián)合方式產(chǎn)生環(huán)簽名。電子現(xiàn)金或電子投票系統(tǒng)對于追究一個投票者多次投票或用戶二次花費(fèi)的問題，可以應(yīng)用關(guān)聯(lián)環(huán)簽名方案來解決。環(huán)簽名的應(yīng)用保護(hù)知識產(chǎn)權(quán)。指紋技術(shù)是保護(hù)數(shù)字產(chǎn)品，防止盜版的有效技術(shù)。應(yīng)用改造后的Schnorr環(huán)簽名方案構(gòu)造了匿名指紋協(xié)議，來保護(hù)知識產(chǎn)權(quán)。若使用該協(xié)議，誠實(shí)購買者不會被陷害，而且當(dāng)非法用戶使用盜版產(chǎn)品時，可以被追溯其身份。ad-hoc、無線傳感器網(wǎng)絡(luò)ad-hoc和無線傳感器網(wǎng)絡(luò)的無中心、自組織等特點(diǎn)與環(huán)簽名的構(gòu)造有很多相似之處。因此對于ad-hoc網(wǎng)絡(luò)中的諸多問題，如：成員的匿名認(rèn)證等，都可以應(yīng)用環(huán)簽名來解決。問題和缺陷因?yàn)楹灻惴ㄒ褂盟谐蓡T的公鑰，導(dǎo)致環(huán)公鑰的長度依賴于環(huán)的大??；由于需要描述環(huán)成員的信息，環(huán)簽名的長度依賴于群的大??；因?yàn)榄h(huán)簽名自身的無條件匿名性，簽名人可以誣陷群中的其他非真實(shí)簽名人；由于可以選擇任意的成員組成一個環(huán)，使得方案不能抵抗選擇群公鑰攻擊。MeshSignature-網(wǎng)狀簽名Boyen在2007年歐密會上提出了網(wǎng)狀簽名的新概念，它是一種類似于環(huán)簽名的匿名簽名。但具有模塊化設(shè)計(jì)的特點(diǎn)，有更強(qiáng)的簽名匿名性表達(dá)能力，可以表示很復(fù)雜的接入結(jié)構(gòu)，特別是允許將其中的簽名組件替換為證書鏈，因此通過強(qiáng)制納入成員，網(wǎng)狀簽名可以用作一種環(huán)簽名。Proxysignature-代理簽名代理簽名體制通常包括：原始簽名人(OriginalSigner),代理簽名人(Proxy

Signer)和簽名驗(yàn)證方(Verifer)三方的參與.代理簽名人代表原始簽名人生成的數(shù)字簽名,稱為代理簽名(ProxySignature).原始簽名人的安全性代理簽名人的隱私保護(hù)代理簽名的長度代理密碼學(xué)Thresholdsignature-門限簽名解決權(quán)力集中問題；(t,n)門限簽名：是指n個成員中大于等于t個成員可代表群體生成簽名,而小于t-1個成員則不能代表群體生成有效簽名.現(xiàn)有的門限簽名均存在惡意成員大于等于門限t時，可以獲取系統(tǒng)秘密參數(shù)。（共謀攻擊）Blindsignature-盲簽名盲簽名允許先將消息盲化，而后讓消息簽名者對盲化的消息進(jìn)行簽名，最后消息擁有者對簽字除去盲因子，得到簽名者關(guān)于原消息的簽名。盲簽名就是接收者在不讓簽名者獲取所簽署消息具體內(nèi)容的情況下所采取的一種特殊的數(shù)字簽名技術(shù)，它除了滿足一般的數(shù)字簽名條件外，還必須滿足下面的兩條性質(zhì)：簽名者對其所簽署的消息是不可見的，即簽名者不知道他所簽署消息的具體內(nèi)容。簽名消息不可追蹤，即當(dāng)簽名消息被公布后，簽名者無法知道這是他哪次的簽署的。具特殊性質(zhì)的數(shù)字簽名在不同的應(yīng)用背景下,人們已經(jīng)提出了60余種數(shù)字簽名模型.指定驗(yàn)證人簽名、不可否認(rèn)簽名、前向安全群簽名等、基于身份的各類簽名。Shortsignature-短簽名當(dāng)前最常用到的DSA和RSA數(shù)字簽名方案，相對提供的安全水平而言，它們給出的簽名，其長度都比較長。例如，當(dāng)用1024bits模數(shù)時，RSA的簽名長度為1024bits；DSA的簽名長度是320bits，DSA的橢圓曲線變型ECDSA也提供320bits的簽名長度。然而，即便是320bits，對于人工嵌入簽名而言，仍然過長?；陔p線性對的簽名，能夠保證短的簽名長度。雙線性對G1和G2是階數(shù)為素?cái)?shù)p的兩個循環(huán)群，生成元分別為g1和g2。一個雙線性對是具有以下性質(zhì)的映射e：G1×G1→G2:雙線性性：對任意的u∈G1，v∈G1，a、b∈Z*有：e(u^a,v^b)=e(u,v)^ab;非退化性：e(g1,g2)≠1;可計(jì)算性：存在有效的算法對所有的u,v∈G1來計(jì)算e(u,v)?；陔p線性對的短簽名密鑰替換攻擊密鑰替換攻擊主要內(nèi)容身份認(rèn)證協(xié)議數(shù)字簽名協(xié)議密鑰分配協(xié)議密鑰分配協(xié)議密鑰分配指的是如何在通信雙方或多方內(nèi)部同時使用一個秘密值的過程。一般來說，密鑰分配可以分為密鑰傳輸和密鑰協(xié)商兩種方式。密鑰傳輸協(xié)議指的是通信一方產(chǎn)生密鑰后，將密鑰秘密地傳送給另一方的密鑰分配技術(shù)，而密鑰協(xié)商指的是通信雙方通過合作來生成通信密鑰的密鑰分配技術(shù)。密鑰分配協(xié)議使用對稱密碼技術(shù)密鑰傳輸協(xié)議密鑰協(xié)商協(xié)議基于公鑰密碼技術(shù)密鑰傳輸協(xié)議密鑰協(xié)商協(xié)議密鑰分配協(xié)議使用對稱密碼技術(shù)的密鑰傳輸協(xié)議無可信第三方的密鑰傳輸協(xié)議有可信第三方的密鑰傳輸協(xié)議基于對稱密碼技術(shù)的密鑰協(xié)商協(xié)議無可信第三方的密鑰傳輸協(xié)議一、基于對稱密碼的點(diǎn)對點(diǎn)的密鑰更新基于對稱密碼的點(diǎn)對點(diǎn)的密鑰更新利用了通信雙方間的長期對稱密鑰，通過這個長期密鑰可以重復(fù)分配通信雙方的會話密鑰。設(shè)rA、tA和nA分別代表隨機(jī)數(shù)、時間戳和序列數(shù)，E代表某種對稱密碼算法。給出幾種密鑰傳輸協(xié)議：無可信第三方的密鑰傳輸協(xié)議（1）一輪密鑰傳輸：A→B：EK(rA)，此時會話密鑰為rA。在此基礎(chǔ)上可以為密鑰傳輸增加一些額外的性質(zhì)，如增加時間戳以保證密鑰的新鮮性；增加冗余信息以檢測消息是否被修改；增加接收者信息以防止對發(fā)送者的重放攻擊如：A→B：EK(rA，tA*，B*)無可信第三方的密鑰傳輸協(xié)議（2）挑戰(zhàn)響應(yīng)模式的密鑰傳輸：A←B：nBA→B：EK(rA，nB，B*)同樣，會話密鑰仍然是rA。如果要求會話密鑰與通信雙方的輸入都相關(guān)，則A可以在上述傳輸過程的第二步加入一次性隨機(jī)數(shù)nA：A←B：nBA→B：EK(rA，nA，nB，B*)A←B：EK(rB，nB，nA，A*)無可信第三方的密鑰傳輸協(xié)議密鑰傳輸技術(shù)的缺點(diǎn)：上述幾種密鑰傳輸技術(shù)不能提供前向保密性，而且若長期密鑰K暴露，則整個技術(shù)就會失效；同時，在不使用時間戳的情況下，密鑰更新技術(shù)易受到重放攻擊，所以其應(yīng)用受到較大的限制。二、基于密鑰獲取和單向函數(shù)的點(diǎn)對點(diǎn)的密鑰傳輸在每次會話時，通信一方利用另一方的隨機(jī)輸入，也可以達(dá)到密鑰更新的目的。如A選擇隨機(jī)數(shù)rA，并將其發(fā)送給B，則二者通信密鑰為EK(rA)。由于此技術(shù)本身并不需要解密，所以可以用恰當(dāng)?shù)膯蜗蚝瘮?shù)代替加密操作。鑒別密鑰交換協(xié)議(AKEP2)：設(shè)A和B有兩個共享長期密鑰K，哈希函數(shù)h。協(xié)議步驟為：A選擇隨機(jī)數(shù)rA，并將其發(fā)送給B；B選擇隨機(jī)數(shù)rB，將(B，A，rA，rB)和hK(B，A，rA，rB)發(fā)送給A；A接收到消息后，對rA和hK(B，A，rA，rB)進(jìn)行驗(yàn)證，若通過，則向B發(fā)送(A，rB)和hK(A，rB)；B接收到消息后，對rB和hK(A，rB)進(jìn)行驗(yàn)證；A和B的會話密鑰為EK(rB)。在此協(xié)議中，可以使用哈希函數(shù)代替對稱密碼算法E，而且這并不影響協(xié)議的安全性。三、無前期共享密鑰的密鑰傳輸協(xié)議Shamir提出了一種密鑰傳輸協(xié)議。在此協(xié)議中，每個通信者只需要有自己的對稱密鑰，而并不需要通信雙方間的前期共享密鑰，但這種協(xié)議只可以抵抗被動攻擊者。Shamir無密鑰協(xié)議定義如下：設(shè)p是公用的大素?cái)?shù)，通信者A、B各自選擇秘密值a和b，1≤a，b≤p-2，且a，b與p-1互素。協(xié)議步驟為：A選擇隨機(jī)值K，1≤K≤p-2，計(jì)算Kamodp并發(fā)送給B；B計(jì)算(Ka)bmodp，并將其發(fā)送給A；A計(jì)算(Kab)a-1modp=Kbmodp，并將其發(fā)送給B；B計(jì)算(Kb)b-1modp=Kmodp。K為A和B的通信密鑰。任何可交換的密碼算法都可以代替此協(xié)議中的模冪操作，但使用時要防止降低安全強(qiáng)度。2.有可信第三方的密鑰傳輸協(xié)議下面討論的密鑰傳輸協(xié)議需要有可信第三方的參與，在整個系統(tǒng)中，每一個實(shí)體都與可信第三方有一個共享密鑰。在這種協(xié)議中，可信第三方可以做為密鑰分發(fā)中心(KDC)或密鑰傳輸中心(KTC)。Kerberos協(xié)議X.509協(xié)議基于公鑰密碼技術(shù)的

密鑰協(xié)商協(xié)議Diffie-Hellman密鑰交換第一個公鑰算法

1976由Diffie和Hellman提出DH算法是一個實(shí)用的密鑰公開交換的算法算法本身只限于進(jìn)行密鑰交換已應(yīng)用在許多商業(yè)產(chǎn)品中“Newdirectionsincryptography”Diffie-Hellman密鑰交換是一個公鑰分配方案不能用于交換任意的消息只限于進(jìn)行公共密鑰的建立只適用于通信雙方已知的情形密鑰的值依賴于通信的參與者(以及他們的私鑰和公鑰信息）有限域中的指數(shù)運(yùn)算（模一個素?cái)?shù)）是相對容易的，而離散對數(shù)的計(jì)算是相對困難的。Diffie-Hellman的建立所有用戶均已知全局參數(shù):一個大素整數(shù)(或多項(xiàng)式)：q一個模q的本原根：α每個用戶

(如xA)產(chǎn)生自己的密鑰選擇一個保密的隨機(jī)數(shù):xA<q計(jì)算其公鑰:yA=αxAmodq

每個用戶公開其公鑰yADiffie-Hellman密鑰交換用戶A和B共享的會話密鑰是KAB:KAB=αxAxBmodq=yxAxBmodq(whichBcancompute)=yxBxAmodq(whichAcancompute)會話密鑰KAB作為A和B兩個用戶在傳統(tǒng)密碼體制中的共享密鑰來使用的可以一直使用前面產(chǎn)生的會話密鑰，直到想重新選擇新的會話密鑰為止。攻擊者需要解出x,必須求解離散對數(shù)。Diffie-Hellman舉例用戶

Alice和

Bob想交換密鑰:雙方同意使用全局參數(shù)

q=353和α=3隨機(jī)選擇一個保密的私鑰:A選擇xA=97,B選擇xB=233分別計(jì)算各自的公鑰:yA=397mod353=40 (Alice)yB=3233mod353=248 (Bob)計(jì)算共享的會話密鑰:KAB=yxBxAmod353=24897=160 (Alice)KAB=yxAxBmod353=40233=160 (Bob)密鑰交換協(xié)議Diffie-Hellman協(xié)議除了可以在有限域上運(yùn)行之外，還可以在橢圓曲線上運(yùn)行。Diffie-Hellman密鑰交換協(xié)議可以很容易的擴(kuò)展到三人或更多的人。但是，Diffie-Hellman協(xié)議不含有交換雙