1.密碼學概述主動攻擊與被動攻擊：對一個保密系統(tǒng)采取截獲密文進行分析的這類攻擊方法稱為被動攻擊(passiveattack)。非法入侵者主動干擾系統(tǒng)，采用刪除、更改、增添、重放等方法向系統(tǒng)加入假消息，則這種攻擊為主動攻擊(activeattack)。從攻擊效果看，敵手可能達到以下結(jié)果：（1）完全攻破。敵手找到了相應(yīng)的密鑰，從而可以恢復任意的密文。（2）部分攻破。敵手沒有找到相應(yīng)的密鑰，但對于給定的密文，敵手能夠獲得明文的特定信息。（3）密文識別。如對于兩個給定的不同明文及其中一個明文的密文，敵手能夠識別出該密文對應(yīng)于哪個明文，或者能夠識別出給定明文的密文和隨機字符串。

第二章經(jīng)典密碼學線性同余密碼將移位密碼和乘數(shù)密碼進行組合就可以得到更多的選擇方式，也叫仿射密碼(affinecipher)。若選取k1，k2兩個參數(shù)，其中(k1,26)＝1，即k1

和26互素，

令C＝k1

m＋k2mod26

k1＝1時便是Kaiser變換。例如k1＝7，k2＝10，則明文

pleasesendmoneys的對應(yīng)數(shù)據(jù)為

16125119519514413151452519

通過變換c＝7m＋10mod26可得

18161917131913194122311419313

對應(yīng)的密文為RPSQMSMSDLWKDSCM習題1、對于線性替代密碼，設(shè)已知明碼字母J(9)對應(yīng)于密文字母P(15)，即9kmod26=15,試計算密鑰k以破譯此密碼。答：k=9-1*15mod269-1mod26=3k=3*15mod26=19第四章序列密碼

序列密碼的加密和解密就是用一個隨機序列與明文序列疊加產(chǎn)生密文，用同一個隨機序列與密文序列疊加來恢復明文。

若設(shè)明文為m，密鑰為k，加密后的密文為c，則加密變換為：c＝m

k，解密變換：m＝c

k，其中m，k，c是0、1隨機序列，

表示模2加法運算。4.1序列密碼的基本概念圖4.1序列密碼的加密和解密4.2密鑰流與密鑰生成器一般地，序列密碼中對密鑰流有如下要求：（1）極大的周期。因為隨機序列是非周期的，而按任何算法產(chǎn)生的序列都是周期的，因此應(yīng)要求密鑰流具有盡可能大的周期。（2）良好的統(tǒng)計特性。隨機序列有均勻的游程分布。游程指序列中相同符號的連續(xù)段，其前后均為異種符號。如

……0111000010……中3個段分別為長為3的1游程、長為4的0游程、長為1的1游程。一般要求其在一周期內(nèi)滿足：同樣長度的0游程和1游程的個數(shù)相等，或近似相等。（3）不能用級數(shù)較小的線性移位寄存器近似代替，即要有很高的線性復雜度。（4）用統(tǒng)計方法由密鑰序列k0k1k2…ki…提取密鑰生成器結(jié)構(gòu)或種子密鑰的足夠信息在計算上是不可能的。

目前密鑰流生成器大都是基于移位寄存器的，這種基于移位寄存器的密鑰流序列稱為移位寄存器序列。4.3線性反饋移位寄存器序列

移位寄存器是序列密碼產(chǎn)生密鑰序列的一個主要組成部分。GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數(shù)f(a1a2...an)組成，如圖4.3所示。圖4.3GF(2)上的n級反饋移位寄存器

每一個存儲器稱為移位寄存器的一級。在任一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)。表4.1三級反饋移位寄存器的輸出狀態(tài)表圖4.4一個3級反饋移位寄存器

這個反饋移位寄存器的狀態(tài)對應(yīng)于一個GF(2)上的n維向量，共有2n種可能的狀態(tài)。每一時刻的狀態(tài)可用n長序列a1,a2,a3,…,an或n維行向量(a1,a2,a3,…,an)表示，其中ai是第i級存儲器的內(nèi)容。

每一級存儲器ai都將其內(nèi)容向下一級ai－1傳遞，并根據(jù)存儲器當前狀態(tài)計算f(a1,a2,a3,…,an)作為an下一時間的內(nèi)容。函f(a1,a2,a3,…,an)稱為反饋函數(shù)，其中f(a1,a2,a3,…,an)是n元布爾函數(shù)，即n個變元a1,a2,a3,…,an可以獨立地取0和1這兩個可能的值.最后的函數(shù)值也為0或1。表4.1三級反饋移位寄存器的輸出狀態(tài)表圖4.4一個3級反饋移位寄存器三級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)＝(1,0,1)，輸出可由表4.1求出，其輸出序列為10111011101…，周期為4。

如果移位寄存器的反饋函數(shù)f(a1,a2,…,an)是a1,a2,…,an的線性函數(shù)，則稱之為線性反饋移位寄存器（LFSR）。此時反饋函數(shù)f可寫為f(a1,a2,…,an)＝cna1

cn?1a2

…

c1an，其中常數(shù)ci＝0或1，

是模2加法。線性反饋移位寄存器（LFSR）f(a1,a2,…,a5)＝a1

a4圖4.6一個5級線性反饋移位寄存器n級線性反饋移位寄存器最多有2n個不同的狀態(tài)。若其初始狀態(tài)非0，則其后繼狀態(tài)不會為0。因此n級線性反饋移位寄存器的狀態(tài)周期≤2n-1。其輸出序列的周期與狀態(tài)周期相等，也≤2n-1

。只要選擇合適的反饋函數(shù)便可使序列的周期達到最大值2n-1，周期達到最大值的序列稱為m序列。

反饋函數(shù):b1+b3

設(shè)n級線性移位寄存器的輸出序列{ai}滿足遞推關(guān)系ak+n＝c1ak＋n－1

c2ak＋n－2

...

cnak，對任何k≥1成立。將這種遞推關(guān)系用一個一元高次多項式表示，稱這個多項式為線性移位寄存器的連接多項式。4.4線性移位寄存器的一元多項式表示反饋函數(shù):b1+b3反饋函數(shù):b1+b2+b3+b4試題設(shè)g(x)=x^4+x^2+1，g(x)為GF（2）上的多項式，以其為連接多項式組成線性移位寄存器。畫出邏輯框圖。設(shè)法遍歷其所有狀態(tài)，并寫出其狀態(tài)變遷及相應(yīng)的輸出序列。解答

通常采用的方法是，由線性移位寄存器(LFSR)和一個非線性組合函數(shù)即布爾函數(shù)組合，構(gòu)成一個密鑰流生成器，如圖4.2所示的密鑰流生成器。4.2密碼流生成器（a）由一個線性移位寄存器和一個濾波器構(gòu)成。（b）由多個線性移位寄存器和一個組合器構(gòu)成。通常將這類生成器分解成兩部分，其中線性移位寄存器部分稱為驅(qū)動部分，另一部分稱為非線性組合部分。

各自用途驅(qū)動部分：控制生成器的狀態(tài)序列，并為非線性組合部分提供統(tǒng)計性能良好的序列。如周期很大；分布較隨機非線性部分：將驅(qū)動部分所提供的序列組合成密碼特性好的序列?？呻[蔽驅(qū)動序列與密鑰k之間過分明顯的依賴關(guān)系第五章分組密碼5.2.1DES加密算法概述DES的加密過程可簡單描述為三個階段：5.2.5DES的安全性對DES安全性的主要爭論：

1、對DES的S盒、迭代次數(shù)、密鑰長度等設(shè)計準則的爭議

2、DES存在著一些弱密鑰和半弱密鑰

3、DES的56位密鑰無法抵抗窮舉工具三重DES加密加密：C=Ek1[Dk2[Ek1[P]]]解密：P=Dk1[Ek2[Dk1[C]]]三重DES加密

兩個密鑰的三重DES稱為加密-解密-加密方案，簡記為EDE(encrypt-decrypt-encrypt)。此方案已在ANSIX9.17和ISO8732標準中采用，并在保密增強郵遞(PEM)系統(tǒng)中得到利用。破譯它的窮舉密鑰搜索量為2112

5×1035量級，而用差分分析破譯也要超過1052量級。此方案仍有足夠的安全性。三個密鑰的三重DES已在因特網(wǎng)的許多應(yīng)用（如PGP和S/MIME）中被采用習題2023/9/2現(xiàn)代密碼學理論與實踐0544復習TheAESCipher2023/9/2現(xiàn)代密碼學理論與實踐0545/28第5章高級加密標準之要點AES是一種分組密碼，用以取代DES的商業(yè)應(yīng)用。其分組長度為128位，密鑰長度為128位、192位或256位AES沒有使用Feistel結(jié)構(gòu)。每輪由四個獨立的運算組成：字節(jié)代換、置換、有限域上的算術(shù)運算，以及與密鑰的異或運算2023/9/2現(xiàn)代密碼學理論與實踐0546/28AES密碼由比利時密碼學家VincentRijmen和JoanDaemen設(shè)計分組長度，密鑰長度可以是128/192/256位之一2023/9/2現(xiàn)代密碼學理論與實踐0547/282023/9/2現(xiàn)代密碼學理論與實踐0548/282023/9/2現(xiàn)代密碼學理論與實踐0549/28GF(28)上的域元素加法2023/9/2現(xiàn)代密碼學理論與實踐0550/28乘法在多項式表示中，有限域GF(28)上的乘法(記為?)定義為多項式的乘積模一個次數(shù)為8的不可約多項式：m(x)=x8+x4+x3+x+1用十六進制表示該多項式為{01}{1b}。例如，{57}?{83}={c1}，因為(x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=x13+x11+x9+x8+x6+x5+x4+x3+1而x13+x11+x9+x8+x6+x5+x4+x3+1modulo(x8+x4+x3+x+1)=x7+x6+12023/9/2現(xiàn)代密碼學理論與實踐0551/28擴展歐幾里德算法求逆元素{01}是乘法單位元。對任意次數(shù)小于8的非零二元多項式b(x)，其乘法逆元記為b-1(x)，可通過下述方法找到：使用擴展歐幾里德算法計算多項式a(x)和c(x)使得b(x)a(x)+m(x)c(x)=1m(x)=x8+x4+x3+x+1因此a(x)?b(x)modm(x)=1意味著b-1(x)=a(x)modm(x).由此可見，由所有256個可能的字節(jié)值組成的集合構(gòu)成有限域GF(28)，其每個元素(除了0)都可用擴展歐幾里德算法求逆。2023/9/2現(xiàn)代密碼學理論與實踐0552/282023/9/2現(xiàn)代密碼學理論與實踐0553/28逆字節(jié)代換2023/9/2現(xiàn)代密碼學理論與實踐0554/28逆S盒2023/9/2現(xiàn)代密碼學理論與實踐0555/28系數(shù)在GF(28)中的多項式考慮含有4個項、且系數(shù)為有限域元素的多項式，即注意本節(jié)中的多項式與有限域元素定義中使用的多項式操作起來是不同的，該節(jié)中的系數(shù)本身就是有限域元素，即字節(jié)(bytes)而不是比特(bits)2023/9/2現(xiàn)代密碼學理論與實踐0556/28c(x)=a(x)?b(x)2023/9/2現(xiàn)代密碼學理論與實踐0557/282023/9/2現(xiàn)代密碼學理論與實踐0558/282023/9/2現(xiàn)代密碼學理論與實踐0559/282023/9/2現(xiàn)代密碼學理論與實踐0560/282023/9/2現(xiàn)代密碼學理論與實踐0561/28安全性暴力攻擊單就金鑰長度來看，AES裡面最少128位元的金鑰絕對比DES的56位元金鑰要安全得多。

差異攻擊與線性攻擊AES系統(tǒng)目前仍然沒有任何已知的差異攻擊或者線性攻擊存在。2023/9/2現(xiàn)代密碼學理論與實踐0562/28國際數(shù)據(jù)加密算法IDEA密碼強度分組長度：64位密鑰長度：128位國際數(shù)據(jù)加密算法IDEAIDEA的基本操作是將兩個16位的值映射成一個16位的值逐位異或，⊕整數(shù)模216(65536)加?整數(shù)模216+1(65537)乘⊙IDEA的三種基本操作5.4IDEA思想該算法所依據(jù)的設(shè)計思想是“混合使用來自不同代數(shù)群中的運算”。該算法所需要的“混亂”可通過連續(xù)使用三個“不相容”的群運算于兩個16比特子塊來獲得，并且該算法所選擇使用的密碼結(jié)構(gòu)可提供必要的“擴散”。5.5SMS4密碼算法SMS4是用于WAPI（WLANAuthenticationandPrivacyInfrastructure）的分組密碼算法，是國內(nèi)官方公布的第一個商用密碼算法。SMS4算法是一個分組算法。SMS4算法的分組長度為128比特，密鑰長度為128比特。加密算法與密鑰擴展算法都采用32輪非線性迭代結(jié)構(gòu)。5.6分組密碼的工作模式分組密碼的工作模式就是以該分組密碼算法為基礎(chǔ)構(gòu)造的各種密碼系統(tǒng)。模式適用于所有的分組密碼，包括DES、AES和IDEA等。5.6分組密碼的工作模式5.6.1電子密碼本模式（ECB）5.6.2密碼分組鏈接模式（CBC）5.6.3密碼反饋模式（CFB）5.6.4輸出反饋模式（OFB）5.6.5記數(shù)模式（CTR）分組鏈接模式CipherBlockChaining(CBC)加密輸入是當前明文分組和前一密文分組的異或，形成一條鏈，使用相同的密鑰，這樣每個明文分組的加密函數(shù)輸入與明文分組之間不再有固定的關(guān)系5.6.2CBC模式的優(yōu)點如果明文分組中的一位出錯，將影響該分組的密文及其以后的所有密文分組。在一定程度上等防止數(shù)據(jù)篡改.但是如果密文序列中丟失1位，那么所有后續(xù)分組要移動1位，并且解密將全部錯誤。CBC模式的缺點加密的消息的長度只能是分組長度的倍數(shù)，不是任意長度的消息。 以des為例，必須等到每8個字節(jié)都接受到之后才能開始加密，否則就不能得到正確的結(jié)果。這在要求實時性比較高的時候就顯得不合適了。CFB模式的優(yōu)點和局限當數(shù)據(jù)以位或字節(jié)形式到達時使用都是適當?shù)脑诩用芙饷軆啥硕夹枰梅纸M加密器明文發(fā)生錯誤時，錯誤會傳播如果其中有一個字節(jié)的密文在傳輸?shù)臅r候發(fā)生錯誤（即使是其中的一位），那么它出現(xiàn)在移位寄存器期間解密的8個字節(jié)的數(shù)據(jù)都會得不到正確的解密結(jié)果，當然，這8個字節(jié)過去之后，依然可以得到正確的解密結(jié)果。該模式也是比較浪費的，因為在每輪加解密中都丟棄了大部分結(jié)果,j

通常為一字節(jié)（8

位）.輸出反饋模式（OFB）5.6.4輸出反饋模式（OFB）優(yōu)點是：錯誤傳播小，當前明文分組的錯誤不會影響后繼的密文分組；且密文中的1比特錯誤只導致明文中的1個錯誤；消息長度是任意的。OFB模式的缺點是：密文篡改難于檢測適合傳輸語音圖像計數(shù)器模式Counter(CRT)CTR的優(yōu)點預處理：

算法和加密盒的輸出不依靠明文和密文的輸入高效:可以做并行加密,允許同時處理多塊明文

/

密文第

i

塊密文的解密不依賴于第

i-1

塊密文，提供很高的隨機訪問能力

加密算法將僅僅是一系列異或運算，這將極大地提高吞吐量。

僅要求實現(xiàn)加密算法，但不要求實現(xiàn)解密算法。對于

AES

等加/解密本質(zhì)上不同的算法來說，這種簡化是巨大的第六章Hash函數(shù)第1類生日問題假設(shè)已經(jīng)知道A的生日為某一天，問至少有多少個人在一起時，至少有1/2的概率使有一個人和A的生日相同？在此，我們假定一年有365天，且所有人的生日均勻分布于365天中。如果已知一個Hash函數(shù)H有n個可能的輸出，其中H(x)是一個特定的輸出。隨機取k個輸入，則至少有一個輸入y使得H(y)＝H(x)的概率為0.5時，k有多大？第1類生日攻擊

假設(shè)一年有365天，每個人的生日均勻分布于365天那么至少有多少個人在一起是，能保證至少有1/2的概率存在2個人有相同的生日。第2類生日問題

若一文件m的Hash值H(m)為n比特，試問至少有多少的文件在一起，有兩個文件的Hash值以至少1/2的概率相同。第2類生日攻擊MD5的安全性MD5算法抗密碼分析的能力較弱，對MD5的生日攻擊所需代價是需要試驗264個消息。2004年8月17日，在美國加州圣巴巴拉召開的美密會（Crypto2004）上，中國的王小云、馮登國、來學嘉、于紅波4位學者宣布，只需1小時就可找出MD5的碰撞。（利用差分分析）圖6.6SHA-1消息處理框圖

SHA-1與MD5的比較安全性：SHA-1的報文摘要比MD5的長32比特抗密碼分析攻擊的強度，SHA-1似乎高于MD5效率：MD5效率比SHA-1高。MD5已被破解；SHA-1目前還可以應(yīng)用總的說來，SHA-1的安全性是以犧牲效率為代價的，類似于分組密碼的加密第七章消息認證碼MAC實質(zhì)上是一個雙方共享的密鑰k和消息m作為輸入的函數(shù)記為MAC=CK(M)MAC----”帶密鑰的hash函數(shù)”MAC:消息認證碼是什么一種是基于分組密碼的一種是基于帶密鑰的Hash函數(shù)的。7.1消息認證碼的構(gòu)造基于分組密碼的MACCBC-MAC（1）接收者確信消息未被更改過。（2）接收者確信消息來自所謂的發(fā)送者。消息認證碼實現(xiàn)認證公鑰密碼體制的基本概念公鑰密碼所依賴的數(shù)學難題背包問題二次剩余問題模n的平方根問題多變量方程系統(tǒng)格規(guī)約:NTRU大整數(shù)分解問題（TheIntegerFactorizationProblem,RSA體制）離散對數(shù)問題：有限域的乘法群上的離散對數(shù)問題（TheDiscreteLogarithmProblem,ELGamal體制）定義在有限域的橢圓曲線上的離散對數(shù)問題（TheEllipticCurveDiscreteLogarithmProblem，類比的ELGamal體制）RSA算法概況：MIT三位年青數(shù)學家R.L.Rivest，A.Shamir和L.Adleman在1978年發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰體制的方法，稱作MIT體制，后來被廣泛稱之為RSA體制。它既可用于加密、又可用于數(shù)字簽名。RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性。2、RSA算法算法描述－密鑰產(chǎn)生KG()：獨立地選取兩大素數(shù)p和q(各100～200位十進制數(shù)字)計算n=p×q，其歐拉函數(shù)值

(n)=(p－1)(q－1)隨機選一整數(shù)e，1

e<

(n)，gcd(

(n),e)=1在模

(n)下，計算e的有逆元d=e-1mod

(n)以n，e為公鑰。私鑰為d。(p,q不再需要，可以銷毀。)

算法描述－加密E()和解密D()：加密將明文分組，各組對應(yīng)的十進制數(shù)小于nc=memodn解密

m=cd

modn3、RSA的安全性RSA的安全性是基于分解大整數(shù)的困難性假定（尚未證明分解大整數(shù)是NP問題）如果分解n=p×q，則立即獲得

(n)=(p－1)(q－1)，從而能夠確定e的模

(n)乘法逆dRSA-129歷時8個月被于1996年4月被成功分解，RSA-130于1996年4月被成功分解n的長度應(yīng)該介于1024bit到2048bit之間1、大素數(shù)的產(chǎn)生試除法費馬法Rabin-Miller算法未通過檢測的整數(shù)一定是合數(shù)但，并非所有通過檢測的整數(shù)都是素數(shù)實用最廣泛，是一種概率算法2、求乘法逆元：擴展的歐幾里得算法RSA的實現(xiàn)3、快速指數(shù)計算利用反復平方乘算法每次乘法運算后就取模3、橢圓曲線密碼體制的優(yōu)點安全性高（橢圓曲線群上的離散對數(shù)更難計算）攻擊有限域上的離散對數(shù)可用指數(shù)積分法，運算復雜度為亞指數(shù)復雜。對ECC上離散對數(shù)攻擊并不有效。攻擊ECC上離散對數(shù)問題的方法只有大步小步法，復雜度為指數(shù)。因此ECC上的密碼體制比基于有限域上離散對數(shù)問題的公鑰體制更安全數(shù)字簽名ElGamal數(shù)字簽名公鑰數(shù)學基礎(chǔ)Euler定