2.1.1什么是密碼學(xué)(續(xù))通信中的參與者發(fā)送者(Alice)：在雙方交互中合法的信息發(fā)送實(shí)體。接收者(Bob)：在雙方交互中合法的信息接收實(shí)體。分析者(Eve)：破壞通信接收和發(fā)送雙方正常平安通信的其他實(shí)體。可以采取被動(dòng)攻擊和主動(dòng)攻擊的手段。信道信道：從一個(gè)實(shí)體向另一個(gè)實(shí)體傳遞信息的通路。平安信道：分析者沒(méi)有能力對(duì)其上的信息進(jìn)展閱讀、刪除、修改、添加的信道。5精精選選文檔(3)公共信道：分析者可以任意對(duì)其上的信2.1.2對(duì)稱與非對(duì)稱密碼思想(續(xù))加密器EK

(m)=c1分析者Eve解密器明文消息源目的地mDK

(c)=

m2mc公共信道AliceBob#

非對(duì)稱密碼加密密鑰與解密密鑰不同：K1

K2代表系統(tǒng)：RSA和ElGamal精精選選文檔82.1.3密碼學(xué)的演進(jìn)及目前的狀態(tài)安全依賴于保密加密方法安全依賴于保密密鑰安全依賴于保密部分密鑰古典密碼精精選選文檔9私鑰密碼公鑰密碼#公鑰密碼體制以其強(qiáng)大的功能使得私鑰密

碼體制顯得已經(jīng)過(guò)時(shí)，但是強(qiáng)大的功能不是

無(wú)代價(jià)獲得的，公鑰

密碼的計(jì)算量遠(yuǎn)大于

一樣情況下的私鑰密

碼。因此，不適合加

密大量數(shù)據(jù)，只適合

于完成少量數(shù)據(jù)加密，如傳送私鑰密碼的密

鑰、簽名等等。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)SecurityPrimitivesPublic-keyPrimitivesSymmetric-keyPrimitivesUnkeyedPrimitivesArbitrary

length

hash

functionsSymmetric-key

ciphersRandom

sequencesOne-way

permutationsBlockciphersStreamciphersArbitrary

length

hash

functions(MACs)SignaturesPseudorandom

sequencesIdentification

primitivesPublic-key

ciphersSignaturesIdentification

primitives圖2.2密碼學(xué)本原分類10精精選選文檔2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(1)加密加密根本術(shù)語(yǔ)明文消息空間M:某個(gè)字母表集密文消息空間C:可能的密文消息集加/解密密鑰空間K:可能的加/解密密鑰集加/解密函數(shù)Ee K

(m M)

/

Dd K

(c C)

:

一個(gè)從M到C/C到M的有效變換精精選選文檔112.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，那么，就是私鑰加密方案。#私鑰加密需要一條平安信道來(lái)建立密鑰對(duì)。主要技術(shù)：分組密碼與流密碼定義4(分組密碼)將明文消息在編碼集按照固定長(zhǎng)度t進(jìn)展分組，再一組一組地加\解密明\密文消息。#著名的DES、AES都是這類密碼。精精選選文檔132.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))定義5

K

是加密變換集的密鑰空間，序列e1e2…ei

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

di為ei的逆，解密那么通過(guò)mi=Ddi(ci)完成。精精選選文檔142.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))公鑰加密定義7一個(gè)由加密函數(shù)集{Ee:e精精選選文檔15K}和解密函數(shù)集{Dd:

d

K}組成加密方案，每一個(gè)相關(guān)聯(lián)的加/解密密鑰對(duì)(e,

d)，加密密鑰e公開(kāi)，稱為公開(kāi)密鑰，而解密密鑰d保密，稱為秘密密鑰。#顯然平安公鑰密碼系統(tǒng)要求從e計(jì)算d為不可能。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))公鑰加密實(shí)例Ee(m1)=c1A1Ee(m2)=c2A2Ee(m3)=c3A3Dd(c1)=m1d

2D

(c

)=m2Dd(c3)=m3Bobec1eec2c316#因?yàn)榇嬖谔娲魡?wèn)題，公鑰系統(tǒng)中公開(kāi)密鑰e必須認(rèn)證，一般是建立精P精選K選文I檔。2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(2)數(shù)字簽名技術(shù)根本術(shù)語(yǔ)明文消息空間M:某個(gè)字母表中串的集合簽名空間S:可能的簽名集合簽名密鑰空間K:用于生成簽名的可能密鑰集，具體取值k需要保密驗(yàn)證密鑰空間K’:用于驗(yàn)證簽名的可能密鑰集，具體取值k’需要公開(kāi)簽名函數(shù)SK(m M):從M到S的有效變換驗(yàn)證函數(shù)VK’(m M,

s):一個(gè)從M S到輸出{True,False}的有效變換17精精選選文檔2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))簽名過(guò)程簽名(簽名者完成)對(duì)一條需要簽名的消息m M計(jì)算簽名s=Sk(m)。將對(duì)消息m的簽名(m,s)發(fā)送出去。驗(yàn)證(驗(yàn)證者完成)得到對(duì)應(yīng)簽名者的驗(yàn)證算法Vk’，計(jì)算

u=Vk’(m,s)。2)如果u=True，承受簽名；如果u=False，拒絕簽名。精精選選文檔

182.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))簽名和認(rèn)證函數(shù)必須滿足的性質(zhì)當(dāng)且僅當(dāng)Vk’(m,s)=True時(shí)，s是消息m的合法簽名。對(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)展仲裁。精精選選文檔192.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))數(shù)字簽名技術(shù)在公鑰根底設(shè)施(PKI)中的應(yīng)用除非對(duì)密鑰產(chǎn)生的認(rèn)證性和合法性有足夠的信任，否那么公鑰密碼的優(yōu)勢(shì)就十分有限。公鑰根底設(shè)施或簡(jiǎn)稱PKI是一個(gè)框架。這個(gè)框架主要由一組策略組成。策略確切定義了關(guān)于密碼系統(tǒng)運(yùn)行和密鑰產(chǎn)生和發(fā)布與證書(shū)的規(guī)那么。X.509是設(shè)計(jì)用來(lái)在大型計(jì)算機(jī)網(wǎng)絡(luò)中提供目錄認(rèn)證效勞的國(guó)際標(biāo)準(zhǔn)。由于它本身是ISO/ITU的一個(gè)標(biāo)準(zhǔn)，很多實(shí)用產(chǎn)品都基于它開(kāi)發(fā)出來(lái)。例如，X.509被用

在Visa和Mastercard的平安電子交易標(biāo)準(zhǔn)中。精精選選文檔202.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))圖2.3

X.509的構(gòu)造原理精精選選文檔212.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))精精選選文檔222.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))A6A1認(rèn)證VT(A6

||

e6

,

s6)秘密密鑰

d6A3,

e3,

ST(A3

||

e3)=s3A4,

e4,

ST(A4

||

e4)=s4e6,

s6Dd6(c)=mc

=

Ee6(m)Public

file精精選選文檔23A1,

e1,

ST(A1

||

e1)=s1A5,

e5,

ST(A5

||

e5)=s5A6,

e6,

ST(A6

||

e6)=s6A2,

e2,

ST(A2

||

e2)=s2圖2.4證書(shū)認(rèn)證過(guò)程#證書(shū)權(quán)威負(fù)荷小(離線、非交互、存儲(chǔ)證書(shū))，權(quán)限低2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))公鑰證書(shū)的產(chǎn)生情況1可信方產(chǎn)生密鑰對(duì)?？尚欧綖閷?shí)體產(chǎn)生公鑰算法的密鑰對(duì)，并將公開(kāi)密鑰和綁定身份的公鑰證書(shū)通過(guò)公共信道發(fā)給該實(shí)體。實(shí)體在證明了自己的身份(例如，出示身份證或個(gè)人可信照片)后，將通過(guò)平安信道得到對(duì)應(yīng)的秘密密鑰。情況2實(shí)體產(chǎn)生自己的密鑰對(duì)。實(shí)體產(chǎn)生自己的公鑰算法的密鑰對(duì)，并平安地將公開(kāi)密鑰傳送給可信方(例如，通過(guò)可信通道或派人送達(dá))，這里主要是保證公開(kāi)密鑰的真實(shí)性。在驗(yàn)證了公開(kāi)密鑰來(lái)源的真實(shí)性后，精精選選文檔

242.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))證書(shū)鏈和證書(shū)路徑25圖2.5證精書(shū)精選選文鏈檔2.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(3)認(rèn)證與鑒別技術(shù)鑒別或?qū)嶓w認(rèn)證定義9鑒別或?qū)嶓w認(rèn)證是一個(gè)過(guò)程。在這個(gè)過(guò)程中一方通過(guò)獲得一些確定的證據(jù)來(lái)確認(rèn)參加實(shí)體認(rèn)證的另一方的身份，而具有相應(yīng)身份的實(shí)體也確實(shí)就是正在參與這一認(rèn)證過(guò)程的另一方。例子1實(shí)體A與B通，如果A與B認(rèn)識(shí)就可以通過(guò)聲音來(lái)確定對(duì)方的真實(shí)性。例子2實(shí)體A通過(guò)信用卡在銀行ATM機(jī)上取錢(qián)。#特點(diǎn)：時(shí)實(shí)性。精精選選文檔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來(lái)冒充A。c(不可冒充性)任何一個(gè)非宣稱者A的C想通過(guò)扮演A的身份，通過(guò)驗(yàn)證者B的認(rèn)證，讓B承受A的身份的可能性可以忽略。這里，可以忽略的含義是概率小到?jīng)]有具體的實(shí)際意義，準(zhǔn)確的度量需要根據(jù)實(shí)際應(yīng)用而定。d即使如下情況存在，以上三個(gè)條件仍然成立。1宣稱者A和驗(yàn)證者B之間以前進(jìn)展的多項(xiàng)式次認(rèn)證會(huì)話且被竊聽(tīng);冒充者C以前參與了同宣稱者A或〔和〕驗(yàn)證者B的認(rèn)證執(zhí)行;冒充者C可能發(fā)起多個(gè)認(rèn)證會(huì)話并行運(yùn)行。精精選選文檔272.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))數(shù)據(jù)源認(rèn)證定義10

數(shù)據(jù)源認(rèn)證或消息認(rèn)證技術(shù)，提供一方通過(guò)一些附加的證據(jù)，確定消息的產(chǎn)生一方的真實(shí)身份。例子3

實(shí)體A向?qū)嶓wB發(fā)送電子郵件，電子郵件通過(guò)網(wǎng)絡(luò)傳輸并存儲(chǔ)，在某個(gè)時(shí)間由B接收到，由于沒(méi)有直接通信，B這時(shí)可能要求認(rèn)證郵件確實(shí)來(lái)自A。精精選選文檔282.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))(4)密碼Hash函數(shù)技術(shù)定義11

Hash函數(shù)h()是一個(gè)有效的計(jì)算方法，它將一個(gè)任意長(zhǎng)度的二進(jìn)制位串影射成固定長(zhǎng)度的二進(jìn)制位串，這個(gè)固定長(zhǎng)度的二進(jìn)制位串叫Hash值。修改發(fā)現(xiàn)碼(MDCs)附加性質(zhì)Hash函數(shù)是單向函數(shù)，即給定y，找到任意x，滿足y=h(x)計(jì)算不可能。x，找x"，滿足h(x)=h(x")計(jì)算不可能。找一任意對(duì)x和x"，滿足h(x)=h(x")計(jì)算不可能。

#修改發(fā)現(xiàn)碼可以進(jìn)一步分類，單向Hash函數(shù)(1-2)(OWHFs)和碰撞抵抗Hash函數(shù)(2-3)(CRHFs)。精精選選文檔292.1.4現(xiàn)代密碼學(xué)主要技術(shù)(續(xù))消息認(rèn)證碼(MACs)消息認(rèn)證碼的目的，通俗講就是不附加任何其他機(jī)制，確保消息來(lái)源的真實(shí)性的Hash函數(shù)。消息認(rèn)證碼有兩個(gè)不同功能的參數(shù)，即消息和秘密密鑰。Hash函數(shù)無(wú)密鑰有密鑰修改發(fā)現(xiàn)碼(MDCs)其他應(yīng)用 其他應(yīng)用消息認(rèn)證碼(MACs)30圖2.6密碼Hash函精精選數(shù)選文檔的簡(jiǎn)單分類2.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à)。精精選選文檔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ì)算法的保密。精精選選文檔322.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))Shannon提出的“優(yōu)質(zhì)〞密碼算法特征加解密的工作量由所要求的平安程度決定。密鑰集合和加密算法不應(yīng)該過(guò)于復(fù)雜。執(zhí)行過(guò)程應(yīng)該盡量簡(jiǎn)單。密碼中的過(guò)失不應(yīng)該具有傳播性。加密后的文本大小不應(yīng)該比原始報(bào)文更大。精精選選文檔332.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))“可信賴的〞加密體制的特點(diǎn)有可靠的數(shù)學(xué)根底。經(jīng)過(guò)專家的嚴(yán)格分析，證實(shí)是可靠的。經(jīng)得起時(shí)間的檢驗(yàn)。精精選選文檔342.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))平安評(píng)估模型(1)無(wú)條件平安(信息論意義下平安)a無(wú)論攻擊者具有何種計(jì)算能力，都無(wú)法破解密碼。b

Shannon證明無(wú)條件平安需要私鑰加密中密鑰的長(zhǎng)度與加密信息的長(zhǎng)度相等。c私鑰加密中有一次一密亂碼本(one-time

pad)是無(wú)條件平安的密碼。d公鑰密碼中沒(méi)有。精精選選文檔352.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))(2)計(jì)算復(fù)雜理論下平安限定攻擊者的計(jì)算能力為多項(xiàng)式能力(P)，證明破譯密碼需要指數(shù)能力(NP)。精精選選文檔362.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))(3)規(guī)約平安規(guī)約破解密碼的能力為一個(gè)數(shù)論(通常是)中的著名困難問(wèn)題，如RSA問(wèn)題或Diffie-Hellman問(wèn)題。步驟通常如下：a刻畫(huà)平安模型。b在平安模型下，定義密碼算法需要到達(dá)的平安目標(biāo)。c描述密碼算法。d規(guī)約密碼算法可以到達(dá)設(shè)定的平安目標(biāo)。#可以看作放寬條件的計(jì)算復(fù)雜理論下平安或下面所說(shuō)的計(jì)算平安的特殊子類，這一方法是目前比較實(shí)用的公鑰密碼分析技術(shù)。精精選選文檔372.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))(4)計(jì)算平安在的攻擊方法和攻擊者的計(jì)算能力下，攻擊密碼成功的可能性是可以忽略的。特點(diǎn)：依賴?yán)щy問(wèn)題，但不存在等價(jià)證明，大多數(shù)私鑰密碼屬于這一類平安，也稱為

實(shí)踐平安。精精選選文檔382.1.5評(píng)價(jià)現(xiàn)代密碼算法的標(biāo)準(zhǔn)(續(xù))(5)啟發(fā)式平安根據(jù)列出的著名攻擊方法，結(jié)合使用的困難問(wèn)題對(duì)密碼進(jìn)展逐條啟發(fā)示分析，得出平安結(jié)論。很多高層復(fù)雜的密碼協(xié)議通常采用這種方法，但經(jīng)過(guò)這種分析方法的協(xié)議只能得到一定程度的計(jì)算復(fù)雜平安。缺點(diǎn)：攻擊的具體手段和方法可能無(wú)法窮盡，而且，設(shè)計(jì)者即使知道某一個(gè)攻擊方法未必就可以設(shè)計(jì)出一個(gè)真正能抵抗這一攻擊的密碼，因此，設(shè)計(jì)的密碼常常仍然存在漏洞。精精選選文檔392.2現(xiàn)代密碼學(xué)的理論根底現(xiàn)代密碼學(xué)要求很高的數(shù)學(xué)根底，包括：數(shù)論、抽象代數(shù)與有限域、計(jì)算復(fù)雜理論、信息論、概率論等。但是掌握根底的密碼算法并不需要精通過(guò)多的底層數(shù)學(xué)理論。這里我們僅講述掌握根本的密碼算法所需要的計(jì)算復(fù)雜理論、數(shù)論等的根底知識(shí)。精精選選文檔402.2.1計(jì)算復(fù)雜理論如果加密算法建立在一個(gè)非常難解決的問(wèn)題或者可能解的數(shù)目巨大的問(wèn)題之上，那么攻擊者要破譯算法就注定要完成一個(gè)即便不是不可能，也是另人沮喪的任務(wù)。即使有計(jì)算機(jī)的支持，一個(gè)窮盡的暴力解答也是不可行的。NP完全問(wèn)題就是這樣一類具有計(jì)算復(fù)雜特點(diǎn)的問(wèn)題。我們用非形式化的方式來(lái)描述

NP完全問(wèn)題。精精選選文檔412.2.1計(jì)算復(fù)雜理論(續(xù))NP完全問(wèn)題幾個(gè)具體實(shí)例例子4

可滿足問(wèn)題給定邏輯公式滿足如下條件：它由變量v1，v2，…，vn和它們的邏輯非?v1，?v2，…，?vn

組成。它表現(xiàn)為一系列子句，且每個(gè)子句的形式是變量以及邏輯非的邏輯或(

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

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

v3) (?

v1

?

v3)為可滿足的，(v2

v3) (?

v精1

精選選文檔?

v3) (?

v2)為不可滿足42

的2.2.1計(jì)算復(fù)雜理論(續(xù))例子5背包問(wèn)題精精選選文檔432.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)，但無(wú)5頂點(diǎn)的團(tuán)。圖2.7圖的團(tuán)子圖精精選選文檔442.2.1計(jì)算復(fù)雜理論(續(xù))NP完全問(wèn)題的特征每個(gè)問(wèn)題都有解法，且總有一個(gè)相對(duì)簡(jiǎn)單的解法(盡管該解法也許十分耗時(shí))。如果要列舉所有可能性，就需要考慮2n中情況(n與問(wèn)題有關(guān))這些問(wèn)題是無(wú)關(guān)的，分別來(lái)自邏輯學(xué)、數(shù)論和圖論。如果能完全猜中，那么可以在相對(duì)較少的時(shí)間內(nèi)求解每一個(gè)問(wèn)題。精精選選文檔452.2.1計(jì)算復(fù)雜理論(續(xù))

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

EXP。精選精文選檔

462.2.1計(jì)算復(fù)雜理論(續(xù))NP完全的含義Cook證明了：如果可滿足問(wèn)題有一個(gè)確定性的、多項(xiàng)式時(shí)間的算法(不帶猜測(cè))，那么對(duì)NP中的每個(gè)問(wèn)題都會(huì)有一個(gè)確定性、多項(xiàng)式時(shí)間的算法，即NP=P。Karp證明了背包問(wèn)題和團(tuán)問(wèn)題具有和可滿足問(wèn)題一樣的性質(zhì)。這一問(wèn)題的逆否命題是：如果可以證明這些問(wèn)題中的某個(gè)問(wèn)題沒(méi)有在多項(xiàng)

式時(shí)間內(nèi)完成確實(shí)定性算法，那么它們中所有問(wèn)

題都不存在確定性多項(xiàng)式時(shí)間算法。這里對(duì)一個(gè)

問(wèn)題的解決是要求找到一個(gè)通用算法來(lái)解決它的

每個(gè)實(shí)例。47精精選選文檔2.2.1計(jì)算復(fù)雜理論(續(xù))圖2.8復(fù)雜性的層次構(gòu)造#

P=NP或P

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

3

5

7

11

13

17

19

23

29

31

37

41

43

47

53

59

61

6771

73

79

83

89

97

101

103

107

109

113

127

131

137139

149

151

157

163

167

173

179

181

191

193

1971992.2.2數(shù)論知識(shí)(續(xù))精精選選文檔562.2.2數(shù)論知識(shí)(續(xù))精精選選文檔572.2.2數(shù)論知識(shí)(續(xù))精精選選文檔582.2.2數(shù)論知識(shí)(續(xù))精精選選文檔592.2.2數(shù)論知識(shí)(續(xù))精精選選文檔602.2.2數(shù)論知識(shí)(續(xù))整數(shù)唯一分解定理精精選選文檔612.2.2數(shù)論知識(shí)(續(xù))精精選選文檔622.2.2數(shù)論知識(shí)(續(xù))一次不定方程精精選選文檔632.2.2數(shù)論知識(shí)(續(xù))(2)同余同余定義與概念精精選選文檔642.2.2數(shù)論知識(shí)(續(xù))精精選選文檔652.2.2數(shù)論知識(shí)(續(xù))剩余類和完全剩余類精精選選文檔662.2.2數(shù)論知識(shí)(續(xù))縮系精精選選文檔672.2.2數(shù)論知識(shí)(續(xù))精精選選文檔682.2.2數(shù)論知識(shí)(續(xù))精精選選文檔692.2.2數(shù)論知識(shí)(續(xù))一次同余式精精選選文檔702.2.2數(shù)論知識(shí)(續(xù))精精選選文檔712.2.2數(shù)論知識(shí)(續(xù))(3)原根精精選選文檔722.2.2數(shù)論知識(shí)(續(xù))精精選選文檔732.2.2數(shù)論知識(shí)(續(xù))精精選選文檔742.2.2數(shù)論知識(shí)(續(xù))精精選選文檔752.2.3群環(huán)域的概念(1)群精精選選文檔762.2.3群環(huán)域的概念(續(xù))精精選選文檔772.2.3群環(huán)域的概念(續(xù))(2)環(huán)精精選選文檔782.2.3群環(huán)域的概念(續(xù))精精選選文檔792.2.3群環(huán)域的概念(續(xù))(3)域精精選選文檔802.3對(duì)稱密碼技術(shù)對(duì)稱密鑰體制的問(wèn)題在平安加密體制中，密鑰是需要經(jīng)常變更的，使得已喪失的密鑰只能泄露數(shù)量有限的信息。密鑰的分發(fā)必須保證平安。一種方式就是對(duì)密鑰分解分發(fā)，如圖2.9。密鑰數(shù)目的增長(zhǎng)與交換信息的人數(shù)的平方成正比，在人數(shù)多的時(shí)候，可以考慮使用信任中心，如圖2.10。精精選選文檔812.3對(duì)稱密碼技術(shù)(續(xù))圖2.9密鑰的分塊分發(fā)圖2.10加密信精精選息選文檔分發(fā)中心822.3.1

DES算法描述1974年，IBM向國(guó)家標(biāo)準(zhǔn)局(NBS)提交了一個(gè)名為L(zhǎng)UCIFER的加密算法。NBS將其轉(zhuǎn)給了國(guó)家平安局(NSA)進(jìn)展審定，之后就得到了一個(gè)名為數(shù)據(jù)加密標(biāo)準(zhǔn)DES的算法。1977年，NBS正式將其用于無(wú)限制級(jí)的政府通信。其間NBS和NSA可能存在某些誤會(huì)。NSA原本打算DES僅用于硬件執(zhí)行，但是NBS卻公布了過(guò)多的技術(shù)細(xì)節(jié)以致于人們可以根據(jù)其寫(xiě)出DES加密軟件。如果NSA預(yù)料到后續(xù)的情況開(kāi)展變化，他們或許不會(huì)同意公布DES。精精選選文檔832.3.1

DES算法描述(續(xù))DES是分組密碼，每個(gè)分組為64比特?cái)?shù)據(jù)。

64比特明文通過(guò)加密最后成為64比特密文。

DES的密鑰通常寫(xiě)為64比特，但每8比特有一位奇偶效驗(yàn)位，可以忽略。因此，實(shí)際只有

56比特。算法只使用不超過(guò)64位的標(biāo)準(zhǔn)算術(shù)操作和邏輯操作，所以在70年代僅使用硬件就可以容易地實(shí)現(xiàn)算法。算法的重復(fù)特性非常適合專用芯片執(zhí)行。起初采用軟件執(zhí)行的

DES顯得笨拙，但目前的軟件執(zhí)行效果也相

當(dāng)不錯(cuò)。DES的核心是一個(gè)被稱為Feistel系統(tǒng)的部件。精精選選文檔842.3.1

DES算法描述(續(xù))明文IPL0R0K1fL1R1L16R16IP-1密文85精選精選文檔圖2.11

DES算法總體流程2.3.1

DES算法描述(續(xù))精精選選文檔862.3.1

DES算法描述(續(xù))初始計(jì)算精精選選文檔872.3.1

DES算法描述(續(xù))精精選選文檔892.3.1

DES算法描述(續(xù))圖2.13

DES的S盒90精精選選文檔2.3.1

DES算法描述(續(xù))精精選選文檔912.3.1

DES算法描述(續(xù))密鑰變換精精選選文檔922.3.1

DES算法描述(續(xù))精精選選文檔932.3.2

DES的平安DES存在關(guān)于密鑰長(zhǎng)度、疊代次數(shù)、S-盒

設(shè)計(jì)準(zhǔn)那么的問(wèn)題。特別是S-盒以常量形式給出，但并未明確說(shuō)明這些常量為何以這種形式出現(xiàn)。雖然IBM聲稱這些是經(jīng)過(guò)17年大量密碼分析得出的結(jié)果，但是人們還是十分擔(dān)憂NSA的介入可能為算法安裝陷

門(mén)以利于其解密。精精選選文檔942.3.2

DES的平安(續(xù))(1)弱密鑰與半弱密鑰圖2.14

4個(gè)DES弱密鑰即EKEK(x)=x95圖2.15

6對(duì)DES半弱密鑰精即精選選文E檔K1EK2(x)=x2.3.2

DES的平安(續(xù))(2)關(guān)于S盒NSA曾公布了一些關(guān)于S盒選擇的信息：沒(méi)有一個(gè)S盒的輸出是輸入的線性或仿射函數(shù)；改變S盒的一位輸入將至少引起2個(gè)輸出位的變化；固定輸入的某一位為0或1后，改變它周?chē)奈徊粦?yīng)導(dǎo)致輸出的0或1的個(gè)數(shù)不成比例的變化。精精選選文檔962.3.2

DES的平安(續(xù))(3)加密輪數(shù)與差分分析攻擊差分分析通過(guò)微小差異的明文對(duì)，研究這些差異對(duì)所得密文的影響。如果同時(shí)更改輸入位的某些組合，輸出結(jié)果中的某些位也會(huì)以很高的概率、以特定方式變化。實(shí)踐說(shuō)明，DES在小于

16輪的情況下，差分攻擊的效率將明顯快于搜索全部密鑰空間的強(qiáng)力攻擊。精精選選文檔972.3.2

DES的平安(續(xù))(4)密鑰長(zhǎng)度問(wèn)題密鑰長(zhǎng)度偏小一直是DES的一個(gè)平安問(wèn)題。1977年，Diffie和Hellman估計(jì)如果花費(fèi)2千萬(wàn)美元建造一臺(tái)機(jī)器，大約僅需一天就可以破譯

DES。1993年，Wiener利用開(kāi)關(guān)技術(shù)設(shè)計(jì)了更加有效的破譯DES設(shè)備。到1996年逐漸形成了3種破譯DES的根本方法。一種方法是利用分布計(jì)算；一種是設(shè)計(jì)專用攻擊芯片；折中的方法是使用可編程邏輯門(mén)陣列。精精選選文檔982.3.2

DES的平安(續(xù))分布計(jì)算方法破譯DES變得十分流行，特別是在Internet興起和壯大的情況下。1997年，RSA數(shù)據(jù)平安公司開(kāi)展了破譯DES密鑰和其加密消息的競(jìng) 。僅僅5個(gè)月，Rocke

Verser

就在搜索了25%的密鑰空間后發(fā)現(xiàn)密鑰。接下來(lái)，RSA數(shù)據(jù)平安公司又開(kāi)展了第二次競(jìng) 。結(jié)果用時(shí)39天搜索了密鑰空間的85%發(fā)現(xiàn)了對(duì)應(yīng)密鑰。1998年，電子領(lǐng)域基金會(huì)(EFF)展開(kāi)了一項(xiàng)名為DES破譯的方案。方案的根本思想是：一般使用的計(jì)算機(jī)對(duì)于完成破譯

DES的任務(wù)來(lái)說(shuō)不是最優(yōu)的。方案使用的構(gòu)造是，硬件用來(lái)判定排除大量不可能的密鑰并返回那些可能的密鑰；軟件那么用來(lái)處理每一個(gè)可能的密鑰，判定這些密鑰是否確實(shí)為密碼系統(tǒng)使用的密鑰。結(jié)果是方案使用1500個(gè)芯片平均在大約在4.5天可以完成對(duì)DES的破譯。精精選選文檔992.3.2

DES的平安(續(xù))6)有傳言說(shuō)根據(jù)預(yù)先處理的不同，NSA可以在3到5分鐘成功破譯DES。而在機(jī)器方面的開(kāi)銷(xiāo)僅有5萬(wàn)美元。#上述結(jié)果說(shuō)明對(duì)于90年代晚期的計(jì)算技術(shù)而言，加密系統(tǒng)使用56比特的密鑰已經(jīng)顯得過(guò)短，不能提供強(qiáng)有力的平安保護(hù)。精精選選文檔1002.3.2

DES的平安(續(xù))(5)增加平安性的DES變化精精選選文檔1012.3.2

DES的平安(續(xù))精精選選文檔1022.3.3

AES算法描述1997年1月2日，國(guó)家標(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ì)過(guò)程的DES，AES的設(shè)計(jì)方案

于1997年9月12向全世界公開(kāi)征集。精精選選文檔1032.3.3

AES算法描述(續(xù))AES需要滿足以下要求：必須詳細(xì)和公開(kāi)說(shuō)明對(duì)稱加密算法的設(shè)計(jì)原理。算法必須支持最小128比特的消息分組，密鑰長(zhǎng)度可以為128，192，256比特，而平安強(qiáng)度至少與三重DES相當(dāng)?shù)蕬?yīng)該高于三重DES。算法適合于在各種硬件設(shè)備上執(zhí)行。如果算法被選種，不應(yīng)該存在專利問(wèn)題并可以在世界范圍內(nèi)使用。精精選選文檔1042.3.3

AES算法描述(續(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è)算法。精精選選文檔1052.3.3

AES算法描述(續(xù))5個(gè)參加決的AES侯選算法是：MARS(來(lái)自IBM，在大型機(jī)上的實(shí)現(xiàn)進(jìn)展了優(yōu)化，個(gè)人計(jì)算機(jī)上就不那么有效了)；RC6(來(lái)自RSA實(shí)驗(yàn)室，它是RC5的延續(xù)，設(shè)計(jì)非常簡(jiǎn)單，甚至可以靠記憶記住它)；

Serpent(來(lái)自Ross

Anderson，

Eli

Biham，和LarsKnudsen，該算法硬件實(shí)現(xiàn)很穩(wěn)定，以4位子處理器的并行操作為根底)；

Twofish(來(lái)自BruceSchneier，John

Kelsey，Doug

Whiting，DavidWagner，Chris

Hall，和Niels

Ferguson，開(kāi)發(fā)者設(shè)計(jì)了一個(gè)替換表的設(shè)計(jì)方案，該方案依賴于加密

密鑰而不是依賴固定的替換表)

；Rijndael(來(lái)自Joan

Daemen和Vincent

Rijmen)

。這些參加決

的算法在又一次更深入的評(píng)論期(第二輪)得到進(jìn)一

步的分析。精精選選文檔1062.3.3

AES算法描述(續(xù))在第二輪中，要征詢對(duì)候選算法的各方面的評(píng)論和分析，這些方面包括但不限于下面的內(nèi)容：密碼分析、知識(shí)產(chǎn)權(quán)、所有AES決賽

侯選算法的剖析、綜合評(píng)價(jià)以及有關(guān)實(shí)現(xiàn)問(wèn)題。在2000年5月15日第二輪公眾分析完畢

后，NIST聚集和研究了所有得到的信息，為最終選擇提供依據(jù)。2000年10月2日，NIST宣布它選中了Rijndael作為AES。NIST指出，之所以選擇Rijndael的原因是因?yàn)樗瞧桨残?、性能、效率、?shí)現(xiàn)方便性和靈活性的最正確組合。精精選選文檔1072.3.3

AES算法描述(續(xù))有限域GF(pn)的知識(shí)精精選選文檔1082.3.3

AES算法描述(續(xù))精精選選文檔1092.3.3

AES算法描述(續(xù))精精選選文檔1102.3.3

AES算法描述(續(xù))精精選選文檔1112.3.3

AES算法描述(續(xù))精精選選文檔112算法架構(gòu)為使論述簡(jiǎn)單，我們以使用128比特密鑰加密

128比特消息為例說(shuō)明，并且先對(duì)算法的整體架構(gòu)予以說(shuō)明。算法由10輪組成。每一輪使用一個(gè)由原始密鑰產(chǎn)生的密鑰。第0輪使用原始的128比特密鑰。每一輪都是128比特輸入128比特輸出。

AES的構(gòu)造如圖2.16。2.3.3

AES算法描述(續(xù))圖2.16

AES的構(gòu)造精精選選文檔1132.3.3

AES算法描述(續(xù))每一輪由四個(gè)根本步驟稱為層(layers)組成：字節(jié)轉(zhuǎn)換(The

Byte

Sub

Transformation)：這是一個(gè)非線性層主要用于防止差分和線性分析攻擊。移動(dòng)行變換(The

Shift

Row

Transformation)：這是一個(gè)線性組合，可以導(dǎo)致多輪之間各個(gè)比特位間的擴(kuò)散?；旌狭凶儞Q(The

Mix

Column

Transformation)：這一層的目的與移動(dòng)行變換一樣。輪密鑰加密變換(Add

Round

Key)：輪密鑰與上一層的結(jié)果進(jìn)展異或操作。精精選選文檔1142.3.3

AES算法描述(續(xù))一輪的過(guò)程Byte

Sub(BS)Shift

Row(SR)Mix

Column(MC)Add

Round

Key(ARK)注意最后一輪忽略了混合列變換(MC)層。精精選選文檔1152.3.3

AES算法描述(續(xù))(2)移動(dòng)行變換精精選選文檔1192.3.3

AES算法描述(續(xù))(3)混合列變換精精選選文檔1202.3.3

AES算法描述(續(xù))(4)輪密鑰加密變換精精選選文檔1212.3.3

AES算法描述(續(xù))輪密鑰產(chǎn)生方法精精選選文檔1222.3.3

AES算法描述(續(xù))解密字節(jié)轉(zhuǎn)換、移動(dòng)行變換、混合列變換、輪密鑰加密變換都存在相應(yīng)的逆變換：字節(jié)轉(zhuǎn)換的逆變換可以通過(guò)查另一個(gè)表來(lái)完成，我們稱之為逆字節(jié)轉(zhuǎn)換(IBS)。移動(dòng)行變換的逆變換可以通過(guò)字節(jié)右移來(lái)實(shí)現(xiàn)，我們稱之為逆移動(dòng)行變換(ISR)。逆混合列變換(IMC)通過(guò)乘上另一個(gè)矩陣實(shí)現(xiàn)。(4)輪密鑰加密變換實(shí)際上是自身的逆。精精選選文檔1232.3.3

AES算法描述(續(xù))S-盒原理精精選選文檔1242.3.3

AES算法描述(續(xù))精精選選文檔1252.3.3

AES算法描述(續(xù))解密變換精精選選文檔1262.3.3

AES算法描述(續(xù))#為了保持構(gòu)造的一致性，在最后一輪加密中忽略了MC操作。精精選選文檔

1272.3.4

AES的平安與執(zhí)行設(shè)計(jì)思考由于加密和解密過(guò)程不一致，相比DES(全1密鑰，加密兩次恢復(fù)為本身)，相信AES不存在任何弱密鑰。不同于Feistel系統(tǒng)，AES對(duì)輸入所有比特的處理一樣，這使得輸入的擴(kuò)展速度很快。實(shí)踐說(shuō)明兩輪計(jì)算就能得到

充分?jǐn)U展，也就是說(shuō)，所有的128比特輸出完全依賴于所有128比特輸入。AES的S-盒的建立有明晰而簡(jiǎn)單的代數(shù)意義，這樣可以防止任何建立在算法上的門(mén)陷，較好防止存在于DES的S-盒上的神秘色彩。AES的S-盒具有良好的非線性特性，它可以很好地用來(lái)阻止差分和線性分析。精精選選文檔1282.3.4

AES的平安與執(zhí)行(續(xù))移動(dòng)行這一層可以很好地阻止新發(fā)現(xiàn)的截?cái)喙艉推椒焦?。混合列可以到達(dá)字節(jié)擴(kuò)散的目的。這步1個(gè)輸入字節(jié)的改變導(dǎo)致所有4個(gè)輸出字節(jié)改變。輪密鑰產(chǎn)生方法使用了密鑰位的非線性組合，因?yàn)樗褂昧薙-盒，這種非線性組合用來(lái)對(duì)付當(dāng)解密者知道了局部密鑰并以此推測(cè)余下局部的攻擊。循環(huán)常量(10)(i-4)/4是用來(lái)消除在循環(huán)過(guò)程中生成每個(gè)循環(huán)差異的對(duì)稱性。精精選選文檔1292.3.4

AES的平安與執(zhí)行(續(xù))(7)輪次之所以選擇10，是因?yàn)樵?輪情況下存在比強(qiáng)力搜索攻擊更好的算法。到2004年，公布的密碼分析結(jié)果在7輪以上還沒(méi)有比強(qiáng)力搜索攻擊更好的方法。多出4輪能夠讓人更有平安感。當(dāng)然，輪次還可以根據(jù)需要增加。精精選選文檔1302.3.4

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

AES的平安與執(zhí)行(續(xù))在MC操作中，有限域GF(28)上的兩個(gè)元的乘法操作也可以用“查表法〞來(lái)實(shí)現(xiàn)：z

=

x y(有限域乘法)，這里x {01，10，11}和y GF(28)。我們進(jìn)一步注意到字節(jié)01為有限域乘法單位元，也就是，01 y=y。因而無(wú)論用軟件還是硬件執(zhí)行“查表法〞時(shí)只需要存儲(chǔ)2 256=512項(xiàng)，這個(gè)表是非常小的。這樣實(shí)現(xiàn)不僅速度很快，而且還能夠減少定時(shí)分析攻擊的危險(xiǎn)。執(zhí)行IMC操作就不像執(zhí)行MC操作那么快。這是因?yàn)镮MC操作的4 4矩陣比MC操作的復(fù)雜得多，一般執(zhí)行IMC操作比MC操作需要多花費(fèi)30%的處理時(shí)間。然而，幸運(yùn)的是在一些應(yīng)用中解密是不需要的。精精選選文檔1322.3.5對(duì)稱密碼的應(yīng)用(1)加密模式通常大多數(shù)消息的長(zhǎng)度大于分組密碼的消

息分組長(zhǎng)度，長(zhǎng)的消息被分成一系列連續(xù)

排列的消息分組，密碼一次處理一個(gè)分組。在分組密碼的上層，不同的加密模式被開(kāi)

發(fā)出來(lái)，這些加密模式可以為整體消息加

密提供一些希望得到的性質(zhì)。如：分組密

碼的不確定性(隨機(jī)性)，將明文消息添加到任意長(zhǎng)度(使得密文長(zhǎng)度不必與相應(yīng)的明文長(zhǎng)度相關(guān))，錯(cuò)誤傳播控制，流密碼的密鑰流生成，等等。精精選選文檔1332.3.5對(duì)稱密碼的應(yīng)用(續(xù))密碼分組鏈接(CBC)模式C0P1EKC1P2EKC2…134圖2.17

CBC模精精選式選文檔加密2.3.5對(duì)稱密碼的應(yīng)用(續(xù))精精選選文檔1352.3.5對(duì)稱密碼的應(yīng)用(續(xù))(2)修改發(fā)現(xiàn)碼(MDC)實(shí)例-使用DES的MDC-2在分組密碼根底上建立Hash函數(shù)的主要?jiǎng)訖C(jī)是：如果系統(tǒng)已經(jīng)擁有了非常有效的分組密碼，那么以分組密碼作為實(shí)現(xiàn)Hash函數(shù)的主要部件，將既可以提供Hash函數(shù)的功能，又能使額外開(kāi)銷(xiāo)最小。精精選選文檔1362.3.5對(duì)稱密碼的應(yīng)用(續(xù))精精選選文檔1372.3.5對(duì)稱密碼的應(yīng)用(續(xù))精精選選文檔138Eg(H

)i-1Eg"(H

)i-12.3.5對(duì)稱密碼的應(yīng)用(續(xù))MiCLi

CRiCL"i

CR"iCLi

CR"iCL"i

CRiH"i139Hi圖2.18

MDC精-精選2選文原檔理圖2.3.5對(duì)稱密碼的應(yīng)用(續(xù))(3)基于CBC的消息認(rèn)證碼(MAC)定義26消息認(rèn)證碼(MAC)算法是帶有密鑰k的函數(shù)族

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

xi在計(jì)算上不可能(當(dāng)然也包括某些i滿足hk(x)=hk(xi)的可能性)

。精精選選文檔1402.3.5對(duì)稱密碼的應(yīng)用(續(xù))精精選選文檔1410EkH12.3.5對(duì)稱密碼的應(yīng)用(續(xù))M1

M2EkH2…Ht-1MtEkHtHtDk"可選Ek142圖2.19基于CBC的精精選M選文A檔C原理圖2.3.6平安Hash算法SHA-1平安Hash算法(SHA)是美國(guó)國(guó)家標(biāo)準(zhǔn)技

術(shù)研究所(NIST)設(shè)計(jì)，并于1993年作為聯(lián)邦信息處理標(biāo)準(zhǔn)(FIPS180)發(fā)布。后做修改，于1995年再次公布修訂后的SHA，通常稱為SHA-1。精精選選文檔1432.3.6平安Hash算法SHA-1(續(xù))SHA-1算法的輸入為小于264比特長(zhǎng)的任意消息，輸出為160比特的消息摘要，算法處理過(guò)程如圖。HSHAIV(160bits)HSHAY0(512bits)

Y1CV1(160bits)…HSHACVqYq…CV2HSHACVL-1精精選選文檔144YL圖2

.20

SHA-1計(jì)算的總體框架CVq+12.3.6平安Hash算法SHA-1(續(xù))消息長(zhǎng)度KSHA-1消息處理過(guò)程：(1)消息填充。填充使得消息的比特長(zhǎng)度為512比特的某個(gè)倍數(shù)減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特?cái)?shù)在1到512。填充方式是第一位為1其他位是0。最后64比特位用來(lái)填充消息被填充前的長(zhǎng)度。這形成了長(zhǎng)度為512比特的一系列分組Y0，Y1，…，YL-1。L×512比特K比特需要產(chǎn)生Hash值的消息

100…0145填充長(zhǎng)度1-512比特圖2.2精1精選消選文檔息填充2.3.6平安Hash算法SHA-1(續(xù))(2)初始化。SHA-1使用160比特的緩沖區(qū)存儲(chǔ)中間和最終Hash值，可用5個(gè)32比特存放器A，B，C，D，E表示，初始值為

A=67452301，B=efcdab89，C=98badcfe，D=10325476，E=c3d2e1f0。精精選選文檔1462.3.6平安Hash算法SHA-1(續(xù))(3)處理。每個(gè)分組Yq經(jīng)過(guò)壓縮函數(shù)處理，壓縮函數(shù)由4輪處理過(guò)程構(gòu)成，如圖2.22所示。每一輪又由20步迭代組成。4輪處理構(gòu)造一樣，但根本邏輯函數(shù)不同，分別為f1，f2，f3，f4。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D、E的當(dāng)前值，輸出仍放在對(duì)應(yīng)緩

沖區(qū)。每一輪處理有一個(gè)加法常量Ki，其中t表示迭代步數(shù)，0≤t≤79。第4輪的輸出與第1輪的輸入CVq依5個(gè)緩沖區(qū)對(duì)應(yīng)進(jìn)展模232相加得到CVq+1。消息的L個(gè)分組都按上述計(jì)算處理完成后最后一個(gè)分組的輸出就是160比特消息摘要。精精選選文檔1472.3.6平安Hash算法SHA-1(續(xù))CVq160位Yq512位20步ADE20步ADE20步ADE20步ADB

Cf1,

Kt,

W[0…19]B

Cf2,

Kt,

W[20…39]B

Cf3,

Kt,

W[40…59]B

Cf4,

Kt,

W[60…79]E+++++148精精選選文檔CVq+1160位圖2.22

SHA的分組處理流程圖2.3.6平安Hash算法SHA-1(續(xù))SHA-1的壓縮函數(shù)各個(gè)20步迭代運(yùn)算的每一步運(yùn)算可以表示為

A，B，C，D，E←(E+fi(B，C，D)+CLS5(A)+Wt+Ki)，A，CLS30(B)，C，D其中，t是迭代的步數(shù)(0≤t≤79)，+是模232相加，fi是i(1≤i≤4)輪的根本邏輯函數(shù)，CLS表示循環(huán)左移s位，Wt是當(dāng)前512比特分組導(dǎo)出的一個(gè)32比特字。精精選選文檔1492.3.6平安Hash算法SHA-1(續(xù))SHA-1的壓縮函數(shù)(續(xù))根本邏輯函數(shù)f1，f2，f3，f4分別定義為：精精選選文檔150f2(X，Y，Z)=f4(X，Y，Z)=Xf1(X，Y，Z)=(X

Y)

(

X

Y)Y

Zf3(X，Y，Z)=(X

Y)

(X

Z)

(Y

Z)其中，

是與，

是或，

是異或，

是非。2.3.6平安Hash算法SHA-1(續(xù))SHA-1的壓縮函數(shù)(續(xù))加法常量K1

=5a827999，對(duì)應(yīng)0≤t≤19K2

=6ed9eba1，對(duì)應(yīng)20≤t≤39K3

=8f1bbcdc，對(duì)應(yīng)40≤t≤59K4

=ca62c1d6，對(duì)應(yīng)60≤t≤79字?jǐn)U展前16個(gè)字W0，W1，…，W15

，直接由輸入得到。精精選選文檔151Wt-8

Wt-14

Wt-16)其余由公式Wt=CLS1(Wt-3得到。2.4公鑰密碼技術(shù)2.4.1

RSA體制Diffie和Hellman提出了建立公鑰密碼系統(tǒng)的可能性。但是，他們并沒(méi)有提出公鑰密碼算法。接下來(lái)的幾

年，一些公鑰密碼算法相繼被提出。其中最為成功

的依賴大整數(shù)分解困難性的公鑰密碼算法，于1977

年由Rivest，Shamir，和Adleman提出。這也就是我們熟知的RSA算法。雖然經(jīng)過(guò)長(zhǎng)期的密碼分析并不能證明也不能否認(rèn)RSA的平安，但是這也無(wú)疑給了算法的平安性一定承諾。精精選選文檔1522.4.1

RSA體制(續(xù))注意這里講到的公鑰密碼算法，都是假定發(fā)送消息者已經(jīng)得到承受者一份真實(shí)的公開(kāi)密鑰拷貝?，F(xiàn)實(shí)中，有許多技術(shù)保障真實(shí)公開(kāi)密鑰分配，包括：在可信信道上交換密鑰，使用可信公開(kāi)文件，使用在線可信效勞器或使用離線效勞器和證書(shū)。精精選選文檔1532.4.1

RSA體制(續(xù))RSA加密精精選選文檔1542.4.1

RSA體制(續(xù))精精選選文檔1552.4.1

RSA體制(續(xù))精精選選文檔1562.4.1

RSA體制(續(xù))精精選選文檔1572.4.1

RSA體制(續(xù))精精選選文檔1582.4.1

RSA體制(續(xù))

RSA-OAEP精精選選文檔1592.4.1

RSA體制(續(xù))

RSA-OAEP(續(xù))精精選選文檔1602.4.1

RSA體制(續(xù))

RSA-OAEP(續(xù))精精選選文檔1612.4.1

RSA體制(續(xù))RSA簽名精精選選文檔1622.4.1

RSA體制(續(xù))精精選選文檔1632.4.1

RSA體制(續(xù))精精選選文檔1642.4.1

RSA體制(續(xù))精精選選文檔1652.4.2

RSA體制的參數(shù)選擇與執(zhí)行(1)參數(shù)選擇模的大小根據(jù)分解整數(shù)算法特別是數(shù)域篩法的進(jìn)展，RSA中的模n應(yīng)該至少為1024比特。從長(zhǎng)遠(yuǎn)的平安考慮，應(yīng)該使用2048比特或更大的模。素?cái)?shù)的選擇素?cái)?shù)p和q的選擇原那么是使分解整數(shù)n

=p

q在計(jì)算上不可能。主要對(duì)p和q的限制是它們必須有足夠的長(zhǎng)度，并且有差不多相等的比特長(zhǎng)度。例如，如果使用1024比特的模n，那么，p和q應(yīng)該都是在512比特左右。精精選選文檔1662.4.2

RSA體制的參數(shù)選擇與執(zhí)行(續(xù))另一個(gè)對(duì)素?cái)?shù)p和q的限制是p-q不能太小。如果p和q是隨機(jī)選擇產(chǎn)生，那么p-q將會(huì)以壓倒的概率比較大。許多地方推薦使用強(qiáng)素?cái)?shù)p和q。一個(gè)素?cái)?shù)p是強(qiáng)素?cái)?shù)需要滿足以下三個(gè)條件：*

p-1有大的素?cái)?shù)因子，稱為r；**

p+1也有大的素?cái)?shù)因子；***

r-1仍然有大的素?cái)?shù)因子。精精選選文檔1672.4.2

RSA加密的參數(shù)選擇與執(zhí)行(續(xù))指數(shù)加密時(shí)指數(shù)可以選擇e=216+1，這樣及既可以保證效率，又可以保證平安。簽名方案時(shí)公開(kāi)指數(shù)e可以選擇3或216+1。不推薦通過(guò)限制秘密指數(shù)d來(lái)到達(dá)改善解密簽名操作效率的方法，通常指數(shù)d>n0.5。精精選選文檔1682.4.2

RSA加密的參數(shù)選擇與執(zhí)行(續(xù))(2)執(zhí)行素性測(cè)試存在一個(gè)奇妙的事實(shí)，就是分解大整數(shù)雖

然十分困難，但測(cè)試整數(shù)的素性并不困難。也就是說(shuō)，證明一個(gè)數(shù)為合數(shù)要比分解它

容易得多。我們知道很多大整數(shù)是合數(shù)，

但卻并不能分解它們。精精選選文檔1692.4.2

RSA加密的參數(shù)選擇與執(zhí)行(續(xù))精精選選文檔1702.4.2

RSA加密的參數(shù)選擇與執(zhí)行(續(xù))模冪精精選選文檔1712.4.3

ElGamal體制(1)離散對(duì)數(shù)問(wèn)題精精選選文檔1722.4.3

ElGamal體制(續(xù))精精選選文檔1732.4.3

ElGamal體制(續(xù))精精選選文檔1742.4.3

ElGamal體制(續(xù))(2)ElGamal公鑰加密算法ElGamal公鑰加密方案依賴于離散對(duì)數(shù)問(wèn)題的困難性。根本的ElGamal公鑰加密方案是

ElGamal于1985年提出的。精精選選文檔1752.4.3

ElGamal體制(續(xù))精精選選文檔1762.4.3

ElGamal