現(xiàn)代密碼學(xué)精講課件

第2章現(xiàn)代密碼學(xué)精講第2章現(xiàn)代密碼學(xué)精講1本章要點(diǎn)現(xiàn)代密碼學(xué)框架現(xiàn)代密碼學(xué)的理論基礎(chǔ)對(duì)稱加密標(biāo)準(zhǔn)：DES和AES公鑰密碼體制：RSA和ElGamal體制本章要點(diǎn)現(xiàn)代密碼學(xué)框架22.1現(xiàn)代密碼學(xué)框架

2.1.1什么是密碼學(xué)

定義1

密碼學(xué)是研究與信息安全各方面有關(guān)的(比如機(jī)密性、數(shù)據(jù)完整性、實(shí)體認(rèn)證及數(shù)據(jù)源認(rèn)證)數(shù)學(xué)技術(shù)的一門學(xué)科。2.1現(xiàn)代密碼學(xué)框架2.1.1什么是密碼學(xué)3

2.1.1什么是密碼學(xué)(續(xù))發(fā)送者Alice密鑰源分析者Eve接收者Bob安全信道公共信道加密器Ek解密器Dk明文m密文c明文m密鑰k密鑰k圖2.1Shannon保密系統(tǒng)2.1.1什么是密碼學(xué)(續(xù))發(fā)送者密鑰源分析者接收者安全4

2.1.1什么是密碼學(xué)(續(xù))

通信中的參與者(1)發(fā)送者(Alice)：在雙方交互中合法的信息發(fā)送實(shí)體。(2)接收者(Bob)：在雙方交互中合法的信息接收實(shí)體。(3)分析者(Eve)：破壞通信接收和發(fā)送雙方正常安全通信的其他實(shí)體?？梢圆扇”粍?dòng)攻擊和主動(dòng)攻擊的手段。

信道

(1)信道：從一個(gè)實(shí)體向另一個(gè)實(shí)體傳遞信息的通路。(2)安全信道：分析者沒有能力對(duì)其上的信息進(jìn)行閱讀、刪除、修改、添加的信道。(3)公共信道：分析者可以任意對(duì)其上的信息進(jìn)行閱讀、刪除、修改、添加的信道。2.1.1什么是密碼學(xué)(續(xù))52.1.2現(xiàn)代密碼學(xué)中的對(duì)稱與非對(duì)稱密碼思想加密器EK1(m)=c分析者Eve解密器DK2(c)=m明文消息源目的地mmc公共信道AliceBob#對(duì)稱密碼加密密鑰與解密密鑰同：K1=K2代表系統(tǒng)：DES和AES2.1.2現(xiàn)代密碼學(xué)中的對(duì)稱與非對(duì)稱密碼思想加密器分析者解62.1.2現(xiàn)代密碼學(xué)中的對(duì)稱與非對(duì)稱密碼思想(續(xù))若互聯(lián)網(wǎng)上有n個(gè)用戶，則需要個(gè)密鑰，若n=1000，則NK500000。#如此眾多的密鑰如何建立，如何保存？2.1.2現(xiàn)代密碼學(xué)中的對(duì)稱與非對(duì)稱密碼思想(續(xù))若互聯(lián)網(wǎng)72.1.2現(xiàn)代密碼學(xué)中的對(duì)稱與非對(duì)稱密碼思想(續(xù))加密器EK1(m)=c分析者Eve解密器DK2(c)=m明文消息源目的地mmc公共信道AliceBob#非對(duì)稱密碼加密密鑰與解密密鑰不同：K1

K2代表系統(tǒng)：RSA和ElGamal2.1.2現(xiàn)代密碼學(xué)中的對(duì)稱與非對(duì)稱密碼思想(續(xù))加密器分82.1.3密碼學(xué)的演進(jìn)及目前的狀態(tài)安全依賴于保密加密方法安全依賴于保密密鑰安全依賴于保密部分密鑰古典密碼私鑰密碼公鑰密碼#公鑰密碼體制以其強(qiáng)大的功能使得私鑰密碼體制顯得已經(jīng)過時(shí)，但是強(qiáng)大的功能不是無代價(jià)獲得的，公鑰密碼的計(jì)算量遠(yuǎn)大于相同情況下的私鑰密碼。因此，不適合加密大量數(shù)據(jù)，只適合于完成少量數(shù)據(jù)加密，如傳送私鑰密碼的密鑰、簽名等等。2.1.3密碼學(xué)的演進(jìn)及目前的狀態(tài)安全依賴于保密加密方法安92.1.4現(xiàn)代密碼學(xué)主要技術(shù)SecurityPrimitivesPublic-keyPrimitivesSymmetric-keyPrimitivesUnkeyedPrimitivesArbitrarylengthhashfunctionsSymmetric-keyciphersRandomsequencesOne-waypermutationsBlockciphersStreamciphersArbitrarylengthhashfunctions(MACs)SignaturesPseudorandomsequencesIdentificationprimitivesPublic-keyciphersSignaturesIdentificationprimitives圖2.2密碼學(xué)本原分類2.1.4現(xiàn)代密碼學(xué)主要技術(shù)SecurityPrimit102.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(1)加密

加密基本術(shù)語明文消息空間M:某個(gè)字母表集密文消息空間C:可能的密文消息集加/解密密鑰空間K:可能的加/解密密鑰集加/解密函數(shù)Ee

K(m

M)

/

Dd

K(c

C)

:一個(gè)從M到C/C到M的有效變換2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(1)加密112.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))

加密方案加密方案是由一個(gè)加密函數(shù)集{Ee:e

K}和解密函數(shù)集{Dd:d

K}構(gòu)成，并且滿足任意一個(gè)加密密鑰e

K存在唯一一個(gè)解密密鑰d

K使

Dd=Ee-1，也就是對(duì)于所有明文消息m

M

，存在Dd(Ee(m))=m，(e,d)稱為密鑰對(duì)。設(shè)計(jì)加密方案就是確定M、C、K、{Ee:e

K}、{Dd:d

K}的過程。定義2

一個(gè)加密方案可以被破譯是指，第三方在沒有事先得到密鑰對(duì)(e,d)的情況下，可以在適當(dāng)?shù)臅r(shí)間里系統(tǒng)地從密文恢復(fù)出相對(duì)應(yīng)的明文。#適當(dāng)?shù)臅r(shí)間由被保護(hù)數(shù)據(jù)生命周期來確定。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))加密方案122.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))私鑰加密定義3

一個(gè)由加密函數(shù)集{Ee:e

K}和解密函數(shù)集{Dd:d

K}組成加密方案，每一個(gè)相關(guān)聯(lián)的密鑰對(duì)(e,d)，如果知道了e在計(jì)算上很容易確定d，知道了d在計(jì)算上很容易確定e，那么，就是私鑰加密方案。#私鑰加密需要一條安全信道來建立密鑰對(duì)。

主要技術(shù)：分組密碼與流密碼定義4(分組密碼)將明文消息在編碼集按照固定長度t進(jìn)行分組，再一組一組地加\解密明\密文消息。#著名的DES、AES都是這類密碼。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))私鑰加密132.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))

定義5K是加密變換集的密鑰空間，序列

e1e2…

ei

K稱為密鑰流。定義6(流密碼)消息m以串的形式(m1m2…mi)給出，密鑰e1e2…ei是K上的密鑰流。流密碼通過ci=Eei(mi)給出密文消息(c1c2…ci)；如果di為ei的逆，解密則通過mi=Ddi(ci)完成。

2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))定義5K是加142.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))

公鑰加密

定義7一個(gè)由加密函數(shù)集{Ee:e

K}和解密函數(shù)集{Dd:d

K}組成加密方案，每一個(gè)相關(guān)聯(lián)的加/解密密鑰對(duì)(e,d)，加密密鑰e公開，稱為公開密鑰，而解密密鑰d保密，稱為秘密密鑰。#顯然安全公鑰密碼系統(tǒng)要求從e計(jì)算d為不可能。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))公鑰加密152.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))公鑰加密實(shí)例Ee(m1)=c1A1Ee(m2)=c2A2Ee(m3)=c3A3Dd(c1)=m1Dd(c2)=m2Dd(c3)=m3Bobec1eec2c3#因?yàn)榇嬖谔娲魡栴}，公鑰系統(tǒng)中公開密鑰e必須認(rèn)證，一般是建立PKI。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))公鑰加密實(shí)例Ee(m1)162.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(2)數(shù)字簽名技術(shù)基本術(shù)語明文消息空間M:某個(gè)字母表中串的集合簽名空間S:可能的簽名集合簽名密鑰空間K:用于生成簽名的可能密鑰集，具體取值k需要保密驗(yàn)證密鑰空間K’:用于驗(yàn)證簽名的可能密鑰集，具體取值k’需要公開簽名函數(shù)SK(m

M):從M到S的有效變換驗(yàn)證函數(shù)VK’(m

M,s):一個(gè)從M

S到輸出{True,False}的有效變換2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(2)數(shù)字簽名技172.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))

簽名過程

簽名(簽名者完成)

1)對(duì)一條需要簽名的消息m

M計(jì)算簽名s=Sk(m)。

2)將對(duì)消息m的簽名(m,s)發(fā)送出去。

驗(yàn)證(驗(yàn)證者完成)

1)得到對(duì)應(yīng)簽名者的驗(yàn)證算法Vk’

，計(jì)算u=Vk’

(m,s)。

2)如果u=True，接受簽名；如果u=False，拒絕簽名。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))簽名過程182.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))簽名和認(rèn)證函數(shù)必須滿足的性質(zhì)1)當(dāng)且僅當(dāng)Vk’

(m,s)=True時(shí)，s是消息m的合法簽名。

2)

對(duì)于任何簽名者以外的實(shí)體在計(jì)算上不可能得到任意的一組mf和sf滿足Vk’

(mf,sf)=True。

數(shù)字簽名的爭(zhēng)議解決(不可否認(rèn))

如果簽名者和驗(yàn)證者對(duì)簽名發(fā)生爭(zhēng)議，可由驗(yàn)證者帶著簽名(m,s)提交給可信任第三方(TTP)，由TTP驗(yàn)證該簽名，最后進(jìn)行仲裁。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))簽名和認(rèn)證函數(shù)必192.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))數(shù)字簽名技術(shù)在公鑰基礎(chǔ)設(shè)施(PKI)中的應(yīng)用

除非對(duì)密鑰產(chǎn)生的認(rèn)證性和合法性有足夠的信任，否則公鑰密碼的優(yōu)勢(shì)就十分有限。公鑰基礎(chǔ)設(shè)施或簡稱PKI是一個(gè)框架。這個(gè)框架主要由一組策略組成。策略確切定義了關(guān)于密碼系統(tǒng)運(yùn)行和密鑰產(chǎn)生和發(fā)布與證書的規(guī)則。X.509是設(shè)計(jì)用來在大型計(jì)算機(jī)網(wǎng)絡(luò)中提供目錄認(rèn)證服務(wù)的國際標(biāo)準(zhǔn)。由于它本身是ISO/ITU的一個(gè)標(biāo)準(zhǔn)，很多實(shí)用產(chǎn)品都基于它開發(fā)出來。例如，X.509被用在Visa和Mastercard的安全電子交易標(biāo)準(zhǔn)中。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))數(shù)字簽名技術(shù)在公202.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))圖2.3X.509的結(jié)構(gòu)原理2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))圖2.3X.509的結(jié)212.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))222.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))圖2.4證書認(rèn)證過程A1A6認(rèn)證VT(A6||e6,s6)秘密密鑰d6A2,e2,ST(A2||e2)=s2A3,e3,ST(A3||e3)=s3A4,e4,ST(A4||e4)=s4e6,s6Dd6(c)=mc=Ee6(m)PublicfileA1,e1,ST(A1||e1)=s1A5,e5,ST(A5||e5)=s5A6,e6,ST(A6||e6)=s6A2,e2,ST(A2||e2)=s2#證書權(quán)威負(fù)荷小(離線、非交互、存儲(chǔ)證書)，權(quán)限低2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))圖2.4證書認(rèn)證過程A232.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))

公鑰證書的產(chǎn)生

情況1可信方產(chǎn)生密鑰對(duì)。可信方為實(shí)體產(chǎn)生公鑰算法的密鑰對(duì)，并將公開密鑰和綁定身份的公鑰證書通過公共信道發(fā)給該實(shí)體。實(shí)體在證明了自己的身份(例如，出示身份證或個(gè)人可信照片)后，將通過安全信道得到對(duì)應(yīng)的秘密密鑰。

情況2實(shí)體產(chǎn)生自己的密鑰對(duì)。實(shí)體產(chǎn)生自己的公鑰算法的密鑰對(duì)，并安全地將公開密鑰傳送給可信方(例如，通過可信通道或派人送達(dá))，這里主要是保證公開密鑰的真實(shí)性。在驗(yàn)證了公開密鑰來源的真實(shí)性后，可信方為公開密鑰生成證書。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))公鑰證書的產(chǎn)生242.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))證書鏈和證書路徑圖2.5證書鏈2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))證書鏈和證書路徑圖2.5252.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))

(3)認(rèn)證與鑒別技術(shù)

鑒別或?qū)嶓w認(rèn)證定義9鑒別或?qū)嶓w認(rèn)證是一個(gè)過程。在這個(gè)過程中一方通過獲得一些確定的證據(jù)來確認(rèn)參加實(shí)體認(rèn)證的另一方的身份，而具有相應(yīng)身份的實(shí)體也確實(shí)就是正在參與這一認(rèn)證過程的另一方。例子1實(shí)體A與B通電話，如果A與B認(rèn)識(shí)就可以通過聲音來確定對(duì)方的真實(shí)性。例子2實(shí)體A通過信用卡在銀行ATM機(jī)上取錢。#特點(diǎn)：時(shí)實(shí)性。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(3)認(rèn)證與262.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))直觀安全目標(biāo)：a在宣稱者A和驗(yàn)證者B都誠實(shí)地執(zhí)行認(rèn)證時(shí)，A能向B成功地證明自己，也就是B將完成執(zhí)行并接受A所宣稱的身份。b(不可轉(zhuǎn)移性)驗(yàn)證者B不能從與宣稱者A交互中獲得的信息，成功地向第三方C來冒充A。c(不可冒充性)任何一個(gè)非宣稱者A的C想通過扮演A的身份，通過驗(yàn)證者B的認(rèn)證，讓B接受A的身份的可能性可以忽略。這里，可以忽略的含義是概率小到?jīng)]有具體的實(shí)際意義，準(zhǔn)確的度量需要根據(jù)實(shí)際應(yīng)用而定。

d即使如下情況存在，以上三個(gè)條件仍然成立。d.1宣稱者A和驗(yàn)證者B之間以前進(jìn)行的多項(xiàng)式次認(rèn)證會(huì)話且被竊聽;d.2冒充者C以前參與了同宣稱者A或（和）驗(yàn)證者B的認(rèn)證執(zhí)行;d.3冒充者C可能發(fā)起多個(gè)認(rèn)證會(huì)話并行運(yùn)行。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))直觀安全目標(biāo)：272.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))數(shù)據(jù)源認(rèn)證定義10數(shù)據(jù)源認(rèn)證或消息認(rèn)證技術(shù)，提供一方通過一些附加的證據(jù)，確定消息的產(chǎn)生一方的真實(shí)身份。例子3實(shí)體A向?qū)嶓wB發(fā)送電子郵件，電子郵件通過網(wǎng)絡(luò)傳輸并存儲(chǔ)，在某個(gè)時(shí)間由B接收到，由于沒有直接通信，B這時(shí)可能要求認(rèn)證郵件確實(shí)來自A。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))數(shù)據(jù)源認(rèn)證282.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))

(4)密碼Hash函數(shù)技術(shù)定義11Hash函數(shù)h()是一個(gè)有效的計(jì)算方法，它將一個(gè)任意長度的二進(jìn)制位串影射成固定長度的二進(jìn)制位串，這個(gè)固定長度的二進(jìn)制位串叫Hash值。

修改發(fā)現(xiàn)碼(MDCs)附加性質(zhì)1)Hash函數(shù)是單向函數(shù)，即給定y，找到任意x，滿足y=h(x)計(jì)算不可能。2)已知x，找x'，滿足h(x)=h(x')計(jì)算不可能。3)找一任意對(duì)x和x'，滿足h(x)=h(x')計(jì)算不可能。#修改發(fā)現(xiàn)碼可以進(jìn)一步分類，單向Hash函數(shù)(1-2)(OWHFs)和碰撞抵抗Hash函數(shù)(2-3)(CRHFs)。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(4)密碼Ha292.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))

消息認(rèn)證碼(MACs)消息認(rèn)證碼的目的，通俗講就是不附加任何其他機(jī)制，確保消息來源的真實(shí)性的Hash函數(shù)。消息認(rèn)證碼有兩個(gè)不同功能的參數(shù)，即消息和秘密密鑰。Hash函數(shù)無密鑰有密鑰修改發(fā)現(xiàn)碼(MDCs)其他應(yīng)用其他應(yīng)用消息認(rèn)證碼(MACs)圖2.6密碼Hash函數(shù)的簡單分類2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))消息認(rèn)證碼(M302.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(5)隨機(jī)數(shù)與隨機(jī)序列密碼中以偽隨機(jī)序列發(fā)生器代替隨機(jī)序列發(fā)生器。偽隨機(jī)序列發(fā)生器以短的隨機(jī)數(shù)做種子，以固定方式產(chǎn)生偽隨機(jī)序列。#偽隨機(jī)序列與真隨機(jī)序列不可區(qū)分假設(shè)，與安全數(shù)字簽名、公鑰密碼的存在性等價(jià)。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(5)隨機(jī)數(shù)與隨312.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)

Kerckhoffs準(zhǔn)則在評(píng)估一個(gè)密碼系統(tǒng)安全性時(shí)，應(yīng)該總是假定我們的敵人了解實(shí)際使用的各種方法。

#落實(shí)到現(xiàn)代密碼算法中就是攻擊者知道密碼算法的所有執(zhí)行細(xì)節(jié)，算法的安全不應(yīng)該依賴于對(duì)算法的保密。2.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)Kerckhoffs322.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))Shannon提出的“優(yōu)質(zhì)”密碼算法特征(1)加解密的工作量應(yīng)該由所要求的安全程度決定。(2)密鑰集合和加密算法不應(yīng)該過于復(fù)雜。(3)執(zhí)行過程應(yīng)該盡量簡單。(4)密碼中的差錯(cuò)不應(yīng)該具有傳播性，也不應(yīng)該影響報(bào)文中的其他信息。(5)加密后的文本大小不應(yīng)該比原始報(bào)文更大。2.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))Shanno332.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))“可信賴的”加密體制的特點(diǎn)(1)有可靠的數(shù)學(xué)基礎(chǔ)。(2)經(jīng)過專家的嚴(yán)格分析，證實(shí)是可靠的。(3)經(jīng)得起時(shí)間的檢驗(yàn)。2.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))“可信賴的”加密體制342.2現(xiàn)代密碼學(xué)的理論基礎(chǔ)現(xiàn)代密碼學(xué)要求很高的數(shù)學(xué)基礎(chǔ)，包括：數(shù)論、抽象代數(shù)與有限域、計(jì)算復(fù)雜理論、信息論、概率論等。但是掌握基礎(chǔ)的密碼算法并不需要精通過多的底層數(shù)學(xué)理論。這里我們僅講述掌握本章的密碼算法所需要的計(jì)算復(fù)雜理論、數(shù)論等的基礎(chǔ)知識(shí)。2.2現(xiàn)代密碼學(xué)的理論基礎(chǔ)現(xiàn)代密碼學(xué)要求很高的數(shù)學(xué)基352.2.1計(jì)算復(fù)雜理論

如果加密算法建立在一個(gè)已知非常難解決的問題或者可能解的數(shù)目巨大的問題之上，那么攻擊者要破譯算法就注定要完成一個(gè)即便不是不可能，也是另人沮喪的任務(wù)。即使有計(jì)算機(jī)的支持，一個(gè)窮盡的暴力解答也是不可行的。NP完全問題就是這樣一類具有計(jì)算復(fù)雜特點(diǎn)的問題。我們用非形式化的方式來描述NP完全問題。2.2.1計(jì)算復(fù)雜理論如果加密算法建立在一個(gè)已知非常362.2.1計(jì)算復(fù)雜理論(續(xù))NP完全問題幾個(gè)具體實(shí)例例子4可滿足問題給定邏輯公式滿足如下條件：(1)它由變量v1，v2，…，vn和它們的邏輯非?v1，?v2，…，?vn組成。(2)它表現(xiàn)為一系列子句，且每個(gè)子句的形式是變量以及邏輯非的邏輯或(

)(3)它表示為這些子句的邏輯與(

)是否存在一種變量的賦值法(賦真或假)，使得公式為真？如果存在，說這個(gè)公式是可滿足的。例如，(v1)

(v2

v3)

(?

v1

?

v3)為可滿足的，(v1)

(v2

v3)

(?

v1

?

v3)(?

v2)為不可滿足的。2.2.1計(jì)算復(fù)雜理論(續(xù))NP完全問題372.2.1計(jì)算復(fù)雜理論(續(xù))例子5背包問題2.2.1計(jì)算復(fù)雜理論(續(xù))例子5背包問題382.2.1計(jì)算復(fù)雜理論(續(xù))例子6團(tuán)給定一個(gè)圖G和一個(gè)整數(shù)n，是否存在一個(gè)包含n個(gè)頂點(diǎn)的子圖，使得子圖中的每個(gè)頂點(diǎn)與其他頂點(diǎn)之間都有一條邊[每個(gè)頂點(diǎn)都與其他所有頂點(diǎn)相連的圖被稱為團(tuán)(clique)]?例如，圖2.7有4頂點(diǎn)的團(tuán)，但無5頂點(diǎn)的團(tuán)。圖2.7圖的團(tuán)子圖2.2.1計(jì)算復(fù)雜理論(續(xù))例子6團(tuán)圖2.7392.2.1計(jì)算復(fù)雜理論(續(xù))

NP完全問題的特征(1)每個(gè)問題都有解法，且總有一個(gè)相對(duì)簡單的解法(盡管該解法也許十分耗時(shí))。(2)如果要列舉所有可能性，就需要考慮2n中情況(n與問題有關(guān))(3)這些問題是無關(guān)的，分別來自邏輯學(xué)、數(shù)論和圖論。(4)如果能完全猜中，則可以在相對(duì)較少的時(shí)間內(nèi)求解每一個(gè)問題。2.2.1計(jì)算復(fù)雜理論(續(xù))NP完全問題的特征402.2.1計(jì)算復(fù)雜理論(續(xù))

P類和NP類

P類問題是一類問題的集合，這個(gè)集合中的問題都可以在一個(gè)與問題大小相關(guān)的多項(xiàng)式函數(shù)時(shí)間內(nèi)完成。NP類問題是所有這樣一類問題的集合，假設(shè)能夠完全猜中，這些問題可以在一個(gè)多項(xiàng)式函數(shù)時(shí)間內(nèi)得到解決(猜測(cè)函數(shù)被稱為是預(yù)言機(jī)或非確定性圖靈機(jī))。這種猜測(cè)是非確定性的。EXP類，它由所有存在指數(shù)時(shí)間cn內(nèi)的確定性解法的問題組成，其中，c是一個(gè)常數(shù)。它們有如下關(guān)系，P

NP

EXP。2.2.1計(jì)算復(fù)雜理論(續(xù))P類和NP類412.2.1計(jì)算復(fù)雜理論(續(xù))NP完全的含義Cook證明了：如果可滿足問題有一個(gè)確定性的、多項(xiàng)式時(shí)間的算法(不帶猜測(cè))，那么對(duì)NP中的每個(gè)問題都會(huì)有一個(gè)確定性、多項(xiàng)式時(shí)間的算法，即NP=P。Karp證明了背包問題和團(tuán)問題具有和可滿足問題一樣的性質(zhì)。這一問題的逆否命題是：如果可以證明這些問題中的某個(gè)問題沒有在多項(xiàng)式時(shí)間內(nèi)完成的確定性算法，那么它們中所有問題都不存在確定性多項(xiàng)式時(shí)間算法。這里對(duì)一個(gè)問題的解決是要求找到一個(gè)通用算法來解決它的每個(gè)實(shí)例。2.2.1計(jì)算復(fù)雜理論(續(xù))NP完全的含義422.2.1計(jì)算復(fù)雜理論(續(xù))圖2.8復(fù)雜性的層次結(jié)構(gòu)#P=NP或P

NP2.2.1計(jì)算復(fù)雜理論(續(xù))圖2.8復(fù)雜性的層次結(jié)構(gòu)#432.2.1計(jì)算復(fù)雜理論(續(xù))

已經(jīng)有很多人對(duì)NP完全問題進(jìn)行了長期研究，如果對(duì)確實(shí)存在多項(xiàng)式時(shí)間算法，那么我們有理由認(rèn)為已經(jīng)有人找到了解法。目前，已經(jīng)有數(shù)以百計(jì)的問題被證明是NP完全問題。我們列舉的這類問題越多，就越有理由確信不存在一個(gè)能解決所有問題的簡單方法。2.2.1計(jì)算復(fù)雜理論(續(xù))已經(jīng)有很多人對(duì)NP完全問442.2.1計(jì)算復(fù)雜理論(續(xù))NP完全性與密碼學(xué)(1)一個(gè)NP完全問題不能保證不存在一種比指數(shù)時(shí)間更容易的算法，它僅表示我們不大可能找到這一算法。(2)每個(gè)NP完全問題都有一個(gè)確定性的指數(shù)時(shí)間算法，即可以與2n成比例的時(shí)間運(yùn)行完成。(3)硬件的不斷進(jìn)步，越來越大規(guī)模的問題都能計(jì)算了。(4)即使一個(gè)加密算法是基于難解問題的，但攻擊者未必總是去解這個(gè)難解問題才能破譯加密算法。2.2.1計(jì)算復(fù)雜理論(續(xù))NP完全性與密碼學(xué)452.2.1計(jì)算復(fù)雜理論(續(xù))其他固有的難解問題數(shù)論中存在大量難解問題，但大多數(shù)數(shù)論中的難解問題都是NP問題，不是NP完全問題。公鑰密碼體制主要依賴數(shù)論中的兩個(gè)難解問題：大整數(shù)分解問題和離散對(duì)數(shù)問題。2.2.1計(jì)算復(fù)雜理論(續(xù))其他固有的難解問題462.2.2數(shù)論知識(shí)(1)基本概念整除性2.2.2數(shù)論知識(shí)(1)基本概念472.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))482.2.2數(shù)論知識(shí)(續(xù))素?cái)?shù)2.2.2數(shù)論知識(shí)(續(xù))素?cái)?shù)492.2.2數(shù)論知識(shí)(續(xù))200以內(nèi)的素?cái)?shù)：

2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199

2.2.2數(shù)論知識(shí)(續(xù))200以內(nèi)的素?cái)?shù)：502.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))512.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))522.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))532.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))542.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))552.2.2數(shù)論知識(shí)(續(xù))整數(shù)唯一分解定理2.2.2數(shù)論知識(shí)(續(xù))整數(shù)唯一分解定理562.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))572.2.2數(shù)論知識(shí)(續(xù))一次不定方程2.2.2數(shù)論知識(shí)(續(xù))一次不定方程582.2.2數(shù)論知識(shí)(續(xù))(2)同余同余定義與概念2.2.2數(shù)論知識(shí)(續(xù))(2)同余592.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))602.2.2數(shù)論知識(shí)(續(xù))剩余類和完全剩余類2.2.2數(shù)論知識(shí)(續(xù))剩余類和完全剩余類612.2.2數(shù)論知識(shí)(續(xù))縮系2.2.2數(shù)論知識(shí)(續(xù))縮系622.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))632.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))642.2.2數(shù)論知識(shí)(續(xù))一次同余式2.2.2數(shù)論知識(shí)(續(xù))一次同余式652.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))662.2.2數(shù)論知識(shí)(續(xù))(3)原根2.2.2數(shù)論知識(shí)(續(xù))(3)原根672.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))682.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))692.2.2數(shù)論知識(shí)(續(xù))2.2.2數(shù)論知識(shí)(續(xù))702.2.3群環(huán)域的概念(1)群2.2.3群環(huán)域的概念(1)群712.2.3群環(huán)域的概念(續(xù))2.2.3群環(huán)域的概念(續(xù))722.2.3群環(huán)域的概念(續(xù))(2)環(huán)2.2.3群環(huán)域的概念(續(xù))(2)環(huán)732.2.3群環(huán)域的概念(續(xù))2.2.3群環(huán)域的概念(續(xù))742.2.3群環(huán)域的概念(續(xù))(3)域2.2.3群環(huán)域的概念(續(xù))(3)域752.3對(duì)稱密碼算法：DES和AES

對(duì)稱密鑰體制的問題(1)在安全加密體制中，密鑰是需要經(jīng)常變更的，使得已丟失的密鑰只能泄露數(shù)量有限的信息。(2)密鑰的分發(fā)必須保證安全。一種方式就是對(duì)密鑰分解分發(fā)，如圖2.9。(3)密鑰數(shù)目的增長與交換信息的人數(shù)的平方成正比，在人數(shù)多的時(shí)候，可以考慮使用信任中心，如圖2.10。2.3對(duì)稱密碼算法：DES和AES對(duì)稱密鑰體制的問762.3對(duì)稱密碼算法：DES和AES(續(xù))圖2.9密鑰的分塊分發(fā)圖2.10加密信息分發(fā)中心2.3對(duì)稱密碼算法：DES和AES(續(xù))圖2.9密鑰的分772.3對(duì)稱密碼算法：DES和AES(續(xù))2.3.1DES算法描述1974年，IBM向國家標(biāo)準(zhǔn)局(NBS)提交了一個(gè)名為LUCIFER的加密算法。NBS將其轉(zhuǎn)給了國家安全局(NSA)進(jìn)行審定，之后就得到了一個(gè)名為數(shù)據(jù)加密標(biāo)準(zhǔn)DES的算法。1977年，NBS正式將其用于無限制級(jí)的政府通信。其間NBS和NSA可能存在某些誤會(huì)。NSA原本打算DES僅用于硬件執(zhí)行，但是NBS卻公布了過多的技術(shù)細(xì)節(jié)以致于人們可以根據(jù)其寫出DES加密軟件。如果NSA預(yù)料到后續(xù)的情況發(fā)展變化，他們或許不會(huì)同意公布DES。2.3對(duì)稱密碼算法：DES和AES(續(xù))2.3.1782.3.1DES算法描述(續(xù))

DES是分組密碼，每個(gè)分組為64比特?cái)?shù)據(jù)。64比特明文通過加密最后成為64比特密文。DES的密鑰通常寫為64比特，但每8比特有一位奇偶效驗(yàn)位，可以忽略。因此，實(shí)際只有56比特。算法只使用不超過64位的標(biāo)準(zhǔn)算術(shù)操作和邏輯操作，所以在70年代僅使用硬件就可以容易地實(shí)現(xiàn)算法。算法的重復(fù)特性非常適合專用芯片執(zhí)行。起初采用軟件執(zhí)行的DES顯得笨拙，但目前的軟件執(zhí)行效果也相當(dāng)不錯(cuò)。DES的核心是一個(gè)被稱為Feistel系統(tǒng)的部件。2.3.1DES算法描述(續(xù))DES是分組密碼，每個(gè)792.3.1DES算法描述(續(xù))圖2.11DES算法總體流程2.3.1DES算法描述(續(xù))圖2.11DES算法總體流802.3.1DES算法描述(續(xù))2.3.1DES算法描述(續(xù))812.3.1DES算法描述(續(xù))初始計(jì)算2.3.1DES算法描述(續(xù))初始計(jì)算822.3.1DES算法描述(續(xù))函數(shù)f(Ri-1,Ki)Ri-1擴(kuò)張E(Ri-1)KiB1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8置換f(Ri-1,Ki)圖2.12f函數(shù)計(jì)算結(jié)構(gòu)2.3.1DES算法描述(續(xù))函數(shù)f(Ri-1,Ki)832.3.1DES算法描述(續(xù))2.3.1DES算法描述(續(xù))842.3.1DES算法描述(續(xù))圖2.13DES的S盒2.3.1DES算法描述(續(xù))圖2.13DES的S盒852.3.1DES算法描述(續(xù))2.3.1DES算法描述(續(xù))862.3.1DES算法描述(續(xù))密鑰變換2.3.1DES算法描述(續(xù))密鑰變換872.3.1DES算法描述(續(xù))2.3.1DES算法描述(續(xù))882.3.2DES的安全

DES存在關(guān)于密鑰長度、疊代次數(shù)、S-盒設(shè)計(jì)準(zhǔn)則的問題。特別是S-盒以常量形式給出，但并未明確說明這些常量為何以這種形式出現(xiàn)。雖然IBM聲稱這些是經(jīng)過17年大量密碼分析得出的結(jié)果，但是人們還是十分擔(dān)心NSA的介入可能為算法安裝陷門以利于其解密。2.3.2DES的安全DES存在關(guān)于密鑰長度、疊代次892.3.2DES的安全(續(xù))(1)弱密鑰與半弱密鑰圖2.144個(gè)DES弱密鑰即EKEK(x)=x圖2.156對(duì)DES半弱密鑰即EK1EK2(x)=x2.3.2DES的安全(續(xù))(1)弱密鑰與半弱密鑰圖2.902.3.2DES的安全(續(xù))

(2)關(guān)于S盒NSA曾公布了一些關(guān)于S盒選擇的信息：1)沒有一個(gè)S盒的輸出是輸入的線性或仿射函數(shù)；2)改變S盒的一位輸入將至少引起2個(gè)輸出位的變化；3)固定輸入的某一位為0或1后，改變它周圍的位不應(yīng)導(dǎo)致輸出的0或1的個(gè)數(shù)不成比例的變化。2.3.2DES的安全(續(xù))(2)關(guān)于S盒912.3.2DES的安全(續(xù))

(3)加密輪數(shù)與差分分析攻擊差分分析通過微小差異的明文對(duì)，研究這些差異對(duì)所得密文的影響。如果同時(shí)更改輸入位的某些組合，輸出結(jié)果中的某些位也會(huì)以很高的概率、以特定方式變化。實(shí)踐表明，DES在小于16輪的情況下，差分攻擊的效率將明顯快于搜索全部密鑰空間的強(qiáng)力攻擊。2.3.2DES的安全(續(xù))(3)加密輪數(shù)與差分分922.3.2DES的安全(續(xù))(4)密鑰長度問題密鑰長度偏小一直是DES的一個(gè)安全問題。1)1977年，Diffie和Hellman估計(jì)如果花費(fèi)2千萬美元建造一臺(tái)機(jī)器，大約僅需一天就可以破譯DES。2)1993年，Wiener利用開關(guān)技術(shù)設(shè)計(jì)了更加有效的破譯DES設(shè)備。3)到1996年逐漸形成了3種破譯DES的基本方法。一種方法是利用分布計(jì)算；一種是設(shè)計(jì)專用攻擊芯片；折中的方法是使用可編程邏輯門陣列。2.3.2DES的安全(續(xù))(4)密鑰長度問題932.3.2DES的安全(續(xù))

4)分布計(jì)算方法破譯DES變得十分流行，特別是在Internet興起和壯大的情況下。1997年，RSA數(shù)據(jù)安全公司開展了破譯DES密鑰和其加密消息的競(jìng)賽。僅僅5個(gè)月，RockeVerser就在搜索了25%的密鑰空間后發(fā)現(xiàn)密鑰。接下來，RSA數(shù)據(jù)安全公司又開展了第二次競(jìng)賽。結(jié)果用時(shí)39天搜索了密鑰空間的85%發(fā)現(xiàn)了對(duì)應(yīng)密鑰。5)1998年，電子領(lǐng)域基金會(huì)(EFF)展開了一項(xiàng)名為DES破譯的計(jì)劃。計(jì)劃的基本思想是：一般使用的計(jì)算機(jī)對(duì)于完成破譯DES的任務(wù)來說不是最優(yōu)的。計(jì)劃使用的結(jié)構(gòu)是，硬件用來判定排除大量不可能的密鑰并返回那些可能的密鑰；軟件則用來處理每一個(gè)可能的密鑰，判定這些密鑰是否確實(shí)為密碼系統(tǒng)使用的密鑰。結(jié)果是計(jì)劃使用1500個(gè)芯片平均在大約在4.5天可以完成對(duì)DES的破譯。2.3.2DES的安全(續(xù))4)分布計(jì)算方法破譯942.3.2DES的安全(續(xù))6)有傳言說根據(jù)預(yù)先處理的不同，NSA可以在3到5分鐘成功破譯DES。而在機(jī)器方面的開銷僅有5萬美元。#上述結(jié)果說明對(duì)于90年代晚期的計(jì)算技術(shù)而言，加密系統(tǒng)使用56比特的密鑰已經(jīng)顯得過短，不能提供強(qiáng)有力的安全保護(hù)。2.3.2DES的安全(續(xù))6)有傳言說根據(jù)預(yù)先952.3.2DES的安全(續(xù))(5)增加安全性的DES變化2.3.2DES的安全(續(xù))(5)增加安全性的DES變化962.3.2DES的安全(續(xù))2.3.2DES的安全(續(xù))972.3.3AES算法描述1997年1月2日，國家標(biāo)準(zhǔn)與技術(shù)研究所(NIST)宣布，啟動(dòng)設(shè)計(jì)新的對(duì)稱分組加密算法，作為新一代加密標(biāo)準(zhǔn)替代DES。新的加密標(biāo)準(zhǔn)將被命名為高級(jí)加密標(biāo)準(zhǔn)(AES)。不同于暗箱設(shè)計(jì)過程的DES，AES的設(shè)計(jì)方案于1997年9月12向全世界公開征集。2.3.3AES算法描述1997年1月2日，國家標(biāo)準(zhǔn)982.3.3AES算法描述(續(xù))AES需要滿足下列要求：(1)必須詳細(xì)和公開說明對(duì)稱加密算法的設(shè)計(jì)原理。(2)算法必須支持最小128比特的消息分組，密鑰長度可以為128，192，256比特，而安全強(qiáng)度至少與三重DES相當(dāng)?shù)蕬?yīng)該高于三重DES。(3)算法適合于在各種硬件設(shè)備上執(zhí)行。(4)如果算法被選種，不應(yīng)該存在專利問題并可以在世界范圍內(nèi)使用。2.3.3AES算法描述(續(xù))AES需要滿足下列要求992.3.3AES算法描述(續(xù))

1998年8月20日，NIST公布了15個(gè)AES侯選算法，這些算法由遍布世界的密碼團(tuán)體的成員提交。公眾對(duì)這15個(gè)算法的評(píng)論被當(dāng)作初始評(píng)論(公眾的初始評(píng)論也被稱為第一輪)。第一輪于1999年4月15日截止。根據(jù)收到的分析和評(píng)論，NIST從15個(gè)算法中選出5個(gè)算法。2.3.3AES算法描述(續(xù))1998年8月20日，1002.3.3AES算法描述(續(xù))5個(gè)參加決賽的AES侯選算法是：MARS(來自IBM，在大型機(jī)上的實(shí)現(xiàn)進(jìn)行了優(yōu)化，個(gè)人計(jì)算機(jī)上就不那么有效了)；RC6(來自RSA實(shí)驗(yàn)室，它是RC5的延續(xù)，設(shè)計(jì)非常簡單，甚至可以靠記憶記住它)；Serpent(來自RossAnderson，EliBiham，和LarsKnudsen，該算法硬件實(shí)現(xiàn)很穩(wěn)定，以4位子處理器的并行操作為基礎(chǔ))；Twofish(來自BruceSchneier，JohnKelsey，DougWhiting，DavidWagner，ChrisHall，和NielsFerguson，開發(fā)者設(shè)計(jì)了一個(gè)替換表的設(shè)計(jì)方案，該方案依賴于加密密鑰而不是依賴固定的替換表)；Rijndael(來自JoanDaemen和VincentRijmen)。這些參加決賽的算法在又一次更深入的評(píng)論期(第二輪)得到進(jìn)一步的分析。2.3.3AES算法描述(續(xù))5個(gè)參加決賽的AES1012.3.3AES算法描述(續(xù))

在第二輪中，要征詢對(duì)候選算法的各方面的評(píng)論和分析，這些方面包括但不限于下面的內(nèi)容：密碼分析、知識(shí)產(chǎn)權(quán)、所有AES決賽侯選算法的剖析、綜合評(píng)價(jià)以及有關(guān)實(shí)現(xiàn)問題。在2000年5月15日第二輪公眾分析結(jié)束后，NIST匯集和研究了所有得到的信息，為最終選擇提供依據(jù)。2000年10月2日，NIST宣布它選中了Rijndael作為AES。NIST指出，之所以選擇Rijndael的原因是因?yàn)樗前踩?、性能、效率、?shí)現(xiàn)方便性和靈活性的最佳組合。2.3.3AES算法描述(續(xù))在第二輪中，要征詢對(duì)候1022.3.3AES算法描述(續(xù))有限域GF(pn)的知識(shí)2.3.3AES算法描述(續(xù))有限域GF(pn)的知識(shí)1032.3.3AES算法描述(續(xù))2.3.3AES算法描述(續(xù))1042.3.3AES算法描述(續(xù))2.3.3AES算法描述(續(xù))1052.3.3AES算法描述(續(xù))2.3.3AES算法描述(續(xù))1062.3.3AES算法描述(續(xù))算法架構(gòu)為使論述簡單，我們以使用128比特密鑰加密128比特消息為例說明，并且先對(duì)算法的整體架構(gòu)予以說明。算法由10輪組成。每一輪使用一個(gè)由原始密鑰產(chǎn)生的密鑰。第0輪使用原始的128比特密鑰。每一輪都是128比特輸入128比特輸出。AES的結(jié)構(gòu)如圖2.16。2.3.3AES算法描述(續(xù))算法架構(gòu)1072.3.3AES算法描述(續(xù))圖2.16AES的結(jié)構(gòu)2.3.3AES算法描述(續(xù))圖2.16AES的結(jié)構(gòu)1082.3.3AES算法描述(續(xù))每一輪由四個(gè)基本步驟稱為層(layers)組成：(1)字節(jié)轉(zhuǎn)換(TheByteSubTransformation)：這是一個(gè)非線性層主要用于防止差分和線性分析攻擊。(2)移動(dòng)行變換(TheShiftRowTransformation)：這是一個(gè)線性組合，可以導(dǎo)致多輪之間各個(gè)比特位間的擴(kuò)散。(3)混合列變換(TheMixColumnTransformation)：這一層的目的與移動(dòng)行變換相同。(4)輪密鑰加密變換(AddRoundKey)：輪密鑰與上一層的結(jié)果進(jìn)行異或操作。2.3.3AES算法描述(續(xù))每一輪由四個(gè)基本1092.3.3AES算法描述(續(xù))一輪的過程ByteSub(BS)ShiftRow(SR)MixColumn(MC)AddRoundKey(ARK)Rijndael加密(1)使用第0輪密鑰執(zhí)行ARK操作。(2)依次使用第1輪到9輪密鑰按順序執(zhí)行BS，SR，MC，和ARK操作。(3)使用第10輪密鑰按順序執(zhí)行BS，SR，和ARK操作。注意最后一輪忽略了混合列變換(MC)層。2.3.3AES算法描述(續(xù))一輪的過程ByteSubS1102.3.3AES算法描述(續(xù))層2.3.3AES算法描述(續(xù))層1112.3.3AES算法描述(續(xù))(1)字節(jié)轉(zhuǎn)換2.3.3AES算法描述(續(xù))(1)字節(jié)轉(zhuǎn)換1122.3.3AES算法描述(續(xù))2.3.3AES算法描述(續(xù))1132.3.3AES算法描述(續(xù))(2)移動(dòng)行變換2.3.3AES算法描述(續(xù))(2)移動(dòng)行變換1142.3.3AES算法描述(續(xù))(3)混合列變換2.3.3AES算法描述(續(xù))(3)混合列變換1152.3.3AES算法描述(續(xù))(4)輪密鑰加密變換2.3.3AES算法描述(續(xù))(4)輪密鑰加密變換1162.3.3AES算法描述(續(xù))輪密鑰產(chǎn)生方法2.3.3AES算法描述(續(xù))輪密鑰產(chǎn)生方法1172.3.3AES算法描述(續(xù))

解密字節(jié)轉(zhuǎn)換、移動(dòng)行變換、混合列變換、輪密鑰加密變換都存在相應(yīng)的逆變換：(1)字節(jié)轉(zhuǎn)換的逆變換可以通過查另一個(gè)表來完成，我們稱之為逆字節(jié)轉(zhuǎn)換(IBS)。(2)移動(dòng)行變換的逆變換可以通過字節(jié)右移來實(shí)現(xiàn)，我們稱之為逆移動(dòng)行變換(ISR)。(3)逆混合列變換(IMC)通過乘上另一個(gè)矩陣實(shí)現(xiàn)。

(4)輪密鑰加密變換實(shí)際上是自身的逆。2.3.3AES算法描述(續(xù))解密1182.3.3AES算法描述(續(xù))S-盒原理2.3.3AES算法描述(續(xù))S-盒原理1192.3.3AES算法描述(續(xù))2.3.3AES算法描述(續(xù))1202.3.3AES算法描述(續(xù))解密變換2.3.3AES算法描述(續(xù))解密變換1212.3.3AES算法描述(續(xù))Rijndael解密(1)使用第10輪密鑰執(zhí)行ARK操作。(2)依次使用第9輪到1輪密鑰按順序執(zhí)行IBS，ISR，IMC，和IARK操作。(3)使用第0輪密鑰按順序執(zhí)行IBS，ISR，和ARK操作。#為了保持結(jié)構(gòu)的一致性，在最后一輪加密中忽略了MC操作。2.3.3AES算法描述(續(xù))Rijndael解密(1)1222.3.4AES的安全與執(zhí)行

設(shè)計(jì)思考(1)由于加密和解密過程不一致，相比DES(全1密鑰，加密兩次恢復(fù)為本身)，相信AES不存在任何弱密鑰。(2)不同于Feistel系統(tǒng)，AES對(duì)輸入所有比特的處理相同，這使得輸入的擴(kuò)展速度很快。實(shí)踐表明兩輪計(jì)算就能得到充分?jǐn)U展，也就是說，所有的128比特輸出完全依賴于所有128比特輸入。(3)AES的S-盒的建立有明晰而簡單的代數(shù)意義，這樣可以避免任何建立在算法上的門陷，較好避免存在于DES的S-盒上的神秘色彩。AES的S-盒具有良好的非線性特性，它可以很好地用來阻止差分和線性分析。2.3.4AES的安全與執(zhí)行設(shè)計(jì)思考1232.3.4AES的安全與執(zhí)行(續(xù))(4)移動(dòng)行這一層可以很好地阻止新發(fā)現(xiàn)的截?cái)喙艉推椒焦簟?5)混合列可以達(dá)到字節(jié)擴(kuò)散的目的。這步1個(gè)輸入字節(jié)的改變導(dǎo)致所有4個(gè)輸出字節(jié)改變。(6)輪密鑰產(chǎn)生方法使用了密鑰位的非線性組合，因?yàn)樗褂昧薙-盒，這種非線性組合用來對(duì)付當(dāng)解密者知道了部分密鑰并以此推測(cè)余下部分的攻擊。循環(huán)常量(10)(i-4)/4是用來消除在循環(huán)過程中生成每個(gè)循環(huán)差別的對(duì)稱性。2.3.4AES的安全與執(zhí)行(續(xù))(4)移動(dòng)行1242.3.4AES的安全與執(zhí)行(續(xù))(7)輪次之所以選擇10，是因?yàn)樵?輪情況下存在比強(qiáng)力搜索攻擊更好的算法。到2004年，公布的密碼分析結(jié)果在7輪以上還沒有比強(qiáng)力搜索攻擊更好的辦法。多出4輪能夠讓人更有安全感。當(dāng)然，輪次還可以根據(jù)需要增加。2.3.4AES的安全與執(zhí)行(續(xù))(7)輪次之所1252.3.4AES的安全與執(zhí)行(續(xù))

執(zhí)行思考我們已經(jīng)看到Rijndael內(nèi)部的層是非常簡單的，它在很小的代數(shù)空間上即可完成。因此，可以高效完成這些層。從前面對(duì)Rijndael的內(nèi)部層描述可以看到，僅有SB/ISB和MC/IMC值得考慮它們的快速實(shí)現(xiàn)問題。(1)對(duì)于SB/ISB，我們建議使用S-盒查表方法：可以一次建立一個(gè)有28=256個(gè)字節(jié)的小表，長期使用(就是說，這個(gè)表可以“固化”在硬件或者是軟件中實(shí)現(xiàn))?！安楸矸ā辈粌H非常有效，還能阻止定時(shí)分析攻擊，這種攻擊根據(jù)不同數(shù)據(jù)的運(yùn)算時(shí)間差異，來推斷運(yùn)算是在比特0還是在比特1上運(yùn)行。2.3.4AES的安全與執(zhí)行(續(xù))執(zhí)行思考1262.3.4AES的安全與執(zhí)行(續(xù))(2)在MC操作中，有限域GF(28)上的兩個(gè)元的乘法操作也可以用“查表法”來實(shí)現(xiàn)：z=x

y(有限域乘法)，這里x

{01，10，11}和y

GF(28)。我們進(jìn)一步注意到字節(jié)01為有限域乘法單位元，也就是，01

y=y。因而無論用軟件還是硬件執(zhí)行“查表法”時(shí)只需要存儲(chǔ)2

256=512項(xiàng)，這個(gè)表是非常小的。這樣實(shí)現(xiàn)不僅速度很快，而且還能夠減少定時(shí)分析攻擊的危險(xiǎn)。(3)執(zhí)行IMC操作就不像執(zhí)行MC操作那么快。這是因?yàn)镮MC操作的4

4矩陣比MC操作的復(fù)雜得多，一般執(zhí)行IMC操作比MC操作需要多花費(fèi)30%的處理時(shí)間。然而，幸運(yùn)的是在一些應(yīng)用中解密是不需要的。2.3.4AES的安全與執(zhí)行(續(xù))(2)在MC1272.3.5對(duì)稱密碼的應(yīng)用(1)加密模式通常大多數(shù)消息的長度大于分組密碼的消息分組長度，長的消息被分成一系列連續(xù)排列的消息分組，密碼一次處理一個(gè)分組。在分組密碼的上層，不同的加密模式被開發(fā)出來，這些加密模式可以為整體消息加密提供一些希望得到的性質(zhì)。如：分組密碼的不確定性(隨機(jī)性)，將明文消息添加到任意長度(使得密文長度不必與相應(yīng)的明文長度相關(guān))，錯(cuò)誤傳播控制，流密碼的密鑰流生成。等等。2.3.5對(duì)稱密碼的應(yīng)用(1)加密模式1282.3.5對(duì)稱密碼的應(yīng)用(續(xù))密碼分組鏈接(CBC)模式C0P1EKC1P2EKC2…圖2.17CBC模式加密2.3.5對(duì)稱密碼的應(yīng)用(續(xù))密碼分組鏈接(CBC)模式1292.3.5對(duì)稱密碼的應(yīng)用(續(xù))2.3.5對(duì)稱密碼的應(yīng)用(續(xù))1302.3.5對(duì)稱密碼的應(yīng)用(續(xù))(2)修改發(fā)現(xiàn)碼(MDC)實(shí)例-使用DES的MDC-2

在分組密碼基礎(chǔ)上建立Hash函數(shù)的主要?jiǎng)訖C(jī)是：如果系統(tǒng)已經(jīng)擁有了非常有效的分組密碼，那么以分組密碼作為實(shí)現(xiàn)Hash函數(shù)的主要部件，將既可以提供Hash函數(shù)的功能，又能使額外開銷最小。2.3.5對(duì)稱密碼的應(yīng)用(續(xù))(2)修改發(fā)現(xiàn)碼1312.3.5對(duì)稱密碼的應(yīng)用(續(xù))2.3.5對(duì)稱密碼的應(yīng)用(續(xù))1322.3.5對(duì)稱密碼的應(yīng)用(續(xù))2.3.5對(duì)稱密碼的應(yīng)用(續(xù))1332.3.5對(duì)稱密碼的應(yīng)用(續(xù))Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iCR'iCLiCR'iCL'iCRiHiH'i圖2.18MDC-2原理圖2.3.5對(duì)稱密碼的應(yīng)用(續(xù))Eg(Hi-1)Eg'(H1342.3.5對(duì)稱密碼的應(yīng)用(續(xù))

(3)

基于CBC的消息認(rèn)證碼(MAC)定義26消息認(rèn)證碼(MAC)算法是帶有密鑰k的函數(shù)族hk，其具有如下性質(zhì)：1)易于計(jì)算：對(duì)于任何已知函數(shù)hk，給定值k和輸入x，值hk(x)容易計(jì)算出來。這個(gè)值被稱做MAC-值或MAC。2)壓縮：函數(shù)hk可以將任意有限比特長度的輸入x影射為固定n比特長度的位串。進(jìn)一步，給出函數(shù)族h的算法描述，對(duì)于任何一個(gè)固定符合要求的密鑰值k(攻擊者不知其值)，需要滿足如下性質(zhì)：3)計(jì)算抵抗：給定0個(gè)或多個(gè)消息-MAC值對(duì)(xi，hk(xi))，找到任意消息-MAC值對(duì)(x，hk(x))滿足x

xi在計(jì)算上不可能(當(dāng)然也包括某些i滿足hk(x)=hk(xi)的可能性)。2.3.5對(duì)稱密碼的應(yīng)用(續(xù))(3)基于CBC的1352.3.5對(duì)稱密碼的應(yīng)用(續(xù))2.3.5對(duì)稱密碼的應(yīng)用(續(xù))1362.3.5對(duì)稱密碼的應(yīng)用(續(xù))M10EkH1M2EkH2…Ht-1MtEkHtEkDk'Ht可選圖2.19基于CBC的MAC原理圖2.3.5對(duì)稱密碼的應(yīng)用(續(xù))M10EkH1M2EkH21372.4公鑰密碼體制：RSA和ElGamal體制

2.4.1RSA體制Diffie和Hellman提出了建立公鑰密碼系統(tǒng)的可能性。但是，他們并沒有提出公鑰密碼算法。接下來的幾年，一些公鑰密碼算法相繼被提出。其中最為成功的依賴大整數(shù)分解困難性的公鑰密碼算法，于1977年由Rivest，Shamir，和Adleman提出。這也就是我們熟知的RSA算法。雖然經(jīng)過長期的密碼分析并不能證明也不能否定RSA的安全，但是這也無疑給了算法的安全性一定承諾。2.4公鑰密碼體制：RSA和ElGamal體制2.1382.4.1RSA體制(續(xù))

注意這里講到的公鑰密碼算法，都是假定發(fā)送消息者已經(jīng)得到接受者一份真實(shí)的公開密鑰拷貝。現(xiàn)實(shí)中，有許多技術(shù)保障真實(shí)公開密鑰分配，包括：在可信信道上交換密鑰，使用可信公開文件，使用在線可信服務(wù)器或使用離線服務(wù)器和證書。2.4.1RSA體制(續(xù))注意這里講到的公鑰密碼算法1392.4.1RSA體制(續(xù))RSA加密2.4.1RSA體制(續(xù))RSA加密1402.4.1RSA體制(續(xù))2.4.1RSA體制(續(xù))141