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

第2章密碼學(xué)基礎(chǔ)第2章密碼學(xué)基礎(chǔ)密碼學(xué)真的有必要嗎密碼學(xué)對稱密碼學(xué)非對稱密碼學(xué)哈希函數(shù)數(shù)字簽名數(shù)字證書安全傳送文件的含義：確保文件來自正確的發(fā)送方接收方能確保在通過Internet傳輸時，文件沒有被修改；只有指定的接收方能夠看到文件，其他各方無法看到，防止文件被竊；事后發(fā)送方不能否認(rèn)曾經(jīng)發(fā)送過文件。

密的化碼藝時學(xué)術(shù)代前5世紀(jì)：明文木棍密文(換位密碼)

人類有記載的通信密碼始于公元前400年。古希臘人是置換密碼的發(fā)明者。前1世紀(jì)：明文字母后移3位密文(替代密碼)密碼學(xué)的發(fā)展史密碼學(xué)的發(fā)展密碼學(xué)是實(shí)現(xiàn)認(rèn)證、加密、訪問控制的核心技術(shù)密碼學(xué)的發(fā)展

9世紀(jì)、16世紀(jì)：比較現(xiàn)實(shí)字母頻度與密文字母頻率(頻度分析法)

1918年,一次性便箋密碼

1881年世界上的第一個電話保密專利出現(xiàn)。電報、無線電的發(fā)明使密碼學(xué)成為通信領(lǐng)域中不可回避的研究課題。

密碼學(xué)的發(fā)展二戰(zhàn)：恩格瑪密碼機(jī)(第一次用電腦協(xié)助破密)

在第二次世界大戰(zhàn)初期，德國軍方啟用“恩尼格瑪”密碼機(jī)，盟軍對德軍加密的信息有好幾年一籌莫展，“恩尼格瑪”密碼機(jī)似乎是不可破的。但是經(jīng)過盟軍密碼分析學(xué)家的不懈努力，“恩尼格瑪”密碼機(jī)被攻破，盟軍掌握了德軍的許多機(jī)密，而德國軍方卻對此一無所知。太平洋戰(zhàn)爭中，美軍破譯了日本海軍的密碼機(jī)，讀懂了日本艦隊司令官山本五十六發(fā)給各指揮官的命令，在中途島徹底擊潰了日本海軍，導(dǎo)致了太平洋戰(zhàn)爭的決定性轉(zhuǎn)折，而且不久還擊斃了山本五十六。相反軸心國中，只有德國是在第二次世界大戰(zhàn)的初期在密碼破譯方面取得過輝煌的戰(zhàn)績。因此，我們可以說，密碼學(xué)在戰(zhàn)爭中起著非常重要的作用。

密碼學(xué)的發(fā)展1977年，DES成為美國國家標(biāo)準(zhǔn)

1977年，美國國家標(biāo)準(zhǔn)局公布實(shí)施了“美國數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）”，軍事部門壟斷密碼的局面被打破，民間力量開始全面介入密碼學(xué)的研究和應(yīng)用中。民用的加密產(chǎn)品在市場上已有大量出售，采用的加密算法有DES、IDEA、RSA等。1976年,公開密鑰思想(密鑰分開)1977年,RSA(公鑰密碼)1985年,量子計算機(jī)(解密)密碼學(xué)的發(fā)展三個階段:1949年以前:數(shù)據(jù)的安全基于算法保密1949~1975:數(shù)據(jù)的安全基于密鑰的保密1976以后:安全的無密鑰傳輸(公鑰密碼學(xué))2.1.1密碼學(xué)的基本概念密碼學(xué)的分類：密碼編碼學(xué)（Cryptography）密碼分析學(xué)（Cryptanalysis）密碼編碼學(xué)(Cryptography)，對信息進(jìn)行編碼實(shí)現(xiàn)隱蔽信息的一門學(xué)問密碼分析學(xué)(Cryptanalytics)，研究分析破譯密碼的學(xué)問編碼密碼學(xué)主要致力于信息加密、信息認(rèn)證、數(shù)字簽名和密鑰管理方面的研究。分析密碼學(xué)主要分析密碼算法的弱點(diǎn)，對其進(jìn)行拷問和攻擊以求攻破該密碼算法。密碼學(xué)是計算機(jī)科學(xué)中唯一一門有著兩個平行、對立而又共生的子分支的分支科學(xué)概念明文(消息)(Plaintext)：被隱蔽消息。密文(Ciphertext)或密報(Cryptogram)：明文經(jīng)密碼變換成的一種隱蔽形式。加密(Encryption)：將明文變換為密文的過程。解密(Decryption)：加密的逆過程，即由密文恢復(fù)出原明文的過程。加密員或密碼員(Cryptographer)：對明文進(jìn)行加密操作的人員。密碼體制五元組:P(M),C,K,E,DDk(Ek(M))=M

加密算法(Encryptionalgorithm)：密碼員對明文進(jìn)行加密時所采用的一組規(guī)則。接收者(Receiver)：傳送消息的預(yù)定對象。解密算法：接收者對密文進(jìn)行解密時所采用的一組規(guī)則。密鑰(Key)：控制加密和解密算法操作的數(shù)據(jù)處理，分別稱作加密密鑰和解密密鑰。截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非授權(quán)者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機(jī)密信息。概念信源Mm加密器解密器接收者m非法接入者搭線信道（主動攻擊）C’搭線信道（被動攻擊）密碼分析員m‘密鑰源K1k1密鑰源K2k2密鑰信道保密系統(tǒng)模型概念

保密系統(tǒng)應(yīng)當(dāng)滿足的要求系統(tǒng)即使達(dá)不到理論上是不可破的，即pr{m’=m}=0，也應(yīng)當(dāng)為實(shí)際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計算上是不可行的。系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。加密和解密算法適用于所有密鑰空間中的元素。系統(tǒng)便于實(shí)現(xiàn)和使用。密碼體制分類密碼體制有2大類：單鑰體制(One-keysystem)：

加密密鑰和解密密鑰相同雙鑰體制(Twokeysystem)：

加密密鑰和解密密鑰不同密碼體制分類單鑰體制加密器EK解密器DK密文明文明文K密鑰產(chǎn)生器K單鑰體制或私鑰體制(privatekeysystem)

每個用戶事先約定共同選定的密鑰k，數(shù)據(jù)的加密和解密使用相同的密鑰。密碼體制分類單鑰體制單鑰體制主要研究問題：密鑰產(chǎn)生(Keygeneration)，密鑰管理(Keymanagement)。分類：流密碼(Streamcipher)分組密碼(Blockcipher)單鑰體制不僅可用于數(shù)據(jù)加密，也可用于消息的認(rèn)證。密碼體制分類雙鑰體制雙鑰體制或公鑰體制(Publickeysystem)

每個用戶都有一對選定的密鑰(公鑰k1；私鑰k2)，公開的密鑰k1可以像電話號碼一樣進(jìn)行注冊公布。加密器EK解密器DK密文明文明文K1密鑰產(chǎn)生器K2密鑰產(chǎn)生器公鑰體制的主要特點(diǎn)加密和解密能分開可以實(shí)現(xiàn)多個用戶加密的消息只能由一個用戶解讀（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）只能由一個用戶加密消息而使多個用戶可以解讀（可用于認(rèn)證系統(tǒng)中對消息進(jìn)行數(shù)字簽字）。無需事先分配密鑰。2.1.2傳統(tǒng)加密技術(shù)1置換密碼依據(jù)一定的規(guī)則，明文字母被相應(yīng)替代移位密碼（模運(yùn)算）加密：Ek(x)=(x+k)mod26

解密：Dk(y)=(y-k)mod26x:明文字母、y:密文字母、k:密鑰愷撒密碼就是移位密碼（k＝3）

缺點(diǎn)：密鑰空間小，容易被破解（窮舉法）2.1.2傳統(tǒng)加密技術(shù)單表代換密碼用一個表將一個明文字母對應(yīng)一個密文字母，加解密則按照此表相應(yīng)轉(zhuǎn)換字母。

缺點(diǎn)：對應(yīng)關(guān)系固定，容易被頻度分析法破解多表代換密碼（vigenere密碼）密鑰K不單一，同一密文字母可能對應(yīng)不同明文字母加密變換：ci≡(mi+ki)mod26

解密變換：mi≡(ci-ki)mod26

密鑰空間較前兩種大，較安全2.1.2傳統(tǒng)加密技術(shù)2代換密碼保持明文不變，將字母順序重新排列

倒序密碼：顛倒明文書寫順序。abamimiaowamimiaow

柵欄密碼：明文交替書寫排列。

密的化碼藝時學(xué)術(shù)代

行列轉(zhuǎn)置：明文行列轉(zhuǎn)置書寫。仍不能抵御統(tǒng)計分析類的攻擊方法（頻度分析）密碼分析概念

密碼設(shè)計和密碼分析是共生的、又是互逆的，兩者密切有關(guān)但追求的目標(biāo)相反。兩者解決問題的途徑有很大差別

密碼設(shè)計是利用數(shù)學(xué)來構(gòu)造密碼密碼分析除了依靠數(shù)學(xué)、工程背景、語言學(xué)等知識外，還要靠經(jīng)驗(yàn)、統(tǒng)計、測試、眼力、直覺判斷能力……，有時還靠點(diǎn)運(yùn)氣。密碼分析方法--窮舉破譯法

對截收的密報依次用各種可解的密鑰試譯，直到得到有意義的明文；或在不變密鑰下，對所有可能的明文加密直到得到與截獲密報一致為止，此法又稱為完全試湊法(Completetrial-and-errorMethod)。只要有足夠多的計算時間和存儲容量，原則上窮舉法總是可以成功的。但實(shí)際中，任何一種能保障安全要求的實(shí)用密碼都會設(shè)計得使這一方法在實(shí)際上是不可行的密碼分析方法—分析法

確定性分析法利用一個或幾個已知量(比如，已知密文或明文-密文對)用數(shù)學(xué)關(guān)系式表示出所求未知量(如密鑰等)。已知量和未知量的關(guān)系視加密和解密算法而定，尋求這種關(guān)系是確定性分析法的關(guān)鍵步驟。

統(tǒng)計分析法利用明文的已知統(tǒng)計規(guī)律進(jìn)行破譯的方法。密碼破譯者對截收的密文進(jìn)行統(tǒng)計分析，總結(jié)出其間的統(tǒng)計規(guī)律，并與明文的統(tǒng)計規(guī)律進(jìn)行對照比較，從中提取出明文和密文之間的對應(yīng)或變換信息。密碼可能經(jīng)受的攻擊攻擊類型攻擊者擁有的資源惟密文攻擊加密算法截獲的部分密文已知明文攻擊加密算法截獲的部分密文和相應(yīng)的明文選擇明文攻擊加密算法加密黑盒子，可加密任意明文得到相應(yīng)的密文選擇密文攻擊加密算法解密黑盒子，可解密任意密文得到相應(yīng)的明文無條件安全和計算安全

無條件安全

如果算法產(chǎn)生的密文不能給出唯一決定相應(yīng)明文的足夠信息，無論截獲多少密文，花費(fèi)所少時間都不能解密密文。

Shannon指出，僅當(dāng)密鑰至少和明文一樣長時達(dá)到無條件安全（即一次一密）

計算安全

破譯密文的代價超過被加密信息的價值破譯密文所花時間超過信息的有效期2.2對稱密碼技術(shù)2.2.1基本概念密碼算法的分類：對稱密碼算法和非對稱密碼算法對稱密碼算法：接受明文作為輸入，然后使用一個對稱密鑰進(jìn)行運(yùn)算，輸出明文的一個加密版本（密文）。對稱密鑰算法注意事項(xiàng)：采用一個好的隨機(jī)數(shù)發(fā)生器來創(chuàng)建對稱密鑰隨機(jī)數(shù)的來源是專門設(shè)計的產(chǎn)生真正隨機(jī)數(shù)的硬件數(shù)據(jù)加密標(biāo)準(zhǔn)DES（DataEncryptionStandard，DES）是目前廣泛使用的分組密碼典型代表。主要用于電子銀行的資金轉(zhuǎn)帳（EFT）組成部分：加密處理、加密變換、子密鑰生成。優(yōu)點(diǎn)：容易標(biāo)準(zhǔn)化、通用化。算法運(yùn)算速度快，易于產(chǎn)生密鑰。缺點(diǎn)：不是非常安全，容易被暴力破解。2.2.2DES加密標(biāo)準(zhǔn)對稱加密流程對稱密碼學(xué)的特點(diǎn)對稱密碼學(xué)中，同一個密鑰既可以用于加密也可用于解密。對稱加密速度快對稱加密是安全的對稱加密得到的密文是緊湊的對稱加密容易受到中途攔截竊聽的攻擊密鑰個數(shù)以使用者數(shù)目的平方速度增長，難以擴(kuò)大使用范圍對稱密碼系統(tǒng)需要復(fù)雜的密鑰管理對稱密碼技術(shù)不適用于數(shù)字簽名和不可否認(rèn)性美國制定數(shù)據(jù)加密標(biāo)準(zhǔn)簡況DES發(fā)展史確定了發(fā)展公用標(biāo)準(zhǔn)算法模式，而EES的制定路線與DES的背道而馳。人們懷疑有陷門和政府部門肆意侵犯公民權(quán)利。此舉遭到廣為反對。1995年5月AT&TBellLab的M.Blaze博士在PC機(jī)上用45分鐘時間使SKIPJACK的LEAF協(xié)議失敗，偽造ID碼獲得成功。1995年7月美國政府宣布放棄用EES來加密數(shù)據(jù)，只將它用于語音通信。1997年1月美國NIST著手進(jìn)行AES（AdvancedEncryptionStandard）的研究，成立了標(biāo)準(zhǔn)工作室。2001年Rijndael被批準(zhǔn)為AES標(biāo)準(zhǔn)。DES算法DES算法框圖輸入64bit明文數(shù)據(jù)初始置換IP乘積變換（16輪迭代）逆初始置換IP-164bit密文數(shù)據(jù)輸出

標(biāo)準(zhǔn)數(shù)據(jù)加密算法DES算法初始置換將64bit明文的位置進(jìn)行置換，得到一個亂序的64bit明文組，而后分成左右兩段，每段為32bit，以L0和R0表示，IP中各列元素位置號數(shù)相差為8，相當(dāng)于將原明文各字節(jié)按列寫出，各列比特經(jīng)過偶采樣和奇采樣置換后，再對各行進(jìn)行逆序。將陣中元素按行讀出構(gòu)成置換輸出。DES算法58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157逆初始置換將16輪迭代后給出的64bit組進(jìn)行置換，得到輸出的密文組。輸出為陣中元素按行讀得的結(jié)果。IP和IP-1在密碼意義上作用不大，它們的作用在于打亂原來輸入的順序關(guān)系。40848165624643239747155523633138646145422623037545135324612936444125217602835343115119592734242105021582633141949235725DES算法乘積變換一輪加解密處理示意圖DES算法乘積變換它是DES算法的核心部分。將經(jīng)過IP置換后的數(shù)據(jù)分成32bit的左右兩組，在迭代過程中彼此左右交換位置。每次迭代時只對右邊的32bit進(jìn)行一系列的加密變換，在此輪迭代即將結(jié)束時，把左邊的32bit與右邊得到的32bit逐位模2相加，作為下一輪迭代時右邊的段，并將原來右邊未經(jīng)變換的段直接送到左邊的寄存器中作為下一輪迭代時左邊的段。在每一輪迭代時，右邊的段要經(jīng)過擴(kuò)展置換E、密鑰加密運(yùn)算、S盒代換、直接置換P和左右混合運(yùn)算。DES算法乘積變換

擴(kuò)展置換E。將輸入的32bitRi-1擴(kuò)展成48bit的輸出，令s表示E原輸入數(shù)據(jù)比特的原下標(biāo)，則E的輸出是將原下標(biāo)s0或1(mod4)的各比特重復(fù)一次得到的，即對原第32,1,4,5,8,9,12,13,16,17,20,21,24,25,28,29各位都重復(fù)一次,實(shí)現(xiàn)數(shù)據(jù)擴(kuò)展。將表中數(shù)據(jù)按行讀出得到48bit輸出。

密鑰加密運(yùn)算。將子密鑰產(chǎn)生器輸出的48bit子密鑰ki與選擇擴(kuò)展運(yùn)算E輸出的48bits數(shù)據(jù)按位模2相加。S盒代換。將前面送來的48bit數(shù)據(jù)自左至右分成8組，每組為6bit。而后并行送入8個S一盒，每個S盒為一非線性代換網(wǎng)絡(luò)，有4個輸出，運(yùn)算S的框圖在圖4-4-6中給出。DES算法擴(kuò)展置換E3212345456789891011121312131415161716171819202120212223242524252627282928293031321直接置換P672021291228171152326518311028241432273919133062211425DES算法Li-1(32bit)

Ri-1(32bit)

擴(kuò)展置換E48bit寄存器按bit模2加密48bit寄存器

S盒代換32bit寄存器直接置換P按bit模2和Li(32bit)Ri(32bit)F函數(shù)變換框圖密鑰產(chǎn)生器S盒代換

6bit8個S盒4bit

48bit寄存器32bit寄存器S1S2S3S4S5S6S7S8DES算法

列行0123456789101112131415014413121511831061259071015741421311061211953824114813621115129731050315128249175113141006130151814611349721312051013134715281412011069115201471110413158126932153138101315421167120514901009146315511312711428113709346102851412111512136498153011121251014731101306987415143115212S盒定義DES算法乘積變換

直接置換P。對S1至S8盒輸出的32bit數(shù)據(jù)進(jìn)行坐標(biāo)置換，置換P輸出的32bit數(shù)據(jù)與左邊32bit即Ri-1逐位模2相加，所得到的32bit作為下一輪迭代用的右邊的數(shù)字段。并將Ri-1并行送到左邊的寄存器，作為下一輪迭代用的左邊的數(shù)字段。

子密鑰產(chǎn)生器。將64bit初始密鑰經(jīng)過置換選擇PC1、循環(huán)移位置換、置換選擇PC2給出每次迭代加密用的子密鑰ki，DES算法

子密鑰產(chǎn)生器框圖

密鑰（64bit）置換選擇1，PC1置換選擇2，PC2

Ci(28bit)

Di(28bit)

循環(huán)左移ti+1bit

循環(huán)左移ti+1bit除去第8,16,,64位(8個校驗(yàn)位)ki2.3.4.2DES算法DES加密的一個例子

取16進(jìn)制明文X：0123456789ABCDEF

密鑰K為：133457799BBCDFF1

去掉奇偶校驗(yàn)位以二進(jìn)制形式表示的密鑰是00010010011010010101101111001001101101111011011111111000

應(yīng)用IP，我們得到：

L0=11001100000000001100110011111111

L1=R0=11110000101010101111000010101010

然后進(jìn)行16輪加密。

最后對L16,R16使用IP-1得到密文：85E813540F0AB405DES算法DES的安全問題S盒設(shè)計

DES靠S盒實(shí)現(xiàn)非線性變換。①由于S盒的設(shè)計細(xì)節(jié)沒有公開，因此DES剛剛提出時，曾被人們懷疑有陷門（Trapdoors），而使美國美國國家安全局能輕易的解密消息，但到目前為止并沒有任何證據(jù)可以證明這一點(diǎn)。

②在DES加密算法的所有部件中，S盒是唯一的具有差分?jǐn)U散功能的部件（相對于逐比特異或），而其它部件除了群加密（逐比特異或）以外，都是簡單的位置交換、添加或刪減，毫無差分?jǐn)U散能力。

③在DES加密算法的所以部件中，S盒是唯一的非線性部件。

DES算法密鑰搜索機(jī)

對DES安全性批評意見中，較為一致的看法是DES的密鑰短了些。IBM最初向NBS提交的建議方案采用112bits密鑰，但公布的DES標(biāo)準(zhǔn)采用64bits密鑰。有人認(rèn)為NSA故意限制DES的密鑰長度。采用窮搜索對已經(jīng)對DES構(gòu)成了威脅．

DES的密鑰只有56比特，總密鑰量為256個，不能抵抗窮舉搜索攻擊。例如1997年，美國科羅拉多州的程序員Verser用了96天的時間，在Internet上數(shù)萬名志愿者的幫助下，成功的找到的DES的密鑰，并獲得了RSA公司發(fā)的10000美金的獎勵。更為嚴(yán)重的是專用密碼搜索機(jī)的設(shè)計。據(jù)新華社1998年7月22日消息，電子邊境基金協(xié)會（EFF）使用一臺25萬美金的計算機(jī)在56個小時內(nèi)攻破了DES。DES的安全問題二重DES

用DES進(jìn)行兩次加密，但這是否就意味著兩重DES加密的強(qiáng)度等價于112bit密鑰的密碼的強(qiáng)度？答案是否定的。

中途相遇攻擊法(Meet-in-the-MiddleAttack)

由Diffie和Hellman[1977]最早提出，可以降低搜索量其基本想法如下。若有明文密文對(xi,yi)滿足

yi=Ek2[Ek1[xi]]則可得z=Ek1[xi]=Dk2[yi]

2.3.4.2DES算法二重DES圖4-14-1中途相遇攻擊示意圖zEEDDxiyixizyi

k1

k1k2k22.3.4.2DES算法中途相遇攻擊給定一已知明密文對(x1,y1)，可按下述方法攻擊。以密鑰k1的所有256個可能的取值對此明文x1加密，并將密文z存儲在一個表中；從所有可能的256個密鑰k2中依任意次序選出一個對給定的密文y1解密，并將每次解密結(jié)果z在上述表中查找相匹配的值。一旦找到，則可確定出兩個密鑰k1和k2；以此對密鑰k1和k2對另一已知明文密文對(x2,y2)中的明文x2進(jìn)行加密，如果能得出相應(yīng)的密文y2就可確定k1和k2是所要找的密鑰。2.3.4.2DES算法中途相遇攻擊對于給定明文x，以兩重DES加密將有264個可能的密文?？赡艿拿荑€數(shù)為2112個。所以，在給定明文下，將有2112/264=248個密鑰能產(chǎn)生給定的密文。用另一對64bits明文密文對進(jìn)行檢驗(yàn)，就使虛報率降為248-64=2-16。這一攻擊法所需的存儲量為256×8Byte，最大試驗(yàn)的加密次數(shù)2×256=257。這說明破譯雙重DES的難度為257量級。2.3.4.2DES算法三重DES加密加密：y=Ek1[Dk2[Ek1[x]]]解密：x=Dk1[Ek2[Dk1[y]]]稱其為加密-解密-加密方案，簡記為EDE(encrypt-decrypt-encrypt)。此方案已在ANSIX9.17和ISO8732標(biāo)準(zhǔn)中采用，并在保密增強(qiáng)郵遞(PEM)系統(tǒng)中得到利用。破譯它的窮舉密鑰搜索量為21125×1035量級，而用差分分析破譯也要超過1052量級。此方案仍有足夠的安全性。2.3.4.2DES算法2.2.3AES加密標(biāo)準(zhǔn)AES(AdvancedEncryptionStandard)

出現(xiàn)的原因：3DES的執(zhí)行時間是DES的3倍S盒的人為制定美國國家標(biāo)準(zhǔn)技術(shù)局（NIST）公布了AES要求：AES為對稱密鑰加密算法AES為分組加密算法，分組長度最少為128位AES密鑰長度是變動的，為128、192、256位可選可同時由硬件或軟件實(shí)現(xiàn)無專利限制，可自由使用2.2.3AES加密標(biāo)準(zhǔn)2000年10月2日NIST正式宣布比利時兩位密碼專家所設(shè)計的Rijndael稱為AES算法。AES算法基于代換和置換運(yùn)算AES算法最小密鑰長度是128位，即使每秒能實(shí)現(xiàn)256個密鑰的搜索，也需要149萬億年，窮舉對其無效。AES也可有效抵抗差分密碼分析和線性密碼分析。對稱加密算法分類對稱密碼學(xué)分類：流密碼（序列密碼）和分組密碼（塊密碼）。分組密碼工作方法：將明文分成固定長度的（塊），用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。核心技術(shù)：在相信復(fù)雜函數(shù)可以通過簡單函數(shù)迭代若干圈得到的原則下，利用簡單圈函數(shù)及對數(shù)運(yùn)算，充分利用非線性運(yùn)算。

明文序列x1,x2,…,xi,…加密函數(shù)E:EKYn解密函數(shù)D：DKXn解密算法加密算法密鑰k密鑰k明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)分組密碼分組密碼算法應(yīng)滿足的要求分組長度n要足夠大防止明文窮舉攻擊法奏效。密鑰量要足夠大盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。由密鑰確定置換的算法要足夠復(fù)雜充分實(shí)現(xiàn)明文與密鑰的擴(kuò)散和混淆，沒有簡單的關(guān)系可循，要能抗擊各種已知的攻擊。

分組密碼加密和解密運(yùn)算簡單易于軟件和硬件高速實(shí)現(xiàn)。數(shù)據(jù)擴(kuò)展一般無數(shù)據(jù)擴(kuò)展，在采用同態(tài)置換和隨機(jī)化加密技術(shù)時可引入數(shù)據(jù)擴(kuò)展。差錯傳播盡可能的小分組密碼算法應(yīng)滿足的要求分組密碼流密碼（序列密碼）序列密碼也稱為流密碼（StreamCipher），它是對稱密碼算法的一種。序列密碼具有實(shí)現(xiàn)簡單、便于硬件實(shí)施、加解密處理速度快、沒有或只有有限的錯誤傳播等特點(diǎn)流密碼是將明文劃分成字符（單個字母），或其編碼的基本單位（如0,1數(shù)字），字符分別與密鑰流作用進(jìn)行加密，解密時以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)流密碼強(qiáng)度完全依賴于密鑰序列的隨機(jī)性和不可預(yù)測性。

明文序列：x1,x2,…,xi,…密鑰流：K1，K2…,Ki…加密函數(shù)E:EKnCn解密函數(shù)D：DKnXn解密算法加密算法密鑰k=(k0,k1,…,kt-1)密鑰k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)流密碼（序列密碼）序列密碼與分組密碼的對比

分組密碼已一定大小作為每次處理的基本單元，而序列密碼則是以一個元素（一個字母或一個比特）作為基本的處理單元。序列密碼是一個隨時間變化的加密變換，具有轉(zhuǎn)換速度快、低錯誤傳播的優(yōu)點(diǎn)，硬件實(shí)現(xiàn)電路更簡單；其缺點(diǎn)是：低擴(kuò)散（意味著混亂不夠）、插入及修改的不敏感性。分組密碼使用的是一個不隨時間變化的固定變換，具有擴(kuò)散性好、插入敏感等優(yōu)點(diǎn)；其缺點(diǎn)是：加解密處理速度慢、存在錯誤傳播。流密碼（序列密碼）分類：同步流密碼和自同步流密碼核心問題是：密鑰流生成器的設(shè)計保持收發(fā)兩端密鑰流的精準(zhǔn)同步是實(shí)現(xiàn)可靠解密的關(guān)鍵流密碼是將明文劃分成字符（單個字母），或其編碼的基本單位（如0,1數(shù)字），字符分別與密鑰流作用進(jìn)行加密，解密時以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)流密碼強(qiáng)度完全依賴于密鑰序列的隨機(jī)性和不可預(yù)測性。流密碼（序列密碼）自同步流密碼：密鑰流的每一位是前面固定數(shù)量密文位的函數(shù)，即密鑰流的產(chǎn)生和前面已經(jīng)產(chǎn)生的若干個密文字有關(guān)。自同步特點(diǎn)：當(dāng)密文被修改時即密碼在同步性遭到破壞時，可自動重建正確的解密。有限的錯誤傳播：密文字符只與其相依賴的密文字符相關(guān)，其后的不受影響。主動攻擊：對檢測主動攻擊時，較困難。明文統(tǒng)計擴(kuò)散：每個明文字符會影響其后的整個密文。同步流密碼：密鑰流是獨(dú)立生成的，和前面已經(jīng)產(chǎn)生的若干個密文字無關(guān)。同步特點(diǎn)：消息的發(fā)送者和接收者必須同步才能做到正確的加密和解密，即雙方用相同密鑰，并對同一位置操作。無錯誤傳播：密文字符即使被修改也不影響其他密文字符的解密。主動攻擊：對主動攻擊的防御性不強(qiáng)。流密碼（序列密碼）一次一密密碼本一次一密（onetimepadding）指在流密碼當(dāng)中使用與消息長度等長的隨機(jī)密鑰,密鑰本身只使用一次。優(yōu)點(diǎn):由于使用與消息等長的隨機(jī)密鑰,產(chǎn)生與原文沒有任何統(tǒng)計關(guān)系的隨機(jī)輸出,因此一次一密方案不可破解。缺點(diǎn):因密鑰與明文要求具有相同長度，密鑰在傳遞和分發(fā)上存在很大困難。

流密碼（序列密碼）RC4算法RC4算法是一種在電子信息領(lǐng)域加密的技術(shù)手段，用于無線通信網(wǎng)絡(luò)，是一種電子密碼，只有經(jīng)過授權(quán)（繳納相應(yīng)費(fèi)用）的用戶才能享受該服務(wù)。RC4算法加密是采用的xor，一旦子密鑰序列出現(xiàn)了重復(fù)，密文就有可能被破解。2001年就有以色列科學(xué)家指出RC4加密算法存在著漏洞，這可能對無線通信網(wǎng)絡(luò)的安全構(gòu)成威脅。流密碼（序列密碼）非對稱密碼技術(shù)2.3非對稱密碼技術(shù)20世紀(jì)70年代Diffie和Hellman最早引入非對稱密碼學(xué)的概念。成功的非對稱密碼學(xué)算法：RSA橢圓曲線密碼算法公鑰加密算法也稱為非對稱密鑰算法，用一對密鑰：一個公鑰和一個私鑰。用戶需要保障私鑰的安全；公鑰可以公布出去。用公鑰加密的信息只能用私鑰解密，反之亦然。主要特點(diǎn)：加密和解密能力分開多個用戶加密的消息只能由一個用戶解讀，（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）只能由一個用戶加密消息而使多個用戶可以解讀（可用于認(rèn)證系統(tǒng)中對消息進(jìn)行數(shù)字簽字）。無需事先分配密鑰。非對稱密碼技術(shù)非對稱密碼加解密流程密文明文非對稱密碼技術(shù)加解密步驟：Bob產(chǎn)生一對密鑰，分別為公鑰B和私鑰B’。Bob將公鑰予以公開，私鑰自己保管。Alice要向Bob發(fā)消息，加密所用密鑰為Bob公開的公鑰B，表示為：C=EB(M)Bob收到密文后，用自己的私鑰B’解密，表示為:M=DB’(C)非對稱密碼技術(shù)公鑰密碼應(yīng)滿足的要求接收方B產(chǎn)生密鑰對在計算上是容易的發(fā)送方A用收方的公開鑰對消息m加密以產(chǎn)生密文c在計算上是容易的。收方B用自己的秘密鑰對密文c解密在計算上是容易的。敵手由密文c和B的公開密鑰恢復(fù)明文在計算上是不可行的。敵手由密文c和B的公開密鑰恢復(fù)秘密密鑰在計算上是不可行的加解密次序可換，即EPKB[DSKB(m)]=DSKB[EPKB(m)],不是對任何算法都做此要求。非對稱密碼技術(shù)2.4.3非對稱密碼學(xué)的特點(diǎn)使用非對稱密碼技術(shù)時，用一個密鑰（公鑰或私鑰）加密的信息只能用另外一個密鑰（私鑰或公鑰）來解密。非對稱加密是安全的非對稱加密不必?fù)?dān)心密鑰被中途攔截的問題需要分發(fā)的密鑰數(shù)目和參與者的數(shù)目一樣非對稱加密沒有復(fù)雜的密鑰分發(fā)問題非對稱加密不需要事先在各參與方建立關(guān)系以交換密鑰非對稱加密支持?jǐn)?shù)字簽名和不可否認(rèn)性非對稱加密速度加密較慢非對稱加密會導(dǎo)致得到的密文變長非對稱密碼學(xué)的主要特點(diǎn)：RSA算法概況MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman

等1978發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法，稱作MIT體制，后來被廣泛稱之為RSA體制。它既可用于加密、又可用于數(shù)字簽字。RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性。算法描述－密鑰產(chǎn)生獨(dú)立地選取兩大素數(shù)p和q(各100～200位十進(jìn)制數(shù)字)計算n=p×q，其歐拉函數(shù)值(n)=(p－1)(q－1)

隨機(jī)選一整數(shù)e，1<

e<(n)，gcd[(n),e]=1在模(n)下，計算e的有逆元d*e=1mod(n)以{e,n}為公鑰。{d,n}為私鑰。(p,q不再需要，可以銷毀。)算法描述－加密和解密加密將明文比特串分組，各組對應(yīng)的十進(jìn)制數(shù)小于nc=memodn解密

m=cd

modnRSA算法舉例選P=7,q=17。設(shè)明文為m=19求密文.n=p*q=7*17=119(n)=(p-1)*(q-1)=6*16=96取e＝5，滿足1<e<(n),且gcd((n),e)=1確定d*e=1mod(n),且小于96的d即求96*x+1=5d因?yàn)?7*5=385=4*96+1所以d=77故公鑰為(5,119)私鑰為(77,119)加密：C=195mod119=2476099mod119=66解密：m=6677mod119=19RSA的安全性RSA的安全性是基于分解大整數(shù)的困難性假定（尚未證明分解大整數(shù)是NP問題）如果分解n=p×q，則立即獲得(n)=(p－1)(q－1)，從而能夠確定e的模(n)乘法逆dRSA-129歷時8個月被于1996年4月被成功分解，RSA－130于1996年4月被成功分解密鑰長度應(yīng)該介于1024bit到2048bit之間由n直接求(n)等價于分解nRSA的安全性P和q的長度相差不要太大，即|p-q|要大p-1,q-1都應(yīng)有大的素因子。gcd(p-1)(q-1)應(yīng)小e<n且d<n1/4,則d能被容易的確定。2.3.3橢圓曲線密碼體制橢圓曲線算法（ECC）：為保證RSA算法的安全，密鑰長度增加帶來運(yùn)算負(fù)擔(dān)增加。ECC算法能采用短的多的密鑰獲得同樣的安全性。ECC算法密碼體制優(yōu)點(diǎn)：安全性高密鑰量小靈活性好RSA/DSA5127681024204821000ECC106132160211600ECC和RSA/DSA在保持同等安全條件下所需密鑰長度（比特）橢圓曲線密碼體制的優(yōu)點(diǎn)：安全性高ECC和其他幾種公鑰加密相比，安全性更高。它的離開對數(shù)問題的計算復(fù)雜度是完全指數(shù)級的，而RSA是亞指數(shù)級的。計算量小而處理速度快在相同條件下，ECC的私鑰處理速度比RSA快，同時，ECC的密鑰生成速度比RSA快百倍以上，因此加密性能更優(yōu)。存儲空間占用小因?yàn)橄嗤踩珡?qiáng)度下，密鑰更短，因此空間占用少。帶寬要求低在短消息加密時，ECC所需帶寬比RSA少很多。2.3.3橢圓曲線密碼體制單向函數(shù)一個可逆函數(shù)f：AB，若它滿足：1對所有xA，易于計算f(x)。2對“幾乎所有xA”由f(x)求x“極為困難”，以至于實(shí)際上不可能做到，則稱f為一單向(One-way)函數(shù)。定義中的“易于計算”是指函數(shù)值能在其輸入長度的多項(xiàng)式時間內(nèi)求出，即若輸入長度為n，計算函數(shù)的時間是na的倍數(shù)，a為一固定的常數(shù)。若計算函數(shù)時間是an的倍數(shù)，則為不可能做到的。2.3.4單向散列函數(shù)2.3.4單向散列函數(shù)單向散列函數(shù)又稱單向Hash函數(shù)、雜湊函數(shù)，就是把任意長的輸入消息串變化成固定長的輸出串且由輸出串難以得到輸入串的一種函數(shù)。這個輸出串稱為該消息的散列值。一般用于產(chǎn)生消息摘要，密鑰加密等。常見的單向散列函數(shù)：MD5、SHA、MAC、CRC性質(zhì)：

給定一個消息M，容易計算出散列值h。給定散列值h，很難根據(jù)H(M)=h計算出消息M。給定一個消息M，很難再找出另一消息滿足H(M)=H(M’)2.3.4單向散列函數(shù)單向散列函數(shù)安全的單向散列函數(shù)應(yīng)該具備的條件①輸入長度是任意的;

②輸出長度是固定的,根據(jù)目前的計算技術(shù)應(yīng)至少取128bits長,以便抵抗生日攻擊;

③對每一個給定的輸入,計算輸出即散列值是很容易的④給定散列函數(shù)的描述,找到兩個不同的輸入消息雜湊到同一個值是計算上不可行的

哈希函數(shù)定義：將任意長的字符串M映射成一個較短的定長輸出字符串H的函數(shù)，以h表示，即h（M）H＝h（M）為M的哈希值、哈希碼、哈希結(jié)果H又稱為輸入M的數(shù)字指紋h為多對一的關(guān)系，不能逆推分類：密碼哈希函數(shù)一般哈希函數(shù)哈希函數(shù)報文CRC匹配CRC'報文多項(xiàng)式收到的報文循環(huán)冗余檢驗(yàn)哈希函數(shù)設(shè)計運(yùn)用特點(diǎn)用戶無法反向執(zhí)行算法來恢復(fù)最初的明文得到的摘要不會泄漏明文信息創(chuàng)建/發(fā)現(xiàn)摘要為某個特定值的明文計算上是不可行的哈希函數(shù)的安全性針對哈希函數(shù)的基本攻擊方式窮舉攻擊法（ExhaustiveAttack）目標(biāo)攻擊自由起始目標(biāo)攻擊生日攻擊（BirthdayAttact）中途相遇攻擊（MeetintheMiddleAttack）生日攻擊（BirthdayAttact）

如果房間里有183個人，那么其中某個人和你的生日相同的概率是50%。然而，如果希望找到其中任意兩個人生日相同的概率為50%，則房間里需要多少人呢？答案是23。計算公式參看P79這個就是生日悖論，結(jié)果要比主觀猜想的要小得多。也就是說你走進(jìn)一個22人的教室，要其中一個人和你的生日相同的概率很小，但要其中任意兩個生日相同的概率則很高。轉(zhuǎn)到代碼安全中的哈希加密，情況轉(zhuǎn)換成兩段不同的字符（人），用哈希加密可能得到相同的密碼（生日），而生日悖論的結(jié)果說明只要不關(guān)心是哪兩個字符，找到兩個匹配的難度會降低很多。利用該理論來破解密碼的方法就叫做“生日攻擊”。MD-5哈希算法MD5算法MD5的全稱是Message-DigestAlgorithm5（信息-摘要算法），在90年代初由MITLaboratoryforComputerScience和RSADataSecurityInc的RonaldL.Rivest開發(fā)出來，經(jīng)MD2、MD3和MD4發(fā)展而來。它的作用是讓大容量信息在用數(shù)字簽名軟件簽署私人密匙前被“壓縮”成一種保密的格式（就是把一個任意長度的字節(jié)串變換成一定長的大整數(shù)）。不管是MD2、MD4還是MD5，它們都需要獲得一個隨機(jī)長度的信息并產(chǎn)生一個128位的信息摘要。MD5之父RonaldRivest算法的應(yīng)用

MD5的典型應(yīng)用是對一段信息（Message）產(chǎn)生信息摘要（Message-Digest），以防止被篡改。比如，在UNIX下有很多軟件在下載的時候都有一個文件名相同，文件擴(kuò)展名為.md5的文件，在這個文件中通常只有一行文本，大致結(jié)構(gòu)如：MD5(tanajiya.tar.gz)=0ca175b9c0f726a831d895e269332461以此保證下載文件的完整性和防抵賴性應(yīng)用2：UNIX系統(tǒng)中用戶的密碼就是以MD5（或其它類似的算法）經(jīng)加密后存儲在文件系統(tǒng)中。有效的避免黑客攻擊中的“跑字典法”MD-5算法王小云教授，1983年至1993年就讀于山東大學(xué)數(shù)學(xué)系，先后獲得學(xué)士、碩士和博士學(xué)位，1993年畢業(yè)后留校任教。2005年獲國家自然科學(xué)基金杰出青年基金資助，同年入選清華大學(xué)“百名人才計劃”，2005年6月受聘為清華大學(xué)高等研究中心“楊振寧講座教授”，現(xiàn)為清華大學(xué)“長江學(xué)者特聘教授”。王小云教授帶領(lǐng)的研究小組于2004年、2005年先后破解了被廣泛應(yīng)用于計算機(jī)安全系統(tǒng)的MD5和SHA-1兩大密碼算法，對于這項(xiàng)十幾年來國際上首次成功破解全球廣泛使用的密碼算法與標(biāo)準(zhǔn)的工作，整個國際密碼學(xué)界為之震驚，密碼學(xué)領(lǐng)域最權(quán)威的兩大刊物Eurocrypto與Crypto將2005年度最佳論文獎授予了這位中國女性，其研究成果引起了國際同行的廣泛關(guān)注。

2004年8月，在美國加州圣芭芭拉召開的國際密碼大會上王小云在國際會議上首次宣布了她及她的研究小組近年來的研究成果——對MD5、HAVAL-128、MD4和RIPMD等四個著名密碼算法的破譯結(jié)果。

王小云的研究成果表明了從理論上講電子簽名可以偽造，必須及時添加限制條件，或者重新選用更為安全的密碼標(biāo)準(zhǔn)，以保證電子商務(wù)的安全。MD5安全性探討：第一，MD5并沒有被完全的破解，目前只是獲得了快速產(chǎn)生碰撞的算法（大約需要2^40次嘗試，在當(dāng)前的計算能力下僅需幾小時即可）。因?yàn)橐獜慕?jīng)過MD5散列處理所得到的結(jié)果逆向分析從而得到散列前的原文是根本不可能的！

根據(jù)MD5的基本原理，該算法是將一段任意長的數(shù)據(jù)轉(zhuǎn)換成一段長度為128位的數(shù)據(jù)，并且保證轉(zhuǎn)換后得到的數(shù)據(jù)是偽隨機(jī)的。從函數(shù)的角度而言，MD5即是將一個不做任何要求的自變量映射成為一個長度固定的因變量，顯然，這是一個多對一的映射（因變量空間僅為2^128，而自變量空間為無窮大，所以可以將MD5視為一個無窮多對一的映射）。由最基本的數(shù)學(xué)定理可知，多對一的函數(shù)是不可逆的，即是說，不可能從MD5的散列結(jié)果逆推出原文。所以，用戶不用擔(dān)心其使用MD5進(jìn)行散列處理后得到的結(jié)果會被人破解得到原文。第二，MD5的碰撞的發(fā)現(xiàn)，僅僅是使得使用其進(jìn)行對隨機(jī)序列的哈希操作變得不可靠，而對于一段有特殊意義或者格式的文字進(jìn)行哈希而言仍然是安全的。

根據(jù)當(dāng)初王教授演示的結(jié)果，我們知道，使用她的碰撞算法得到的結(jié)果是一串隨機(jī)字符串。因此，我們?nèi)匀豢梢允褂肕D5對軟件等進(jìn)行哈希，并且，目前市面上仍然有大量的軟件是使用的MD5進(jìn)行哈希作為驗(yàn)證碼。只是利用MD5存儲密碼等已經(jīng)不再安全！RSA公司的blog上一篇討論MD5在目前仍然可以使用的文章，作者提出的解決方案是在需要哈希處理的代碼前加入一段格式固定的字符串，這個簡單的做法就可以使王教授的攻擊無效，這一點(diǎn)是值得我們?nèi)ミM(jìn)一步探討的！

當(dāng)然，為了獲得更高的安全性，在仍然使用MD5的同時，我們也應(yīng)該考慮將軟件向SHA-256等仍然安全的算法進(jìn)行遷移，并且期待密碼學(xué)家們提出更加安全的哈希算法。

SHA算法家族安全散列算法SHA(SecureHashAlgorithm)一種數(shù)據(jù)加密算法，公認(rèn)的最安全的散列算法之一。

取一串輸入碼（稱為預(yù)映射或信息），并把它們轉(zhuǎn)化為長度較短、位數(shù)固定的輸出序列即散列值（也稱為信息摘要或信息認(rèn)證代碼）的過程。散列函數(shù)值可以說時對明文的一種“指紋”或是“摘要”。SHA-1輸入：512位分組，輸出：160位。MAC算法MAC（MessageAuthenticationCode）消息認(rèn)證碼（帶密鑰的Hash函數(shù)）:密碼學(xué)中，通信實(shí)體雙方使用的一種驗(yàn)證機(jī)制，保證消息數(shù)據(jù)完整性的一種工具。2.3.5非對稱密鑰技術(shù)的應(yīng)用1.混合密碼系統(tǒng)產(chǎn)生原因：對稱加密密鑰管理和分發(fā)困難，不能實(shí)現(xiàn)數(shù)字簽名，而非對稱加密運(yùn)算速度太慢。解決方法：對稱加密與非對稱加密結(jié)合。基本方法：非對稱密碼體制用來加密關(guān)鍵的核心的數(shù)據(jù)（密鑰），對稱密鑰體制用來加密大量數(shù)據(jù)（明文）。結(jié)果：從對稱密碼得到速度和緊湊的密文，你也可以從公／私鑰密碼學(xué)當(dāng)中得到你想要的伸縮性、簡化的密鑰管理、抗竊聽以及對數(shù)字簽名／不可否認(rèn)性的支持過程：先生成一個隨機(jī)對稱密鑰（會話密鑰）。用會話密鑰加密明文。用接受者公鑰加密對稱密鑰。將被打包的密鑰附在密文的后面發(fā)送給接收者。AB密文數(shù)據(jù)包密鑰打包2.3.5非對稱密鑰技術(shù)的應(yīng)用2.數(shù)字信封數(shù)字信封是公鑰密碼體制在實(shí)際中的一個應(yīng)用，是用加密技術(shù)來保證只有規(guī)定的特定收信人才能閱讀通信的內(nèi)容。信息發(fā)送方采用對稱密鑰來加密信息內(nèi)容，然后將此對稱密鑰用接收方的公開密鑰來加密，這部分稱數(shù)字信封。2.3.5非對稱密鑰技術(shù)的應(yīng)用3.Diffie-Hellman密鑰交換Diffie–Hellmankeyexchange，簡稱“D–H”

是一種安全協(xié)議。它可以讓雙方在完全沒有對方任何預(yù)先信息的條件下通過不安全信道創(chuàng)建起一個密鑰。這個密鑰可以在后續(xù)的通訊中作為對稱密鑰來加密通訊內(nèi)容。算法的有效性（安全性）依賴于計算離散對數(shù)的難度。2.3.5非對稱密鑰技術(shù)的應(yīng)用算法表示（藍(lán)色表示非秘密信息,紅色表示秘密信息）：愛麗絲與鮑伯協(xié)定使用p=23以及baseg=5.愛麗絲選擇一個秘密整數(shù)a=6,計算A=g

amodp并發(fā)送給鮑伯。

A=56mod23=8.鮑伯選擇一個秘密整數(shù)b=15,計算B=

g

bmodp并發(fā)送給愛麗絲。

B=5

15mod23=19.愛麗絲計算s=B

amodp

19

6mod23=2.鮑伯計算<s=A

bmodp

815mod23=22.3.5非對稱密鑰技術(shù)的應(yīng)用愛麗絲和鮑伯最終都得到了同樣的值，因?yàn)樵趍odp下gab和gba相等。注意a,b和gab=gbamodp是秘密的。其他所有的值都可以在公共信道上傳遞。一旦愛麗絲和鮑伯得出了公共秘密，他們就可以把它用作對稱密鑰，以進(jìn)行雙方的加密通訊，因?yàn)檫@個密鑰只有他們才能得到。