第四章 傳統(tǒng)密碼學(xué)與典型算法

第4章對(duì)稱密碼體制與典型算法本章內(nèi)容分組密碼體制AES密碼算法Camellia密碼算法序列密碼1第4章對(duì)稱密碼體制與典型算法教學(xué)要求了解對(duì)稱密碼體制的基本概念掌握分組密碼的基本原理了解分組密碼的操作模式掌握AES和Camellia密碼算法了解序列密碼的基本原理2密碼體制概述密碼體制對(duì)稱密碼體制非對(duì)稱密碼體制分組密碼體制序列密碼體制傳統(tǒng)密碼體制公鑰密碼體制加、解密密鑰相同，保密加、解密密鑰不同，一個(gè)保密，一個(gè)公開(kāi)公鑰密碼體制也是分組密碼體制3對(duì)稱密碼體制的數(shù)學(xué)模型44.1分組密碼體制特點(diǎn)明文、密文組長(zhǎng)度為n，密鑰長(zhǎng)度為t，密鑰量為2t密文中的任一位數(shù)字與該組明文所有的數(shù)字均有關(guān)每組明文使用相同密鑰加密本質(zhì)是{0，1，…，2n-1}集合上的自映射或置換5一、分組密碼算法的基本要求分組長(zhǎng)度足夠大防止明文窮舉法奏效密鑰量足夠大

防止密鑰窮舉法奏效密碼變換足夠復(fù)雜使對(duì)手除了用窮舉法破譯外，無(wú)其它捷徑可走，有效對(duì)抗統(tǒng)計(jì)破譯法6問(wèn)題與對(duì)策分組長(zhǎng)度足夠大：代換網(wǎng)絡(luò)十分復(fù)雜，難以控制與實(shí)現(xiàn)對(duì)策

將分組劃分為幾個(gè)小段，分別設(shè)計(jì)這些小段的代換網(wǎng)絡(luò)密鑰量足夠大：密碼系統(tǒng)十分復(fù)雜，同樣難以控制與實(shí)現(xiàn)對(duì)策

概率加權(quán)法：設(shè)計(jì)多個(gè)子系統(tǒng)，使用時(shí)隨機(jī)抽取乘積密碼法：設(shè)計(jì)多個(gè)子系統(tǒng)，對(duì)明文多次加密密碼變換足夠復(fù)雜：抗統(tǒng)計(jì)破譯法的要求，難以簡(jiǎn)單實(shí)現(xiàn)

對(duì)策擴(kuò)散法：將每1位明文和密鑰數(shù)字的影響擴(kuò)散到每1位密文數(shù)字混淆法：使密文與明文、密鑰的統(tǒng)計(jì)特性復(fù)雜化揉面團(tuán)乘積密碼置亂主要實(shí)現(xiàn)擴(kuò)散，非線性代換主要實(shí)現(xiàn)混淆7二、分組密碼算法原理的典型結(jié)構(gòu)

Feistel密碼結(jié)構(gòu)加密解密特點(diǎn)①采用多輪乘積密碼迭代，實(shí)現(xiàn)擴(kuò)散與混淆。②每輪僅改變一半數(shù)據(jù)，且運(yùn)算結(jié)束時(shí)左、右各半數(shù)據(jù)交換位置。③用于改變數(shù)據(jù)的輪函數(shù)F通常包括代換和置亂操作。實(shí)現(xiàn)置亂的裝置常稱為P盒，實(shí)現(xiàn)代換的裝置常稱為S盒，它們分別實(shí)現(xiàn)擴(kuò)散與混淆。④解密算法與加密算法本質(zhì)上相同，僅僅是輪密鑰顛倒順序使用。⑤密碼的安全性能取決于分組長(zhǎng)度、密鑰位數(shù)、迭代輪數(shù)、子密鑰產(chǎn)生算法和輪函數(shù)F等參數(shù)。為了保障密碼的安全性能，這些參數(shù)必須精心選擇，精心設(shè)計(jì)。8SP網(wǎng)絡(luò)Substitution代換，實(shí)現(xiàn)混淆Permutation換位，實(shí)現(xiàn)擴(kuò)散迭代密碼結(jié)構(gòu)，實(shí)現(xiàn)乘積密碼9SP網(wǎng)絡(luò)的兩種基本操作10DES的一般設(shè)計(jì)準(zhǔn)則相關(guān)免疫性隨機(jī)性雪崩效應(yīng)特性完全性非線性11三、分組密碼的操作模式電子密碼本（ECB）模式密碼分組鏈接（CBC）模式計(jì)數(shù)器（CRT）模式密碼反饋（CFB）模式輸出反饋（OFB）模式121、電碼本（ECB）模式優(yōu)、缺點(diǎn)操作簡(jiǎn)單速度快無(wú)差錯(cuò)傳播單表代換不適合格式固定或變化比較少的長(zhǎng)數(shù)據(jù)（如圖象數(shù)據(jù)）加密132、密碼分組鏈接(CBC)模式優(yōu)、缺點(diǎn)操作較簡(jiǎn)單速度較快多表代換適用面廣差錯(cuò)傳播1組143、計(jì)數(shù)器（CTR）模式優(yōu)點(diǎn)操作較簡(jiǎn)單速度較快多表代換適用面廣無(wú)差錯(cuò)傳播154、密碼反饋（CFB）模式優(yōu)、缺點(diǎn)多表代換適用面廣操作復(fù)雜速度較慢差錯(cuò)傳播大165、輸出反饋（OFB）模式優(yōu)、缺點(diǎn)多表代換適用面廣無(wú)差錯(cuò)傳播操作復(fù)雜速度較慢17四、典型的分組密碼算法DES：數(shù)據(jù)加密標(biāo)準(zhǔn)算法IDEA：國(guó)際數(shù)據(jù)加密算法AES：高級(jí)加密標(biāo)準(zhǔn)算法Camellia：歐洲加密標(biāo)準(zhǔn)算法184.2AES密碼算法榮代爾Advanced

Encryption

Standard1997年9月12日：美國(guó)NIST提出征集該算法的公告1998年8月20日：NIST召開(kāi)了第一次候選大會(huì)，并公布了15個(gè)候選算法1999年3月22日：NIST從15個(gè)候選算法中公布了5個(gè)進(jìn)入第二輪選擇：MARS，RC6，Rijindael，SERPENT和Twofish2000年10月2日：以安全性、性能、大小、實(shí)現(xiàn)特性為標(biāo)準(zhǔn)而最終選定了Rijndael算法2001年：正式發(fā)布AES標(biāo)準(zhǔn)一、AES的誕生背景19202122Rijndael

算法是由兩位比利時(shí)的密碼專家發(fā)明的，它很快而且所需的內(nèi)存不多，且算法非?？煽縍ijndael

算法的設(shè)計(jì)策略是針對(duì)差分和線性分析提出來(lái)的，是一個(gè)分組迭代密碼，具有可變的分組長(zhǎng)度和密鑰長(zhǎng)度Rijndael

匯聚了安全性能、效率、可實(shí)現(xiàn)性和靈活性等優(yōu)點(diǎn)23破譯時(shí)間宇宙年齡1011年24二、AES的算法結(jié)構(gòu)采用Square結(jié)構(gòu)10/12/14輪迭代251、AES的數(shù)據(jù)結(jié)構(gòu)按列填充26基本運(yùn)算字節(jié)代換SubBytes行移位ShiftRows列混合MixColumns輪密鑰加AddRoundKeySquare結(jié)構(gòu)（方形結(jié)構(gòu)）有10/12/14輪迭代2、AES的算法結(jié)構(gòu)最后1輪沒(méi)有列混合27采用乘積密碼迭代，實(shí)現(xiàn)擴(kuò)散與混淆。每一輪都使用代換和混淆技術(shù)并行地處理整個(gè)數(shù)據(jù)分組。無(wú)論是加密還是解密，除了最后一輪少了列混合運(yùn)算外，其它各輪都是按照相同順序依次執(zhí)行四種基本運(yùn)算（解密時(shí)為四種基本運(yùn)算的逆運(yùn)算）。解密算法完全是加密算法的倒推，加、解密原理清晰，便于理解。和其它分組密碼相同，輪密鑰在解密時(shí)顛倒順序使用。AES結(jié)構(gòu)特點(diǎn)28利用S盒將中間態(tài)s中的每個(gè)字節(jié)非線性變換為另一個(gè)字節(jié)。實(shí)現(xiàn)每個(gè)字節(jié)數(shù)據(jù)中各位的混淆。

三、AES的基本運(yùn)算1、字節(jié)代換運(yùn)算SubBytes29S盒的構(gòu)造方法第一步：將S盒的輸入字節(jié)首先映射為它在有限域GF(28)中的乘法逆元，{00}映射為它自身。使用不可約多項(xiàng)式。任何非0元素都存在乘法逆元。30記S盒輸入的乘法逆元記S盒輸出對(duì)做仿射變換，得到S盒輸出或其中ci為{63}的第i位：S盒的構(gòu)造方法第二步：31S盒變換舉例乘法逆元S盒變換仿射變換32S盒查找表S盒變換33三、AES的基本運(yùn)算2、行移位運(yùn)算ShiftRows中間態(tài)s中各行的循環(huán)左移第0行不移位第1行循環(huán)左移1個(gè)字節(jié)第2行循環(huán)左移2個(gè)字節(jié)第3行循環(huán)左移3個(gè)字節(jié)。行移位運(yùn)算打亂了中間態(tài)s中各字節(jié)的位置關(guān)系，在功能上相當(dāng)于置亂操作，可以實(shí)現(xiàn)擴(kuò)散效果。34三、AES的基本運(yùn)算3、列混合運(yùn)算MixColumns實(shí)現(xiàn)中間態(tài)s中各列數(shù)據(jù)基于GF(28)域的變換。對(duì)每列數(shù)據(jù)起到良好的混淆作用。第i列變換：字節(jié)運(yùn)算字運(yùn)算35系數(shù)在GF(2)上的多項(xiàng)式運(yùn)算1）加法“+”：字節(jié)的按位異或運(yùn)算，即模2加

+

其中，＝＋，i＝0，1,…,7。（1）GF(28)域上的字節(jié)運(yùn)算

362）乘法“?”類似普通多項(xiàng)式乘法，但系數(shù)運(yùn)算要看作比特的乘法和異或運(yùn)算，即看作{0,1}域上的運(yùn)算。不可約多項(xiàng)式，元素才有乘法逆有限域上的多項(xiàng)式乘法①模多項(xiàng)式法計(jì)算字節(jié)乘法運(yùn)算37例4-1

計(jì)算字節(jié)乘法運(yùn)算。不便軟硬件實(shí)現(xiàn)38對(duì)于GF(28)上模n次多項(xiàng)式m(x)乘法，有

Xn

modm(x)=m(x)-xn

GF(28)上x(chóng).a(x)模m(x)乘法②移位相加法計(jì)算字節(jié)乘法運(yùn)算39x·a(x)模m(x)乘法的討論相當(dāng)于系數(shù)左移1位（右側(cè)補(bǔ)0）相當(dāng)于系數(shù)左移1位（右側(cè)補(bǔ)0），再和1B異或乘以x2相當(dāng)于在乘以x的基礎(chǔ)上再乘以x。以此類推。*結(jié)論40例4-2用移位相加法，計(jì)算解：41例4-2用移位相加法，計(jì)算42課堂練習(xí)：用移位相加法計(jì)算

(10000011)?(01010111)(00000001)?(01010111)=(01010111)(00000010)?(01010111)=(10101110)(00000100)?(01010111)=(01011100)⊕(00011011)=(01000111)(00001000)?(01010111)=(10001110)(00010000)?(01010111)=(00011100)⊕(00011011)=(00000111)(00100000)?(01010111)=(00001110)(01000000)?(01010111)=(00011100)(10000000)?(01010111)=(00111000)(10000011)?(01010111)=[(00000001)+(00000010)+(10000000)]?(01010111)=(01010111)⊕(10101110)⊕(00111000)=(11000001)最高位是1，左移1位，異或1B最高位是1，左移1位，異或1B最高位是0，左移1位最高位是0，左移1位最高位是0，左移1位，最高位是0，左移1位最高位是0，左移1位43③表操作法計(jì)算字節(jié)乘法運(yùn)算將GF(28)域上所有的非0元素{xy}表示為生成元{03}的冪，即{xy}={03}{XY}，并將{xy}與冪指數(shù){XY}的對(duì)應(yīng)關(guān)系制作成一張對(duì)數(shù)表:例：44例4-3證明域上的元素45例4-3證明域上的元素證：46③表操作法計(jì)算字節(jié)乘法運(yùn)算將字節(jié)乘法變換為冪指數(shù)的加法。即若，則有：算術(shù)加注意：47③表操作法計(jì)算字節(jié)乘法運(yùn)算例：將{xy}與冪指數(shù){XY}的對(duì)應(yīng)關(guān)系制作成一張對(duì)數(shù)表，從而根據(jù){XY}查找到域上所有的非0元素{xy}：{03}{XY}={xy}。48例4-4利用表操作法，計(jì)算解：49例4-4利用表操作法，計(jì)算解：課堂練習(xí)查表法計(jì)算{7a}·{93}50查表求任意域元素的乘法逆元方法除了｛00｝外所有的域元素都有逆

如果，則可表示為：51例4-5求{95}的乘法逆{95}-1查對(duì)數(shù)表：{95}={03}{16}乘法逆元：{95}-1={03}{ff}-{16}={03}{e9}查反對(duì)數(shù)表：{03}{e9}＝{8a}

故{95}的乘法逆為{8a}驗(yàn)算{95}-1{95}={8a}{95}={03}{e9}{03}{16}={03}{ff}={01}對(duì)數(shù)表反對(duì)數(shù)表52（2）字運(yùn)算—系數(shù)在GF(28)域上的運(yùn)算1）字加法運(yùn)算逐字節(jié)按位模2加法運(yùn)算。例：53（2）字運(yùn)算—系數(shù)在GF(28)域上的運(yùn)算2）字乘法運(yùn)算模不可約多項(xiàng)式f(x)=x4+1的乘法運(yùn)算。根據(jù)可得形式與前面列混合式子相同！54列混合運(yùn)算舉例例4-6計(jì)算，其中解：55列混合運(yùn)算舉例例4-6計(jì)算，其中解：56列混合運(yùn)算舉例例4-6計(jì)算，其中解：57列混合運(yùn)算舉例例4-6計(jì)算，其中解：584、輪密鑰加運(yùn)算AddRoundKey密鑰擴(kuò)展后面介紹實(shí)現(xiàn)中間態(tài)與密鑰字的按列異或運(yùn)算。59四、AES的解密運(yùn)算AES的解密算法完全由加密算法倒推而來(lái)。與加密算法相比，主要的不同之處有兩點(diǎn)。四種基本運(yùn)算用它們的逆運(yùn)算取代。輪密鑰顛倒順序使用。此處僅介紹逆字節(jié)代換運(yùn)算invSubBytes、逆行移位運(yùn)算invShiftRows和逆列混合運(yùn)算invMixColumns等三種逆運(yùn)算。601、逆字節(jié)代換運(yùn)算InvSubBytesinvSubBytes的輸入字節(jié)。invSubBytes輸出字節(jié)的乘法逆元。才是invSubBytes的輸出字節(jié)。61逆S盒查找表例：逆字節(jié)代換622、逆行移位運(yùn)算InvShiftRows圖4-17逆行移位運(yùn)算invShiftRows與行移位方向相反：第0行不變；第1行循環(huán)右移1個(gè)字節(jié)；第2行循環(huán)右移2個(gè)字節(jié)；第3行循環(huán)右移3個(gè)字節(jié)。633、逆列混和運(yùn)算InvMixColumns64五、密鑰擴(kuò)展ExpandKey作用根據(jù)種子密鑰（也稱主密鑰）k擴(kuò)展出每輪迭代所需要的4個(gè)密鑰字。

種子密鑰k128比特：迭代10輪，需44個(gè)密鑰字192比特：迭代12輪，需52個(gè)密鑰字256比特：迭代14輪，需60個(gè)密鑰字651、128比特密鑰擴(kuò)展w43661、128比特密鑰擴(kuò)展擴(kuò)展過(guò)程直接用種子密鑰k按列填充構(gòu)成前4個(gè)密鑰字。當(dāng)且時(shí)，密鑰字按下式擴(kuò)展構(gòu)成：。當(dāng)且時(shí)，密鑰字按照下式擴(kuò)展構(gòu)成：密鑰字循環(huán)左移一個(gè)字節(jié)字節(jié)代換輪常數(shù)67輪常數(shù)輪常數(shù)Rconj的高字節(jié)總是前一個(gè)輪常數(shù)高字節(jié)的2倍模m(x)的結(jié)果{80}*2={100}=x8

=x8modm(x)=x4+x3+x+1={1b}m(x)=x8+x4+x3+x+1682、128比特密鑰擴(kuò)展舉例例4-8假設(shè)128比特種子密鑰k為：2b7e151628aed2a6abf7158809cf4f3c試列表給出AES的密鑰擴(kuò)展過(guò)程及結(jié)果。69加密密鑰k

2b7e151628aed2a6abf7158809cf4f3c輸入明文m3243f6a8885a308d313198a2e0370734六、AES加、解密實(shí)例輸出密文c3902dc1925dc116a8409850b1dfb9732解密參見(jiàn)教材7021世紀(jì)歐洲NESSIE(NewEuropeanSchemesforSignatures，Integrity，andEncryption)密碼工程確定的分組密碼算法Feistel結(jié)構(gòu)密碼算法在21世紀(jì)的典型代表外觀參數(shù)與AES相同安全性能和實(shí)現(xiàn)特性與AES算法大致相當(dāng)知名度和影響力目前還不及AES算法4.3Camellia密碼算法71緊隨AES之后，保持歐洲工業(yè)界在密碼學(xué)研究領(lǐng)域的領(lǐng)先地位2000年元旦啟動(dòng)NESSIE，同年3月公開(kāi)征集2000年11月，征集到17個(gè)分組密碼算法2001年9月，從中篩選出7個(gè)算法2003年2月，選定日本電報(bào)電話公司（NTT）的ShihoMoriai和日本三菱電子公司（MEC）的MitsuruMatsui兩位密碼學(xué)家聯(lián)合設(shè)計(jì)的Camellia算法AES算法同時(shí)列為歐洲NESSIE標(biāo)準(zhǔn)算法一、Camellia的誕生背景721、Camellia算法的符號(hào)及含義二、Camellia的算法結(jié)構(gòu)732、Camellia的算法結(jié)構(gòu)預(yù)白化后白化典型的Feistel密碼結(jié)構(gòu)打亂算法的規(guī)律性加密結(jié)構(gòu)128比特密鑰2輪FL/FL-1和18輪Feistel疊代742、Camellia