應(yīng)用密碼學(xué)1教材

信息安全與應(yīng)用密碼學(xué)第一講密碼學(xué)基礎(chǔ)第二講數(shù)學(xué)背景第三講密碼協(xié)議第四講報文鑒別與散列函數(shù)第五講

數(shù)據(jù)加密及密鑰管理第六講對稱加密算法第七講公開密鑰算法趙學(xué)龍zhaoxuelong@第一講密碼學(xué)基礎(chǔ)密碼學(xué)的起源可能要追溯到人類剛剛出現(xiàn)，并且嘗試去學(xué)習(xí)如何通信的時候。公元六年前，古希臘人，scytale棍子（棍子的寬度為密鑰）；羅馬軍隊，凱撒密碼（三個字母表輪換）；由于戰(zhàn)爭和各個國家之間的利益，密碼學(xué)重要的進(jìn)展很少在公開文獻(xiàn)中出現(xiàn)。1918年，20世紀(jì)最有影響的密碼分析文章之一：–WilliamF.Friedman,TheIndexofCoincidenceandItsApplicationinCryptography.（重合指數(shù)及其在密碼學(xué)中的應(yīng)用）；1920加州奧克蘭的EdwardH.Herbern申請了第一個轉(zhuǎn)輪機(jī)專利，這種裝置，在差不多50年內(nèi)被制定為美軍的主要密碼設(shè)備；一戰(zhàn)以后，完全處于秘密工作狀態(tài)的美國陸軍和海軍的機(jī)要部門開始在密碼學(xué)方面取得根本性的進(jìn)展。但由于戰(zhàn)爭原因，公開文獻(xiàn)幾乎殆盡。從1949－1967年，密碼學(xué)文獻(xiàn)近乎空白。密碼學(xué)歷史性事件1949年，Shannon的論文：–C.E.Shannon.Amathematicaltheoryofcommunication.BellSystemTechnicalJournal,1948,27(4):379~423,623~656.–C.E.Shannon.Communicationtheoryofsecrecysysytem.BellSystemTechnicalJournal,1949,28(4):656~715.1967年，DavidKahn,“TheCodebreakers”（破譯者）–沒有任何新的技術(shù)思想，但卻對密碼學(xué)的歷史做了相當(dāng)完整的記述；–它使成千上萬原本部知道密碼學(xué)的人了解了密碼學(xué)。新的密碼學(xué)文章慢慢開始源源不斷被編寫出來了。1976年，Diffie,Hellman的論文：–W.Diffe,M.E.Hellman.Newdirectionsincryptography.IEEETrans.Inform.Theroy,November1976,22(6):644~654.–提出公鑰密碼的思想；1977年，美國聯(lián)邦政府頒布數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）；1994年，美國聯(lián)邦政府頒布密鑰托管加密標(biāo)準(zhǔn)（EES）；1994年，美國聯(lián)邦政府頒布數(shù)字簽名標(biāo)準(zhǔn)（DSS）；2001年，美國聯(lián)邦政府頒布高級加密標(biāo)準(zhǔn)（AES）；信息安全的含義通信保密（COMSEC）：60-70年代

信息保密信息安全（INFOSEC）：80-90年代

機(jī)密性、完整性、可用性、不可否認(rèn)性等信息保障（IA）：90年代-?信息安全的基本方面–保密性Confidentiality即保證信息為授權(quán)者享用而不泄漏給未經(jīng)授權(quán)者。–完整性Integrity?數(shù)據(jù)完整性，未被未授權(quán)篡改或者損壞?系統(tǒng)完整性，系統(tǒng)未被非授權(quán)操縱，按既定的功能運行–可用性Availability即保證信息和信息系統(tǒng)隨時為授權(quán)者提供服務(wù)，而不要出現(xiàn)非授權(quán)者濫用卻對授權(quán)者拒絕服務(wù)的情況。–信息的不可否認(rèn)性Non-repudiation：

要求無論發(fā)送方還是接收方都不能抵賴所進(jìn)行的傳輸。–鑒別Authentication

鑒別就是確認(rèn)實體是它所聲明的。適用于用戶、進(jìn)程、系統(tǒng)、信息等。–

審計Accountability

確保實體的活動可被跟蹤。–可靠性Reliability

特定行為和結(jié)果的一致性。2.消息和加密

消息(message)被稱為明文（plaintext）.

加密（encryption）用某種方法偽裝消息以隱藏它的內(nèi)容過程稱為加密。被加密的消息稱為密文（ciphertext），而把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密(decryption)明文加密密文解密原始明文1基礎(chǔ)知識1.

1專業(yè)術(shù)語1.計算機(jī)安全：把設(shè)計用來保護(hù)數(shù)據(jù)、阻擋黑客的工具集合稱為計算機(jī)安全.

密碼編碼學(xué)：使信息保密的技術(shù)和科學(xué)叫密碼編碼學(xué)（cryptography）。從事此行的叫密碼編碼者，密碼分析者是從事密碼分析的專業(yè)人員；密碼分析學(xué)(cryptanalysis)就是破譯密文的科學(xué)與技術(shù)，即揭穿偽裝。

明文用M表示，它可能是位序列、文本文件、位圖、數(shù)字化的語音序列或數(shù)字化的視頻圖像等。對于計算機(jī)，M指簡單的二進(jìn)制數(shù)據(jù)

密文用C表示，它亦是二進(jìn)制數(shù)據(jù)。

加密函數(shù)E作用于M得到密文C可用數(shù)學(xué)公式表示：

E（M）=C

解密函數(shù)D作用于C產(chǎn)生M：

D（C）=M

先加密后解密，原始明文將恢復(fù)，故有

D（E（M））=M

3.

鑒別、完整性和抗抵賴性

鑒別（authentication）消息的接受者應(yīng)該能夠確認(rèn)消息的來源；入侵者不可能偽裝成他人。

完整性（integrity）：消息的接受者應(yīng)該能夠驗證在傳送過程中消息沒有被修改；入侵者不可能用假消息代替合法的消息。

抗抵賴性（nonrepudiation）：發(fā)送者事后不可能虛假地否認(rèn)他發(fā)送的消息。4．

算法和密鑰

密碼算法（algorithm）亦叫密碼（cipher）,是用于加密和解密的數(shù)學(xué)函數(shù)。通常情況下有兩個相關(guān)的函數(shù)：一個用作加密，一個用作解密。

如果算法的保密性是基于保持算法的秘密，這種算法稱為受限制的算法?，F(xiàn)代密碼學(xué)用密鑰解決問題，密鑰用K表示。K可以是很多值里的任意值。密鑰K的可能值的范圍叫做密鑰空間（keyspace）。

如加密和解密都用一個密鑰，加/解密函數(shù)變成：EK（M）=CDK（C）=MDK（EK（M））=M

密碼系統(tǒng)：由算法以及所有可能的明文、密文和密鑰組成的。

對稱算法（symmetricalgorithm）有時叫傳統(tǒng)密碼算法，就是加密密鑰能夠從解密密鑰中推算出來，反過來亦成立。在大多數(shù)對稱算法中，加/解密密鑰是相同的。這些算法亦叫秘密密鑰算法或單密鑰算法，它要求發(fā)送者和接受者在安全通信之前，商定一個密鑰。對稱算法的安全性依賴于密鑰。只要通信需要保密，密鑰就必須保密。對稱算法的加密和解密表示為：

EK（M）=CDK（C）=M對稱算法可以分為兩類：一次只對明文中的單個位（有時字節(jié)）運算的算法稱為序列算法（streamalgorithm）或者序列密碼（streamcipher）。另一類是是對明文的一組位進(jìn)行運算，這些位組稱為分組（block)，相應(yīng)算法稱為分組算法（blockalgorithm)。現(xiàn)代密碼典型長度是64位。5．

對稱算法基于密鑰的算法通常分為兩類：對稱算法和公開密鑰算法。

6.

公開密鑰算法

公開密鑰算法（public-keyalgorithm）亦稱為非對稱算法：用作加密的密鑰不同于用作解密的密鑰，而且解密密鑰不能根據(jù)加密密鑰計算出來（至少在合理假定的時間內(nèi)）。之所以叫公開密鑰算法是因為加密密鑰能夠公開。加密密鑰叫公開密鑰（publickey），解密密鑰叫私人密鑰（privatekey)。Ek(M)=CDk(C)=M

7．

密碼分析

密碼編碼學(xué)的目的是保持明文（或密鑰、明文和密鑰）的秘密以防止偷聽者（對手、攻擊者、入侵者）知道。

密碼分析學(xué)是在不知道密碼的情況下，恢復(fù)明文的科學(xué)。對密碼進(jìn)行分析的嘗試稱為攻擊。密碼分析（攻擊）的目的：

–C－>M，等價算法，K。–恢復(fù)盡可能多的明文。–導(dǎo)出一個算法，此算法可以對用同一密鑰加密的任何新的消息進(jìn)行解密。–推算出加密消息的密鑰來，以便可采用相同的密鑰解出其他被加密的消息。Kerckhoffs假設(shè)1883年，荷蘭人A.Kerckhoffs

提出。–秘密必須全寓于密鑰中。即，密碼體制的安全性僅依賴于對密鑰的保密，而不應(yīng)依賴于算法的保密。–假設(shè)密碼分析者已有密碼算法及其實現(xiàn)的全部詳細(xì)資料

密碼攻擊的方法

窮舉攻擊–理論上，窮舉攻擊可攻破所有密碼；–可以通過增大密鑰量或加大解密（加密）算法的復(fù)雜性來對抗窮舉攻擊；；統(tǒng)計分析攻擊–通過分析密文和明文的統(tǒng)計規(guī)律來破譯密碼；–許多古典密碼都可以通過分析密文字母和字母的頻率和其他統(tǒng)計參數(shù)而破譯；–對抗統(tǒng)計分析攻擊的方法是設(shè)法使明文的統(tǒng)計特性不帶入密文；–能夠抵抗統(tǒng)計分析攻擊已成為現(xiàn)代密碼的基本要求；數(shù)學(xué)分析攻擊–針對加密算法的數(shù)學(xué)基礎(chǔ)和某些密碼特性，通過數(shù)學(xué)求解的方法來破譯密碼；–數(shù)學(xué)分析攻擊是基于數(shù)學(xué)難題的各種密碼的主要威脅；–為了對抗這種數(shù)學(xué)分析攻擊，應(yīng)當(dāng)選用具有堅實數(shù)學(xué)基礎(chǔ)和足夠復(fù)雜的加解密算法；常用的密碼分析攻擊有四類：

（1）唯密文攻擊：密碼分析者有一些消息的密文，這些消息都用同一加密算法加密。密碼分析者的任務(wù)是恢復(fù)盡可能多的明文，或者最好是能推算出加密消息密鑰來，以便能采用相同密鑰解出其它被加密的信息。（2）已知明文攻擊：密碼分析者不僅可得到一些消息的密文，而且可以知道這些消息的明文。分析者的任務(wù)就是用加密信息推出用來加密的密鑰或?qū)С鲆粋€算法，此算法可以對用同一密鑰加密的任何信息進(jìn)行解密。

（3）選擇明文攻擊：

分析者不僅可得到一些消息的密文和相應(yīng)的明文，而且他們亦可選擇被加密的明文。（4）自適應(yīng)密文攻擊：這是選擇明文攻擊的特殊情況。密碼分析者不僅能選擇被加密的明文，而且亦能基于以前加密的結(jié)果修正這個選擇。

那些因為自己不能破譯某個算法就草草地聲稱有一個不可破譯的密碼的人要么是天才，要么是笨蛋。不幸的是后者居多。千萬要提防那些一味吹噓算法的優(yōu)點，但又拒絕公開的人，相信他們的算法就像相信騙人的包治白病的靈丹妙藥一樣。BruceSchnier《應(yīng)用密碼學(xué)》8．算法的安全性如果破譯算法的代價大于加密數(shù)據(jù)價值，那么你是安全的。如果破譯算法所需的時間比加密數(shù)據(jù)保密的時間長，那么你可能是安全的。1．2隱寫術(shù)隱寫術(shù)是將秘密消息隱藏在其他消息中，這樣真正存在的信息被隱藏了。如發(fā)表一篇無關(guān)緊要的文章等。最近人們在圖像中隱藏秘密的消息，用圖像的每個字節(jié)的最不重要的位代替消息位，圖像并沒有發(fā)生多大的改變。1.3代替和換位密碼 在計算機(jī)出現(xiàn)前，密碼學(xué)由基于字符的密碼算法構(gòu)成。不同的密碼算法是字符之間互相之間換位（即置換）或者互相替代，好的密碼算法結(jié)合了這兩種方法，并且每次都進(jìn)行多次運算。 現(xiàn)在密碼算法的主要變化是對比特而不是對字母進(jìn)行變換，實際上這只是字母表長度上的改變，從26個元素變?yōu)?個元素。大多數(shù)好的密碼算法仍然是置換和替代的組合。①置換密碼

置換是一種最基本的數(shù)學(xué)變換，每個置換都可以用一個整數(shù)序列來表示，例如：P=（2，1，4，3）表示這樣一個置換：將位置1和位置2對調(diào)，同時將位置3和位置4對調(diào)。每個置換都有一個與之對應(yīng)的逆置換。序列經(jīng)過置換和其逆置換之后，將保持不變。有時置換與其逆置換可能在形式上是相同的，例如，上述P的逆置換也是Q=（2，1，4，3）。

置換密碼的核心是一個僅有發(fā)信方和收信方知道的秘密置換（加密）和其逆置換（解密）。加密過程是用加密置換去對明文消息進(jìn)行置換。例如，明文取M=“置換密碼”，則用P去加密后就得到密文C=“換置碼密”。解密過程是用解密逆置換去對密文消息進(jìn)行置換。例如，密文取C=“換置碼密”，則用Q去解密后就得到明文取M=“置換密碼”。 置換密碼的最大特點是明文和密文中所含的元素是相同的，僅僅是位置不同而已。置換密碼雖然簡單，而且還不很安全，但是許多現(xiàn)代密碼體制中都或多或少地利用了置換方式。

下面的簡單縱行換位密碼就應(yīng)用了置換密碼。明文以固定的寬度水平地寫在一張圖表紙上，密文按垂直方向讀出，解密就是將密文按相同的寬度垂直地寫在圖表紙上，然后水平地讀出明文。

明文：COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVE COMPUTERGR APHICSMAYB ESLOWBUTAT LEASTITSEX PENSIVE

密文：CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX②替代密碼

替代密碼就是明文中每一個字符被替換成密文中的另外一個字符，接收者對密文進(jìn)行逆替換以恢復(fù)明文。（1）簡單替代密碼（單字母替代密碼）：即明文的一個字符用相應(yīng)的一個密文字符替代。

著名的凱撒密碼就是一種最簡單的替代密碼，它的每一個明文字符都由其右邊第3個（模26）字符替代，如：A由D替代，B由E替代，W由Z替代，X由A替代，Y由B替代，Z由C替代等。凱撒密碼實際上非常簡單，因為其密文字符僅僅是明文字符的環(huán)移，并且不是任意置換。

另一種簡單替代密碼是ROT13，它是Unix系統(tǒng)上的簡單加密程序。在這種密碼中，每一個字母是環(huán)移13所對應(yīng)的字母，如：A被N替代，B被O替代等等。用ROT13加密文件兩遍便恢復(fù)出原始明文：P=ROT13（ROT13（P））。

簡單替代密碼沒有掩蓋明文中不同字母的出現(xiàn)頻率，因而通過統(tǒng)計分析很容易破譯它。凱撒（Caesar）密碼

?課堂練習(xí)：字符串“Iloveyou”用Caesar密碼加密得到的密文是??明文字符串：Iloveyou?明文對應(yīng)數(shù)字形式：8,11,14,21,4,24,14,20?密文對應(yīng)數(shù)字形式：11,14,17,24,7,1,17,23?密文字符串：loryhbrx（2）多名碼替代密碼：它與簡單替代密碼系統(tǒng)相似，惟一的不同是單個字符明文可以映射成密文的幾個字符之一，例如A可能對應(yīng)于5、13、25或56，“B”可能對應(yīng)于7、19、31或42。

多名碼替代密碼在1401年最早由DuchyMantua公司使用，要求明文中出現(xiàn)的每一個字母循環(huán)或隨機(jī)使用它所對應(yīng)的密文字符。這樣，如果分配給每個字母的密文符號數(shù)目與該字母的統(tǒng)計頻率成正比，那么單字母的頻率信息就會完全被淹沒。這使得多名碼替代密碼比簡單替代密碼更難破譯，但它仍不能掩蓋明文語言的所有統(tǒng)計特性，多字母的組合頻率仍能保存在密文中，例如tion，ing等等。如果用已知明文攻擊，破譯這種密碼非常容易，惟密文攻擊要難一些，但在計算機(jī)上實現(xiàn)破譯也只需幾秒鐘。（3）多字母替代密碼：字符塊被成組加密，例如“ABA”可能對應(yīng)于“RTQ”，ABB可能對應(yīng)于“SLL”等。這種方法是為了減少在密文中保留明文中結(jié)構(gòu)的程度。Playfair密碼和Hill密碼就屬于這一類。多字母代替密碼-Playfair密碼Playfair密碼是英國科學(xué)家ChaelesWheatstone于1854年發(fā)明的，但是用了他的朋友BarronPlayfair的名字。

Playfair密碼是最為著名的多字母加密密碼，它將明文中的雙字母組合作為一個單元，并將這些單元轉(zhuǎn)換為密文雙字母的組合。Playfair算法基于一個5×5的字母矩陣，該矩陣通過一個關(guān)鍵詞構(gòu)造。 例如，關(guān)鍵詞為playfair，相應(yīng)矩陣如圖所示，其矩陣的構(gòu)造如下：首先，從左到右、從上到下填入該關(guān)鍵詞的字母，并去除重復(fù)的字母（兩個a只取一個）；其次，按照字母表順序?qū)⑵溆嘧帜柑钊刖仃嚨氖Ｓ嗫臻g。字母I和J被算作一個字母，可以根據(jù)使用者的意愿在形成密文時確定用I或J。PLAYFI/JRBCDEGHKMNOQSTUVWXZPlayfair密碼的構(gòu)造矩陣Playfair算法根據(jù)下列規(guī)則一次對明文的兩個字母進(jìn)行加密，這兩個字母構(gòu)成一對：（1）一對明文字母如果是重復(fù)的，則在這對明文字母種間插入一個填充字符，如x。因此，單詞session將被分割成：sesx

sion。（2）如果分割后的明文字母對在矩陣的同一行中都出現(xiàn)，則分別用矩陣中其右側(cè)的字母代替，行的最后一個字母由行的第一個字母代替。例如，on被加密成QO，而st被加密成TN。（3）如果分割后的明文字母對在矩陣的同一列中都出現(xiàn)，則分別用矩陣中其下方的字母代替，列的最后一個字母由列的第一個字母代替。例如，en被加密成NU，而aw被加密成BA。（4）否則，明文對中的每個字母將由與其同行，且與另一個字母同列的字母代替。例如，se被加密成NK，而cu被加密成IX（或JX）。

Playfair密碼與單字母替代密碼相比有明顯的優(yōu)勢：其一，雙字母有26×26＝676種組合方式，識別各種雙字母組合比單字母困難得多；其二，各種字母組的相對頻率范圍也更為廣泛，使頻率分析更加困難。因此，Playfair曾被認(rèn)為是不可破譯的，英國陸軍在第一次世界大戰(zhàn)中采用了它，二戰(zhàn)中它仍被美國陸軍和其他同盟國大量使用。當(dāng)然，由于許多明文的語言結(jié)構(gòu)在Playfair密碼中能夠保存完好，所以它還是相對容易破譯的，通常有幾百字的密文就足夠了。Playfair密碼（4）多表替代密碼：由多個簡單的替代密碼構(gòu)成，例如，可能有5個不同的簡單替代密碼，分別用于替代明文中不同位置的字符。

多表替代密碼由LeonBattista在1568年發(fā)明，在美國南北戰(zhàn)爭期間由聯(lián)軍使用。盡管在計算機(jī)的幫助下這種密碼容易被破譯，但仍有許多商用計算機(jī)的保密產(chǎn)品使用它。比較著名的多表替代密碼是1858年法國密碼學(xué)家維吉尼亞設(shè)計的以移位替代為基礎(chǔ)的一種周期替代密碼，稱為維吉尼亞密碼（Vigenère）。此外，還有博福特密碼（Beaufort）、弗納姆密碼（Vernam）等。

多表替代密碼有多個單字母密鑰，每一個密鑰被用來加密一個明文字母。第一個密鑰加密明文的第一個字母，第二個密鑰加密明文的第二個字母等等。在所有的密鑰用完后，密鑰又再循環(huán)使用，若有20個單個字母密鑰，那么每隔20個字母的明文都被同一密鑰加密，這稱為密碼的周期。在古典密碼學(xué)中，密碼周期越長越難破譯。雖然使用計算機(jī)能夠輕易破譯具有很長周期的替代密碼，但在古代，靠手工計算是很難破譯的。

滾動密鑰密碼（有時叫書本密碼）也是多表替代密碼，它用一個文本去加密另一個文本，即使這種密碼的周期與文本一樣長，也容易被破譯。Vigenère密碼

Vigenère密碼是最著名且最簡單的多表替代密碼，右圖是一個現(xiàn)代Vigenère表格，用它可以方便地進(jìn)行加密。在表格中，密鑰字母為行標(biāo)，明文字母為列標(biāo)?，F(xiàn)代Vigenère表格密鑰字母為行標(biāo)明文字母為列標(biāo)Vigenère密碼加密的過程為： 給定一個密鑰字母和一個明文字母，則在行標(biāo)與列標(biāo)的交叉點上的就是密文字母。例如，密鑰字母為d，明文字母為l，則密文字母為O。

加密一個消息，需要與該消息同樣長度的密鑰。通常，該密鑰是一個不斷重復(fù)的關(guān)鍵詞。 例如，設(shè)關(guān)鍵詞為encipher， 消息為Thespeechcontainedsomeinterestingideas，則

密鑰：encipherencipherencipherencipherenciph

明文：thespeechcontainedsomeinterestingideas

密文：XUGAELITLPQVIHMEIQUWBLMEXRTMHAMEKVFMPZ

Vigenère密碼所有運算都是（mod26）進(jìn)行，由于是多表替換體制，每個明文字母對應(yīng)多個密文字母，且明文字母對應(yīng)選定關(guān)鍵詞的特定字母，因此，字母的頻率信息被模糊了。

Vigenère密碼的密鑰和明文共享相同的字母頻率分布，所以它對于應(yīng)用統(tǒng)計技術(shù)進(jìn)行密碼分析也是脆弱的。對抗此類密碼分析的根本方法是選擇與明文一樣長，并且與之沒有統(tǒng)計關(guān)系的密鑰。若密鑰為非周期無限序列，則相應(yīng)的密碼為非周期多表替代密碼。此時，每個明文字母都采用不同的替代表進(jìn)行加密，稱作是一次一密鑰密碼，這是一種在理論上惟一不可破的密碼。這種密碼對于明文的特征可實現(xiàn)完全隱蔽，但由于需要的密鑰量和明文消息長度相同而難以實用。為了減少密鑰量，實際中多采用周期多表替代密碼。③轉(zhuǎn)輪機(jī)

20世紀(jì)20年代，人們發(fā)明了各種機(jī)械加密設(shè)備用來自動處理加密，這些設(shè)備多數(shù)是基于轉(zhuǎn)輪的概念，即將機(jī)械轉(zhuǎn)輪用線連起來完成通常的密碼替代。

轉(zhuǎn)輪機(jī)有鍵盤和一系列轉(zhuǎn)輪，它是Vigenère

密碼的一種實現(xiàn)。每個轉(zhuǎn)輪是字母的任意組合，有26個位置，并且完成一種簡單替代。例如：一個轉(zhuǎn)輪可能被用線連起來以完成用“F”替代“A”，用“U”替代“B”，用“L”替代“C”等等，而且轉(zhuǎn)輪的輸出栓連接到相鄰的輸入栓。

例如，在4個轉(zhuǎn)輪的密碼機(jī)中，第一個轉(zhuǎn)輪可能用“F”替代“A”，第二個轉(zhuǎn)輪可能用“Y”替代“F”，第三個轉(zhuǎn)輪可能用“E”替代“Y”，第四個轉(zhuǎn)輪可能用“C”替代“E”，“C”應(yīng)該是輸出密文。那么當(dāng)轉(zhuǎn)輪移動后，下一次替代將有所不同。

為使機(jī)器更安全，可把幾種轉(zhuǎn)輪和移動的齒輪結(jié)合起來。所有轉(zhuǎn)輪以不同的速度移動，n個轉(zhuǎn)輪的機(jī)器的周期是26n。為進(jìn)一步阻止密碼分析，有些轉(zhuǎn)輪機(jī)在每個轉(zhuǎn)輪上還有不同的位置號。最著名的轉(zhuǎn)輪裝置是恩尼格馬（Enigma），它在第二次世界大戰(zhàn)期間由德國人使用并改進(jìn)。恩尼格馬有三個轉(zhuǎn)輪，從五個轉(zhuǎn)輪中選擇。轉(zhuǎn)輪機(jī)中有一塊稍微改變明文序列的插板，有一個反射輪導(dǎo)致每個轉(zhuǎn)輪對每一個明文字母操作兩次。1.4一次一密亂碼本

1917年，MajorJosephMauborgne和AT&T公司的GilbertVernam發(fā)明了一次一密亂碼本的加密方案。通常，一次一密亂碼本是一個大的不重復(fù)的真隨機(jī)密鑰字母集，這個密鑰字母集被寫在幾張紙上，并一起粘成一個亂碼本，它最初用于電傳打字機(jī)。發(fā)方用亂碼本中的每一密鑰字母準(zhǔn)確地加密一個明文字符。加密是明文字符和一次一密亂碼本密鑰字符的模26加法。 每個密鑰僅對一個消息使用一次。發(fā)方對所發(fā)的消息加密，然后銷毀亂碼本中用過的一頁或用過的磁帶部分。收方有一個同樣的亂碼本，并依次使用亂碼本上的每個密鑰去解密密文的每個字符。收方在解密消息后銷毀亂碼本中用過的一頁或用過的磁帶部分。新的消息則用亂碼本中新的密鑰加密。例如，如果消息是：ONETIMEPAD， 而取自亂碼本的密鑰序列是：TBFRGFARFM， 那么密文就是：IPKLPSFHGQ，因為O+Tmod26=IN+Bmod26=PE+Fmod26=K

等等。由于明文消息是等概率的，所以密碼分析者沒有辦法確定哪一個明文消息是正確的。隨機(jī)密鑰序列異或一非隨機(jī)的明文消息將產(chǎn)生完全隨機(jī)的密文消息，即便現(xiàn)代的高速計算機(jī)對此也無能為力。例：m=Iloveyou，一次性密碼本。m=(8,11,14,21,4,24,14,20)k=(5,13,1,0,7,2,20,16)注：可能的密鑰序列共268個。c=(13,24,15,21,11,0,8,10)使用一次一密亂碼本需要注意的是：（1）密鑰字母必須隨機(jī)產(chǎn)生。對這種方案的攻擊主要是針對用來產(chǎn)生密鑰序列的方法。偽隨機(jī)數(shù)發(fā)生器通常具有非隨機(jī)性，所以不能用于產(chǎn)生隨機(jī)密鑰序列。采用真隨機(jī)源，它才是安全的。（2）密鑰序列不能重復(fù)使用。如果密碼分析家有多個密鑰重疊的密文，那么即使你用多兆字節(jié)的亂碼本，他也能重構(gòu)明文。他可以把每排密文移來移去，并計算每個位置的適配量。如果他們排列正確，則適配的比例會突然升高（準(zhǔn)確的百分比與明文的語種有關(guān)）。從這一點來說，密碼分析是容易的，它類似于重合指數(shù)法，只不過用兩個"周期"。所以千萬別重復(fù)使用密鑰序列。1.5計算機(jī)算法計算機(jī)密碼算法有多種,最通用有以下三種：

（1）DES（dataencryptionstandard，數(shù)據(jù)加密標(biāo)準(zhǔn)）是最通用的計算機(jī)加密算法。DES是國際標(biāo)準(zhǔn)，它是對稱算法，加密和解密的密鑰是相同的。（2）RSA（RonRivest、Adi

Shamir、Len

Adleman)算法是最流行的公開密鑰算法，它用作加密和數(shù)字簽名。（3）DSA（digitalsignaturealgorithm,數(shù)字簽名算法，用作數(shù)字簽名的一部份）是另一種公開密鑰算法，它不能用作加密，只用作數(shù)字簽名。1.6密碼的分類從不同的角度根據(jù)不同的標(biāo)準(zhǔn)，可以把密碼分成若干類。一、按應(yīng)用技術(shù)或歷史發(fā)展階段劃分：1、手工密碼。以手工完成加密作業(yè)，或者以簡單器具輔助操作的密碼，叫作手工密碼。第一次世界大戰(zhàn)前主要是這種作業(yè)形式。2、機(jī)械密碼。以機(jī)械密碼機(jī)或電動密碼機(jī)來完成加解密作業(yè)的密碼，叫作機(jī)械密碼。這種密碼從第一次世界大戰(zhàn)出現(xiàn)到第二次世界大戰(zhàn)中得到普遍應(yīng)用。3、電子機(jī)內(nèi)亂密碼。通過電子電路，以嚴(yán)格的程序進(jìn)行邏輯運算，以少量制亂元素生產(chǎn)大量的加密亂數(shù)，因為其制亂是在加解密過程中完成的而不需預(yù)先制作，所以稱為電子機(jī)內(nèi)亂密碼。從五十年代末期出現(xiàn)到七十年代廣泛應(yīng)用。4、計算機(jī)密碼，是以計算機(jī)軟件編程進(jìn)行算法加密為特點，適用于計算機(jī)數(shù)據(jù)保護(hù)和網(wǎng)絡(luò)通訊等廣泛用途的密碼。

?

按照保密的內(nèi)容分:

受限制的（restricted)算法:算法的保密性基于保持算法的秘密。

基于密鑰（key-based)的算法:算法的保密性基于對密鑰的保密。按照明文的處理方法：

分組密碼（blockcipher):將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度密文。

流密碼（streamcipher):又稱序列密碼.序列密碼每次加密一位或一字節(jié)的明文，也可以稱為流密碼。

序列密碼是手工和機(jī)械密碼時代的主流

二、按保密程度劃分1、理論上保密的密碼不管獲取多少密文和有多大的計算能力，對明文始終不能得到唯一解的密碼，叫作理論上保密的密碼。也叫理論不可破的密碼。如隨機(jī)一次一密的密碼就屬于這種。2、實際上保密的密碼在理論上可破，但在現(xiàn)有客觀條件下，無法通過計算來確定唯一解的密碼，叫作實際上保密的密碼。3、不保密的密碼在獲取一定數(shù)量的密文后可以得到唯一解的密碼，叫作不保密密碼。如早期單表代替密碼，后來的多表代替密碼，以及明文加少量密鑰等密碼，現(xiàn)在都成為不保密的密碼。

三、按密鑰方式劃分1、對稱式密碼收發(fā)雙方使用相同密鑰的密碼，叫作對稱式密碼。傳統(tǒng)的密碼都屬此類。就是加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個易于推出另一個。又稱秘密密鑰算法或單密鑰算法。

2、非對稱式密碼收發(fā)雙方使用不同密鑰的密碼，叫作非對稱式密碼。如現(xiàn)代密碼中的公共密鑰密碼就屬此類。非對稱密鑰算法（asymmetriccipher):加密密鑰和解密密鑰不相同，從一個很難推出另一個。又稱公開密鑰算法（public-keycipher)。?公開密鑰算法用一個密鑰進(jìn)行加密,而用另一個進(jìn)行解密.其中的加密密鑰可以公開,又稱公開密鑰（publickey)，簡稱公鑰.解密密鑰必須保密,又稱私人密鑰（privatekey)私鑰.簡稱私鑰。

四、按明文形態(tài)

1、模擬型密碼用以加密模擬信息。如對動態(tài)范圍之內(nèi)，連續(xù)變化的語音信號加密的密碼，叫作模擬式密碼。2、數(shù)字型密碼用于加密數(shù)字信息。對兩個離散電平構(gòu)成0、1二進(jìn)制關(guān)系的電報信息加密的密碼叫作數(shù)字型密碼。五、近代加密技術(shù)1.數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）是美國經(jīng)長時間征集和篩選后，于1977年由美國國家標(biāo)準(zhǔn)局頒布的一種加密算法。它主要用于民用敏感信息的加密，后來被國際標(biāo)準(zhǔn)化組織接受作為國際標(biāo)準(zhǔn)。DES主要采用替換和移位的方法加密.

DES主要的應(yīng)用范圍有：（1）計算機(jī)網(wǎng)絡(luò)通信：對計算機(jī)網(wǎng)絡(luò)通信中的數(shù)據(jù)提供保護(hù)是DES的一項重要應(yīng)用。但這些被保護(hù)的數(shù)據(jù)一般只限于民用敏感信息，即不在政府確定的保密范圍之內(nèi)的信息。（2）電子資金傳送系統(tǒng)：采用DES的方法加密電子資金傳送系統(tǒng)中的信息，可準(zhǔn)確、快速地傳送數(shù)據(jù)，并可較好地解決信息安全的問題。

(3）保護(hù)用戶文件：用戶可自選密鑰對重要文件加密，防止未授權(quán)用戶竊密。

(4）用戶識別：DES還可用于計算機(jī)用戶識別系統(tǒng)中。

2.

國際數(shù)據(jù)加密算法IDEA是瑞士的著名學(xué)者提出的。它在1990年正式公布并在以后得到增強(qiáng),這種算法是在DES算法的基礎(chǔ)上發(fā)展出來的，類似于三重DES.

3.公開密鑰密碼體制傳統(tǒng)的加密方法是加密、解密使用同樣的密鑰，由發(fā)送者和接收者分別保存，在加密和解密時使用，采用這種方法的主要問題是密鑰的生成、注入、存儲、管理、分發(fā)等很復(fù)雜，特別是隨著用戶的增加，密鑰的需求量成倍增加。在網(wǎng)絡(luò)通信中，大量密鑰的分配是一個難以解決的問題。例如，若系統(tǒng)中有n個用戶，其中每兩個用戶之間需要建立密碼通信，則系統(tǒng)中每個用戶須掌握(n-1)個密鑰，而系統(tǒng)中所需的密鑰總數(shù)為n*(n-1)/2個。對10個用戶的情況，每個用戶必須有9個密鑰，系統(tǒng)中密鑰的總數(shù)為45個。對100個用戶來說，每個用戶必須有99個密鑰，系統(tǒng)中密鑰的總數(shù)為4950個。這還僅考慮用戶之間的通信只使用一種會話密鑰的情況。如此龐大數(shù)量的密鑰生成、管理、分發(fā)確實是一個難處理的問題。本世紀(jì)70年代，美國斯坦福大學(xué)的兩名學(xué)者迪菲和赫爾曼提出了一種新的加密方法—公開密鑰加密隊PKE方法。與傳統(tǒng)的加密方法不同，該技術(shù)采用兩個不同的密鑰來對信息加密和解密，它也稱為非對稱式加密方法。每個用戶有一個對外公開的加密密鑰（公鑰）和對外保密的解密密鑰（私鑰）。

1.7數(shù)字簽名的特征

簽名是可信的簽名使文件的接受者相信簽名者是慎重地在文件上簽字的。

簽名不可偽造簽名證明是簽名者而不是其它人慎重地在文件上簽字。

簽名不可重用簽名是文件的一部分，不法之徒不可能將和簽名移到不同的文件上。

簽名的文件是不可改變的在文件答名后，文件不能改變。簽名是不可抵賴的簽名和文件是物理的東西。簽名者事后不能稱他沒有簽名。思考作業(yè)：解釋以下概念：密碼學(xué)，密碼編碼，密碼分析，明文，密文，加密，解密，密碼體制，對稱密碼體制，公鑰密碼體制，分組密碼，流密碼。Kerckhoffs假設(shè)的內(nèi)容是什么？根據(jù)自身經(jīng)驗說明對密碼學(xué)的理解，舉出密碼應(yīng)用的一些例子。第二講

數(shù)學(xué)背景

一、信息論1．熵和不確定性信息論定義一條消息的信息量如下：假設(shè)所有消息是等可能的，對消息中所有可能的值進(jìn)行編碼所需要的最小位數(shù)。如數(shù)據(jù)庫中有關(guān)“一周中的每一天”這一字段包含不超過3位的信息，因此此消息可以用3位進(jìn)行編碼：000=星期日

……110=星期六111是未用的一條消息M的信息量可通過它的熵（entropy）來度量，表示為H（M）。一條表示性別的熵為1位，一條表示一周的天數(shù)的消息的熵略小于3位。通常一條消息的熵是log2n,其中n是消息所有可能的值。一條消息的熵亦表示了它的不確定性（uncertainty）,即當(dāng)消息被加密成密文時，為了獲取明文，需要解密的明文的位數(shù)。例職關(guān)于性別消息的不確定性是1。2．混亂與擴(kuò)散

混亂（confusion）用于掩蓋明文和密文間的關(guān)系。這可以挫敗通過研究密文以獲取冗余度和統(tǒng)計模式的企圖?？梢酝ㄟ^代替密碼實現(xiàn)。擴(kuò)散（diffusion）通過將明文冗余度分散到密文中使之分散開來。密碼分析者尋求這些冗余度將會更難。產(chǎn)生擴(kuò)散的方法是通過換位（亦稱置換）

分組密碼算法即用到擴(kuò)散又用到混亂。二、復(fù)雜性理論1．算法的復(fù)雜性一個算法的復(fù)雜性即運行它所需的計算能力。算法的計算復(fù)雜性常常用兩個變量度量：T（時間復(fù)雜性（timecomplexity））和S(空間復(fù)雜性（spacecomplexity）或所需存儲空間)，T和S通常表示為n的函數(shù)。O（1）：算法的復(fù)雜性不依賴于n，它是常數(shù)的。O（n）：線性的。O（nm）:其中m為一常數(shù)。有些算法是二次方、三次方的等。所有這些算法都是多項式的。具有多項式時間復(fù)雜性的算法稱為多項式時間（polynomial-time）算法。O(tf(n)):指數(shù)的(exponential)。t是大于1的常數(shù),f(n)是n的多項式函數(shù)

2．問題的復(fù)雜性圖靈機(jī)的理論計算機(jī)上解決最難的問題實例所需要的最少時間和空間。圖靈機(jī)是一種無限讀寫存儲帶的有限狀態(tài)機(jī)。能夠用多項式時間算法解決的問題稱之為易處理的（tractable），因為它們能夠用適當(dāng)?shù)妮斎氤叽?，在適當(dāng)?shù)臅r間開銷內(nèi)解決。不能在多項式時間內(nèi)解決的問題稱之為難處理的（intractable）

,也稱為難題（hard)。問題可分為：PNP（NP完全）

PSPACE(PSPACE完全)EXPTIMEP類問題是指所有能用多項式時間解決的問題.NP問題是所有在非確定型圖靈機(jī)上可用多項式時間解決的問題.非確定型圖靈機(jī)是標(biāo)準(zhǔn)圖靈機(jī)的變形,它能進(jìn)行猜測.此機(jī)器通過幸運猜測或平行嘗試猜測所有可能的問題的解,然后在多項式時間內(nèi)檢查它的猜測.

NP的英文全稱是Non-deterministicPolynomial的問題，即多項式復(fù)雜程度的非確定性問題。簡單的寫法是NP=P？，問題就在這個問號上，到底是NP等于P，還是NP不等于P。

3.NP完全問題旅行商問題:一名旅行商必須到n個不同的城市,而它僅有一箱汽油.有方法使它僅用一箱汽油而旅行到每個城市恰好一次嗎?(Himilton問題)

背包問題(knapsack),又稱子集合問題（subsetsum)屬于NP問題。4.嚴(yán)格單向函數(shù)?一個單射函數(shù)f:X→Y稱為是嚴(yán)格單向函數(shù)，如果下述條件成立：存在一個有效的方法，對所有的x∈X可計算f（x），但不存在一個有效的辦法由y=f（x）計算x,所有的y∈Y?嚴(yán)格單向函數(shù)是不能用于加解密的,

對于嚴(yán)格單向函數(shù)的存在，現(xiàn)無法證明三、數(shù)論數(shù)論就是指研究整數(shù)性質(zhì)的一門理論。整數(shù)的基本元素是素數(shù)，所以數(shù)論的本質(zhì)是對素數(shù)性質(zhì)的研究。

1、模運算（求余運算

）例：如果TOM說10：00他回家，而他遲到了13個小時，那么他什么時間回家。這是一個模12運算，23模12等11，記為：23MOD12=11MOD12=11

另一種寫法認(rèn)為23和11的模12運算相等：23

11（MOD12）一般表示為：a=b+kn，即：a

b(modn)稱a和b同余2．素數(shù)（質(zhì)素）比1大,其因子只有1和它本身,沒有其他數(shù)可以整除它.2,73,2521,2365347734339等.素數(shù)是無限的.密碼學(xué)特別是公開密鑰密碼學(xué)常用大的素數(shù)（512位長或更長）（1）最大公因子兩個數(shù)互素(relativelyprime)是指當(dāng)它們除了1之外沒有共同的公因子。計算最大公因子(greatestcommondivisor)算法為歐機(jī)里德算法：Gcd(x,y)=gcd(y,xmody)int

gcd(int

x,inty){intg;

if(x<0)x=-x;

if(y<0)y=-y;

if(x+y==0)returnerror;g=y;

while(x>0){g=x;x=y%x;y=g;}returng;}如果a和n的最大公因子為1,可以寫作:gcd(a,n)=1(2)求模逆元

逆元的概念

模逆元：4

x

1(mod7)這個方程等價于尋找一個x和k使得：4x=7k+1x,k均為整數(shù)。更一般的問題是尋找一個x，使得：1=(a

x)modn亦可寫作：

a-1

x(modn)5模14有逆元是3，2模14沒有逆元。一般而論。如果a和n互素的，那么a-1

x(modn)有唯一解；如果a和n不是互素的，那么a-1

x(modn)沒有解，如果n是一個素數(shù)，那么從1到n-1的每個數(shù)與n都互素的，且在這個范圍內(nèi)恰好有一個逆元。求a模n的逆元的擴(kuò)展歐幾里德算法。3費爾馬小定理費馬小定理是數(shù)論中的一個重要定理,其內(nèi)容為:假如p是質(zhì)數(shù)，且(a,m)=1（am互質(zhì)），那么a^(m-1)≡１（modp）假如m是質(zhì)數(shù)，且a,m互質(zhì)，那么a的(m-1)次方除以m的余數(shù)恒等于1

如果m是一個素數(shù)，且a不是m的倍數(shù)(即a,m互素)，那么，根據(jù)費爾馬小定理有：

am-1

1(modm)他是解析幾何的發(fā)明者之一；對于微積分誕生的貢獻(xiàn)僅次于艾薩克·牛頓、戈特弗里德·威廉·凡·萊布尼茨，概率論的主要創(chuàng)始人，以及獨承17世紀(jì)數(shù)論天地的人

4歐拉

函數(shù)

歐拉函數(shù)，亦稱為歐拉

函數(shù)，寫作

（n），它表示模n的余數(shù)化簡集中元素的數(shù)目。換句話說，

（n）表示與n互素的小于n的正整數(shù)的數(shù)目（n>1）。

如果n是素數(shù)，那么

（n）=n-1；

如果n=pq,且p,q互素，那么

（n）=（p-1）(q-1)

這些數(shù)字在公開密鑰中經(jīng)常用到。

根據(jù)費爾馬小定理的歐拉推廣，如果gcd(a,n)=1，那么

a

(n)modn=1

由于an-1modn=1，（a*x)modn=1

現(xiàn)在計算a模n逆元很容易：x=a

(n)-1modn

例如求5模7的逆元是多少？既然7是素數(shù)，

（7）=7-1=6，因此5模7的逆元是56-1

mod7=3法國”業(yè)余數(shù)學(xué)家之王”皮埃爾?德?費馬于1636年發(fā)現(xiàn)了這個定理瑞士數(shù)學(xué)家和物理學(xué)家

5.中國剩余定理中國古代求解一次同余式組的方法。是數(shù)論中一個重要定理。又稱中國剩余定理。公元前后的《孫子算經(jīng)》中有“物不知數(shù)”問題：“今有物不知其數(shù)，三三數(shù)之余二，五五數(shù)之余

三，七七數(shù)之余二，問物幾何？答曰：『二十三』”。也就是求同余式組x≡2（mod3），x≡3（mod5），x≡2（mod7）的正整數(shù)解。

如果已知n的素因子，那么就利用中國剩余定理求解整個方程組。一般而言，如果n的素因子分解為n=p1×p2×p3…×pt,那么方程組（xmodpi）=ai有唯一的解，

x小于n（注意一些素數(shù)可能不止一次出現(xiàn)）換句話說，一個數(shù)（小于一些素數(shù)之積）被它的余數(shù)模這些素數(shù)唯一地確定。例如：取素數(shù)3和5，取一個數(shù)14，那么14mod3=2,14mod5=4,則小于15且有上述余數(shù)的數(shù)只有14，即由這兩個余數(shù)唯一地確定數(shù)14

如果對于任何a<p,b<q（p,q都是素數(shù)），那么當(dāng)x小于p×q時，存在唯一一個x使得：

x

a(modp)且x

b(modq)為求這個數(shù)先用歐幾里德算法找到u，使得：

u×q=1(modp)然后計算：

x=(((a-b)×u)mod

p)×q+b

例：p=5,q=3a=4,b=2u=7x=146．有限域上的離散對數(shù)僅含有限多個元素的域。它首先由E.伽羅瓦所發(fā)現(xiàn)，因而又稱為伽羅瓦域。模指數(shù)運算是頻繁用于密碼學(xué)中的另一個單向函數(shù)。所謂離散對數(shù)，就是給定正整數(shù)x，y，n，求出正整數(shù)k（如果存在的話），使y≡xk(modn)。就目前而言，人們還沒有找到計算離散對數(shù)的快速算法

.計算下列表達(dá)式很容易

axmodn

模指數(shù)運算的逆問題是找出一個數(shù)的離散對數(shù)，這是個難題：

求解x，使得ax

b(modn)例如：3x

15mod17，那么x=6,不是所有的離散對數(shù)都有解。3x

7mod13無解。7．單向散列函數(shù)單向散列函數(shù)H（M）作用于任意長度的消息M，它返回一固定長度的散列值h:h=H(M)其中h的長度為m

輸入任意長度且輸出為固定長度的函數(shù)有多種，但單向散列函數(shù)還具有使其單向的如下特征：。給定M，很容易計算h。給定h，根據(jù)H（M）=h計算M很難。給定M，要找到另一個消息M’并滿足H（M）=H（M’）很難在一些其它的應(yīng)用中，僅有單向性是不夠的，還需要稱之為抗碰撞的條件：要找出兩個隨機(jī)的消息M和M’來滿足H（M）=H（M’）滿足很難8．因子分解對一個數(shù)進(jìn)行因子分解就是找出它的素因子10=2*560=2*2*3*5252601=41*61*101目前最好的因子分解算法是：。數(shù)域篩選法（numberfieldsieve,NFS）。二次篩選法。橢園曲線法。Pollard的蒙特卡羅算法。連分式算法。試除法9．生成元如果p是一個素數(shù)，且g小于p，對于從0到p-1的每一個b，都存在某個a，使得ga

b(modp)，那么g是模p的生成元（generator）。另一種稱法稱g是p的本原元（primitive）。例如，如果p=11，2是模11的一個生成元210=1024

1（mod11）21=2

2（mod11）28=256

3（mod11）22=4

4（mod11）24=16

5（mod11）29=512

6（mod11）27=128

7（mod11）23=8

8（mod11）26=64

9（mod11）25=32

10（mod11）10．二次剩余在數(shù)論中，特別在同余理論裏，一個整數(shù)X對另一個整數(shù)p的二次剩餘（英語：Quadraticresidue）指X的平方X^2除以p得到的余數(shù)。當(dāng)對於某個d及某個X，式子X^2=

d(modp)成立時，稱「d是模p的二次剩餘」當(dāng)對於某個d及某個X，X^2=

d(modp)不成立時，稱「d是模p的二次非剩餘」如果p是素數(shù)，且a小于p，如果x2

a（modp）,對一些x成立，那么稱a是對模p的二次剩余（quadraticresidue）。

不是所有的a的值都滿足這個特性。如果a是對模n的一個二次剩余，那么它必定是對模n的所有素因子的二次剩余。如：p=7，二次剩余是1，2，4：12=1

1（mod7）22=4

4（mod7）32=9

2（mod7）42=16

2（mod7）52=25

4（mod7）62=36

1（mod7）沒有x值可滿足下列這些方程的任意一個：

x2

3（mod7）x2

5（mod7）x2

6（mod7）

所以3，5，6是對模7的二次非剩余。

11.有限域僅含有限多個元素的域。它首先由E.伽羅瓦（1811-1832）所發(fā)現(xiàn)，因而又稱為伽羅瓦域（Galoisfield）。

有限域中元素的個數(shù)為一個素數(shù)，或者一個素數(shù)的冪，記為GF（P）或GF（pn),其中P為素數(shù)。

有限域中運算滿足交換律、結(jié)合律、和分配律。密碼學(xué)中用到很多有限域中的運算，因為可以保持?jǐn)?shù)在有限的范圍內(nèi)，且不會有取整的誤差。–GF(p)–GF(2n)GaloisFieldsGF(p)

GF(p)是整數(shù)集合{0,1,…,p-1}具有模素數(shù)p的運算作業(yè)：在RSA算法中，如果p＝3，q＝11，e=3，試寫出d的計算過程；給出RSA加密算法對明文m＝5進(jìn)行加密和解密的過程；描述中間人攻擊情況下，攻擊者需要做的工作。描述迪菲－赫爾曼密鑰交換（Diffie–Hellmankeyexchange）協(xié)議中是如何實現(xiàn)密鑰交換的。以p=23以及g=5為例來說明。第三講

密碼協(xié)議協(xié)議結(jié)構(gòu)模塊協(xié)議（protocol）是一系列步驟，它包括兩方或者多方，設(shè)計它的目的是要完成一件任務(wù)。特點：每個人都了解協(xié)議，預(yù)先知道所有步驟。每個人都必須同意并遵守。協(xié)議必須是清楚，不會有誤解、歧義。必須完整，每種可能情況必須規(guī)定具體動作。密碼協(xié)議就是使用密碼學(xué)的協(xié)議。協(xié)議中的角色Alice協(xié)議中的第一個參與者Bob協(xié)議中的第二個參與者carol三方協(xié)議的參與者Dave四方協(xié)議的參與者Eve竊聽者M(jìn)allory惡意的主動攻擊者Trend值得信賴的仲裁者Walter監(jiān)察人：保護(hù)Alice和BobPeggy證明人Victor驗證者被動攻擊，主動攻擊2．1基本協(xié)議一、密鑰交換1．對稱密碼學(xué)的密鑰交換此協(xié)議假設(shè)Alice和Bob每人和

KDC(KeyDistributionCenter)共享一個秘密密鑰，在我們的協(xié)議中Trent就是KDC。在協(xié)議開始之前，這些密鑰必須在適當(dāng)?shù)奈恢?。?）

Alice呼叫KDC，并請求一個與Bob通信的會話密鑰。（2）KDC產(chǎn)生一隨機(jī)會話密鑰，并對它的兩個副本加密：一個用Alice的密鑰，另一個用Bob的密鑰加密。Trent發(fā)送這兩個副本給Alice（3）Alice對她的會話密鑰的副本解密（4）Alice將Bob的會話密鑰的副本傳給Bob（5）Bob對他的會話密鑰的副本解密Alice和Bob用這個會話密鑰安全通信。這個協(xié)議依賴于Trent的絕對安全性。Trent更可能是可信的計算機(jī)程序，而不是可信的個人。此協(xié)議的缺點是：（1）MALLORY可能破壞KDC，整個網(wǎng)絡(luò)都會破壞。他有Trent與每個用戶共享的秘密密鑰；（2）KDC可能成為瓶頸。他必須參與每一次密鑰交換，如果KDC失敗了，這個系統(tǒng)就會被破壞。2．公開密鑰密碼學(xué)的密鑰交換基礎(chǔ)的混合密碼系統(tǒng)中，Alice和Bob使用公開密鑰密碼協(xié)商會話密鑰，并用協(xié)商的會話密鑰加密數(shù)據(jù)。在一些實際的現(xiàn)實中，Alice和Bob簽名的公開密鑰可在數(shù)據(jù)庫中獲得。這使得密鑰交換更容易，即使Bob從來沒有聽說過Alice，Alice亦能夠把消息安全地發(fā)送給BOB。（1）Alice從KDC得到BOB的公開密鑰。（2）Alice產(chǎn)生隨機(jī)會話密鑰，用Bob的公開密鑰加密它，然后將它傳給BOB。（3）BOB用他的私人密鑰解密Alice的消息。（4）

兩人用同一會話密鑰對他們的通信進(jìn)行加密。

3．

中間人攻擊Eve除了試圖破譯公開密鑰算法或者對密文攻擊之外，沒有更好的辦法。MALLORY比EVE更有能力，他不僅能竊聽Alice和BOB間的消息，還能修改、刪除消息，并能產(chǎn)生全新的消息并能模仿Alice和BOB談話。（1）Alice將她的公開密鑰傳遞給BOB。MALLORY截取這個密鑰，并將自己的公開密鑰傳送給BOB（2）BOB將他的公開密鑰傳遞給Alice。MALLORY截取這個密鑰，并將自己的公開密鑰傳送給Alice（3）當(dāng)Alice將用BOB的公開密鑰加密消息傳遞給BOB時，MALLORY截取它。由于消息實際上是用MALLORY的公開密鑰加密的，他就用自己的私人密鑰解密。再用BOB的公開密鑰對消息重新加密，并將它傳送給BOB。（4）BOB將用Alice的公開密鑰加密消息傳遞給Alice時，MALLORY截取它。由于消息實際上是用MALLORY的公開密鑰加密的，他就用自己的私人密鑰解密。再用Alice的公開密鑰對消息重新加密，并將它傳送給Alice。

即使Alice和BOB的公開密鑰存儲在數(shù)據(jù)庫中，這種攻擊亦是可行的。MALLORY能夠截取Alice的數(shù)據(jù)庫查詢，并用自己的公開密鑰代替BOB的公開密鑰，對BOB他可做同樣的事情。

4．

聯(lián)鎖協(xié)議由RonRivest和AdiShamir發(fā)明的聯(lián)鎖協(xié)議是阻止中間人攻擊的好辦法。（1）Alice將她的公開密鑰傳送給BOB（2）BOB將她的公開密鑰傳送給Alice（3）Alice用BOB的公開密鑰加密她的消息，并將加密消息的一半傳送給BOB（4）BOB用Alice的公開密鑰加密她的消息，并將加密消息的一半傳送給Alice（5）Alice將加密的另一半消息傳遞給BOB

（6）

BOB將Alice的兩半消息合在一起，并用他的私人密鑰解密；BOB將她加密的另一半消息傳遞給Alice(7)Alice將BOB兩半消息合在一起，并用她的私人密鑰解密。

5．

使用數(shù)字簽名的密鑰交換在會話密鑰交換協(xié)議期間采用數(shù)字簽名亦能防止中間人攻擊。KDC對Alice和BOB的公開密鑰簽名。簽名的密鑰包括一個已簽名的所有權(quán)證書。當(dāng)Alice和BOB收到密鑰時，他們每個人都能驗證KDC的簽名。他們就知道公開密鑰是哪個人的。密鑰的交換就能進(jìn)行了。

6．

密鑰和消息傳輸Alice和BOB在交換消息前不需要完成密鑰交換協(xié)議。在下面的協(xié)議中，Alice在沒有任何以前的密鑰交換的情況下，將消息M傳送給BOB。（1）Alice產(chǎn)生一隨機(jī)會話密鑰K，并用K加密M：EK（M）（2）Alice從數(shù)據(jù)庫中得到BOB的公開密鑰。（3）Alice用BOB的公開密鑰加密K：EB（K）（4）Alice將加密的消息和加密的會話密鑰傳送給BOB：

EK（M）、EB（K）。

為人增加安全性，防止中間人攻擊，Alice可對傳輸簽名。（5）BOB用他的私人密鑰將Alice的會話密鑰K解密。（6）BOB用會話密鑰將Alice的消息解密。這個混合系統(tǒng)表示，公開密鑰密碼是怎樣經(jīng)常用于通信系統(tǒng)的。它可以和數(shù)字簽名、時間標(biāo)記以及任何其他安全協(xié)議合在一起使用。

7．

密鑰和消息廣播Alice想把消息傳送給BOB、CAROL和DAVE（1）

Alice產(chǎn)生一隨機(jī)會話密鑰K，并用K加密M：EK（M）（2）Alice從數(shù)據(jù)庫中得到BOB、CAROL和DAVE的公開密鑰。（3）Alice用BOB的公開密鑰加密K，用CAROL的公開密鑰加密K，用DAVE的公開密鑰加密K：EB（K）、EC（K）、ED（K）（4）Alice廣播加密的消息和所有加密的會話密鑰傳送給BOB、CAROL和DAVE：EK（M）、EB（K）EC（K）、ED（K）。（5）BOB、CAROL、DAVE用他們的私人密鑰將Alice的會話密鑰將解密。（6）

BOB、CAROL、DAVE用會話密鑰將Alice的消息解密。二、鑒別1．使用單向函數(shù)鑒別RogerNeedham和MikeGuy意識到計算機(jī)沒有必要知道口令。計算機(jī)只需有能力區(qū)別有效口令和無效口令就成。這種辦法很容易用單向函數(shù)來實現(xiàn)。計算機(jī)存儲口令的單向函數(shù)而不是口令。（1）

Alice將她的口令傳送給計算機(jī)（2）

計算機(jī)完成口令的單向函數(shù)計算。（3）計算機(jī)把單向函數(shù)的運算結(jié)果和它以前存儲的值比較。由于計算機(jī)不再存儲每人的有效口令表，所以某些人侵入計算機(jī)，并偷取口令的可能就減少了。由口令的單向函數(shù)產(chǎn)生的口令表是沒用的，因為單向函數(shù)不可能逆向恢復(fù)出口令。

2．

字典式攻擊和salt

用單向函數(shù)加密的口令文件還是很脆弱。MALLORY在業(yè)余時間編制了1000000個最常用的口令表，他用單向函數(shù)對所有1000000個口令進(jìn)行運算，并將結(jié)果存儲起來?，F(xiàn)在MALLORY偷出加密的口令文件，將它與自己的可能的口令文件進(jìn)行比較，再觀察哪個能匹配。這就是字典式攻擊。

Salt是使這種攻擊更困難的一種。Salt是一隨機(jī)字符串，它與口令連接在一起，再用單向函數(shù)對其運算，然后將salt值和單向函數(shù)運算的結(jié)果存入主機(jī)數(shù)據(jù)庫中。如果可能的salt值的數(shù)目足夠大的話，它實際上就消除了對常用口令采用的字典式攻擊。

3．

SKEYSKEY是一種鑒別程序，它依賴于單向函數(shù)的安全性。為了設(shè)置系統(tǒng)，Alice輸入隨機(jī)數(shù)R，計算機(jī)計算f(R)、f(f(R))、……等等大約100次，調(diào)用x1,x2,……x100這些數(shù)。計算機(jī)打印出這些信息的列表，Alice保管這些數(shù)，計算機(jī)亦順利地在數(shù)據(jù)庫中Alice的名字后面存儲x101的值。當(dāng)Alice第一次登錄時，她輸入她的名字和x100，計算機(jī)計算f(x100)，并把它和x101比較，如果它們匹配，那么證明Alice身份是真的。然后，計算機(jī)用x100代替數(shù)據(jù)庫中的x101，Alice將從她的列表中取消x100.Alice每次登錄時，都輸入她的列表中未取消的最后的數(shù)xi，計算機(jī)計算f(xi)，并和存儲在它的數(shù)據(jù)庫中的xi+1比較.因為每個數(shù)只被使用一次，并且這個函數(shù)是單向的，所以攻擊者不可能得到任何有用的信息。同樣的，數(shù)據(jù)庫對攻擊者亦毫無用處。當(dāng)然用完了列表中的數(shù)據(jù)后，必須重新初始化系統(tǒng)。2．2中級協(xié)議一、時間標(biāo)記服務(wù)在很多情況中，人們需要證明某個文件在某個時期存在。對于紙上的文件，公證人可以對文件簽名，律師可以保護(hù)副本。如果產(chǎn)生了爭端，公證人或律師可以證明某封信產(chǎn)生于某個時間。在數(shù)字世界中，事情要復(fù)雜得多。沒有辦法檢查竄改簽名的數(shù)字文件，他們可以無止境地復(fù)制和修改而無人發(fā)現(xiàn)。人們采用了數(shù)字時間標(biāo)志協(xié)議。協(xié)議有三條性質(zhì)：?數(shù)據(jù)本身必須有時間標(biāo)記，而不用考慮它所用的物理媒介。?改變文件的哪怕是1個位而文件卻沒有明顯變化是不可能的。?不可能用不同于當(dāng)前日期和時間的日期和時間來標(biāo)記文件。1．仲裁解決方法這個協(xié)議需要Trent和Alice，Trent提供可信的時間標(biāo)記服務(wù)，Alice希望對文件加上時間標(biāo)記：（1）

Alice將文件的副本傳送給Trent。（2）

Trent將他收到文件的日期和時間記錄下來，并妥善保存文件的副本?，F(xiàn)在，如果有人對Alice所聲明的文件產(chǎn)生的時間有懷疑，Alice只要打電話給Trent，Trent將提供文件的副本，并證明他在標(biāo)記的日期和時間接收到文件。這個協(xié)議是可行的，但有明顯的問題。第一、沒有保密性，Alice不得將文件的副本交給Trent。

第二、數(shù)據(jù)庫本身將是巨大的。并且發(fā)送大量的文件給Trent所要求的寬帶亦非常大。第三、存在潛在危險。傳送錯誤或Trent的中央計算機(jī)中某些地方的電磁炸彈引爆將使Alice聲明的時間標(biāo)記完全無效?？赡苡行﹫?zhí)行時間標(biāo)記業(yè)務(wù)的人并不象Trent那樣誠實。2．改進(jìn)的仲裁解決方法單向散列函數(shù)和數(shù)字簽名能夠輕而易舉地解決大部分問題：（1）Alice產(chǎn)生文件的單向散列值。（2）Alice將散列值傳送給Trent。（3）Trent將接收到的散列值的日期和時間附在散列值后，并對結(jié)果進(jìn)行數(shù)字簽名。（4）

Trent將簽名的散列和時間標(biāo)記送回給Alice.

這種方法解決了除最后一個問題的所有問題。

二、

閾下信道假設(shè)Alice和BOB被捕入獄。他將去男牢房，