第三章分組密碼

第三章分組密碼3.1分組密碼概述3.2DES3.3分組密碼運(yùn)行模式3.4AES一、分組密碼概述分組密碼概述分組密碼是許多系統(tǒng)安全的一個(gè)重要組成部分。可用于構(gòu)造偽隨機(jī)數(shù)生成器流密碼消息認(rèn)證碼(MAC)和雜湊函數(shù)消息認(rèn)證技術(shù)、數(shù)據(jù)完整性機(jī)制、實(shí)體認(rèn)證協(xié)議以及單鑰數(shù)字簽字體制的核心組成部分。

應(yīng)用中對(duì)于分組密碼的要求安全性運(yùn)行速度存儲(chǔ)量(程序的長(zhǎng)度、數(shù)據(jù)分組長(zhǎng)度、高速緩存大小)實(shí)現(xiàn)平臺(tái)(硬、軟件、芯片)運(yùn)行模式分組密碼概述明文序列x1,x2,…,xi,…

加密函數(shù)E:Vn×KVm

這種密碼實(shí)質(zhì)上是字長(zhǎng)為n的數(shù)字序列的代換密碼。

解密算法加密算法密鑰k=(k0,k1,…,kt-1)密鑰k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xn-1)明文x=(x0,x1,…,xn-1)密文x=(y0,y1,…,ym-1)

分組密碼概述通常取n=m。若n<m

，則為有數(shù)據(jù)擴(kuò)展的分組密碼。若n>m

，則為有數(shù)據(jù)壓縮的分組密碼。分組密碼設(shè)計(jì)問(wèn)題

分組密碼的設(shè)計(jì)問(wèn)題在于找到一種算法，能在密鑰控制下從一個(gè)足夠大且足夠好的置換子集中，簡(jiǎn)單而迅速地選出一個(gè)置換，用來(lái)對(duì)當(dāng)前輸入的明文的數(shù)字組進(jìn)行加密變換。分組密碼設(shè)計(jì)準(zhǔn)則混淆：人們所設(shè)計(jì)的密碼應(yīng)使用使得密鑰和明文以及密文之間的依賴(lài)關(guān)系相當(dāng)復(fù)雜以至于這種依賴(lài)性對(duì)密碼分析者來(lái)說(shuō)是無(wú)法利用的。擴(kuò)散：人們所設(shè)計(jì)的密碼應(yīng)使得密鑰的每一位數(shù)字影響密文的許多位數(shù)字以防止對(duì)密鑰進(jìn)行逐段破譯，而且明文的每一位數(shù)字也應(yīng)影響密文的許多位數(shù)字以便隱藏明文數(shù)字統(tǒng)計(jì)特性。分組密碼算法應(yīng)滿(mǎn)足的要求分組長(zhǎng)度n要足夠大：防止明文窮舉攻擊法奏效。密鑰量要足夠大：盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。由密鑰確定置換的算法要足夠復(fù)雜：充分實(shí)現(xiàn)明文與密鑰的擴(kuò)散和混淆，沒(méi)有簡(jiǎn)單的關(guān)系可循，要能抗擊各種已知的攻擊。分組密碼算法應(yīng)滿(mǎn)足的要求加密和解密運(yùn)算簡(jiǎn)單：

易于軟件和硬件高速實(shí)現(xiàn)。數(shù)據(jù)擴(kuò)展：

一般無(wú)數(shù)據(jù)擴(kuò)展，在采用同態(tài)置換和隨機(jī)化加密技術(shù)時(shí)可引入數(shù)據(jù)擴(kuò)展。差錯(cuò)傳播盡可能地小。

分組密碼的實(shí)現(xiàn)原則軟件實(shí)現(xiàn)的原則：使用子塊和簡(jiǎn)單的運(yùn)算。如將分組n化分為子段，每段長(zhǎng)為8、16或32。在以軟件實(shí)現(xiàn)時(shí)，應(yīng)選用簡(jiǎn)單的運(yùn)算，使作用于子段上的密碼運(yùn)算易于以標(biāo)準(zhǔn)處理器的基本運(yùn)算，如加、乘、移位等實(shí)現(xiàn)，避免用以軟件難于實(shí)現(xiàn)的逐比特置換。硬件實(shí)現(xiàn)的原則：加密解密可用同樣的器件來(lái)實(shí)現(xiàn)。代換網(wǎng)絡(luò)代換是輸入集A到輸出A’上的雙射變換：

fk：AA＇

k是控制輸入變量，在密碼學(xué)中則為密鑰。實(shí)現(xiàn)代換fk的網(wǎng)絡(luò)稱(chēng)作代換網(wǎng)絡(luò)。雙射條件保證在給定k下可從密文惟一地恢復(fù)出原明文。代換網(wǎng)絡(luò)代換fk的集合：

S={fkkK}K是密鑰空間。如果網(wǎng)絡(luò)可以實(shí)現(xiàn)所有可能的2n!個(gè)代換，則稱(chēng)其為全代換網(wǎng)絡(luò)。代換結(jié)構(gòu)代換網(wǎng)絡(luò)密碼設(shè)計(jì)中需要先定義代換集S，而后還需定義解密變換集，即逆代換網(wǎng)絡(luò)S-1，它以密文y作為輸入矢量，其輸出為恢復(fù)的明文矢量x。要實(shí)現(xiàn)全代換網(wǎng)絡(luò)并不容易。因此實(shí)用中常常利用一些簡(jiǎn)單的基本代換，通過(guò)組合實(shí)現(xiàn)較復(fù)雜的、元素個(gè)數(shù)較多的代換集。實(shí)用密碼體制的集合S中的元素個(gè)數(shù)都遠(yuǎn)小于2n!。代換盒(S盒)

在密碼設(shè)計(jì)中，可選n=rn0，其中r和n0都為正整數(shù)，將設(shè)計(jì)n個(gè)變量的代換網(wǎng)絡(luò)化為設(shè)計(jì)r個(gè)較小的子代換網(wǎng)絡(luò)，而每個(gè)子代換網(wǎng)絡(luò)只有n0個(gè)輸入變量，稱(chēng)每個(gè)子代換網(wǎng)絡(luò)為代換盒(SubstitutionBox)

S盒x5

x4

x3

x2

x1

x0y3

y2

y1

y0DES的S盒DES的S1-盒的輸入和輸出關(guān)系x5x0x5x4x3x2x1x010101100

列號(hào)0123456789101112131415

行號(hào)

01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613

(y3

,

y2,

y1

,y0)=(0,0,1,0)

S盒的設(shè)計(jì)準(zhǔn)則迄今為止，有關(guān)方面未曾完全公開(kāi)有關(guān)DES的S盒的設(shè)計(jì)準(zhǔn)則。Branstead等曾披露過(guò)下述準(zhǔn)則：P1S盒的輸出都不是其輸入的線性或仿射函數(shù)。P2改變S盒的一個(gè)輸入比特，其輸出至少有兩比特產(chǎn)生變化，即近一半產(chǎn)生變化。P3當(dāng)S盒的任一輸入位保持不變，其它5位輸入變化時(shí)(共有25=32種情況)，輸出數(shù)字中的0和1的總數(shù)近于相等。這三點(diǎn)使DES的S盒能夠?qū)崿F(xiàn)較好的混淆。Feistel密碼結(jié)構(gòu)

乘積密碼指順序地執(zhí)行兩個(gè)或多個(gè)基本密碼系統(tǒng)，使得最后結(jié)果的密碼強(qiáng)度高于每個(gè)基本密碼系統(tǒng)產(chǎn)生的結(jié)果.Feistel還提出了實(shí)現(xiàn)代換和置換的方法。其思想實(shí)際上是Shannon提出的利用乘積密碼實(shí)現(xiàn)混淆和擴(kuò)散思想的具體應(yīng)用。Feistel網(wǎng)絡(luò)示意圖

輸入是分組長(zhǎng)為2w的明文和一個(gè)密鑰K。將每組明文分成左右兩半L0和R0，在進(jìn)行完n輪迭代后，左右兩半再合并到一起以產(chǎn)生密文分組。第i輪迭代的輸入為前一輪輸出的函數(shù)：其中Ki是第i輪用的子密鑰，由加密密鑰K得到。一般地，各輪子密鑰彼此不同而且與K也不同。Feistel密碼結(jié)構(gòu)Feistel密碼結(jié)構(gòu)Feistel網(wǎng)絡(luò)的實(shí)現(xiàn)與以下參數(shù)和特性有關(guān)：①分組大小:分組越大則安全性越高，但加密速度就越慢。②密鑰大?。好荑€越長(zhǎng)則安全性越高，但加密速度就越慢。③輪數(shù)：?jiǎn)屋喗Y(jié)構(gòu)遠(yuǎn)不足以保證安全性，但多輪結(jié)構(gòu)可提供足夠的安全性。典型地，輪數(shù)取為16。④子密鑰產(chǎn)生算法：該算法的復(fù)雜性越大，則密碼分析的困難性就越大。⑤輪函數(shù)：輪函數(shù)的復(fù)雜性越大，密碼分析的困難性也越大。在設(shè)計(jì)Feistel網(wǎng)絡(luò)時(shí)，還有以下兩個(gè)方面需要考慮：①快速的軟件實(shí)現(xiàn)：在很多情況中，算法是被鑲嵌在應(yīng)用程序中，因而無(wú)法用硬件實(shí)現(xiàn)。此時(shí)算法的執(zhí)行速度是考慮的關(guān)鍵。②算法容易分析：如果算法能被無(wú)疑義地解釋清楚，就可容易地分析算法抵抗攻擊的能力，有助于設(shè)計(jì)高強(qiáng)度的算法。Feistel密碼結(jié)構(gòu)

Feistel解密過(guò)程本質(zhì)上和加密過(guò)程是一樣的，算法使用密文作為輸入，但使用子密鑰Ki的次序與加密過(guò)程相反，即第1輪使用Kn，第2輪使用Kn-1，……，最后一輪使用K1。這一特性保證了解密和加密可采用同一算法。Feistel解密結(jié)構(gòu)

Feistel加解密過(guò)程在加密過(guò)程中：在解密過(guò)程中Feistel密碼結(jié)構(gòu)所以解密過(guò)程第1輪的輸出為L(zhǎng)E15‖RE15，等于加密過(guò)程第16輪輸入左右兩半交換后的結(jié)果。容易證明這種對(duì)應(yīng)關(guān)系在16輪中每輪都成立。一般地，加密過(guò)程的第i輪有因此Feistel密碼結(jié)構(gòu)3.2美國(guó)數(shù)據(jù)加密標(biāo)準(zhǔn)—DES（DataEncryptionStandard）美國(guó)制定數(shù)據(jù)加密標(biāo)準(zhǔn)簡(jiǎn)況目的

通信與計(jì)算機(jī)相結(jié)合是人類(lèi)步入信息社會(huì)的一個(gè)階梯，它始于六十年代末，完成于90年代初。計(jì)算機(jī)通信網(wǎng)的形成與發(fā)展，要求信息作業(yè)標(biāo)準(zhǔn)化，安全保密亦不例外。只有標(biāo)準(zhǔn)化，才能真正實(shí)現(xiàn)網(wǎng)的安全，才能推廣使用加密手段，以便于訓(xùn)練、生產(chǎn)和降低成本。

美國(guó)制定數(shù)據(jù)加密標(biāo)準(zhǔn)簡(jiǎn)況美國(guó)NBS（NationalBureauofStandards）在1973年5月15公布了征求建議。1974年8月27日NBS再次出公告征求建議，對(duì)建議方案提出如下要求：(1)算法必須提供高度的安全性(2)算法必須有詳細(xì)的說(shuō)明,并易于理解(3)算法的安全性取決于密鑰,不依賴(lài)于算法(4)算法適用于所有用戶(hù)(5)算法適用于不同應(yīng)用場(chǎng)合(6)算法必須高效、經(jīng)濟(jì)(7)算法必須能被證實(shí)有效(8)算法必須是可出口的美國(guó)制定數(shù)據(jù)加密標(biāo)準(zhǔn)簡(jiǎn)況IBM公司在1971年完成的LUCIFER密碼(64bit分組，代換-置換，128bit密鑰)的基礎(chǔ)上，改進(jìn)成為建議的DES體制1975年3月17日NBS公布了這個(gè)算法，并說(shuō)明要以它作為聯(lián)邦信息處理標(biāo)準(zhǔn)，征求各方意見(jiàn)。1977年1月15日建議被批準(zhǔn)為聯(lián)邦標(biāo)準(zhǔn)[FIPSPUB46]，并設(shè)計(jì)推出DES芯片。1981年美國(guó)ANSI（AmericanNationalStandardsInstitute）將其作為標(biāo)準(zhǔn)，稱(chēng)之為DEA[ANSIX3.92]1983年國(guó)際標(biāo)準(zhǔn)化組織(ISO，InternationalOrganizationforStandardization)采用它作為標(biāo)準(zhǔn)，稱(chēng)作DEA-1

美國(guó)制定數(shù)據(jù)加密標(biāo)準(zhǔn)簡(jiǎn)況NSA（NationalSecurityAgency）宣布每隔5年重新審議DES是否繼續(xù)作為聯(lián)邦標(biāo)準(zhǔn)，1988年（FIPS46-1）、1993年（FIPS46-2），1998年不再重新批準(zhǔn)DES為聯(lián)邦標(biāo)準(zhǔn)。雖然DES已有替代的數(shù)據(jù)加密標(biāo)準(zhǔn)算法，但它仍是迄今為止得到最廣泛應(yīng)用的一種算法，也是一種最有代表性的分組加密體制。1993年4月，Clinton政府公布了一項(xiàng)建議的加密技術(shù)標(biāo)準(zhǔn)，稱(chēng)作密鑰托管加密技術(shù)標(biāo)準(zhǔn)EES(EscrowedEncryptionStandard)。算法屬美國(guó)政府SECRET密級(jí)。美國(guó)制定數(shù)據(jù)加密標(biāo)準(zhǔn)簡(jiǎn)況DES發(fā)展史確定了發(fā)展公用標(biāo)準(zhǔn)算法模式，而EES(EscrowedEncryptionStandard)的制定路線與DES的背道而馳。人們懷疑有陷門(mén)和政府部門(mén)肆意侵犯公民權(quán)利。此舉遭到廣為反對(duì)。1995年5月AT&TBellLab的M.Blaze博士在PC機(jī)上用45分鐘時(shí)間使SKIPJACK的LEAF協(xié)議失敗，偽造ID碼獲得成功。1995年7月美國(guó)政府宣布放棄用EES來(lái)加密數(shù)據(jù)，只將它用于語(yǔ)音通信。1997年1月美國(guó)NIST著手進(jìn)行AES（AdvancedEncryptionStandard）的研究，成立了標(biāo)準(zhǔn)工作室。2001年Rijndael被批準(zhǔn)為AES標(biāo)準(zhǔn)。DES（DataEncryptionStandard）算法于1977年得到美國(guó)政府的正式許可，是一種用56位密鑰來(lái)加密64位數(shù)據(jù)的方法。這是IBM的研究成果。DES是第一代公開(kāi)的、完全說(shuō)明細(xì)節(jié)的商業(yè)級(jí)現(xiàn)代算法，并被世界公認(rèn)。美國(guó)制定數(shù)據(jù)加密標(biāo)準(zhǔn)簡(jiǎn)況

DES算法分組長(zhǎng)度為64bits(8bytes)密文分組長(zhǎng)度也是64bits。密鑰長(zhǎng)度為64bits，有8bits奇偶校驗(yàn)，有效密鑰長(zhǎng)度為56bits。算法主要包括：初始置換IP、16輪迭代的乘積變換、逆初始置換IP-1以及16個(gè)子密鑰產(chǎn)生器。

DES算法框圖

初始置換IP將64bit明文的位置進(jìn)行置換，得到一個(gè)亂序的64bit明文組，而后分成左右兩段，每段為32bit，以L0和R0表示。逆初始置換IP-1。將16輪迭代后給出的64bit組進(jìn)行置換，得到輸出的密文組。輸出為陣中元素按行讀得的結(jié)果。IP和IP-1在密碼意義上作用不大，它們的作用在于打亂原來(lái)輸入x的ASCII碼字劃分的關(guān)系。

DES算法（續(xù)）1初值置換IP

1.初始置換M1M2M3M4M5M6M7M8 M9M10M11M12M13M14M15M16M17M18M19M20M21M22M23M24M25M26M27M28M29M30M31M32M33M34M35M36M37M38M39M40M41M42M43M44M45M46M47M48M49M50M51M52M53M54M55M56M57M58M59M60M61M62M63M64DES算法（續(xù)）

其中Mi是二元數(shù)字。由下表得X=IP(M)為：

M58M50M42M34M26M18M10M2M60M52M44M36M28M20M12M4M62M54M46M38M30M22M14M6M64M56M48M40M32M24M16M8M57M49M41M33M25M17M9M1M59M51M43M35M27M19M11M3M61M53M45M37M29M21M13M5M63M55M47M39M31M23M15M7DES算法（續(xù)）

如果再取逆初始置換Y=IP-1(X)=IP-1(IP(M))，可以看出，M各位的初始順序?qū)⒈换謴?fù)。DES算法（續(xù)）

DES算法輪結(jié)構(gòu)

DES算法（續(xù)）圖3.7函數(shù)F(R,K)的計(jì)算過(guò)程DES算法（續(xù)）DES算法（續(xù)）

對(duì)每個(gè)盒Si，其6比特輸入中，第1個(gè)和第6個(gè)比特形成一個(gè)2位二進(jìn)制數(shù)用來(lái)選擇行，中間4位用來(lái)選擇列。行和列選定后，得到其交叉位置的十進(jìn)制數(shù)，將這個(gè)數(shù)表示為4位二進(jìn)制數(shù)即得這一S盒的輸出。 例如，S1的輸入為011001，行選為01（即第1行），列選為1100（即第12列），行列交叉位置的數(shù)為9，其4位二進(jìn)制表示為1001，所以S1的輸出為1001。

S盒的每一行定義了一個(gè)可逆代換。DES算法（續(xù)）DES的S1-盒的輸入和輸出關(guān)系x0x5x0x1x2x3x4x510101100

列號(hào)0123456789101112131415

行號(hào)

01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613

(y0

,

y1,

y2

,y3)=(0,0,1,0)P置換DES算法密鑰的產(chǎn)生置換選擇1置換選擇1DES算法密鑰的產(chǎn)生（續(xù)）

和Feistel密碼一樣，DES的解密和加密使用同一算法，但子密鑰使用的順序相反。DES解密DES的安全性互補(bǔ)性。DES算法具有下述性質(zhì)。若明文組x逐位取補(bǔ)，密鑰k逐位取補(bǔ)，即y=DESk(x),則有這種互補(bǔ)性會(huì)使DES在選擇明文破譯下所需的工作量減半。弱密鑰和半弱密鑰。DES算法在每次迭代時(shí)都有一個(gè)子密鑰供加密用。如果給定初始密鑰k，各輪的子密鑰都相同，即有k1=k2=…=k16

就稱(chēng)給定密鑰k為弱密鑰(Weakkey)。DES的安全性若k為弱密鑰，則有

DESk(DESk(x))=xDESk-1(DESk-1(x))=x

即以k對(duì)x加密兩次或解密兩次都可恢復(fù)出明文。其加密運(yùn)算和解密運(yùn)算沒(méi)有區(qū)別。

弱密鑰下使DES在選擇明文攻擊下的搜索量減半。如果隨機(jī)地選擇密鑰，弱密鑰所占比例極小，而且稍加注意就不難避開(kāi)。因此，弱密鑰的存在不會(huì)危及DES的安全性。DES的安全性S盒設(shè)計(jì)。

DES靠S盒實(shí)現(xiàn)非線性變換。密鑰搜索機(jī)。

對(duì)DES安全性批評(píng)意見(jiàn)中，較為一致的看法是DES的密鑰短了些。采用窮搜索對(duì)已經(jīng)對(duì)DES構(gòu)成了威脅．DES算法的安全性DES算法正式公開(kāi)發(fā)表以后，引起了一場(chǎng)激烈的爭(zhēng)論。1977年，Diffie和Hellman提出了制造一個(gè)每秒能測(cè)試106個(gè)密鑰的大規(guī)模芯片，這種芯片的機(jī)器大約一天就可以搜索DES算法的整個(gè)密鑰空間，制造這樣的機(jī)器需要兩千萬(wàn)美元。1993年，R.Session和M.Wiener給出了一個(gè)非常詳細(xì)的密鑰搜索機(jī)器的設(shè)計(jì)方案，它基于并行的密鑰搜索芯片，此芯片每秒測(cè)試5×107個(gè)密鑰，當(dāng)時(shí)這種芯片的造價(jià)是10.5美元，5760個(gè)這樣的芯片組成的系統(tǒng)需要10萬(wàn)美元，這一系統(tǒng)平均1.5天即可找到密鑰，如果利用10個(gè)這樣的系統(tǒng)，費(fèi)用是100萬(wàn)美元，但搜索時(shí)間可以降到2.5小時(shí)?？梢?jiàn)這種機(jī)制是不安全的。DES的56位短密鑰面臨的另外一個(gè)嚴(yán)峻而現(xiàn)實(shí)的問(wèn)題是：國(guó)際互聯(lián)網(wǎng)Internet的超級(jí)計(jì)算能力。1997年1月28日，美國(guó)的RSA數(shù)據(jù)安全公司在互聯(lián)網(wǎng)上開(kāi)展了一項(xiàng)名為“密鑰挑戰(zhàn)”的競(jìng)賽，懸賞一萬(wàn)美元，破解一段用56位密鑰加密的DES密文。一位名叫Rocke

Verser的程序員設(shè)計(jì)了一個(gè)可以通過(guò)互聯(lián)網(wǎng)分段運(yùn)行的密鑰窮舉搜索程序，組織實(shí)施了一個(gè)稱(chēng)為DESHALL的搜索行動(dòng)，成千上萬(wàn)的志愿者加入到計(jì)劃中，在計(jì)劃實(shí)施的第96天，即挑戰(zhàn)賽計(jì)劃公布的第140天，1997年6月17日晚上10點(diǎn)39分，美國(guó)鹽湖城Inetz公司的職員MichaelSanders成功地找到了密鑰，在計(jì)算機(jī)上顯示了明文：“Theunknownmessageis:Strongcryptographymakestheworldasaferplace”。1998年7月電子前沿基金會(huì)（EFF）使用一臺(tái)25萬(wàn)美元的電腦在56小時(shí)內(nèi)破譯了56比特密鑰的DES。1999年1月RSA數(shù)據(jù)安全會(huì)議期間，電子前沿基金會(huì)用22小時(shí)15分鐘就宣告破解了一個(gè)DES的密鑰。盡管DES有這樣那樣的不足，但是作為第一個(gè)公開(kāi)密碼算法的密碼體制成功地完成了它的使命，它在密碼學(xué)發(fā)展歷史上具有重要的地位。二重DES

zEEDDxiyixizyi

k1

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

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

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

yi=Ek2[Ek1[xi]]

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

中途相遇攻擊給定一已知明密文對(duì)(x1,y1)，可按下述方法攻擊。以密鑰k1的所有256個(gè)可能的取值對(duì)此明文x1加密，并將密文z存儲(chǔ)在一個(gè)表中；從所有可能的256個(gè)密鑰k2中依任意次序選出一個(gè)對(duì)給定的密文y1解密，并將每次解密結(jié)果z在上述表中查找相匹配的值。一旦找到，則可確定出兩個(gè)密鑰k1和k2；以此對(duì)密鑰k1和k2對(duì)另一已知明文密文對(duì)(x2,y2)中的明文x2進(jìn)行加密，如果能得出相應(yīng)的密文y2就可確定k1和k2是所要找的密鑰。三重DES加密加密：y=Ek1[Dk2[Ek1[x]]]解密：x=Dk1[Ek2[Dk1[y]]]稱(chēng)其為加密-解密-加密方案，簡(jiǎn)記為EDE(encrypt-decrypt-encrypt)。此方案已在ANSIX9.17和ISO8732標(biāo)準(zhǔn)中采用，并在保密增強(qiáng)郵遞(PEM)系統(tǒng)中得到利用。破譯它的窮舉密鑰搜索量為21125×1035量級(jí)，而用差分分析破譯也要超過(guò)1052量級(jí)。此方案仍有足夠的安全性。3.3分組密碼的運(yùn)行模式填充(Padding)

給定加密消息的長(zhǎng)度是隨機(jī)的，按64bit分組時(shí)，最后一組消息長(zhǎng)度可能不足64bit。可以填充一些數(shù)字，通常用最后1字節(jié)作為填充指示符（PI）。它所表示的十進(jìn)制數(shù)字就是填充占有的字節(jié)數(shù)。數(shù)據(jù)尾部、填充字符和填充指示符一起作為一組進(jìn)行加密。

數(shù)據(jù)填充PI

主要工作模式

即使有了安全的分組密碼算法，也需要采用適當(dāng)?shù)墓ぷ髂Ｊ絹?lái)隱蔽明文的統(tǒng)計(jì)特性、數(shù)據(jù)的格式等，以提高整體的安全性，降低刪除、重放、插入和偽造成功的機(jī)會(huì)。電碼本(ECB，ElectronicCodeBook)密碼分組鏈接模式(CBC,CipherBlockChaining)密碼反饋模式(CFB,CipherFeedback)輸出反饋模式(OFB,OutputFeedback)

電碼本ECB模式直接利用加密算法分別對(duì)分組數(shù)據(jù)組加密。在給定的密鑰下，同一明文組總產(chǎn)生同樣的密文組。這會(huì)暴露明文數(shù)據(jù)的格式和統(tǒng)計(jì)特征。

明文數(shù)據(jù)都有固定的格式，需要以協(xié)議的形式定義，重要的數(shù)據(jù)常常在同一位置上出現(xiàn)，使密碼分析者可以對(duì)其進(jìn)行統(tǒng)計(jì)分析、重傳和代換攻擊。

電碼本ECB模式

電碼本ECB模式

ECB在用于短數(shù)據(jù)（如加密密鑰）時(shí)非常理想，因此如果需要安全地傳遞DES密鑰，ECB是最合適的模式。

ECB的最大特性是同一明文分組在消息中重復(fù)出現(xiàn)的話(huà)，產(chǎn)生的密文分組也相同。

ECB用于長(zhǎng)消息時(shí)可能不夠安全，如果消息有固定結(jié)構(gòu)，密碼分析者有可能找出這種關(guān)系。密碼分組鏈接CBC模式為了解決ECB的安全缺陷，可以讓重復(fù)的明文分組產(chǎn)生不同的密文分組，CBC（cipherblockchaining）模式就可滿(mǎn)足這一要求。 加密算法的輸入是當(dāng)前明文分組和前一次密文分組的異或，因此加密算法的輸入不會(huì)顯示出與這次的明文分組之間的固定關(guān)系，所以重復(fù)的明文分組不會(huì)在密文中暴露出這種重復(fù)關(guān)系。

CBC模式示意圖CBC的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：能隱蔽明文的數(shù)據(jù)模式，在某種程度上能防止數(shù)據(jù)纂改，諸如重放、嵌入和刪除等。缺點(diǎn)：會(huì)出現(xiàn)傳播錯(cuò)誤，對(duì)同步差錯(cuò)敏感（增加或丟失一個(gè)或多個(gè)比特）。CBC的錯(cuò)誤傳播1.明文有一組中有錯(cuò)，會(huì)使以后的密文組都受影響，但經(jīng)解密后的恢復(fù)結(jié)果，除原有誤的一組外，其后各組明文都正確地恢復(fù)。2.若在傳送過(guò)程中，某組密文組yi出錯(cuò)時(shí)，則該組恢復(fù)的明文x’i和下一組恢復(fù)數(shù)據(jù)x’i+1出錯(cuò)。再后面的組將不會(huì)受yi中錯(cuò)誤比特的影響。k-比特密碼反饋CFB模式若待加密消息必須按字符(如電傳電報(bào))或按比特處理時(shí)，可采用CFB模式。CFB實(shí)際上是將加密算法DES作為一個(gè)密鑰流產(chǎn)生器，當(dāng)k＝1時(shí)就退化為前面討論的流密碼了。CFB與CBC的區(qū)別是反饋的密文長(zhǎng)度為k，且不是直接與明文相加，而是反饋至密鑰產(chǎn)生器。CFB模式示意圖密碼反饋CFB模式CFB的優(yōu)點(diǎn)它特別適于用戶(hù)數(shù)據(jù)格式的需要。能隱蔽明文數(shù)據(jù)圖樣，也能檢測(cè)出對(duì)手對(duì)于密文的篡改。CFB的缺點(diǎn)對(duì)信道錯(cuò)誤較敏感，且會(huì)造成錯(cuò)誤傳播。CFB也需要一個(gè)初始矢量，并要和密鑰同時(shí)進(jìn)行更換。輸出反饋OFB模式將分組密碼算法作為一個(gè)密鑰流產(chǎn)生器，其輸出的k-bit密鑰直接反饋至分組密碼的輸入端，同時(shí)這k-bit密鑰和輸入的k-bit明文段進(jìn)行對(duì)應(yīng)位模2相加。克服了CBC和CFB的錯(cuò)誤傳播所帶來(lái)的問(wèn)題。對(duì)于密文被篡改難以進(jìn)行檢測(cè)不具有自同步能力，要求系統(tǒng)要保持嚴(yán)格的同步比較和選用ECB模式，簡(jiǎn)單、高速，但最弱、易受重發(fā)攻擊，一般不推薦。CBC適用于文件加密，但較ECB慢。安全性加強(qiáng)。當(dāng)有少量錯(cuò)誤時(shí)，也不會(huì)造成同步錯(cuò)誤。OFB和CFB較CBC慢許多。每次迭代只有少數(shù)bit完成加密。若可以容忍少量錯(cuò)誤擴(kuò)展，則可換來(lái)恢復(fù)同步能力，此時(shí)用CFB。在字符為單元的流密碼中多選CFB模式。OFB用于高速同步系統(tǒng)，不容忍差錯(cuò)傳播。3.4高級(jí)加密標(biāo)準(zhǔn)

AES

AES提出1997年1月，美國(guó)NIST向全世界密碼學(xué)界發(fā)出征集21世紀(jì)高級(jí)加密標(biāo)準(zhǔn)（AES——AdvancedEncryptionStandard）算法的公告，并成立了AES標(biāo)準(zhǔn)工作研究室，1997年4月15日的例會(huì)制定了對(duì)AES的評(píng)估標(biāo)準(zhǔn)。

AES的要求（1）AES是公開(kāi)的；（2）AES為單鑰體制分組密碼；（3）AES的密鑰長(zhǎng)度可變，可按需要增大；（4）AES適于用軟件和硬件實(shí)現(xiàn)；（5）AES可以自由地使用，或按符合美國(guó)國(guó)家標(biāo)準(zhǔn)（ANST）策略的條件使用；算法衡量條件滿(mǎn)足以上要求的AES算法，需按下述條件判斷優(yōu)劣a.安全性b.計(jì)算效率c.內(nèi)存要求d.使用簡(jiǎn)便性e.靈活性。AES的評(píng)審

1998年4月15日全面征集AES算法的工作結(jié)束。1998年8月20日舉行了首屆AES討論會(huì)，對(duì)涉及14個(gè)國(guó)家的密碼學(xué)家所提出的候選AES算法進(jìn)行了評(píng)估和測(cè)試，初選并公布了15個(gè)被選方案，供大家公開(kāi)討論。

CAST-256，RC-6，CRYPTON-128，DEAL-128，

FROG，DFC，LOKI-97，MAGENTA，

MARS，HPC,RIJNDAEL，SAFER+，

SERPENT，E-2，TWOFISH。這些算法設(shè)計(jì)思想新穎，技術(shù)水平先進(jìn)，算法的強(qiáng)度都超過(guò)3-DES，實(shí)現(xiàn)速度快于3-DES。

AES的評(píng)審1999年8月9日NIST宣布第二輪篩選出的5個(gè)候選算法為：

MARS(C.Burwick等,IBM），

RC6TM（R.Rivest等,RSALab.)，

RIJNDEAL(J.Daemen,比)，

SERPENT(R.Anderson等，英、以、挪威)，

TWOFISH(B.Schiener)。2000年10月2日，NIST宣布Rijndael作為新的AESAES算法設(shè)計(jì)思想抵抗所有已知的攻擊；在多個(gè)平臺(tái)上速度快，編碼緊湊；設(shè)計(jì)簡(jiǎn)單。Rijndael沒(méi)有采用Feistel結(jié)構(gòu)，輪函數(shù)由3個(gè)不同的可逆均勻變換構(gòu)成的，稱(chēng)為3個(gè)層均勻變換是指狀態(tài)的每個(gè)bit都用類(lèi)似的方法處理輪函數(shù)的3層線性混合層確保多輪之上的高度擴(kuò)散；非線性層將具有最優(yōu)的“最壞情況非線性特性”的S盒并行使用；密鑰加層單輪子密鑰簡(jiǎn)單的異或到中間狀態(tài)上，實(shí)現(xiàn)一次性掩蓋。算法說(shuō)明密鑰長(zhǎng)度可變，各自可獨(dú)立指定為128、192、256比特。狀態(tài)算法中間的結(jié)果也需要分組，稱(chēng)之為狀態(tài)，狀態(tài)可以用以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)Nb為分組長(zhǎng)度除32種子密鑰以字節(jié)為元素的矩陣陣列描述，陣列為4行，列數(shù)Nk為密鑰長(zhǎng)度除321.Rijndael數(shù)學(xué)基礎(chǔ)定義一個(gè)由組成的字節(jié)b可表示為系數(shù)為{0，1}的二進(jìn)制多項(xiàng)式：

定義在上的加法定義為二進(jìn)制多項(xiàng)式的加法，且其系數(shù)模2。定義

在上的乘法（用符號(hào)·表示）定義為二進(jìn)制多項(xiàng)式的乘積模一個(gè)次數(shù)為8的不可約二進(jìn)制多項(xiàng)式，此不可約多項(xiàng)式為（十六進(jìn)制為‘11B’）

上面定義的乘法在上滿(mǎn)足結(jié)合律，且有一個(gè)本原元（‘02’）。定義

在上的二進(jìn)制多項(xiàng)式b(x)的乘法逆為滿(mǎn)足方程式的二進(jìn)制多項(xiàng)式a(x)，記為定義

函數(shù)xtime(x)定義為上的x·b(x)。其運(yùn)算如下：若b7=0，則x·b(x)的結(jié)果就是把字節(jié)b左移一位；若b7=1，則結(jié)果需異或‘1B’。定義

有限域上的多項(xiàng)式是系數(shù)取自元素的多項(xiàng)式，這樣，一個(gè)4字節(jié)向量與一個(gè)次數(shù)小于4的多項(xiàng)式相對(duì)應(yīng)。定義

上的多項(xiàng)式的加法定義為相應(yīng)項(xiàng)系數(shù)相加。因?yàn)樵谟蛏系募邮呛?jiǎn)單的按位異或，所以在域上的兩向量的加也就是簡(jiǎn)單的按位異或。定義

上的多項(xiàng)式和相乘模的積（表示為）為，其系數(shù)由下面4個(gè)式子得到：，，，，利用該定義有。可將上述計(jì)算表示為 注意到M(x)不是GF(28)上的不可約多項(xiàng)式（甚至也不是GF(2)上的不可約多項(xiàng)式），因此非0多項(xiàng)式的這種乘法不是群運(yùn)算。不過(guò)在Rijndael密碼中，對(duì)多項(xiàng)式b(x)，這種乘法運(yùn)算只限于乘一個(gè)固定的有逆元的多項(xiàng)式a(x)=a3x3+a2x2+a1x+a0。 定理3.1系數(shù)在GF(28)上的多項(xiàng)式a3x3+a2x2+a1x+a0是模x4+1可逆的，當(dāng)且僅當(dāng)矩陣在GF(28)上可逆。

證明：a3x3+a2x2+a1x+a0是模x4+1可逆的，當(dāng)且僅當(dāng)存在多項(xiàng)式h3x3+h2x2+h1x+h0(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1mod(x4+1)

因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0x+h3)=xmod(x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0x2+h3x+h2)=x2mod(x4+1)(a3x3+a2x2+a1x+a0)(h0x3+h3x2+h2x+h1)=x3mod(x4+1)將以上關(guān)系寫(xiě)成矩陣形式即得（證畢）多輪整體結(jié)構(gòu)算法說(shuō)明算法的輸入、輸出和種子密鑰可看成字節(jié)組成的一維數(shù)組。下標(biāo)范圍輸入輸出：0－4Nb-1，種子密鑰：0－4Nk-1數(shù)據(jù)單位數(shù)據(jù)單位轉(zhuǎn)換Nb=6和Nk=4的狀態(tài)密鑰陣列按此順序放入和讀出按此順序放入將明文變成狀態(tài)（state）分組和陣列中元素對(duì)應(yīng)關(guān)系分組下標(biāo)n陣列位置(i,j)i=nmod4,j=[n/4];n=i+4j輪數(shù)Nr與Nb和Nk對(duì)應(yīng)關(guān)系Nb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414輪函數(shù)字節(jié)代換行移位列混合密鑰加字節(jié)代換非線性代換，獨(dú)立地對(duì)狀態(tài)的每個(gè)字節(jié)進(jìn)行，并且代換表(S盒)可逆，記為ByteSub(State),分兩步將字節(jié)作為GF(28)上的元素映射到自己的逆元將字節(jié)做如下的GF(2)上變換字節(jié)代換AES的S盒y0123456789abcdefx0637c777bf26b6fc53001672bfed7ab761ca82c97dfa5947f0add4a2af9ca472c02b7fd9326363ff7cc34a5e5f171d83115304c723c31896059a071280e2eb27b275409832c1a1b6e5aa0523bd6b329e32f84553d100ed20fcb15b6acbbe394a4c58cf6d0efaafb434d338545f9027f503c9fa8751a3408f929d38f5bcb6da2110fff3d28cd0c13ec5f974417c4a77e3d645d1973960814fdc222a908846eeb814de5e0bdbae0323a0a4906245cc2d3ac629195e479be7c8376d8dd54ea96c56f4ea657aae08cba78252e1ca6b4c6e8dd741f4bbd8b8ad703eB5664803f60e613557b986c11d9eee1f8981169d98e949b1e87e9ce5528dff8ca1890dbfe6426841992d0fB054bb1695->2A逆字節(jié)代換InvSubBytes()逆字節(jié)替代變換是字節(jié)第替代變換的逆變換，在狀態(tài)的每個(gè)字節(jié)上應(yīng)用逆S盒。這是通過(guò)應(yīng)用字節(jié)替代變換中的仿射變換的逆變換，再對(duì)所得結(jié)果應(yīng)用有限域的乘法逆運(yùn)算得到的。AES的逆S盒y0123456789abcdefx052096ad53036a538bf40a39e81f3d7fb17ce339829b2fff87348e4344c4dee9cb2547b9432a6c2233dee4c950b42fac34e3082eA16628d924b2765ba2496d8bd125472f8f66486689816d4a45ccc5d65B69256c704850fdedb9da5e154657a78d9d84690d8ab008cbcd30af7e45805b8b345067d02c1e8fca3f0f02c1afbd0301138a6b83a9111414f67dcea97f2cfcef0b4e673996ac7422e7ad3585e2f937e81c75df6ea47f11a711d29c5896fb7620eaa18be1bbfc563e4bc6d279209adbc0fe78cd5af4c1fdda8338807c731b11210592780ec5fd60517fa919b54a0d2de57a9f93c99cefea0e03b4dae2af5b0c8ebbb3c83539961f172b047eba77d626e169146355210c7d上述S-盒對(duì)狀態(tài)的所有字節(jié)所做的變換記為例子行移位將狀態(tài)陣列的各行進(jìn)行循環(huán)移位，不同行的移位量不同0行：不動(dòng)1行：循環(huán)左移C1字節(jié)2行：循環(huán)左移C2字節(jié)3行：循環(huán)左移C3字節(jié)記為：ShiftRow(State)行移位示意圖行移位移位量與分組長(zhǎng)度的關(guān)系NbC1C2C3412361238134逆行移位InvShiftRows()逆行移位變換是行移位變換的逆變換，它對(duì)狀態(tài)的每一行進(jìn)行循環(huán)右移，其中第一行保持不變，第二行循環(huán)右移1個(gè)字節(jié)，第三行循環(huán)右移2個(gè)字節(jié)，第四行循環(huán)右移3個(gè)字節(jié)。列混合將每列視為GF(28)上多項(xiàng)式，與固定的多項(xiàng)式c(x)進(jìn)行模x4+1乘法,要求c(x)模x4+1可逆。表示為MixColumn(State)c(x)是與x4+1互素的，因此是模x4+1可逆的。列混合運(yùn)算也可寫(xiě)為矩陣乘法。設(shè)b(x)=c(x)a(x)，則圖3.21列混合運(yùn)算示意圖逆列混合InvMixColumns()逆列混合變換是列混合變換的逆，它將狀態(tài)矩陣中的每一列視為系數(shù)在上的次數(shù)小于4的多項(xiàng)式與同一個(gè)固定的多項(xiàng)式d(x)相乘。d(x)滿(mǎn)足(‘03’x3+‘01’x2+‘01’x+‘02