第2章 密碼學(xué)基礎(chǔ)教材

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)1第2章密碼學(xué)基礎(chǔ)2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)2本章主要內(nèi)容密碼學(xué)基本概念對(duì)稱密碼體制公鑰密碼體制散列函數(shù)數(shù)字簽名信息隱藏與數(shù)字水印2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)32.1概述經(jīng)典密碼：古埃及人用以保密傳遞的消息；

單表置換密碼——?jiǎng)P撒密碼，

多表置換密碼——Vigenere密碼近代密碼：DES數(shù)據(jù)加密標(biāo)準(zhǔn)——70年代Diffie,Hellman

的開創(chuàng)性工作——公鑰體制密碼應(yīng)用：電子數(shù)據(jù)，軍事目的，經(jīng)濟(jì)目的。應(yīng)用形式：數(shù)據(jù)的保密性、真實(shí)性、完整性。主要內(nèi)容：數(shù)據(jù)加密，分析，數(shù)字簽名，信息

鑒別，零泄密認(rèn)證，秘密共享等等。信息攻擊：主動(dòng)攻擊——對(duì)數(shù)據(jù)的惡意刪除、篡改等

被動(dòng)攻擊——從信道上截取、偷竊、拷貝

信息。

無(wú)意攻擊——錯(cuò)誤操作、機(jī)器故障等。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)42.1概述2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)52.1概述1)古代加密方法大約起源于公元前440年出現(xiàn)在古希臘戰(zhàn)爭(zhēng)中的隱寫術(shù)。當(dāng)時(shí)為了安全傳送軍事情報(bào)，奴隸主剃光奴隸的頭發(fā)，將情報(bào)寫在奴隸的光頭上，待頭發(fā)長(zhǎng)長(zhǎng)后將奴隸送到另一個(gè)部落，再次剃光頭發(fā)原有的信息復(fù)現(xiàn)出來(lái)，從而實(shí)現(xiàn)這兩個(gè)部落之間的秘密通信.2)密碼學(xué)用于通信的另一個(gè)記錄是斯巴達(dá)人于公元前400年應(yīng)用Scytale加密工具在軍官間傳遞秘密信息。Scytale實(shí)際上是一個(gè)錐形指揮棒，周圍環(huán)繞一張羊皮紙，將要保密的信息寫在羊皮紙上。解下羊皮紙，上面的消息雜亂無(wú)章、無(wú)法理解，但將它繞在另一個(gè)同等尺寸的棒子上后，就能看到原始的消息。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)62.1概述經(jīng)典密碼：古埃及人用以保密傳遞的消息；

單表置換密碼，凱撒密碼，

多表置換密碼，Vigenere密碼等等3)我國(guó)古代也早有以藏頭詩(shī)、藏尾詩(shī)、漏格詩(shī)及繪畫等形式，將要表達(dá)的真正意思或“密語(yǔ)”隱藏在詩(shī)文或畫卷中特定位置的記載，一般人只注意詩(shī)或畫的表面意境，而不會(huì)去注意或很難發(fā)現(xiàn)隱藏其中的“話外之音”4)16世紀(jì)意大利數(shù)學(xué)家卡爾達(dá)諾發(fā)明的一種保密通信方法，史稱“卡爾達(dá)諾漏格板”．漏格板是一張用硬質(zhì)材料(如硬紙、羊皮、金屬等)做成的板，上面挖了一些長(zhǎng)方形的孔，即漏格．2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)7Polybius的校驗(yàn)表——表中包含許多后來(lái)在加密系統(tǒng)中非常常見的思想，如代替與換位。Polybius校驗(yàn)表由一個(gè)5×5的網(wǎng)格組成（如表1-1所示），網(wǎng)格中包含26個(gè)英文字母，其中I和J在同一格中。每一個(gè)字母被轉(zhuǎn)換成兩個(gè)數(shù)字，第一個(gè)是字母所在的行數(shù)，第二個(gè)是字母所在的列數(shù)。如字母A就對(duì)應(yīng)著11，字母B就對(duì)應(yīng)著12，以此類推。使用這種密碼可以將明文“message”置換為密文“32

15

43

43

11

22

15”。在古代，這種棋盤密碼被廣泛使用。2.1概述2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)82.1概述123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)92024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)102.1概述2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)111941年12月，日本取得了突襲珍珠港、摧毀美國(guó)太平洋艦隊(duì)主力的重大勝利，為了完全控制太平洋，并設(shè)法誘出在珍珠港的美國(guó)艦隊(duì)殘部予以徹底消滅，日本制定了于1942年6月突然攻擊夏威夷前哨中途島的計(jì)劃?！型緧u之戰(zhàn)中途島戰(zhàn)役，是第二次世界大戰(zhàn)的一場(chǎng)重要戰(zhàn)役，也是美國(guó)海軍以少勝多的一個(gè)著名戰(zhàn)例。1942年6月4日展開，美國(guó)海軍不僅在此戰(zhàn)役中成功地?fù)敉肆巳毡竞＼妼?duì)中途島環(huán)礁的攻擊，還得到了太平洋戰(zhàn)區(qū)的主動(dòng)權(quán)，因此成為二戰(zhàn)太平洋戰(zhàn)區(qū)的轉(zhuǎn)折點(diǎn)。2.1概述2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)12當(dāng)時(shí)日本海軍使用的是日本最高級(jí)的密碼體制——紫密，它的第二版本JN25b自1940年12月1日啟用后應(yīng)在1942年4月1日內(nèi)第三版本JN25c替換。但由于艦船分散在廣闊的海域不停地轉(zhuǎn)移，給分發(fā)新的版本增添許多困難，因此替換工作延期到5月1日，后因同樣的原因再延期—個(gè)月，到6月1日啟用新版本。這就使盟國(guó)破譯人員有充分的時(shí)間更透徹地破解JN25b。5月27日，山本的作戰(zhàn)命令已基本上被破譯，美國(guó)太平洋艦隊(duì)司令尼米茲海軍上將發(fā)布作戰(zhàn)計(jì)劃，將3艘航空母艦部署在敵艦不可能偵察到的海域，戰(zhàn)斗打響時(shí)也以突然攻擊的方式打擊日軍的突擊艦隊(duì)。6月4日，日軍4艘巨型航空母艦在一日之內(nèi)相繼被炸沉．從此日本海軍由進(jìn)攻轉(zhuǎn)為防御，最終走向失敗。2.1概述2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)131943年春天，山本五十六為了控制不斷惡化的殘局，親自前住所羅門群島基地巡視，以鼓舞士氣。在視察前五天，1943年4月13日，日軍第八艦隊(duì)司令將山本行將視察的行程、時(shí)間表，用JN25體制加密后播發(fā)給有關(guān)基地，以作好迎接的準(zhǔn)備，盡管該體制的所用版本在4月1日剛換過，但美國(guó)破譯人員根據(jù)過去的經(jīng)驗(yàn)，迅速地破譯了這份密報(bào)，美軍決定在空中打掉山本的座機(jī)，使日軍失去一位戰(zhàn)略家，沉重地打擊日軍士氣。經(jīng)過精心組織，周密安排，終于使山本五十六在飛往視察地途中，被美軍飛機(jī)擊落，葬身于叢林深處。2.1概述2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)14密碼學(xué)的理論基礎(chǔ)1949年ClaudeShannon發(fā)表的“保密系統(tǒng)的通信理論”（TheCommunicationTheoryofSecrecySystems），這篇文章發(fā)表了30年后才顯示出它的價(jià)值。1976年W.Diffie和M.Hellman發(fā)表了“密碼學(xué)的新方向”（NewDirectionsinCryptography）一文，提出了適應(yīng)網(wǎng)絡(luò)上保密通信的公鑰密碼思想，開辟了公開密鑰密碼學(xué)的新領(lǐng)域，掀起了公鑰密碼研究的序幕受他們的思想啟迪，各種公鑰密碼體制被提出，特別是1978年RSA公鑰密碼體制的出現(xiàn)，成為公鑰密碼的杰出代表，并成為事實(shí)標(biāo)準(zhǔn)，在密碼學(xué)史上是一個(gè)里程碑。1976美國(guó)國(guó)家標(biāo)準(zhǔn)局（NBS，即現(xiàn)在的國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所NIST）正式公布實(shí)施了美國(guó)的數(shù)據(jù)加密標(biāo)準(zhǔn)（DataEncryptionStandard，DES），公開它的加密算法，并被批準(zhǔn)用于政府等非機(jī)密單位及商業(yè)上的保密通信。

2.1概述2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)15一個(gè)簡(jiǎn)單的加密算法—異或2.2密碼學(xué)基本概念2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)16一個(gè)簡(jiǎn)單的加密算法—異或異或

密文：0110

解密： 密鑰：

0101

明文：0011 已知明文、密文，怎樣求得密鑰？C=PKP=CK異或運(yùn)算（不帶進(jìn)位加法）： 明文:0011

加密： 密鑰:0101

密文：0110K=CP只知道密文，如何求得密文和密鑰？2.2密碼學(xué)基本概念2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)17密碼學(xué)基本模型發(fā)送方接收方EncryptionDecryption加密：c=EK(m)解密：m=DK(c)不安全信道密碼分析（Cryptanalysis）PlaintextciphertextplaintextKeyKey2.2密碼學(xué)基本概念2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)18密碼編碼：通過信息編碼使信息保密密碼分析：用分析方法解密信息術(shù)語(yǔ)明文(plaintext)，密文(ciphertext)加密(encrypt,encryption),解密(decrypt,decryption)密碼算法（Algorithm），密碼（Cipher）:用來(lái)加密和解密的數(shù)學(xué)函數(shù)

c=E(m),m=D(c),D(E(m))=m密鑰（Key）:算法中的一個(gè)變量

c=EKe(m),m=DKd(c),DKd(EKe(m))=m2.2密碼學(xué)基本概念2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)192.2密碼學(xué)基本概念現(xiàn)代密碼系統(tǒng)的組成現(xiàn)代密碼系統(tǒng)(通常簡(jiǎn)稱為密碼體制)一般由五個(gè)部分組成：明文空間M

密文空間C

密鑰空間K

加密算法E

解密算法D

則五元組（M，C，K，E，D）稱為一個(gè)密碼體制。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)20現(xiàn)代密碼算法把算法和密鑰分開密碼算法可以公開，密鑰保密密碼系統(tǒng)的安全性在于保持密鑰的保密性發(fā)送方接收方mm加密E解密Dc=Ek(m)m=Ek(c)密碼分析密鑰分配（秘密信道）kk2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)21密碼體制細(xì)分

對(duì)稱密鑰體制

非對(duì)稱密鑰體制

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)22根據(jù)密碼算法對(duì)明文信息的加密方式，對(duì)稱密碼體制常分為兩類：分組密碼(Blockcipher，也叫塊密碼)——DES、IDEA、BLOWFISH序列密碼(Streamcipher，也叫流密碼)。

——A5、FISH、PIKE

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)23密碼分析學(xué)窮舉攻擊：又稱作蠻力攻擊，是指密碼分析者用試遍所有密鑰的方法來(lái)破譯密碼對(duì)可能的密鑰或明文的窮舉統(tǒng)計(jì)分析攻擊：指密碼分析者通過分析密文和明文的統(tǒng)計(jì)規(guī)律來(lái)破譯密碼。

數(shù)學(xué)分析攻擊：指密碼分析者針對(duì)加密算法的數(shù)學(xué)依據(jù)，通過數(shù)學(xué)求解的方法來(lái)破譯密碼。

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)241、唯密文攻擊：僅根據(jù)密文進(jìn)行的密碼攻擊；2、已知明文攻擊：根據(jù)一些相應(yīng)的明、密文對(duì)進(jìn)行的密碼攻擊。3、選擇明文攻擊：可以選擇一些明文，并獲取相應(yīng)的密文，這是密碼分析者最理想的情形。例如，在公鑰體制中。4、選擇密文攻擊：密碼分析者能選擇不同的被加密的密文，并可得到對(duì)應(yīng)的解密的明文，密碼分析者的任務(wù)是推出密鑰。5、選擇密鑰攻擊：這種攻擊并不表示密碼分析者能夠選擇密鑰，它只表示密碼分析者具有不同密鑰之間關(guān)系的有關(guān)知識(shí)。6、軟磨硬泡攻擊：密碼分析者威脅、勒索，或者折磨某人，直到他給出密鑰為止。

根據(jù)密碼分析者掌握明、密文的程度密碼分析可分類為：2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)25密碼算法的安全性：

理論上，除一文一密外，沒有絕對(duì)安全的密碼體制，通常，稱一個(gè)密碼體制是安全的是指計(jì)算上安全的，即：密碼分析者為了破譯密碼，窮盡其時(shí)間、存儲(chǔ)資源仍不可得，或破譯所耗資材已超出因破譯而獲得的獲益。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)262.3對(duì)稱密碼體制經(jīng)典的密碼體制中，加密密鑰與解密密鑰是相同的，或者可以簡(jiǎn)單相互推導(dǎo)，也就是說：知道了加密密鑰，也就知道了解密密鑰；知道了解密密鑰，也就知道了加密密鑰。所以，加、解密密鑰必須同時(shí)保密。這種密碼體制稱為對(duì)稱（也稱單鑰）密碼體制。最典型的是DES數(shù)據(jù)加密標(biāo)準(zhǔn)，應(yīng)該說數(shù)據(jù)加密標(biāo)準(zhǔn)DES是單鑰體制的最成功的例子。

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)271973.5.15：美國(guó)國(guó)家標(biāo)準(zhǔn)局（NSA）公開征求密碼體制的聯(lián)邦注冊(cè)；1975.3.17：DES首次在《聯(lián)邦記事》公開，它由IBM開發(fā)，它是LUCIFER的改進(jìn)；1977.2.15：DES被采用作為非國(guó)家機(jī)關(guān)使用的數(shù)據(jù)加密標(biāo)準(zhǔn)，此后，大約每五年對(duì)DES進(jìn)行一次審查，1992年是最后一次審查，美國(guó)政府已聲明，1998年后對(duì)DES不再審查了；1977.2.15：《聯(lián)邦信息處理》標(biāo)準(zhǔn)版46（FIPSPUB46）給出了DES的完整描述。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)282.3.1DES分組密碼系統(tǒng)DES是DataEncryptionStandard（數(shù)據(jù)加密標(biāo)準(zhǔn)）的縮寫。它是由IBM公司研制的一種加密算法,數(shù)十年來(lái)，它一直活躍在國(guó)際保密通信的舞臺(tái)上，扮演了十分重要的角色。DES是一個(gè)分組加密算法，它以64位為分組對(duì)數(shù)據(jù)加密。同時(shí)DES也是一個(gè)對(duì)稱算法：加密和解密用的是同一個(gè)算法它的密鑰長(zhǎng)度是56位（因?yàn)槊總€(gè)第8位都用作奇偶校驗(yàn)），密鑰可以是任意的56位的數(shù)。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)292.3.1DES分組密碼系統(tǒng)DES加密算法：

（一）初始置換：x0=L0R0=IP(x)；64位明文按照32分組，并用函數(shù)IP進(jìn)行初始置換（二）16次迭代：xi-1=Li-1Ri-1，

Li=Ri-1，Ri=Li-1

f(Ri-1,ki)

Li-1，Ri-1分別為xi-1的前32位和后32位，

是異或運(yùn)算f由S置換構(gòu)成，ki是由初始的56位經(jīng)過密鑰編排函數(shù)產(chǎn)生的48位塊（三）逆置換：x16=L16R16，y=IP-1(x16)分別解釋：密鑰生成器：密鑰ki是由56位系統(tǒng)密鑰k生成的32位子密鑰。函數(shù)f及S盒：f(Ri-1,ki)=P(S(E(Ri-1)

ki))2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)30

其中：——E，P是兩個(gè)置換——

表示比特的“異或”——S是一組八個(gè)變換S1，S2，S3，…，S8，稱為S盒，每個(gè)盒以6位輸入，4位輸出2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)312.3.1DES分組密碼系統(tǒng)明文（64bits）IP置換（64bits）L0(32bits)R0(32bits)L1=R0R1=L0f(R0,k1)fki+16輪同樣運(yùn)算…L16+R16=L15f(R15,ki)+IP-1置換（64bits）DES算法結(jié)構(gòu)2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)32IP置換表58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157(1)58表示：結(jié)果中位于第1個(gè)位置的值，等于原文中第58個(gè)位置的值(2)圖中的一格代表1bit，共有64bit，即8字節(jié)DES：IP置換2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)33初始換位（IP）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157M=m1m2,……m62m63,m64M’=m58m50,……m23m15,m7IP(M)DES：IP置換2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)34DES：f

的結(jié)構(gòu)(即黑盒變換)R（32bit）EE(R)（48bit）K（48bit）B1

B2

B3

B4

B5

B6

B7

B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8P+（48bit）（32bit）2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)35

Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器擴(kuò)充/置換運(yùn)算48比特寄存器子密鑰Ki（48比特）32比特寄存器代換/選擇運(yùn)算置換運(yùn)算PRi（32比特）Li=Ri-1DES的一輪迭代f函數(shù)2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)36DES:F函數(shù)Expansion:32

48（擴(kuò)充）S-box:64（壓縮）Permutation:置換2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)37擴(kuò)展置換(E)將Ri從32位擴(kuò)展到48位目的：輸入的一位影響下一步的兩個(gè)替換，使得輸出對(duì)輸入的依賴性傳播得更快，密文的每一位都依賴于明文的每一位12345678123456783248321234545678989….313211234567891011121314……4647482024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)38S－盒置換將48比特壓縮成32比特ES1S2S3S4S5S6Ri-1(32bits)Ki(48bits)48bitsS7S82024/3/1939S－盒置換輸入6比特:b1b2b3b4b5b6輸出4比特：S(b1b6,b2b3b4b5)S1b1b2b3b4b5b60123456789101112131415S101441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S2015181461134972131205101..........23舉例：S1(100110)=10008=b1b2b3b42024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)40S-盒的設(shè)計(jì)原則S-盒的設(shè)計(jì)原理沒有公開，一些原則如下：所有S-盒的每一行是0,1,…,15的一個(gè)置換；所有S-盒的輸出都不是輸入的線性函數(shù)或仿射函數(shù)；S-盒的輸入改變?nèi)我庖晃欢紩?huì)引起輸出中至少兩位發(fā)生變化；對(duì)于任何輸入x（6位），S(x)與S(x⊕001100)至少有兩位不同；對(duì)于任何輸入x（6位），S(x)與S(x⊕00ef00)不相等，e,f取0或1；對(duì)于任意一個(gè)輸入位保持不變而其他五位變化時(shí)，輸出中0和1的數(shù)目幾乎相等。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)41S-Box對(duì)每個(gè)盒，6比特輸入中的第1和第6比特組成的二進(jìn)制數(shù)確定的行，中間4位二進(jìn)制數(shù)用來(lái)確定的列。相應(yīng)行、列位置的十進(jìn)制數(shù)的4位二進(jìn)制數(shù)表示作為輸出。例如的輸入為101001，則行數(shù)和列數(shù)的二進(jìn)制表示分別是11和0100，即第3行和第4列，的第3行和第4列的十進(jìn)制數(shù)為3，用4位二進(jìn)制數(shù)表示為0011，所以的輸出為0011。

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)42P-盒置換32比特輸入，32比特輸出123456789303132167202129122817115......11425P-盒的輸出：2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)43子密鑰生成拆分：56bits的密鑰分成兩部分，Ci,Di，各28bits循環(huán)左移：根據(jù)迭代的輪數(shù)，分別左移一位或兩位123456789101112131415161122222212222221壓縮置換（置換選擇）：從56bits中選擇48bits14171124153281562110231912426816727201324152313747553040514533484449395634534642503629322024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)44子密鑰的產(chǎn)生

k1

（56位）(48位)

ki

（56位）

（48位）64位密鑰置換選擇1

C0（28位）

D0（28位）

循環(huán)左移循環(huán)左移

C1（28位）

D1（28位）

循環(huán)左移循環(huán)左移

Ci（28位）

Di（28位）置換選擇2置換選擇2密鑰表的計(jì)算邏輯循環(huán)左移：11912110232112421225213262142721528

21612024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)45DES解密過程DES解密過程與加密過程完全相似，只不過將16次迭代的子密鑰順序倒過來(lái)，首先使用k16，再使用k15，…

，最后使用k1。即m=DES-1(c)=IP-1?T1?T2?.....T15?T16

?IP(c)可以證明，DES(DES-1(m))=m2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)46總結(jié)－DES示意圖2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)472.3.2關(guān)于DES的討論S盒是唯一非線性組件：有人認(rèn)為其中可能含有某種“陷門”。DES的密鑰量太?。好荑€量為2561977年：Diffie.Hellman提出制造一個(gè)每秒測(cè)試106的VLSI芯片，則一天就可以搜索完整個(gè)密鑰空間，當(dāng)時(shí)造價(jià)2千萬(wàn)美圓。CRYPTO’93：R.Session，M.Wiener提出并行密鑰搜索芯片，每秒測(cè)試5x107個(gè)密鑰，5760片這種芯片，造價(jià)10萬(wàn)美圓，平均一天即可找到密鑰。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)48Internet的超級(jí)計(jì)算能力：1997年1月28日，美國(guó)RSA數(shù)據(jù)安全公司在Internet上開展了一項(xiàng)“秘密密鑰挑戰(zhàn)”的競(jìng)賽，懸賞一萬(wàn)美圓，破解一段DES密文。計(jì)劃公布后，得到了許多網(wǎng)絡(luò)用戶的強(qiáng)力相應(yīng)科羅拉州的程序員R.Verser設(shè)計(jì)了一個(gè)可以通過互聯(lián)網(wǎng)分段運(yùn)行的密鑰搜索程序，組織了一個(gè)稱為DESCHALL的搜索行動(dòng)，成千上萬(wàn)的的志愿者加入到計(jì)劃中。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)49第96天，即競(jìng)賽公布后的第140天，1997年6月17日晚上10點(diǎn)39分美國(guó)鹽湖城Inetz公司職員M.Sanders成功地找到了密鑰解密出明文：TheunknownMessageis：“Strongecryptographymakesthewordasaferplace”(高強(qiáng)度密碼技術(shù)使世界更安全)Internet僅僅利用閑散資源，毫無(wú)代價(jià)就破譯了DES密碼，這是對(duì)密碼方法的挑戰(zhàn)，是Internet超級(jí)計(jì)算能力的顯示.2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)50差分分析法：除去窮舉搜索密鑰外，還有其他形式的攻擊方法，最著名的有Biham，Shamir的差分分析法。這是一個(gè)選擇明文攻擊方法。雖然對(duì)16輪DES沒有攻破，但是，如果迭代的輪數(shù)降低，則它可成功地被攻破。例如，8輪DES在一個(gè)個(gè)人計(jì)算機(jī)上只需要2分鐘即可被攻破。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)512.4公鑰密碼體制

一個(gè)安全的對(duì)稱密鑰密碼系統(tǒng)，可以達(dá)到下列功能：保護(hù)信息機(jī)密

認(rèn)證發(fā)送方之身份

確保信息完整性對(duì)稱密鑰密碼系統(tǒng)具有下列缺點(diǎn)：

收發(fā)雙方如何獲得其加密密鑰及解密密鑰？

無(wú)法達(dá)到不可否認(rèn)服務(wù)

2.4.1傳統(tǒng)密碼體制的缺陷與公鑰密碼體制的產(chǎn)生

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)52現(xiàn)代密碼學(xué)修正了密鑰的對(duì)稱性，1976年，Diffie，Hellmann提出了公開密鑰密碼體制（簡(jiǎn)稱公鑰體制），它的加密、解密密鑰是不同的，也是不能（在有效的時(shí)間內(nèi)）相互推導(dǎo)。所以，它可稱為雙鑰密碼體制。是密碼學(xué)革命性的發(fā)展，一方面，為數(shù)據(jù)的保密性、完整性、真實(shí)性提供了有效方便的技術(shù)。另一方面，科學(xué)地解決了密碼技術(shù)的瓶頸──密鑰的分配問題。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)53第一個(gè)公鑰體制是1977年由Rivest，Shamir，Adleman提出的，稱為RSA公鑰體制，其安全性是基于整數(shù)的因子分解的困難性。RSA公鑰體制已得到了廣泛的應(yīng)用。其后，諸如基于背包問題的Merkle-Hellman背包公鑰體制，基于有限域上離散對(duì)數(shù)問題的EIGamal公鑰體制基于橢圓曲線的密碼體制等等公鑰體制不斷出現(xiàn)，使密碼學(xué)得到了蓬勃的發(fā)展，2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)542.4.2公鑰密碼體制介紹

公鑰密碼體制加解密過程主要有以下幾步：

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)55公鑰加密傳統(tǒng)加密過程加密和解密使用相同密鑰明文明文密文2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)56公鑰加密公鑰密碼算法加密和解密使用不同密鑰明文明文密文2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)57

用公鑰密碼實(shí)現(xiàn)保密2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)58基于公開密鑰的加密過程2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)59

用公鑰密碼實(shí)現(xiàn)認(rèn)證2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)60基于公開密鑰的認(rèn)證過程2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)61

用公鑰密碼實(shí)現(xiàn)保密與認(rèn)證Ek’a(m)數(shù)字簽名Ek’a(m)Ek’a(m)認(rèn)證Dkb(m)2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)62數(shù)字簽名的順序

信息進(jìn)行簽名和加密，順序？A->B:Epkb(Eska(m))-先簽名再加密C:Epkc(Eska(m))-偽造中間人攻擊A->B:Eska(Epkb(m))-先加密再簽名C:Epkc(Epkb(m))-篡改中間人攻擊2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)63

公鑰密鑰的應(yīng)用范圍加密/解密數(shù)字簽名(身份鑒別)密鑰交換不同算法加/解密數(shù)字簽名密鑰交換RSA是是是Dieffie-Hellman否否是DSS否是否2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)64（1）簡(jiǎn)化了密鑰分配及管理公鑰體制用于數(shù)據(jù)加密時(shí)：用戶將自己的公開（加密）密鑰登記在一個(gè)公開密鑰庫(kù)或?qū)崟r(shí)公開，秘密密鑰則被嚴(yán)格保密。信源為了向信宿發(fā)送信息，去公開密鑰庫(kù)查找對(duì)方的公開密鑰，或臨時(shí)向?qū)Ψ剿魅」€，將要發(fā)送的信息用這個(gè)公鑰加密后在公開信道上發(fā)送給對(duì)方，對(duì)方收到信息（密文）后，則用自己的秘密（解密）密鑰解密密文，從而，讀取信息?？梢?，這里省去了從秘密信道傳遞密鑰的過程。這是公鑰體制的一大優(yōu)點(diǎn)。

公鑰密鑰的應(yīng)用范圍2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)65（2）保護(hù)信息機(jī)密

任何人均可將明文加密成密文，此后只有擁有解密密鑰的人才能解密。

公鑰密鑰的應(yīng)用范圍2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)66（3）實(shí)現(xiàn)不可否認(rèn)功能

公鑰體制用于數(shù)字簽名時(shí)：信源為了他人能夠驗(yàn)證自己發(fā)送的消息確實(shí)來(lái)自本人，他將自己的秘密（解密）密鑰公布，而將公開（加密）密鑰嚴(yán)格保密。與別人通信時(shí)，則用自己的加密密鑰對(duì)消息加密──稱為簽名，將原消息與簽名后的消息一起發(fā)送.對(duì)方收到消息后，為了確定信源的真實(shí)性，用對(duì)方的解密密鑰解密簽名消息──稱為（簽名）驗(yàn)證，如果解密后的消息與原消息一致，則說明信源是真實(shí)的，可以接受，否則，拒絕接受。

公鑰密鑰的應(yīng)用范圍2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)672.4.3基本數(shù)學(xué)概念群模逆元費(fèi)爾馬小定理

Euler函數(shù)

生成元

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)68模p運(yùn)算給定一個(gè)正整數(shù)p，任意一個(gè)整數(shù)n，一定存在等式n=kp+r其中k、r是整數(shù)，且0≤r<p，稱k為n除以p的商，r為n除以p的余數(shù)。對(duì)于正整數(shù)p和整數(shù)a,b，定義如下運(yùn)算：取模運(yùn)算：amodp表示a除以p的余數(shù)15除以7的運(yùn)算：15=2*7+1N=15,k=2,p=7,r=1a=15,k=2,p=7,b=1,15mod7=12024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)69模p加法：(a+b)modp，其結(jié)果是a+b算術(shù)和除以p的余數(shù)，也就是說，(a+b)=kp+r，則(a+b)modp=r。模p減法：(a-b)modp，其結(jié)果是a-b算術(shù)差除以p的余數(shù)。模p乘法：(a×b)modp，其結(jié)果是a×b算術(shù)乘法除以p的余數(shù)?？梢园l(fā)現(xiàn),模p運(yùn)算和普通的四則運(yùn)算有很多類似的規(guī)律，如：規(guī)律公式結(jié)合率((a+b)modp+c)modp=(a+(b+c)modp)modp((a*b)modp*c)modp=(a*(b*c)modp)modp交換率(a+b)modp=(b+a)modp(a×b)modp=(b×a)modp分配率((a+b)modp×c)modp=((a×c)modp+(b×c)modp)modp2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)70基本數(shù)學(xué)概念群：對(duì)于非空集合G，其上的一個(gè)二元運(yùn)算（.）滿足：封閉性、結(jié)合律、單位元和可逆性實(shí)列：模n加法運(yùn)算下的整數(shù)模n群群Z15=={0,1,2,3,…14},其中的模運(yùn)算實(shí)例為：5+6mod15=115+10mod15=012+6mod15=32024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)71基本數(shù)學(xué)概念模逆元：X屬于Z存在逆元X-1，當(dāng)且僅當(dāng)ｘ與ｎ存在最大公因子１，即ｇｃｄ（ｘ，ｎ）＝１，即ｘ與ｎ互為素?cái)?shù)存在ｘ－１＊ｘｍｏｄｎ＝１素?cái)?shù)（質(zhì)數(shù)）：只有１和它本身兩個(gè)約數(shù)的數(shù)，如３、５、１３2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)72基本數(shù)學(xué)概念菲爾馬小定理：當(dāng)ｎ是素?cái)?shù)，有ａｎ－１＝＝１ｍｏｄｎ例如，２７－１＝＝１ｍｏｄ７Ｅｕｌｅｒ函數(shù)：當(dāng)ｎ〉１，在１，２，．．Ｎ，中互為素?cái)?shù)的元素的個(gè)數(shù)記為Ｅｕｌｅｒ函數(shù)ｆ（ｎ）例如，ｆ（５）＝４，ｆ（６）＝２，ｆ（９）＝６2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)732.4.4RSA算法1976年：Diffie，Hellman在“NewDirectioninCryptography”(密碼學(xué)新方向)一文中首次提出公開密鑰密碼體制的思想。1977年：Rivest,Shamir,Adleman第一次實(shí)現(xiàn)了公開密鑰密碼體制，現(xiàn)稱為RSA公鑰體制。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)74基本算法：①生成兩個(gè)大素?cái)?shù)p和q（保密）；

②計(jì)算這兩個(gè)素?cái)?shù)的乘積n=pq（公開）；

③計(jì)算小于n并且與n互素的整數(shù)的個(gè)數(shù)，即歐拉函數(shù)

(n)=(p–1)(q–1)（保密）；

④選取一個(gè)隨機(jī)整數(shù)e滿足1<e<(n)，并且e和

(n)互素，即gcd(e,(n))=1（公開）；

⑤計(jì)算d，滿足de=1mod(n)（保密）；公鑰｛ｅ，ｎ｝秘鑰｛ｄ，ｎ｝2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)75E(m)Kb1AKa1BD(E(m))Kb2mmRSA的加解密過程公開信道2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)76RSA算法概要：Bob選擇保密的素?cái)?shù)p和q，并計(jì)算n=pq；Bob通過gcd(e,(p-1)(q-1))=1來(lái)選擇e；Bob通過de≡1(mod(p-1)(q-1))來(lái)計(jì)算d；Bob將n和e設(shè)為公開的，p、q、d設(shè)為秘密的；Alice將m加密為c≡me(modn)，并將c發(fā)送給Bob；Bob通過計(jì)算m≡cd(modn)解密。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)77RSA:例1選擇兩個(gè)素?cái)?shù):p=17&q=11計(jì)算

n=pq=17×11=187計(jì)算

?(n)=(p–1)(q-1)=16×10=160選擇e:gcd(e,160)=1;其中e=72024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)78RSA:例1計(jì)算d:de=1mod160且d<160，則

d=23（因?yàn)?3×7=161）公布公鑰KU={ｅ＝7,187}保存私鑰KR={ｄ＝23,1８7}2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)79如果待加密的消息M=88(注意：88<187)加密：C=887mod187=11解密:M=1123mod187=88RSA：例1公布公鑰KU={7,187}保存私鑰KR={23,1８7}2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)80RSA：例2Bob選擇p=885320693，q=238855417，則可以計(jì)算

n=p*q=211463707796206571，設(shè)加密系數(shù)為e=9007，將n和e發(fā)送給Alice。假設(shè)Alice傳遞的信息是cat。令a=01c=03t=20，則cat=030120=30120。

Alice計(jì)算：c≡me≡301209007≡113535859035722866(modn)

她將c傳給Bob。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)81RSA：例2Bob已知p和q的值，他用擴(kuò)展歐幾里德算法計(jì)算d：

de≡1(mod(p-1)(q-1))，得到

d=116402471153538991

然后Bob計(jì)算：

cd≡113535859035722866116402471153538991≡30120(modn)

由此他可以得到最初的信息。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)82算法分析：該體制的數(shù)學(xué)依據(jù)是Euler定理及大數(shù)分解的困難性，體制中使用的是Zn中的計(jì)算。設(shè)是兩個(gè)不同奇素?cái)?shù)p,q的乘積，對(duì)于這樣的正整數(shù)，其Euler函數(shù)值是容易計(jì)算的，它是

(n)=(p-1)(q-1)。對(duì)于給定的明文x<n，選定一個(gè)正整數(shù)b，稱為加密密鑰。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)83作Zn中的指數(shù)運(yùn)算，將明文以指數(shù)形式xb表示出來(lái)，即以指數(shù)形式將明文隱藏起來(lái)。即使知道一個(gè)明、密文對(duì)(x,y)，y=xbmodn,要得到密鑰b，必須求解離散對(duì)數(shù)問題：b=logxy，在Zn中這也是一個(gè)困難問題這種加密思想是簡(jiǎn)單、明確的。

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)84RSA安全性分析

加密密鑰b是公開的，從而，要求從b不能有效地推導(dǎo)出a，解已知b，求解ab≡1mod(n)是計(jì)算上不可能的。

(n)是n的Euler函數(shù)，如果已知(n)，則可以應(yīng)用展轉(zhuǎn)相除法求得b的逆元a，從而(n)的保密是安全的關(guān)鍵，而(n)的有效計(jì)算則依賴于n的素因子分解，從而，RSA的安全性與n的素因子分解等價(jià)。體制的安全性機(jī)理是大數(shù)分解的困難性。

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)85大數(shù)分解是一個(gè)NP問題，目前已知的最好的算法需要進(jìn)行ex次算術(shù)運(yùn)算。假設(shè)我們用一臺(tái)每秒運(yùn)算（即：一億）次的計(jì)算機(jī)來(lái)分解一個(gè)200位十進(jìn)制的數(shù)

要分解一個(gè)200位十進(jìn)制的數(shù)，需要3.8×107年，類似地，可算出要分解一個(gè)300位的十進(jìn)制整數(shù)，則需要年4.86×1013?？梢?，增加的位數(shù)，將大大地提高體制的安全性。由以上分析可見，從直接分解大數(shù)來(lái)破譯RSA是計(jì)算上不可能的，那么是否存在一種破譯方法不依賴于的分解呢？雖然現(xiàn)在還沒有發(fā)現(xiàn)，但是也沒有嚴(yán)格的論證。

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)86直接分解一個(gè)大素?cái)?shù)的強(qiáng)力攻擊的一個(gè)實(shí)例是：1994年4月分解的RSA密鑰RSA-129，即分解了一個(gè)129位十進(jìn)制，425比特的大素?cái)?shù)。分解時(shí)啟用了1600臺(tái)計(jì)算機(jī)，耗時(shí)8個(gè)月，處理了4600MIPS年的數(shù)據(jù)。1MIPS年是1MIPS的機(jī)器一年所能處理數(shù)據(jù)量。Pentium100大約是125MIPS，它分解RSA-129需要37年。100臺(tái)Pentium100需要4個(gè)月。Ｍｉｐｓ：每秒處理的百萬(wàn)級(jí)的機(jī)器語(yǔ)言指令數(shù)2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)87硬件實(shí)現(xiàn)時(shí)，RSA比DES要慢大約1000倍，軟件實(shí)現(xiàn)時(shí)，RSA比DES要慢大約100倍用RSA直接加密信息有諸多不便，所以，很多實(shí)際系統(tǒng)中，只用RSA來(lái)交換DES的密鑰，而用DES來(lái)加密主體信息。

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)882.5散列函數(shù)2.5.1散列函數(shù)的概念

散列函數(shù)是一種把可變輸入長(zhǎng)度串轉(zhuǎn)變成固定長(zhǎng)度輸出串（叫做散列值）的一種函數(shù)。散列值是信息的“指紋”，散列值可用于檢查信息的完整性。１）輸入長(zhǎng)度任意２）輸出固定，１２８ｂｉｔ３）對(duì)每個(gè)給定的輸入，散列函數(shù)計(jì)算，指紋2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)892.5散列函數(shù)主要用作數(shù)字簽名散列函數(shù)又可稱為壓縮函數(shù)、雜湊函數(shù)、消息摘要、指紋、密碼校驗(yàn)、信息完整性檢驗(yàn)(DIC)、操作檢驗(yàn)碼(MDC)。散列函數(shù)有4個(gè)主要特點(diǎn)：①它能處理任意大小的信息②它是不可預(yù)見的③它是完全不可逆的，即散列函數(shù)是單向的④它是抗碰撞的2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)90單向散列函數(shù)的工作原理

常用的散列函數(shù)算法有：（1）MD2算法（2）MD4和MD5算法（3）SHA算法2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)91單向散列函數(shù)SHA（securehashstandard算法）根據(jù)上限為2**64比特的消息算出160比特的散列值的單項(xiàng)散列函數(shù)1）消息轉(zhuǎn)換成512比特的整數(shù)倍2）根據(jù)輸入分組的512比特計(jì)算出80個(gè)32比特的值3）分組處理對(duì)輸入分組依次進(jìn)行80個(gè)步驟處理，計(jì)算5個(gè)32比特值。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)922024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)932.5.2MD5算法（２００４年山大王小云破解）１）首先填充消息成512比特的整數(shù)倍，但最后64比特是由文件長(zhǎng)度填充的；２）其次，將個(gè)512比特分割成16個(gè)32比特子塊；取4個(gè)初始向量，從其及第一個(gè)子塊出發(fā)，作4輪（MD4只有3輪）16次迭代，得128比特輸出；３）以此作為初始向量，對(duì)下一個(gè)512比特執(zhí)行同樣的操作；

４）依次下去，直到所有的512比特都處理完畢，輸出128比特，此即MD5的輸出。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)942.6數(shù)字簽名數(shù)字簽名最早被建議用來(lái)對(duì)禁止核試驗(yàn)條律的驗(yàn)證禁止核試驗(yàn)條律的締約國(guó)為了檢測(cè)對(duì)方的核試驗(yàn)，需要把地震測(cè)試儀放在對(duì)方的地下，而把測(cè)試的數(shù)據(jù)送回，自然這里有一個(gè)矛盾：東道主需要檢查發(fā)送的數(shù)據(jù)是否僅為所需測(cè)試的數(shù)據(jù)；檢測(cè)方需要送回的數(shù)據(jù)是真實(shí)的檢測(cè)數(shù)據(jù)，東道主沒有篡改。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)95基本要求：簽名不能偽造：簽名是簽名者對(duì)文件內(nèi)容合法性的認(rèn)同、證明、和標(biāo)記，其他人的簽名無(wú)效；簽名不可抵賴：這是對(duì)簽名者的約束，簽名者的認(rèn)同、證明、標(biāo)記是不可否認(rèn)的；簽名不可改變：文件簽名后是不可改變的，這保證了簽名的真實(shí)性、可靠性；簽名不可重復(fù)使用：簽名需要時(shí)間標(biāo)記，這樣可以保證簽名不可重復(fù)使用。簽名容易驗(yàn)證：對(duì)于簽名的文件，一旦發(fā)生糾紛，任何第三方都可以準(zhǔn)確、有效地進(jìn)行驗(yàn)證。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)96數(shù)字簽名的基本原理：應(yīng)用一對(duì)不可互相推導(dǎo)的密鑰，一個(gè)用于簽名（加密），一個(gè)用于驗(yàn)證（解密），顛倒使用加解密過程。公鑰簽名原理：這種簽名就是加密過程的簡(jiǎn)單顛倒使用，簽名者用加密密鑰（保密）簽名（加密）文件，驗(yàn)證者用（公開的）解密密鑰解密文件，確定文件的真?zhèn)巍?024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)97散列函數(shù)：散列函數(shù)是數(shù)字簽名的一個(gè)重要輔助工具，應(yīng)用散列函數(shù)可以生成一個(gè)文件的，具有固定長(zhǎng)度的文件摘要，從而使數(shù)字簽名可以迅速有效地簽名一個(gè)任意長(zhǎng)度的文件。一般地，對(duì)文件的任意小改動(dòng)，都會(huì)改變文件的散列值，從而，秘密的散列函數(shù)可以用來(lái)檢測(cè)病毒等對(duì)文件的破壞。對(duì)簽名的攻擊：對(duì)數(shù)字簽名有各種各樣的欺騙存在，重復(fù)使用是一個(gè)典型欺騙，如電子支票，重復(fù)的使用具有可怕后果，阻止這種欺騙的有效方法是簽名中包含時(shí)間日期標(biāo)志。2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)98常用算法介紹1、Elgamal算法：ElGamal簽名方案——基于離散對(duì)數(shù)問題離散對(duì)數(shù)問題：設(shè)p是一個(gè)素?cái)?shù)，bZ*p，尋找整數(shù)d，0<d<p，滿足：ad≡bmodp。這樣的問題稱為離散對(duì)數(shù)問題。選取p至少150位十進(jìn)制數(shù)，p-1至少有一個(gè)“大”素因子，則離散對(duì)數(shù)問題稱為困難問題，困難問題不存在多項(xiàng)式時(shí)間算法2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)99ElGamal簽名方案于1985年提出，改進(jìn)后，被美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究所（NIST）采納為數(shù)字簽名標(biāo)準(zhǔn)。ElGamal簽名方案是一個(gè)非確定性的方案，也就是說，驗(yàn)證算法可以接受的合法簽名不止一個(gè)。

2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)100ElGamal簽名方案的定義：

設(shè)p是一個(gè)素?cái)?shù)，Zp中的離散對(duì)數(shù)是困難問題，

aZ*p是一個(gè)生成元，b≡admodp，則定義：

簽名算法Sig：Sigk(x,t)=(,)，≡atmodp，

≡(x-a

)t-1modp-1，t是一保密的隨機(jī)數(shù)。

驗(yàn)證算法：對(duì)給定的消息及簽名(x,(,))，x,Z*p,

Zp-1，驗(yàn)證算法為2024/3/19計(jì)算機(jī)系統(tǒng)安全原理與技術(shù)1012、DSA算法：DSA是Schnorr和ElGamal簽名算法的變種，被美國(guó)NIST作為DSS。

數(shù)字簽名標(biāo)準(zhǔn)DSS：

設(shè)p是一個(gè)512比特的素?cái)?shù)，Zp中的離散對(duì)數(shù)是困難

問題，q是一個(gè)60比特的素?cái)?shù)，q|p-1，aZ*p是p模

q的單位根。則定義：

簽名算法：Sigk(x,t)=(,)，≡(atmodp)modq，

≡(x+a

)t-1modq；

驗(yàn)證