第三章信息加密與認證技術1授課人：肖敏專業：卓越班2本章內容概述對稱密碼技術公鑰密碼技術信息認證單向Hash函數與消息認證碼的基本概念和原理數字簽名的原理和技術身份認證的典型技術密碼學(Cryptology):是研究信息系統安全保密的科學密碼學包括密碼編碼學和密碼分析學密碼編碼學研究密碼體制的設計密碼分析學研究密碼體制的破譯（密碼分析科學家的工作則是評估一種密碼算法的安全性，尋找更安全的密碼算法）密碼編碼和密碼分析是既相互對立的又是相互依存的。密碼學的發展過程就是編碼與分析互相斗爭的過程。一個密碼體制的推出，給密碼分析提出新的挑戰；一個密碼體制的破譯，導致一個新的密碼體制的誕生。這樣的過程不斷反復，就構成了密碼的歷史。密碼學概念3密碼系統（體制）一般模型4明文明文密文加密算法解密算法加密密鑰解密密鑰原有的消息（待加密的消息）（Plaintext，簡稱P）密碼系統（體制）一般模型5明文明文密文加密算法解密算法加密密鑰解密密鑰用某種方法偽裝消息以隱藏它的內容的過程稱為加密(Encrtption)對明文進行加密操作時所采用的一組規則稱作加密算法(EncryptionAlgorithm)密碼系統（體制）一般模型6明文明文密文加密算法解密算法解密密鑰被加密的消息（Ciphertext，簡稱C）加密密鑰密碼系統（體制）一般模型7明文明文密文加密算法解密算法加密密鑰解密密鑰把密文轉變為明文的過程稱為解密(Decryption)接收者對密文解密所采用的一組規則稱為解密算法(DecryptionAlgorithm)密碼系統（體制）一般模型8明文明文密文加密算法解密算法加密密鑰解密密鑰為了有效控制加密、解密算法的實現，在這些算法的實現過程中，需要有某些只被通信雙方所掌握的專門的、關鍵的信息參與，這些信息就稱為密鑰。用作加密的稱加密密鑰(EncryptionKey)，用作解密的稱作解密密鑰(DecryptionKey)。在授權方之間的密鑰關系的建立和維護，是密碼系統有效的關鍵點之一，相關的技術和過程，稱為密鑰管理。加密密鑰和解密密鑰可能相同，也可能不同密碼系統（體制）一般模型9明文明文密文加密算法解密算法加密密鑰解密密鑰密碼系統（體制）可以形式化表達為一個五元組（P,C,K,E,D)：（1）M是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構成的有限集；（密鑰空間）*（4）任意k∈K,有一個加密算法和相應的解密算法，使得和分別為加密解密函數，滿足dk(ek(x))=x,這里x∈M。密碼系統（體制）一般模型明文M加密器E公開信道密文解密器D明文發送方接收方密碼系統（體制）一般模型11明文明文密文加密算法解密算法加密密鑰解密密鑰在一個密碼系統中，算法是固定不變的運算規則和步驟的集合，密鑰是可變的一定長度的數字、符號序列。在一個密碼體制之下，以相同的明文作為輸入，密鑰不同則輸出的密文不同。收信方收到密文之后，用與發方約定的密碼算法和共享的密鑰，對密文作逆向的密碼變換得到明文。而對于未授權的不知密鑰或密碼算法與密鑰都不知道的第三者，密文是無意義的亂碼，這正是加密變換要達到的目的。防竊聽假設破譯者Oscar是在已知密碼體制的前提下來破譯Bob使用的密鑰。這個假設稱為Kerckhoff原則。最常見的破解類型如下：1.唯密文攻擊：Oscar具有密文串y.2.已知明文攻擊:Oscar具有明文串x和相應的密文y.3.選擇明文攻擊：Oscar可獲得對加密機的暫時訪問，因此他能選擇明文串x并構造出相應的密文串y。4.選擇密文攻擊:Oscar可暫時接近密碼機,可選擇密文串y，并構造出相應的明文x.

這一切的目的在于破譯出密鑰或密文密碼分析學12無條件安全（Unconditionallysecure）無論破譯者有多少密文,他也無法解出對應的明文,即使他解出了,他也無法驗證結果的正確性計算上安全（Computationallysecure）破譯的代價超出信息本身的價值破譯的時間超出了信息的有效期密碼分析學13對稱密碼體制加密密鑰和解密密鑰一樣，即加解密共用一把密鑰根據加密針對的數據單元，對稱密碼體制又可分為：分組密碼——每次對一塊數據加密，多數網絡加密應用，主要算法有DES、IDEA、TDEA、MD5、RC5、AES等流（序列）密碼——每次對一位或一字節加密，多數手機加密應用，如One-timepadding,Vigenére,Vernam，RC4非對稱密碼體制加密密鑰和解密密鑰不一樣，即加解密各用不同的密鑰大部分是分組密碼，只有概率密碼體制屬于流密碼，如，RSA,ECC,ElGamal主要的現代密碼體制14將明文劃分成字符(單個字母)，或其編碼的基本單元(0,1數字)

字符分別與密鑰流作用進行加密，解密時以同步產生的同樣的密鑰流實現kI

安全信道kI······

KGKG

ki

ki

mi

ci

ci

mi

Eki(mi)···Dki(mi)KG:密鑰流生成器kI:初始密鑰流密碼(streamcipher)的基本概念加法流密碼：

ci=Eki(mi)=miki加法流密碼：

mi=Dki(Ci)=mikiki

事實上，流密碼算法其安全性依賴于簡單的異或運算和隨機密鑰流。密鑰流發生器生成的看似隨機的密鑰流實際上是確定的，在解密的時候能很好的將其再現。密鑰流發生器輸出的密鑰越接近隨機，對密碼分析者來說就越困難。

如果密鑰流發生器每次都生成同樣的密鑰流的話，對攻擊來說，破譯該算法就容易了。假的Alice得到一份密文和相應的明文，她就可以將兩者異或恢復出密鑰流。現在，無論她再攔截到什么密文消息，她都可以用她所擁有的密鑰流進行解密。另外，她還可以解密，并閱讀以前截獲到的消息。一旦Alice得到一明文/密文對，她就可以讀懂任何東西了。流密碼(streamcipher)的基本概念16這就是為什么所有序列密碼也有密鑰的原因。密鑰流發生器的輸出是密鑰的函數。這樣，Alice有一個明文/密文對，但她只能讀到用特定密鑰加密的消息。更換密鑰，攻擊者就不得不重新分析。流密碼(streamcipher)的基本概念17流密碼強度完全依賴于密鑰序列的隨機性(Randomness)和不可預測性(Unpredictability)。

核心問題是密鑰流生成器的設計。

保持收發兩端密鑰流的精確同步是實現可靠解密的關鍵技術同步流密碼(SSC:synchronousstreamcipher)產生密鑰序列的算法與明文、密文無關.只要通信雙方的密鑰序列產生器具有相同的“種子序列”和相同的“初始狀態”,就能產生相同的密鑰序列.通信雙方必須保持精確同步,才能正確解密.容易檢測插入、刪除、重播等主動攻擊.沒有差錯傳播.流密碼的分類18ciE(zi,mi)mizi

密鑰流生成器k自同步流密碼(SSSC:self-synchronousstreamcipher)產生密鑰序列的算法與以前的密文有關密鑰流生成器是一種有記憶變換器密鑰流與明文符號有關：i時刻的密文不僅取決于i時刻的明文，而且與i時刻之前的l個明文符號有關具有有限的差錯傳播具有自同步能力把明文每個字符擴散在密文多個字符中,強化了抗統計分析的能力流密碼的分類19E(zi,mi)mizi

密鑰流生成器kci產生密鑰序列的最重要部件是線性反饋移位寄存器，是因為:

(1)LFSR非常適合于硬件實現;(2)能產生大的周期序列;(3)能產生較好統計特性的序列;(4)其結構能應用代數方法進行很好的分析.GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數f(a1,a2,…,an)組成。線性反饋移位寄存器(LFSR)20每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內容構成該反饋移位寄存器的狀態，每一狀態對應于GF(2)上的一個n維向量，共有2n種可能的狀態。每一時刻的狀態可用n長序列“a1,a2,…,an”n維向量“(a1,a2,…,an)”來表示，其中ai是第i級存儲器的內容。初始狀態由用戶確定，當第i個移位時鐘脈沖到來時，每一級存儲器ai都將其內容向下一級ai-1傳遞，并計算f(a1,a2,…,an)作為下一時刻的an。線性反饋移位寄存器(LFSR)2023/2/521

基于LFSR的序列密碼非常適合于硬件實現，但是不特別適合軟件實現。比較常用的序列密碼是A5、SEAL和RC4序列密碼算法，A5是典型的基于LFSR的序列密碼算法，SEAL和RC4不是基于LFSR的序列密碼算法，而是基于分組密碼的輸出反饋模式（OFB）和密碼反饋模式（CFB）來實現的。常用的流密碼算法22A5有兩個版本：A5/1和A5/2，前者有更高的安全性，根據相關法規限制被僅用于歐洲范圍，而后者用于其它地區。A5算法從未公布于眾，但因為一些疏漏，該算法被Bradford大學研究人員泄密，我國學者徐勝波、何大可和王新梅也由此于1994年率先實現A5算法。A5是歐洲數字蜂窩移動電話系統（GSM）采用的流密碼算法，用于加密從用戶到基站的連接A5算法23GSM會話每幀有228bitA5算法的密鑰長64bit有一個22bit幀序號每次產生228bit會話密鑰逐幀加密，每個幀的加密密鑰不同A5算法24A5算法工作過程（1）將64比特密鑰輸入LFSR；（2）將22比特幀序號與LFSR反饋值模2加，再輸入LFSR；（3）LFSR開始停走鐘控；（4）舍去產生的100比特輸出；（5）產生114比特作為密鑰流；（6）舍去產生的100比特輸出；（7）產生114比特作為密鑰流A5算法25RC4是由Rivest于1987年開發的一種序列密碼,它已被廣泛應用于Windows,LotusNotes和其它軟件,還被用于安全套接字(SSL)和無線通信系統等.RC4優點是算法簡單、高效，特別適于軟件實現，加密速度比DES大約快10倍。RC4可以支持不同密鑰長度，美國政府特別限定，用于出口的RC4的密鑰長度不得超過40位RC4算法26RC4使用了一個28字節大小的非線性數據表(簡稱S表),S表的值S0,S1,…,S255是數字0到255的一個排列。對S表進行非線性變換,得到密鑰流RC4算法271.I=0,J=02.I=I+1(mod256);3.J=J+SI(mod256);4.交換SI和SJ;5.t=SI+SJ(mod256);6.z=St.RC4輸出密鑰流字節z的算法對稱密碼體制——分組密碼

28分組密碼以一個固定長度的明文分組為加密變換單元。加密變換采用多層迭代方式，即同一結構的變換多次地使用。加密變換在密鑰參與之下進行多層迭代變換中，各層的變換除所加的層密鑰不同之外，其他的運算皆不變。分組密碼算法的一個重要特點就是：當給定一個密鑰后，若明文分組相同，那么所變換出密文分組也相同，且密文分組和明文分組長度相同。分組密碼的一個重要優點是不需要同步一個分組密碼有三個指標：分組長度（如64，128，256）密鑰長度（如56，112，128，256）變換層數（如8，10，16，32）三個主要算法加密算法解密算法密鑰擴展算法要求：1分組長度足夠大，防止窮舉攻擊；2密鑰空間足夠大，但不能太長，以便于密鑰的管理；3算法要足夠復雜，充分實現明文和密鑰的擴散；沒有簡單的關系可尋對稱密碼體制——分組密碼

29采用分組密碼體制；用64bit密鑰來加密64bit數據的方法；DES的安全性不依賴于算法的保密，安全性僅以加密密鑰的保密為基礎；DES(DataEncryptionStandard)加密算法30DES算法的實現步驟第一步：初始置換IP對給定的64位比特的明文x，首先通過一個置換IP表來重新排列x，從而構造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位。第二步：16輪迭代迭代規則為Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)（i=1,2,3…16）經過第一步變換已經得到L0和R0的值，其中符號⊕表示的數學運算是異或，f表示一種置換，由S盒置換構成，Ki是一些由密鑰編排函數產生的子密鑰。第三步：逆初始置換IP-1對L16R16進行交換得到R16L16對R16L16利用IP-1作逆置換，就得到了密文y。16輪迭代k1+fL0R0L1=R0L15=R14組碼移位kik16+ff初始置換IP輪運算：Li

=Ri-1Ri=Li-1⊕f(Ri-1,Ki)（i=1,2,3…16）初始逆置換IP-1DES的一輪迭代Li-1

（32bit）Ri-1

（32bit）選擇擴展運算E盒48bit寄存器48bit寄存器選擇壓縮運算S盒32bit寄存器置換運算PRi=Li-1⊕f(Ri-1,ki)（32bit）（32bit）⊕⊕Li=Ri-1輪開始：64bit分成左右兩半子密鑰Ki

（48bit）子密鑰計算

在64位密鑰中，由于不考慮每個字節的第8位(校驗位)，DES密鑰由64位減至56位。將這56位密鑰分解成16個48位的子密鑰，每個子密鑰控制一次迭代過程。每個子密鑰參與加密或解密運算過程，從而直接影響到加密或解密變換的結果。密鑰(56位)密鑰(64位)置換選擇1循環左移密鑰(56位)置換選擇2密鑰(48位)密鑰計算邏輯64位密鑰置換選擇1C0(28位)D0(28位)循環左移循環左移C1D1置換選擇2K1(48位)(56位)循環左移循環左移C16D16(56位)置換選擇2(48位)K16DES實際上就是一種單字符替代，而這種字符的長度是64bit。也就是說，對于DES算法，相同的明文就產生相同的密文。這對DES的安全性來說是不利的。為了提高DES的安全性，可采用加密分組鏈接的方法。DES的明顯缺點密文分組連接模式（CBCCipherBlockChaining）

X0Y0X1Y1X2Y2X3Y3X0Y0X1Y1X2Y2X3Y3……初始向量初始向量密鑰密鑰明文明文密文密文加密解密EEEEDDDD明文分組與前一個密文分組相加作為加密算法的輸入（第一個明文分組則與初始設定的向量IV相加作為加密算法的第一個輸入）。DES

的保密性DES的保密性僅取決于對密鑰的保密，而算法是公開的。盡管人們在破譯DES方面取得了許多進展，但至今仍未能找到比窮舉搜索密鑰更有效的方法。DES是世界上第一個公認的實用密碼算法標準，它曾對密碼學的發展做出了重大貢獻。目前較為嚴重的問題是DES的密鑰的長度。現在已經設計出來搜索DES密鑰的專用芯片。

二重DES(DoubleDES)給定明文P和兩個加秘密鑰k1和k2，采用DES對P進行加密E，有密文C=EK2(EK1(P))對C進行解密D，有明文P=DK1(DK2(C))EEPXCK2K1加密圖DDK2K1CXP解密圖二重DES很難抵擋住中間相遇攻擊法（Meet-in-the-MiddleAttack)二重DES(DoubleDES)40由

C=EK2(EK1(P))從圖中可見

X=EK1(P)=DK2(C)EEPCXK1K2DDCPXK2K1加密解密若給出一個已知的明密文對（P,C)做：對256個所有密鑰K1做對明文P的加密，得到一張密鑰對應于密文X的一張表；類似地對256個所有可能的密鑰K2做對密文C的解密，得到相應的“明文”X。做成一張X與K2的對應表。比較兩個表就會得到真正使用的密鑰對K1,K2。Tuchman給出雙密鑰的EDE模式（加密-解密-加密）：

C=EK1(DK2(EK1(P)))……對P加密

P=DK1(EK2(DK1(C)))……對C解密這種替代DES的加密較為流行并且已被采納用于密鑰管理標準（TheKeyManagerStandardsANSX9.17和ISO8732).TDEA——三重DES41到目前為止，還沒有人給出攻擊三重DES的有效方法。對其密鑰空間中密鑰進行蠻干搜索，那么由于空間太大為2112=5×1033，這實際上是不可行的。若用差分攻擊的方法，相對于單一DES來說復雜性以指數形式增長，要超過1052。注意：1*.Merkle和Hellman設法創造一個條件，想把中間相遇攻擊（meet-in-the-middleattack）的方法用于三重DES，但目前也不太成功。2*.雖然對上述帶雙密鑰的三重DES到目前為止還沒有好的實際攻擊辦法，但人們還是放心不下，又建議使用三密鑰的三重DES，此時密鑰總長為168bits.

C=EK3(DK2(EK1(P)))TDEA——三重DES2023/2/543IDEA瑞士聯邦技術學院來學嘉（X.J.Lai）和J.L.Massey提出的第1版IDEA（internationaldataencryptionalgorithm，國際數據加密算法）于1990年公布，當時稱為PES（proposedencryptionstandard，建議加密標準）。1991年，在Biham和Shamir提出差分密碼分析之后，設計者推出了改進算法IPES，即改進型建議加密標準。1992年，設計者又將IPES改名為IDEA，目前已在PGP中采用。2023/2/544IDEAIDEA加密算法是在DES算法的基礎上發展而來的，類似于三重DES算法，其分組長度也是64位，但密鑰長度是128位，增加了破譯難度。IDEA使用的運算有異或、模216加法和模（216+1）乘法算法的強度主要是通過有效的混淆和擴散特性而得以保證。IDEA可方便地通過軟件和硬件實現現代計算機速度的迅速提高，使得只有56bit密鑰的DES算法的安全性面臨著極大的挑戰。1997年，NIST公開征求AES（AdvancedEncryptionStandard）作為2001年以后的數據加密標準。1998年8月，AES召開第一次候選會，確定15個算法入圍。1999年3月，AES召開第二次候選會，有5個算法入圍（MARS,RC6,Rijndael,Serpent和Twofish）。2000年10月，NIST選出由比利時的JoanDaemen和VincentRijmen提交的Rijndael算法作為AES。2001年夏天，NIST頒布新的信息處理標準（FIPS），將Rijndael算法作為AES。高級加密標準(AES，AdvancedEncryptionStandard)45高級加密標準(AES，AdvancedEncryptionStandard)46分組長度（bit）128192256密鑰長度（bit）128192256Rijndael是一個分組密碼算法，其分組長度和密鑰長度相互獨立，都可以改變。輪數（Round）的不同取值輪數（Round）BlockLength=128BlockLength=192BlockLength=256KeyLength=128101214KeyLength=192121214KeyLength=256141414高級加密標準(AES)AES算法的每一步都是可逆的。算法有多輪相同的運算，每一輪包括4個步驟：非線性代替（S-盒）行循環左移（ShiftRow）列混合變換（MixColum）與擴展密鑰相異或每一輪的子密鑰從擴展密鑰中取出，輪密鑰長度等于分組長度密鑰擴展過程同時應用了非線性變換和循環左移算法定義的所有運算都是在有限域GF(28)上進行的AES加密算法概述1.強力攻擊法強力攻擊可用于任何分組密碼，且攻擊的復雜度僅依賴于分組長度和密鑰長度。工作效率包括加/解密速度、密鑰擴展速度、存儲空間等2.差分密碼分析已知最有效的攻擊迭代密碼的方法之一。基本思想是通過分析明文對的差值對密文對的差值的影響來恢復某些密鑰比特。差分密碼分析最初是針對DES加密提出的一種攻擊方法，能成功破解輪數較低的DES。

對稱密鑰的密碼分析方法493.線性密碼分析本質上是一種已知明文攻擊法，是對DES加密方法進行破譯的主要方法。基本思想是通過尋找一個給定密碼算法的有效的線性近似表達式來破譯密碼系統。4、差分-線性密碼分析對差分密碼分析和線性密碼分析進行改進，是降低它們復雜度的眾多改進之一。它利用的是差分密碼分析和線性密碼分析相結合的技術。

對稱密鑰的密碼分析方法505、插值攻擊利用了拉格朗日插值公式的思想。如果一個密碼算法是固定的密鑰的低次多項式函數，或項數較少的多項式，其項數可以估算出來，則通過插值法可以得到其代數表達式，從而可能恢復出密鑰。對稱密鑰的密碼分析方法51非對稱密鑰體制（公鑰密碼體制）在擁有大量用戶的通信網絡，若想讓兩兩用戶都能進行保密通信，即要求(1)任意一對用戶共享一個會話密鑰(2)不同的用戶對共享的會話密鑰不相同對于分配中心，N個用戶則需要分配CN2個會話密鑰，大量的數據存儲和分配是一件很麻煩的事，在計算機網絡環境下顯的尤為突出。另外傳統密碼不易實現數字簽名，也進一步限制了其發展。公開密鑰算法的提出非對稱密鑰體制（公鑰密碼體制）公鑰密碼學是1976年由Diffie和Hellman在其“密碼學新方向”一文中提出的，見文獻：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography，

IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公開密鑰算法是非對稱算法，即密鑰分為公鑰和私鑰，因此稱雙密鑰體制雙鑰體制的公鑰可以公開，因此也稱公鑰算法公鑰算法的出現，給密碼的發展開辟了新的方向。公鑰算法雖然已經歷了30多年的發展，但仍具有強勁的發展勢頭，在鑒別系統和密鑰交換等安全技術領域起著關鍵的作用非對稱密鑰體制（公鑰密碼體制）加密與解密由不同的密鑰完成已知密碼算法和加密密鑰，求解密密鑰在計算上是不可行的兩個密鑰中任何一個都可以作為加密密鑰，而另一個用作解密密鑰公開密鑰算法的基本要求

用公鑰密碼實現保密PKB是公開鑰，SKB是秘密鑰因為只有B知道SKB，所以其他人都無法對c解密。c=EPKB[m]m=DSKB[EPKB[m]]用公鑰密碼實現鑒別c=ESKA[m]m=DPKA[c]因為從m得到c是經過A的秘密鑰SKA加密，只有A才能做到。因此c可當做A對m的數字簽字。另一方面，任何人只要得不到A的秘密鑰SKA就不能篡改m，所以以上過程獲得了對消息來源和消息完整性的認證。用公鑰密碼體制實現認證和保密58c=EPKB[ESKA[m]]m=DPKA[DSKB[c]]公鑰密碼體制往往基于一個數學難題基于離散對數求解困難性（DLP）的公開密鑰密碼體制

離散對數難題是多個公開密鑰密碼算法的基礎，如Diffie-Hellman的密鑰交換算法和DSA數字簽名算法。基于大整數分解難題（IFP）的公開密鑰密碼體制

第一個完全意義上的公開密鑰密碼體制是由RonRivest，AdiShamir和LenAdleman創設的RSA算法。這是一個基于大整數分解困難性的密碼算法。非對稱密鑰體制（公鑰密碼體制）59在模p運算下，已知p和a，對任意的整數Y，存在唯一的1≤i≤P-1，使得Y≡ai(modP)，i被稱為以a為底（模p）Y的離散對數，記為INDa,p(y)。模數為p=11，以a=7為底，可得數值y的離散對數的列表離散對數求解困難性60i123456789107i(mod11)75231046981設a為模p的本原根，p是一個素數，則在模p運算下底a的冪ai（i=1，2，3，…P-1）互不相同，取遍1，2，3，…P-1。如p=11,a=7y12345678910IND7,11(y)10346271985求離散對數是求冪運算的逆運算。求冪運算與其逆運算相比，前者易于計算，而后者則難計算。特別在模數很大（如100位以上的大素數）的運算中，求離散對數成為數學的難題。離散對數求解困難性61Diffie-Hellman的密鑰交換算法是基于離散對數難解這一數學難題構建的。設p為一個大素數，給定模p的一個本原元a，（p,a）是公開的。A，B雙方為建立共享的密鑰，執行如下的協議：①AB：ax(modp)②BA：ay(modp)③A對收到的ay求(ay)x=ayx(modp)④B對收到的ax求(ax)y=axy(modp)A，B雙方建立了共享的密鑰K=

(ay)x(modp)=axy(modp)在該協議中，x是A的秘密密鑰，y是B的秘密密鑰。第三者獲得ax和ay，無論由ax求x或由ay求y都是離散對數求解的難題。而無法求得x或y，就不能獲得A，B的共享密鑰axy(modp)。Diffie-Hellman的密鑰交換算法62D-H算法可能遭受中間人攻擊ManintheMiddleAttack

63YC=azYA=axYB=ayYC=azK2=azxK1=azyD-H算法沒有提供關于雙方身份的任何信息，容易遭受中間人攻擊D-H的改進措施1992年Diffie,vanOorschot和Wiener開發了authenticatedDiffie-Hellmankeyagreementprotocol，或稱為Station-to-Station(STS)協議，它用于防止在Diffie-Hellmankeyagreementprotocol上的中間人攻擊。它對中間人攻擊的免疫來自于兩方面，一個是使用數字簽名來相互認證，另一個是使用public-keycertificate。

D-H算法的改進65Diffie-Hellmankeydistributionscheme的變形能夠用于安全交換密鑰publishedin1985byElGamal:T.ElGamal,"APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms",IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.

安全性是基于離散對數缺點：增加了消息長度（2倍）ElGamal公鑰加密方案密鑰建立密鑰生成：選取一個大素數p及本原根a接收者Bob有一個密秘鑰

XB

計算yB=aXB

modp

公開yBElGamal加密為加密M，發送者選擇隨機數k,0<=k<=p-1，（發送者私鑰）

計算消息密鑰K:K=yBkmodp

=(aXB)kmodp

計算密文對:C={C1,C2}

C1=akmodp

C2=K.Mmodp

=(aXB)kMmodp

發送到接收者k

需要永久保密ElGamal解密首先計算messagekeyKK=C1XB

modp=ak.XBmodp

計算明文:M=C2.K-1

modp

ElGamal方法是概率密碼系統，即同一個明文在不同的時間由相同加密者加密會產生不同的密文①系統不需要保存秘密參數，所有的系統參數均可公開；②復雜度比RSA方法要大。

ElGamal方法的優點70RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一種用數論構造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應用。

RSA算法9p和q是素數 （秘密的）n=p×q

(公開密鑰)

（非秘密的）(n)=(p-1)(q-1)

（秘密的）e是公開密鑰(加密密鑰) （非秘密的）d是秘密密鑰(解密密鑰） （秘密的）m是明文 （秘密的）c是密文 （非秘密的）加密算法：c=E(m)≡me(modn)解密算法：m=D(c)≡cd(modn)e滿足條件：e和(p-1)(q-1)互素，即(e,

(n))=1d滿足條件：ed≡1mod(p-1)(q-1)RSA描述RSA密鑰產生1.隨機選擇兩素數p和q

(長度在100位左右)2.計算公開模數：n=p×q3.計算秘密的歐拉指示函數：(n)=(p-1)(q-1)

4.選擇隨機數e(即加密密鑰)，使之與(n)互素即gcd(e,(n))=15.計算解密密鑰d=e-1mod(n)6.公布整數n和加密密鑰e，并將d秘密保存為其秘密密鑰。p和q

可以毀去不用，以增加其安全性。RSA加解密過程設B欲將明文m秘密傳送給A1.B在公開檔案庫中找出A的公開密鑰E(e，n)。2.將m分組為m=m1m2…mr，使得每個分組對應的十進制數小于n3.B對每一分組執行加密操作：c=me(modn)4.B將c傳送給A。5.A收到密文c后，利用其私有密鑰d，執行解密操作：m=cd(modn)RSA的安全性是基于分解大整數的困難性假定，之所以為假定是因為至今還未能證明分解大整數就是NP問題，也許有尚未發現的多項式時間分解算法。如果RSA的模數n被成功地分解為p×q，則立即獲得φ(n)=(p-1)(q-1)，從而能夠確定e模φ(n)的乘法逆元d，即d≡e-1modφ(n)，因此攻擊成功。RSA的安全性26隨著人類計算能力的不斷提高，原來被認為是不可能分解的大數已被成功分解。

例如RSA-129（即n為129位十進制數，大約428個比特）已在網絡上通過分布式計算歷時8個月于1994年4月被成功分解RSA-130已于1996年4月被成功分解RSA-140已于1999年2月被成功分解RSA-155（512比特）已于1999年8月被成功分解，得到了兩個78位（十進制）的素數。RSA的安全性27對于大整數的威脅除了人類的計算能力外，還來自分解算法的進一步改進。分解算法過去都采用二次篩法，如對RSA-129的分解。而對RSA-130的分解則采用了一個新算法，稱為推廣的數域篩法，該算法在分解RSA-130時所做的計算僅比分解RSA-129多10%。將來也可能還有更好的分解算法因此在使用RSA算法時對其密鑰的選取要特別注意其大小。估計在未來一段比較長的時期，密鑰長度介于1024比特至2048比特之間的RSA是安全的。RSA的安全性28RSA參數的選擇1.P與q必須為強素數2.P與q的差必須很大（差幾個位以上）3.p-1與q-1的最大公因子應很小4.e不可以太小5.d的長度不得小于N長度的1/4DES與RSA的比較1.處理效率方面：DES優于RSA2.密鑰管理方面：RSA優于DES3.安全性方面：一樣4.簽名和認證方面：RSA可以RSA的安全性橢圓曲線系統第一次應用于密碼學上是于1985年由Koblitz與Miller分別提出橢圓曲線密碼體制在相同的安全強度下所要求的密鑰強度僅是RSA的1/6，因此在運算速度和存儲空間方面具有很大的優勢，在實際應用中具有很大的使用價值。橢圓曲線密碼79令p>3為質數，在GF(p)中的橢圓曲線E:y2=x3+ax+bmodp，其中，4a3+27b2≠0(modp)。曲線上另定義一個無窮遠點O，對任一點A∈E，A+O=O+A=A。在E上定義加法運算令A=(x1，y1)與B=(x2，y2)為E上的點。若x2=x1，且y2=-y1，則A+B=O;

否則A+B=(x3，y3)，其中：x3=λ2-x1-x2，y3=λ(x1-x3)-y1，且λ=(y2-y1)/(x2-x1)在此加法運算下，E為Abel群。橢圓曲線定義80橢圓曲線密碼體制是基于橢圓曲線群上的離散對數問題（ECDLP）的難解性。K=tG

[其中K,G為Ep(a,b)上的點，t為小于n（n是點G的階）的整數]（相當于冪運算）給定t和G，根據加法法則，計算K很容易；

但給定K和G，求t就相對困難(稱為橢圓曲線上的離散對數，ECDLP)橢圓曲線密碼體制（ECC，EllipticCurveCryptosystem）81橢圓曲線密碼體制橢圓曲線密碼體制橢圓曲線密碼體制一個利用橢圓曲線進行加密通信的過程：

1、用戶A選定一條橢圓曲線Ep(a,b)，并取橢圓曲線上一點，作為基點G。2、用戶A選擇一個私有密鑰t，并生成公開密鑰K=tG。3、用戶A將Ep(a,b)和點K，G傳給用戶B。4、用戶B接到信息后，將待傳輸的明文編碼到Ep(a,b)上一點M（編碼方法很多），并產生一個隨機整數r（r<n）。5、用戶B計算點C1=M+rK；C2=rG。6、用戶B將C1、C2傳給用戶A。7、用戶A接到信息后，計算C1-tC2，結果就是點M。因為

C1-tC2=M+rK-t(rG)=M+rK-r(tG)=M8、再對點M進行解碼就可以得到明文。橢圓曲線密碼體制的優勢85橢圓曲線密碼體制的優勢86混合加密算法

87如果RSA和DES結合使用，則正好彌補RSA的缺點。即DES用于明文加密，RSA用于DES密鑰的加密。一種混合了非對稱和對稱加密算法的加密方式如圖：混合加密算法

88認證又稱為鑒別，是防止主動攻擊（如篡改、偽造信息等）的一項重要技術，解決網絡數據傳輸過程中可能出的非法訪問與篡改、假冒偽造、拒絕服務、抵賴等安全問題。

根據認證的目的，認證可包括：消息認證：證實收到的消息來自可信的源點且數據在傳輸和存儲過程中是否會被篡改、重放或延遲，常見的方法有：散列函數（Hash）：一個將任意長度的消息映射為定長的散列值的公共函數，以散列值作為認證碼。消息認證碼（MAC）：以一個消息的公共函數和用于產生一個定長值的密鑰作為認證碼。身份認證：驗證信息的發送者是否是合法的，即實體認證，包括信源、信宿的認證與識別。常用的方法包括：數字簽名身份識別技術3.5信息認證技術概述

89驗證某個指定的數據是否來源于某個特定的實體。為了確定被認證的實體與一些特定數據項有著靜態的不可分割的聯系。包括信源、信宿的認證與識別。典型技術有數字簽名技術 驗證消息的完整性以及數據在傳輸和存儲過程中是否會被篡改、重放或延遲。典型技術有Hash函數、消息認證碼3.6Hash函數與消息認證90Hash函數：把可變長度的輸入串M轉換成固定長度的輸出串h的一種函數。h＝H(M)Hash函數具備以下性質：Hash函數H可適用于任意長度的輸入數據塊，產生固定長度的Hash值。(數據指紋)對于每一個給定輸入數據M，都能很容易計算出它的Hash值H(M)。使得硬件和軟件實現成為實際可行如果給定Hash值h，要逆向推出輸入數據M在計算上不可行，即Hash函數具備單向性對于給定的消息M1和其Hash值H(M1)，找到滿足M2≠M1，且H（M2）＝H（M1）的M2在計算上是不可行的，即抗弱碰撞性要找到任何滿足H（M1）＝H（M2）且M1≠M2的消息對（M1，M2）在計算上是不可行的，即抗強碰撞性雪崩效應：當一個輸入位發生變化時，輸出位將有一半會發生變化3.6Hash函數與消息認證——

Hash函數91Hash函數92Hash函數的一般結構哈希函數的核心技術——設計無碰撞的壓縮函數f攻擊者對算法的攻擊重點是壓縮函數f

的內部結構，分析過程常常需要先找出壓縮函數f

的碰撞。由于是壓縮函數，其碰撞是不可避免的。因此，在設計壓縮函數f

時就應保證找出其碰撞在計算上是不可行的。常用的散列函數：MD5；SHA系列；Hash函數9390年代初由MIT（麻省理工學院MassachusettsInstituteofTechnology）

LaboratoryforComputerScience和RSADataSecurityinc.（RSA數碼保安公司）的RonaldRivest開發出來，經MD2、MD3和MD4發展而來MD5的典型應用是對一段信息（message）產生信息摘要（message-digest），以防止被篡改

MD5還廣泛用于加密和解密技術上

廣泛的應用于unix系統中

MD5（Message-DigestAlgorithm5）94MD5以512位分組來處理輸入文本，每一分組又劃分為16個32位子分組。算法的輸出由四個32位分組組成，將它們級聯形成一個128位散列值。MD595壓縮函數算法邏輯包含4個具有相似結構的“循環”，但每個循環使用不同的原始邏輯函數。每一循環都以當前的正在處理的512bit分組（Yq）和128bit的緩存值ABCD為輸入，然后更新緩存的內容。每一循環還使用一個64元素表T[1…64]的四分之一，該表通過正弦函數構建。這個表提供了一個“隨機化“的32bit模式集，它將消除輸入數據的任何規律性。第4次循環的輸出加到第1次循環的輸入（CVq）上產生CVq+1。相加是緩存中4個字分別與CVq中對應的4個字以模232相加。MD596壓縮函數單循環算法邏輯MD597循環原始函數g(b,c,d)1F(b,c,d)2G(b,c,d)3H(b,c,d)4I(b,c,d)每一循環由對緩存ABCD的16步操作組成。每一步操作的形式為：a←b+((a+g(b,c,d)+X[k]+T[i])<<<s)算法邏輯要點在一次循環的一步中，表T中64個32bit字元素中的每一個也只被使用一次。在每一步中，只有緩存ABCD的四個字節中的一個被更新。因此，該緩存的每個字節在這次循環中將被更新四次，然后在最后第五次產生這個分組的最后輸出。注意每一循環均要使用四個不同的循環左移，且在不同的循環中使用的不同。所有這些復雜操作的意義在于使產生沖突（兩個512bit分組產生相同的輸出）非常困難。MD598算法由來安全散列算法（SHA）由美國國家標準和技術協會（NIST）提出，并作為聯邦信息處理標準（FIPSPUB180）在1993年公布；1995年又發布了一個修訂版FIPSPUB180-1，通常稱之為SHA-1算法邏輯圖消息的總體算法邏輯圖與MD5的總體算法邏輯圖類似。算法輸入消息的最大長度不超過264

bit，輸入是按512bit的分組進行處理的，最后產生的輸出是一個160bit的消息摘要。SHA-199壓縮函數算法邏輯包含四個具有相似結構的“循環”，但每循環使用不同的原始邏輯函數。每一循環都以當前正在處理的512bit（Yq）和160bit的緩存值ABCDE為輸入，然后更新緩存的內容。第四循環（第80步）的輸出加到第一循環的輸入（CVq）產生CVq+l。相加是緩存中5個字分別與CVq中對應的5個字以模232相加。SHA-1100壓縮函數單循環算法邏輯SHA-1每一循環的操作邏輯為：A,B,C,D,E←(E+f(t,B,C,D)+S5(A)+Wt+Kt),A,S30(B),C,D其中A,B,C,D,E=緩存中的5個字t=

步驟數；0≤t≤79f(t,B,C,D)=步驟t的原始邏輯函數Sk=32bit參數循環左移（旋轉）k位Wt=由當前512bit輸入分組導出的一個32bit字Kt=一個額外的常數；使用四個不同的值+=模232加法壓縮函數單循環算法邏輯Wt前16個字的值直接取自當前分組中16個字的值。余下字的值定義如下：Wt=S1(Wt-16⊕Wt-14⊕Wt-8⊕Wt-3)SHA-1SHA-l利用Wt在壓縮函數中將16個分組字擴展為80個字，這將在壓縮的消息分組內引入許多冗余和相關，使尋找產生相同壓縮函數輸出的不同消息分組的工作更加復雜。對強行攻擊的安全性：最顯著和最重要的區別是SHA-1摘要比MD5摘要長32bit。使用強行技術，產生任何一個消息使其摘要等于給定消息摘要的難度對MD5是2128數量級的操作，而對SHA-l則是2160數量級的操作。此外，使用強行技術，產生具有相同消息摘要的兩個消息的難度對MD5是264數量級的操作，而對SHA-1則是280數量級的操作。這樣，SHA-1對強行攻擊有更大的強度。對密碼分析的安全性：由于MD5的設計，它易受密碼分析的攻擊。SHA-l顯得不易受這樣的攻擊。由于有關SHA-1的設計標準幾乎沒有公開，因此很難判斷其強度。速度：因為兩個算法都在很大程度上依賴模232的加法，因此兩者在32bit結構的機器上速度均很好。SHA-l有更多的步驟（80對64）且要處理160bit的緩存，相比之下MD5僅處理128bit的緩存。這樣在相同的硬件上，SHA-l的行速度應該比MD5慢。簡單性和緊湊性：兩個算法均描述簡單、易于實現，并且無需冗長的程序或很大的替換表。SHA-1與MD5的比較NIST已經在FIPS1820-2中頒布了三個修訂的sha標準。SHA-256,SHA-384,SHA-512修訂的sha標準2004年8月，在美國加州圣芭芭拉召開的國際密碼大會上，并沒有被安排發言的王小云教授拿著自己的研究成果找到會議主席，要求進行大會發言。就這樣，王小云在國際會議上首次宣布了她及她的研究小組的研究成果——對MD5、HAVAL－128、MD4和RIPEMD等四個著名密碼算法的破譯結果。在MD5被王小云為代表的中國專家破譯之后，世界密碼學界仍然認為SHA－1是安全的。2005年2月7日，美國國家標準技術研究院發表申明，SHA－1沒有被攻破，并且沒有足夠的理由懷疑它會很快被攻破，開發人員在2010年前應該轉向更為安全的SHA－256和SHA－512算法。而僅僅在一周之后，王小云就宣布了破譯SHA－1的消息。MD5和SHA-1的破解105TigerHash106TigerHash結構比MD5和SHA-1更復雜，接近于分組密碼。為了適應64位處理器，Tiger選擇輸出位數是192位。使用了4個S盒，每個S盒將8位映射成64位。還應用了密鑰擴展算法，對輸入分組進行擴展

MAC實質上是一個將雙方共享的密鑰k和消息m作為輸入的函數，如果將函數值記為MACK(M)，

，這個函數值就是一個認證標記，用δ表示。將MAC附加到消息中。接收者通過重新計算MAC來對消息進行認證。消息認證碼（MAC，Messages

Authentication

Codes）107MAC應具有的性質如果對手竊取到M和MACK(M)，試圖生成一個消息M’，使得MACK(M’)=MACK(M)，這在計算上不可行。MACK(M)應該能夠均勻分布。對于隨機選擇的消息M和M’，MACK(M)=MACK(M’)的概率為2-n，其中n為MAC的比特長度。讓M'為M的某種已知變換，即M'=f(M)。例如，f可能為將一個或多個特定的比特取反。在對種情況下，Pr[MACK(M)=MACK(M')]=2-n。MAC的構造方法有很多，主要類型是基于帶密鑰的Hash函數和基于分組密碼的構造方法消息認證碼利用對稱分組密碼體制（如DES、AES）的密碼分組鏈接模式（CBC）一直是構造MAC的最常見的方法。如CBC-MAC、XOR-MAC、EMAC（加密的CBC-MAC）、PMAC、XECB-MAC等CBC-MAC對消息使用CBC模式進行加密，取密文的最后一塊作為認證標記。被認證的數據（例如消息、記錄文件或者程序）被分為連續的等長的分組：D1，D2，…，DN。基于分組密碼的MAC基于DES的消息認證碼基于分組密碼的MACXOR-MACXOR-MAC有兩種方式：無狀態（XMACR）和有狀態（XMACC）。在計算過程中引入索引值使得分組密碼每次加密的明文各不相同，最后再將所有的密文異或。由于XOR-MAC使用異或來生成標記，這就為其帶來了并行性、增量式、亂序驗證等優點。攻擊XOR-MAC成功的概率要比攻擊CBC-MAC成功的概率低，并且這個概率跟消息長度沒有關系。缺點是在算法中引入了索引信息，引起了消息的擴展，導致了加密次數的成倍增加，降低了運算速度

基于分組密碼的MAC111XECB-MACXECB-MAC也可看成是XOR-MAC的一種改進，支持并行計算、增量式操作、亂序驗證等特性。

XECB-MAC沒有使用消息的有效位來記錄消息的位置，減少了加密的次數，因此它的速度要高于XOR-MAC，但低于CBC-MAC。該方法的不足之處在于使用了兩個密鑰，這給密鑰的存儲和分發帶來了困難。基于分組密碼的MAC112PMAC

PMAC可以看成是對XOR-MAC的改進，具有可并行、支持消息的添加、截短和替換等優點。PMAC在計算MAC的時候不需要事先知道消息的長度，且不需要一個隨機數或維持一個計數。但是，它的速度比CBC-MAC要慢，且該算法受專利保護，不能免費使用。基于分組密碼的MAC113OCBOCB是在綜合了PMAC和XCBC-MAC的構造方法的基礎上提出來的，同時提供了加密和認證。

OCB的優點有：能處理任意長度的消息、運算速度快、支持并行處理。缺點在于算法復雜并且受專利保護，不可免費使用。基于分組密碼的MAC114近幾年，人們越來越感興趣于利用哈希函數來設計MAC，這是因為像MD5、SHA-1這樣的哈希函數，其軟件執行速度比諸如DES這樣的對稱分組密碼要快。基于帶密鑰的Hash函數的構造方法最早是由M.Bellare等人提出的。它要求所使用的Hash函數具有迭代結構（如MD5，SHA-1等），即反復地使用壓縮函數f將長消息映射為短消息。然而，諸如SHA-1這樣的哈希函數并不是專門為MAC而設計的，由于哈希函數不依賴于密鑰，所以它不能直接用于MAC。目前，已經提出了許多方案將密鑰加到現有的哈希函數中。HMAC是最受支持的方案，并且在Internet協議中（如SSL）中有應用HMAC115算法由來HMAC是針對MAC設計的，是一個將一個密鑰與一個現有的散列函數結合起來的提議，是針對MAC設計的，能直接用作MAC。發表為RFC2104，已經作為IP安全中強制實行的MAC，同時也被其他的Internet協議如SSL使用。設計目標無需修改地使用現有的散列函數。特別是，散列函數的軟件實現執行很快，且程序代碼是公開的和容易獲得的。當出現或獲得更快的或更安全的散列函數時，對算法中嵌入的散列函數要能輕易地進行替換。保持散列函數的原有性能不會導致算法性能的降低。使用和處理密鑰的方式很簡單。基于對嵌入散列函數合理的假設，對認證機制的強度有一個易懂的密碼編碼分析。HMAC算法邏輯圖Yi=M中的第i個分組，0≤i≤L-1K=密鑰；如果密鑰的長度大于b，該密鑰輸入散列函數產生一個n比特的密鑰；推薦密鑰長度大于等于nK+=在K的左邊填充0，使總長度等于bipad=將00110110重復b／8次opad=將01011010重復b／8次HMACHMACK=H[(K+

⊕opad)||H[(K+

⊕ipad)||M]]和ipad異或的結果是使K中一半的比特值反轉。同樣的opad異或的結果也是使K中一半的比特值反轉，不同的是反轉的比特不同。從效果上看，Si和So通過散列函數中的壓縮函數將從K產生兩個偽隨機密鑰。對于長消息，HMAC的執行時間近似等于嵌入散列函數的執行時間。HMAC增加了三個散列壓縮函數（對Si、So和從內部散列函數產生的分組）的執行時間。對HMAC攻擊成功的概率等價于對嵌入散列函數進行如下攻擊中的一種：攻擊者能夠計算出壓縮函數的輸出，即使對攻擊來說IV是隨機的，秘密的和未知的。——攻擊所需運算的數量級為2n。攻擊者能夠找到散列函數的碰撞，即使IV是隨機的和秘密的。——攻擊所需運算的數量級雖為2n/2，但由于密鑰的存在，需要在線觀察由同一個密鑰產生的2n/2個分組，這在實際中是不可能的。HMAC1183.7數字簽名（DigitalSignature）技術每天都在使用簽名，如簽訂合同，在銀行取款，批復文件等等，但這些都是手寫簽名。數字簽名以電子方式存儲簽名消息，是在數字文檔上進行身份驗證的技術。數字簽名是附加在數據單元上的一些數據，或是對數據單元所做的密碼變換，這些數據變換允許數據的接受者用來確認數據單元來源和數據單元的完整性，并保護數據，防止被人偽造通過電子設備實現快速、遠距離交易，用于商業系統。數字簽名的要求類似于手寫簽名，數字鑒名也應滿足以下要求：(1)收方能夠確認或證實發方的簽名，但不能偽造(2)發方發出簽名的消息送收方后，就不能再否認他所簽發的消息：(3)收方對已收到的簽名消息不能否認，即有收到認證。(4)第三者可以確認收發雙方之間的消息傳送，但不能偽造這一過程。相比于MAC，數字簽名可以支持不可否認服務121數字簽名的特征簽名是不可偽造的：數字簽名證明是簽名者本人而不是別人簽署了文件簽名是可信的：簽名使文件的接受者相信簽名者慎重的簽署了該文件數字簽名不能重復使用：簽名是文件的一部分，任何人都不能把它轉移到別的文件上簽名后的文件是不能改變的簽名是不可否認的：簽名者不能事后聲稱他沒有簽署過文件數字簽名的組成簽名過程：包括數字簽名生成算法，以及某種將數據編碼成可簽名消息的方法。驗證過程：包括驗證算法，以及某種將消息恢復數據的解碼方法。數字簽名的組成122基于公鑰密碼體制和私鑰密碼體制都可以獲得數字簽名，目前主要是基于公鑰密碼體制的數字簽名，包括普通數字簽名和特殊數字簽名普通數字簽名算法有RSA、ElGamal、Fiat-Shamir、Guillou-Quisquarter、Schnorr、Ong-Schnorr-Shamir數字簽名算法、DES/DSA、橢圓曲線數字簽名算法和有限自動機數字簽名算法等特殊數字簽名有盲簽名、代理簽名、群簽名、不可否認簽名、公平盲簽名、門限簽名、具有消息恢復功能的簽名等，它與具體應用環境密切相關數字簽名的執行方法123基于公鑰密碼體制的數字簽名124BobAlice簽名驗證公共信道SKBPKBsigsig只有B知道SKB，能用它對消息進行簽名。傳輸中無法篡改。任何第三方可以用PKB驗證簽名。基本實現方案12023/2/5125基于公鑰密碼體制的數字簽名改進措施采用對稱密碼體制對簽名進行加密保護只有知道該密鑰的人才能對簽名進行解密，進而可以驗證簽名并獲得消息m的內容。

AB:Ek(ESK(m))MSEDVKKPKSKM公鑰加密速度比較慢2023/2/5126基于公鑰密碼體制的數字簽名基本方案2AB:m||ESK(h(m))Alice簽名驗證公共信道SKBPKBsigsigh(m)同時提供了消息完整性和消息源認證功能，由于h(m)具有數據壓縮功能，使得簽名處理的內容減少，速度加快。RSA數字簽名2023/2/5127簽名發送者簽名接收者原始消息mSHA-1H(m)RSA加密算法A的私鑰消息m摘要RSA解密算法消息m摘要A的公鑰SHA-1H(m)H’(m)？2023/2/5128ElGamal簽名方案該方案是由1985年提出的簽名方案,其變型已被美國國家標準技術研究所采納為數字簽名算法(DSA)。DSA同時吸收了被稱為schnorr簽名方案的一些思想。ElGamal簽名方案是一個隨機化簽名方案，他對任意長度的二元消息生成數字簽名，且需要一個雜湊函數h:{0,1}Zp，其中p是大素數。2023/2/5129ElGamal簽名方案ElGamal簽名方案的密鑰生成每個實體產生各自的公鑰和相應私鑰，實體A：2023/2/5130ElGamal簽名方案ElGamal簽名生成即使對同一個消息，不同的時間簽名也不同2023/2/5131ElGamal簽名方案ElGamal簽名驗證er×rs=

(αd)

αk×αkk-1{m-dαk}=αm公布于1994年5月19日的聯邦記錄上，并于1994年12月1日采納為標準DSS。DSS最初只支持DSA簽名算法，是ElGamal簽名方案的改進。(目前的標準增加