新編密碼學(xué) 課件 第4章 分組密碼

4.1分組密碼的設(shè)計準(zhǔn)則

4.2數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)

4.3高級數(shù)據(jù)加密標(biāo)準(zhǔn)(AES)

4.4IDEA算法

4.5SM4分組加密算法

4.6分組密碼的工作模式

4.7分組密碼的安全性4.1分組密碼的設(shè)計準(zhǔn)則分組密碼是指對固定長度的一組明文進行加密的一種加密算法,這一固定長度稱為分組長度。分組長度是分組密碼的一個參數(shù),其值取決于實際應(yīng)用的環(huán)境。對于通過計算機來實現(xiàn)的分組密碼算法,通常選取的分組長度為64位。這是一個折中的選擇,考慮到分組算法的安全性,分組長度不能太短,以保證加密算法能夠應(yīng)付密碼分析;考慮到分組密碼的實用性,分組長度又不能太長,以便于操作和運算。近年來,隨著計算機計算能力的不斷提高,分組長度為64位的分組密碼的安全性越來越不能滿足實際需求,為了提高加密的安全性,很多分組密碼開始選擇128位作為算法的分組長度。分組密碼的加密是對整個明文進行操作的,包括空格、標(biāo)點符號和特殊字符,而不僅僅是字符。分組密碼的加密過程是按分組長度n將明文分成若干個組,對每一個長度為n位的明文消息分組執(zhí)行相同的加密操作,相應(yīng)地產(chǎn)生一個n位的密文分組。由此可見,不同的n位明文消息分組共有2n個?？紤]到加密算法的可逆性(即保證解密過程的可行性),每一個不同的n位明文消息分組都應(yīng)該產(chǎn)生一個唯一的密文消息分組,加密過程對應(yīng)的變換被稱為可逆變換或非奇異變換。所以分組密碼算法從本質(zhì)上定義了一種從分組的明文消息到相應(yīng)的密文消息的可逆變換。在分組密碼中,必須處理一個問題———填充。因為分組加密是作用在大小固定的塊上的,如果明文的大小不是分組長度的整數(shù)倍,就需要進行填充。例如,分組的長度是64位(即8個字節(jié)),而明文的大小只有96位(即12個字節(jié)),在這種情況下,第二個分組就只有32位,這時需要進行填充。在分組加密中,要求填充是可逆的。也就是說,必須在加密時能添加填充字符,而在解密時能檢測出填充字符。常見的解決辦法是為明文添加(填充)足夠的0,從而使明文長度是分組長度的整數(shù)倍。這樣做就面臨它可能不可逆的問題。例如,對于明文字母“p”與添加了一些“0”后的明文字母“p”,經(jīng)加密后,再解密都得到“p”,這就無從知道明文是否帶有“0”。下面以舉例的方式介紹4種常見的分組密碼填充方式,其中第1種填充方式不可逆,后3種填充方式均可逆。假定塊長度為8字節(jié),要加密的明文數(shù)據(jù)長度為9字節(jié),那么消息被切成兩個塊,第2塊只有1字節(jié),需要填充7字節(jié)。如果把9字節(jié)的明文數(shù)據(jù)記為(1)Zeros填充算法:需要填充的7字節(jié)全部填充0。分組結(jié)果如下:第1個消息分組:F1F2F3F4F5F6F7F8。第2個消息分組:F900000000000000。Zeros填充算法無法區(qū)分第2個消息分組中F9

后的0序列是否明文中的原始序列,因此該填充算法不可逆。(2)X923填充算法:需要填充的7字節(jié)中前6字節(jié)填充0,最后1字節(jié)記錄填充的總字節(jié)數(shù)。分組結(jié)果如下:第1個消息分組:F1F2F3F4F5F6F7F8。第2個消息分組:F900000000000007。(3)PKCS7填充算法:需要填充的7字節(jié)中的每字節(jié)填充需要填充的總字節(jié)數(shù)。分組結(jié)果如下:第1個消息分組:F1F2F3F4F5F6F7F8。第2個消息分組:F907070707070707。(4)ISO10126填充算法:需要填充的7字節(jié)中前6字節(jié)填充隨機字節(jié)序列,最后1字節(jié)記錄填充的總字節(jié)數(shù)。分組結(jié)果如下:第1個消息分組:F1F2F3F4F5F6F7F8。第2個消息分組:F97D2A75EFF8EF07。與古典密碼不同的是,在分組密碼中,密文塊的所有位與明文塊的所有位有關(guān),正是這個原因體現(xiàn)了分組密碼的最重要特征:如果明文的單個位發(fā)生了改變,那么密文塊的位平均有一半要發(fā)生改變。分組密碼是現(xiàn)代密碼學(xué)的重要組成部分,當(dāng)前被廣泛使用的分組加密算法幾乎都是基于Feistel分組密碼的結(jié)構(gòu)設(shè)計的。為了對具有代表性的分組密碼DES算法、AES算法和IDEA算法進行深入研究和分析,我們首先介紹Feistel分組密碼的基本結(jié)構(gòu)和設(shè)計準(zhǔn)則。4.1.1Feistel分組密碼的基本結(jié)構(gòu)Feistel密碼結(jié)構(gòu)是基于1949年Shannon提出的交替使用替換和置換方式構(gòu)造密碼體制的設(shè)想提出的。在設(shè)計密碼體制的過程中,Shannon提出了能夠破壞對密碼系統(tǒng)進行各種統(tǒng)計分析攻擊的兩個基本操作:擴散和混淆。擴散的目的是使明文和密文之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜;混淆的目的是使密文和密鑰之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜。為了使攻擊者無法得到密鑰,在擴散過程中,明文的統(tǒng)計信息被擴散到密文的更長的統(tǒng)計信息中,使得每一個密文數(shù)字與許多明文數(shù)字相關(guān),從而使密文的統(tǒng)計信息與明文之間的統(tǒng)計關(guān)系盡量復(fù)雜,以至于密文的統(tǒng)計信息對于攻擊者來說是無法利用的;在混淆過程中,密文的統(tǒng)計信息與加密密鑰的取值之間的關(guān)系盡量復(fù)雜,以至于攻擊者很難從中推測出加密密鑰。擴散和混淆給出了分組密碼應(yīng)具有的本質(zhì)特性,成為分組密碼設(shè)計的基礎(chǔ)。Feistel分組密碼的基本結(jié)構(gòu)如圖4-1所示。加密算法的初始輸入是一個長度為2L位的明文分組序列和一個初始密鑰K,在加密之前先將分組的明文序列等分成長度均為L位的L0

和R0

兩部分。加密過程分為n輪,其中第i輪以第i-1輪輸出的Li-1和Ri-1作為輸入,此外第i輪加密過程的輸入還包括從初始密鑰K產(chǎn)生的子密鑰Ki。第i輪的加密過程由兩步操作實現(xiàn):第一步先對Ri-1使用輪函數(shù)F和子密鑰Ki進行變換,再將變換結(jié)果與Li-1進行異或運算,運算結(jié)果作為Ri;第二步將Ri-1直接作為Li

得到第i輪的輸出值。最終將加密過程的輸出序列Ln

和Rn

組合起來產(chǎn)生相應(yīng)的長度為2L位的密文。Feistel分組密碼的第一個加密階段的示意圖如圖4-2所示。S操作通過密鑰為每一個階段生成一個子密鑰,T操作為每一輪加密過程中的核心操作,要求為非線性運算,保證加密算法的安全性。在Feistel分組密碼的每一輪加密過程中,第一步操作是一個替換過程,第二步操作是一個置換過程,通過“替換

置換”這兩步操作實現(xiàn)了Shannon提出的擴散和混淆的目的。根據(jù)圖41所示的Feistel分組密碼的基本結(jié)構(gòu)和圖42所示的Feistel分組密碼的第一個加密階段可知,Feistel分組密碼的安全性取決于以下幾個方面。(1)明文消息和密文消息的分組大小:在其他條件相同的情況下,每一輪加密的分組長度越大,加密算法的安全性就越高,而相應(yīng)的加密速度也越慢,效率越低。(2)子密鑰的大小:算法的安全性隨著子密鑰長度的增加而提高,但是相應(yīng)的加密速度會降低,所以設(shè)計分組密碼時需要在安全性和加密效率之間進行平衡。在實際應(yīng)用中,一般認(rèn)為,要保證分組加密算法滿足計算安全性,子密鑰的長度至少為128位。(3)循環(huán)次數(shù):循環(huán)次數(shù)越多,安全性越高,相應(yīng)的加密效率也就越低。(4)子密鑰產(chǎn)生算法:在初始密鑰給定的情況下,產(chǎn)生子密鑰的算法越復(fù)雜,加密算法的安全性越高。(5)輪函數(shù)F:對于輪函數(shù)的討論相對較復(fù)雜,一般認(rèn)為,輪函數(shù)F越復(fù)雜,對應(yīng)的加密算法的安全性越高。Feistel分組密碼的解密過程與加密過程是相同的。解密過程將密文作為算法的輸入,同時按照與加密過程相反的次序使用子密鑰對密文序列進行加密,即第1輪使用Kn,第2輪使用Kn-1,依次類推,最后一輪使用K1,進行相同次數(shù)加密,就得到相應(yīng)的明文序列。4.1.2F函數(shù)的設(shè)計準(zhǔn)則Feistel分組密碼的核心是輪函數(shù)F。輪函數(shù)F在Feistel分組密碼算法中的作用是對消息序列進行混淆操作。為了保證這樣的混淆操作的安全性,設(shè)計輪函數(shù)F的一個基本準(zhǔn)則是要求輪函數(shù)F是非線性的。輪函數(shù)F的非線性程度越強,則算法的安全性越高,相應(yīng)的攻擊難度也就越大。S-盒是F函數(shù)的重要組成部分,其設(shè)計問題一直是人們關(guān)注的重點。對于S-盒的設(shè)計,基本要求是希望S-盒輸入序列的任何變動都使得輸出序列產(chǎn)生看似隨機的變動,并且這兩種變動之間的關(guān)系應(yīng)該是非線性的。一個好的加密算法必須具有以下特征:密鑰要足夠大,使得強力攻擊法無效或至少是得不償失,這是最基本的特征;如果加密算法生成的密文通過了隨機性測試,那么在很長一段時間里,該加密算法會給人以安全感。對于加密算法的評價,更為正式的要求是加密算法應(yīng)該具有良好的雪崩效應(yīng),即任何輸入位或密鑰位與輸出位之間不應(yīng)有任何聯(lián)系。換句話說,密文中的內(nèi)容不能含有關(guān)于密鑰或明文的提示,即輸入消息序列或密鑰位的一個位的值發(fā)生改變,相應(yīng)的輸出序列應(yīng)該使多個位的值發(fā)生變化。設(shè)計的F函數(shù)應(yīng)該滿足嚴(yán)格的雪崩準(zhǔn)則(StrictAvalancheCriterion,SAC)。這個準(zhǔn)則的具體內(nèi)容是:對于任意的i,j,當(dāng)任何一個輸入位i發(fā)生改變時,S-盒的任何輸出位j的值發(fā)生改變的概率為1/2。雖然以上準(zhǔn)則是對S-盒的設(shè)計提出的,但是由于S-盒是F函數(shù)的重要組成部分,所以該準(zhǔn)則的要求也可以作為F函數(shù)的設(shè)計要求。設(shè)計的F函

數(shù)

還

應(yīng)

滿

足

的

另

一

個

準(zhǔn)

則

是

位

獨

立

準(zhǔn)

則

。這個準(zhǔn)則的具體內(nèi)容是:對于任意的i,j,k,當(dāng)任何一個輸入位i發(fā)生改變時,輸出位j和k的值應(yīng)該獨立地發(fā)生改變。S-盒的設(shè)計除了要滿足SAC和BIC準(zhǔn)則外,還應(yīng)該滿足的一個條件是保證的雪崩準(zhǔn)則。這個準(zhǔn)則的具體內(nèi)容是:一個好的S-盒應(yīng)該滿足?階的GA。也就是說,若輸入序列中有1位的值發(fā)生改變,則輸出序列中至少有?位的值發(fā)生改變。一般要求?的值介于2~5。當(dāng)然,除了以上要求,關(guān)于F函數(shù)和S-盒的設(shè)計還有其他建議和要求。這些要求和建議都是為了改進F函數(shù)和S-盒的非線性和隨機性,從而增強分組密碼算法的安全性。4.2數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)DES算法是使用最為廣泛的一種分組密碼算法。DES對推動密碼理論的發(fā)展和應(yīng)用起了重大作用。學(xué)習(xí)DES算法對掌握分組密碼的基本理論、設(shè)計思想和實際應(yīng)用都有重要的參考價值。20世紀(jì)70年代中期,美國政府認(rèn)為

需要一個強大的標(biāo)準(zhǔn)加密系統(tǒng),美國國家標(biāo)準(zhǔn)局提出了開發(fā)這種加密算法的請求,最終IBM的Lucifer加密系統(tǒng)勝出。有關(guān)DES算法的歷史過程如下:1972年,美國商業(yè)部所屬的美國國家標(biāo)準(zhǔn)局開始實施計算機數(shù)據(jù)保護標(biāo)準(zhǔn)的開發(fā)計劃。1973年5月13日,美國國家標(biāo)準(zhǔn)局發(fā)布文告征集在傳輸和存儲數(shù)據(jù)中保護計算機數(shù)據(jù)的密碼算法。1975年3月17日,美國國家標(biāo)準(zhǔn)局首次公布DES算法描述,認(rèn)真地進行

了

公

開討論。1977年1月15日,美國國家標(biāo)準(zhǔn)局正式批準(zhǔn)DES為無密級應(yīng)用的加密標(biāo)準(zhǔn)(FIPS46)。該標(biāo)準(zhǔn)于當(dāng)年7月1日正式生效。以后每隔5年美國國家安全局對DES的安全性進行一次評估,以便確定是否繼續(xù)使用它作為加密標(biāo)準(zhǔn)。在1994年1月的評估后,美國國家標(biāo)準(zhǔn)局決定1998年12月以后不再將DES作為數(shù)據(jù)加密標(biāo)準(zhǔn)。4.2.1DES的描述DES是一個包含16個階段的“替換

置換”的分組加密算法,它以64位為分組長度對數(shù)據(jù)進行加密。64位的分組明文序列作為加密算法的輸入,經(jīng)過16輪加密得到64位的密文序列。DES密鑰的長度有64位,但用戶只提供56位,其余8位由算法提供,分別放在8,16,24,32,40,48,56,64位上,結(jié)果是每8位密鑰包含了用戶提供的7位和DES算法確定的1位。添加的位是有選擇的,使得每個8位的塊都含有奇數(shù)個奇偶校驗位(即1的個數(shù)為奇數(shù))。DES的密鑰可以是任意的56位的數(shù),其中極少量的56位的數(shù)被認(rèn)為是弱密鑰。為了保證加密的安全性,在加密過程中應(yīng)該盡量避免使用這些弱密鑰。DES對64位的明文分組進行操作。首先通過一個初始置換IP,將64位的明文分成各32位長的左半部分和右半部分,只在16輪加密過程進行之前進行一次初始置換,在接下來的輪加密過程中不再進行該置換操作。在經(jīng)過初始置換操作后,對得到的64位序列進行16輪加密運算(運算函數(shù)為f),在運算過程中,輸入數(shù)據(jù)與密鑰結(jié)合。經(jīng)過16輪后,左、右半部分合在一起得到一個64位的輸出序列,該序列再經(jīng)過一個末尾置換IP-1(逆初始置換)獲得最終的密文。具體加密流程見圖4-3。初始置換IP和對應(yīng)的逆初始置換IP-1操作并不會增強DES算法的安全性,它的主要目的是更容易地將明文和密文數(shù)據(jù)以字節(jié)大小放入DES芯片中。DES的每個階段使用的是不同的子密鑰和上一階段的輸出,但執(zhí)行的操作相同。這些操作定義在3種盒中,分別稱為擴充盒(ExpansionBox,E-盒)、替換盒(SubstitutionBox,S-盒)、置換盒(PermutationBox,P-盒)。在每一輪加密過程中,3個盒子的使用順序如圖4-4所示。如圖4-4所示,在每一輪加密過程中,函數(shù)f的運算包括以下四步:首先將56位的密鑰等分成長度為28位的兩部分,根據(jù)加密輪數(shù),這兩部分密鑰分別循環(huán)左移1位或2位后合并成新的56位密鑰序列,從移位后的56位密鑰序列中選出48位(該部分采用一個壓縮置換實現(xiàn));其次通過一個擴展變換E-盒將輸入序列32位的右半部分?jǐn)U展成48位后與48位的輪密鑰進行異或運算;接下來通過8個S-盒將異或運算后獲得的48位的序列替代成一個32位的序列;最后對32位的序列應(yīng)用P-盒進行置換變換得到函數(shù)f的32位輸出序列。將函數(shù)f的輸出與輸入序列的左半部分進行異或運算后的結(jié)果作為新一輪加密過程的輸入序列的右半部分,將當(dāng)前輸入序列的右半部分作為新一輪加密過程的輸入序列的左半部分。上述過程重復(fù)操作16次,便實現(xiàn)了DES的16輪加密運算。假設(shè)Bi是第i輪計算的結(jié)果,則Bi為一個64位的序列,Li

和Ri

分別是Bi

的左半部分和右半部分,Ki是第i輪的48位密鑰,且f是實現(xiàn)替換、置換、密鑰異或等運算的函數(shù),前15輪中每一輪變換的邏輯關(guān)系為第16輪變換的邏輯關(guān)系為下面詳細說明DES加密過程中的基本操作。(1)初始置換。初始置換(InitialPermutation)又稱IP置換,在第一輪運算之前執(zhí)行,對輸入分組實施如圖4-5所示的IP置換。例如,圖4-5表示該IP置換把輸入序列的第58位置換到輸出序列的第1位,把輸入序列的第50位置換到輸出序列的第2位,依次類推。(2)密鑰置換。DES加密算法輸入的初始密鑰為8字節(jié),由于每字節(jié)的第8位用來作為初始密鑰的校驗位,所以加密算法的初始密鑰不考慮每字節(jié)的第8位,DES的初始密鑰實際對應(yīng)一個56位的序列,每字節(jié)的第8位作為奇偶校驗位以確保密鑰不發(fā)生錯誤。DES密鑰的生成過程如圖4-6所示。首先對初始密鑰進行如圖4-7所示的密鑰置換操作,然后從密鑰置換后的56位密鑰中產(chǎn)生出不同的48位子密鑰(Subkey),這些子密鑰Ki

通過以下方法產(chǎn)生。首先將56位密鑰等分成兩部分,然后根據(jù)加密輪數(shù),這兩部分密鑰分別循環(huán)左移1位或2位。表4-1給出了對應(yīng)不同輪數(shù)產(chǎn)生子密鑰時具體循環(huán)左移的位數(shù)。對兩個28位的

密

鑰

循

環(huán)

左

移

以

后,通

過

如

圖4-8所

示

的

壓

縮

置

換(也稱為置換選擇)從56位密鑰中選出48位作為當(dāng)前加密的輪密鑰。圖48給出的壓縮置換不僅置換了56位密鑰序列的順序,同時也選擇出了一個48位的子密鑰。例如,56位密鑰中位于第33位的密鑰對應(yīng)輸出到48位輪密鑰的第35位,而56位的密鑰中位于第18位的密鑰在輸出的48位輪密鑰中將不會出現(xiàn)。圖4-6所示的產(chǎn)生輪密鑰的過程中,由于每一次壓縮置換之前都包含一個循環(huán)移位操作,所以產(chǎn)生每一個子密鑰時使用了不同的初始密鑰子集。雖然初始密鑰的所有位在子密鑰中使用的次數(shù)并不完全相同,但在產(chǎn)生的16個48位子密鑰中,初始密鑰的每一位大約會被14個子密鑰使用。由此可見,密鑰的設(shè)計非常精巧,使得密鑰隨明文的每次置換而不同,每個階段使用不同的密鑰來執(zhí)行“替換”或“置換”操作。(3)擴展變換。擴展變換(ExpansionPermutation,E-盒)將64位輸入序列的右半部分Ri從32位擴展到48位。擴展變換不僅改變了Ri中32位輸入序列的次序,而且重復(fù)了此位。這個操作有以下3個基本目的:①

經(jīng)過擴展變換可以應(yīng)用32位輸入序列產(chǎn)生一個與輪密鑰長度相同的48位序列,從而實現(xiàn)與輪密鑰的異或運算;②

擴展變換針對32位輸入序列提供了一個48位的結(jié)果,使得在接下來的替代運算中能進行壓縮,從而達到更好的安全性;③

由于輸入序列的每一位將影響到兩個替換,所以輸出序列對輸入序列的依賴性將傳播得更快,體現(xiàn)出良好的雪崩效應(yīng)。因此該操作有助于設(shè)計的DES算法盡可能快地使密文的每一位依賴明文的每一位。圖4-9給出了擴展變換中輸出位與輸入位的對應(yīng)關(guān)系。例如,處于輸入分組中第3位的數(shù)據(jù)對應(yīng)輸出序列的第4位,而輸入分組中第21位的數(shù)據(jù)則分別對應(yīng)輸出序列的第30位和第32位。在擴展變換過程中,每一個輸出分組的長度都大于輸入分組,而且該過程對于不同的輸入分組都會產(chǎn)生唯一的輸出分組。E-盒的真正作用是確保最終的密文與所有的明文位都有關(guān)。(4)S-盒替換。每一輪加密的48位輪密鑰與擴展后的分組序列進行異或運算以后,得到一

個48位

的

結(jié)

果

序

列,接

下

來

應(yīng)

用S-盒

對

該

序

列

進

行

替換運算。替換由8個S-盒完成,每個S-盒對應(yīng)6位輸入序列,得到相應(yīng)的4位輸出序列。在DES算法中,這8個S-盒是不同的,48位輸入被分為8個6位的分組,每一分組對應(yīng)一個S-盒替換操作,分組1由S-盒1操作,分組2由S-盒2操作,依次類推(見圖4-10)。4.2.2搜索引擎的基本工作原理看似簡單的搜索引擎背后涉及包括數(shù)據(jù)結(jié)構(gòu)、索引、算法、知識表示、自然語言處理、信息檢索、人工智能、計算機網(wǎng)絡(luò)、分布式處理、數(shù)據(jù)庫、數(shù)據(jù)挖掘等多個方面的內(nèi)容。通常，搜索引擎主要包括信息采集、信息加工、信息檢索與檢索結(jié)果提供這幾個部分。信息采集模塊(搜集器)以一定的策略在因特網(wǎng)等信息源中采集相關(guān)信息。大多數(shù)搜索引擎利用能夠從互聯(lián)網(wǎng)上自動收集網(wǎng)頁的Spider系統(tǒng)程序，自動訪問互聯(lián)網(wǎng)，并沿著網(wǎng)頁中的URL爬到其他網(wǎng)頁。不斷重復(fù)此過程，并把爬過的所有網(wǎng)頁收集回來。DES算法中,每個S-盒對應(yīng)一個4行16列的表,表中的每一項都是一個十六進制的數(shù),相應(yīng)地對應(yīng)一個4位的序列。圖4-11列出了所有8個S-盒。輸入序列以一種非常特殊的方式對應(yīng)S-盒中的某一項,通過S-盒的6位輸入確定其對應(yīng)的輸出序列所在的行和列的值。假定將S-盒的6位輸入標(biāo)記為b1,b2,b3,b4,b5,b6,則b1和b6組合構(gòu)成了一個2位序列,該2位序列對應(yīng)一個介于0~3的十進制數(shù)字,該數(shù)字表示輸出序列在對應(yīng)的S-盒中所處的行,輸入序列中b2~b5

構(gòu)成了一個4位序列,該4位序列對應(yīng)一個介于0~15的十六進制數(shù)字,該數(shù)字表示輸出序列在對應(yīng)的S-盒中所處的列,根據(jù)行和列的值可以確定相應(yīng)的輸出序列。4.2.2DES的分析DES自被采用作為聯(lián)邦數(shù)據(jù)加密標(biāo)準(zhǔn)以來,就遭到了人們猛烈的批評和懷疑。首先是DES的密鑰長度是56位,很多人擔(dān)心這樣的密鑰長度不足以抵御窮舉式搜索攻擊;其次是DES的內(nèi)部結(jié)構(gòu)即S-盒的設(shè)計標(biāo)準(zhǔn)是保密的,使用者無法確信DES的內(nèi)部結(jié)構(gòu)不存在任何潛在的弱點。S-盒是DES強大功能的源泉,8個不同的S-盒定義了DES的替換模式。查看DES的S-盒結(jié)構(gòu)可以發(fā)現(xiàn),S-盒具有非線性的特征,這意味著給定一個“輸入-輸出”對的集合,很難預(yù)計所有S-盒的輸出。S-盒的另一個很重要的特征是:改變一個輸入位,至少會改變兩個輸出位。例如,如果S-盒1的輸入為010010,其輸出位于行0(二進制為0000)列9(二進制為1001),值為10(二進制為1010)。如果輸入的某位改變,假設(shè)改變?yōu)?10010,那么輸出位于行2(二進制為0010)列9(二進制為1001),其值為12(二進制為1100)。比較這兩個值,中間的兩個位發(fā)生了改變。事實上,后來的實踐表明,DES的S-盒被精心設(shè)計成能夠防止差分分析方法等的攻擊。另外,DES的初始方案———IBM的Lucifer密碼體制具有128位的密鑰長度,DES的最初方案也有64位的密鑰長度,但是后來公布的DES算法將其減少到56位。IBM聲稱減少的原因是必須在密鑰中包含8位奇偶校驗位,這意味著64位的存儲空間只能包含一個56位的密鑰。經(jīng)過人們的不懈努力,對S-盒的設(shè)計已經(jīng)有了一些基本的設(shè)計要求。例如,S-盒的每行必須包括所有可能輸出位的組合;如果S-盒的兩個輸入只有1位不同,那么輸出位必須至少有2位不同;如果兩個輸入中間的2位不同,那么輸出也必須至少有2位不同。許多密碼體制都存在著弱密鑰,DES也存在這樣的弱密鑰和半弱密鑰。如果DES的密鑰k產(chǎn)生的子密鑰滿足:k1=k2=…=k16則有這樣的密鑰k稱為DES算法的弱密鑰。DES的弱密鑰有以下4種:如果DES的密鑰k和k'滿足:則稱密鑰k和k'是DES算法的一對半弱密鑰。半弱密鑰只交替地生成兩種密鑰。DES的半弱密鑰有以下6對:以上0表示二值序列0000,1表示二值序列0001,E表示二值序列1110,F表示二值序列1111。對DES攻擊最有意義的方法是差分分析方法。差分分析方法是一種選擇明文攻擊法,最初是由IBM的設(shè)計小組在1974年發(fā)現(xiàn)的,所以IBM在設(shè)計DES算法的S-盒和換位變換時有意識地避免差分分析攻擊,對S-盒在設(shè)計階段進行了優(yōu)化,使得DES能夠抵抗差分分析攻擊。對DES攻擊的另一種方法是線性分析方法。線性分析方法是一種已知明文攻擊法,由MitsuruMatsui在1993年提出。這種攻擊需要大量的已知“明文-密文”對,但比差分分析方法的少。當(dāng)將DES用于智能卡等硬件裝置時,通過觀察硬件的性能特征,可以發(fā)現(xiàn)一些加密操作的信息,這種攻擊方法叫作旁路攻擊法。例如,當(dāng)處理密鑰的“1”位時,要消耗更多的能量,通過監(jiān)控能量的消耗可以知道密鑰的每個位。此外,還有一種攻擊可用于監(jiān)控完成一個算法所耗時間的微秒數(shù),所耗時間數(shù)也可以反映部分密鑰的位。DES加密的輪數(shù)對安全性也有較大的影響。如果DES只進行8輪加密過程,則在普通的個人電腦上只需要幾分鐘就可以破譯密碼。如果DES加密過程進行16輪,則應(yīng)用差分分析攻擊比窮盡搜索攻擊稍微有效一些。然而如果DES加密過程進行18輪,則差分分析攻擊和窮盡搜索攻擊的效率基本一樣。如果DES加密過程進行19輪,則窮盡搜索攻擊的效率還要優(yōu)于差分分析攻擊的效率?？傮w來說,對DES的破譯研究大體上可分為以下三個階段:第一階段是從DES誕生至20世紀(jì)80年代末,這一時期,研究者發(fā)現(xiàn)了DES的一些可利用的弱點,如DES中明文、密文和密鑰間存在互補關(guān)系,DES存在弱密鑰、半弱密鑰等,然而這些弱點都沒有對DES的安全性構(gòu)成實質(zhì)性威脅。第二階段以差分密碼分析和線性密碼分析這兩種密碼分析方法的出現(xiàn)為標(biāo)志。差分密碼攻擊的關(guān)鍵是基于分組密碼函數(shù)的差分不均勻性,分析明文對的“差量”對后續(xù)各輪輸出的“差量”的影響,由某輪的輸入差量和輸出對來確定本輪的部分內(nèi)部密鑰。線性密碼分析的主要思想是尋求具有最大概率的明文若干比特的和、密鑰若干比特的和與密文若干比特的和之間的線性近似表達式,從而破譯密鑰的相應(yīng)比特。盡管這兩種密碼分析方法還不能完全破譯16輪的DES,但它們成功破譯了8輪、12輪的DES,徹底打破了DES密碼體制“牢不可破”的神話,奏響了破譯DES的前奏曲。第三階段是DES被破譯階段。20世紀(jì)90年代末,隨著大規(guī)模集成電路工藝的不斷發(fā)展,采用窮舉法搜索DES密鑰空間來進行破譯在硬件設(shè)備上已經(jīng)具備條件。由美國

電子前沿基金會牽頭,密碼研究所和高級無線電技術(shù)公司參與設(shè)計建造了DES破

譯

機。該

破

譯

機

可

用

兩

天

多

時

間

破

譯

一

份DES加密的密文,而整個破譯機的研

制

經(jīng)

費

不

到25萬

美

元。DES破

譯

機

采

用

的

破

譯

方

法

是強破譯攻擊法,這種方法針對特定的加密算法設(shè)計出相應(yīng)的硬件來對算法的密鑰空間進行窮舉搜索。在2000年的“挑

戰(zhàn)DES”比

賽

中,強

破

譯

攻

擊

法

僅

用2個

小

時

就

破

譯了DES算法。DES密碼體制雖然已經(jīng)被破譯,但是從對密碼學(xué)領(lǐng)域的貢獻來看,DES密碼體制的提出和廣泛使用推動了密碼學(xué)在理論和實現(xiàn)技術(shù)上的發(fā)展。DES密碼體制對密碼技術(shù)的貢獻可以歸納為以下幾點:(1)DES密碼體制公開展示了能完全適應(yīng)某一歷史階段的信息安全需求的一種密碼體制的構(gòu)造方法。(2)DES密碼體制是世界上第一個數(shù)據(jù)加密標(biāo)準(zhǔn),它確立了這樣一個原則,即算法的細節(jié)可以公開但密碼的使用法仍是保密的。(3)DES密碼體制表明用分組密碼對密碼算法進行標(biāo)準(zhǔn)化這種方法是方便可行的。(4)由DES的出現(xiàn)而引起的討論及附帶的標(biāo)準(zhǔn)化工作確立了安全使用分組密碼的若干準(zhǔn)則。(5)DES的出現(xiàn)推動了密碼分析理論和技術(shù)的快速發(fā)展,出現(xiàn)了差分分析、線性分析等許多新的有效的密碼分析方法。隨著計算機硬件技術(shù)的飛速發(fā)展,DES的安全性越來越受到人們的質(zhì)疑。為了提高DES加密算法的安全性,人們一直在研究改進DES算法安全性能的方法。下面介紹兩種較為基本的針對DES算法的改進方法。(1)改進方法一。設(shè)明文消息x的長度比較大,將其分為64位一組,其結(jié)果表示如下:相應(yīng)的密文序列y表示為其中,yi=DESk(xi)(i=1,2,…,n)。在以上加密過程中,當(dāng)明文序列的結(jié)構(gòu)有一定的固定格式時,相應(yīng)的密文序列也會表現(xiàn)出一定的規(guī)律性,從而導(dǎo)致加密算法不安全。對該問題可以采用分組反饋的方法進行改進。對明文分組xi(i=2,3,…,n)進行加密前,先將明文分組消息和前一組加密的密文分組序列yi-1進行異或運算,然后對運算的結(jié)果序列進行加密操作,即以上加密過程的流程如圖4-14所示。相應(yīng)的解密過程為以上解密過程的流程如圖415所示。以上改進方法采用了密文反饋的方式進行加密,當(dāng)明文序列的結(jié)構(gòu)有一定的固定格式時,相應(yīng)的密文序列表現(xiàn)出的規(guī)律性會被隱藏,從而能有效改進加密算法的安全性。(2)改進方法二。由于DES算法的密鑰長度只有56位,因此其安全性較差。最簡單的改進算法安全性的方法是應(yīng)用不同的密鑰對同一個分組消息進行多次加密,由此產(chǎn)生了多重DES加密算法。4.2.3多重DES下面分別描述雙重DES和三重DES的加密過程。1.雙重DES最簡單的雙重DES的加密過程是采用兩個不同的密鑰分兩步對明文分組消息進行加密。給定一個明文分組x和兩個加密密鑰K1、K2,相應(yīng)的密文消息y由下式得到:雙重DES算法的加密流程如圖4-16所示。相應(yīng)的解密過程為雙重DES算法的解密流程如圖4-17所示。相比于傳統(tǒng)的DES算法,以上改進方案的密鑰長度變?yōu)?28位(實際為112位),因此算法的安全性有一定的改進。下面我們對雙重DES加密方法進行安全性分析。假設(shè)對DES與所有的56位密鑰值給定任意的兩個密鑰K1

和K2,如果都可以得到一個密鑰K3,使得成立,那么雙重DES的兩次加密(甚至包括任意多次加密)對算法的安全性來說都沒有實質(zhì)性的意義,因為得到的加密結(jié)果都等于DES算法使用一個56位密鑰進行一次加密的結(jié)果。好在這一假設(shè)并不成立,如果將DES加密算法看作從64位分組消息序列到另一個64位消息序列的一個映射,考慮到加密/解密結(jié)果的唯一性,這個映射應(yīng)是一個置換。對于所有可能的264個明文消息分組序列,用一個特定的密鑰進行DES加密就是把每個分組映射為另一個唯一的64位消息序列,那么對于264個明文消息分組序列,產(chǎn)生一個置換的不同映射的個數(shù)為另一方面,DES的每一個密鑰都可以定義一個映射,因此由56位密鑰可以定義的映射個數(shù)為1992年,人們證明了由兩個不同的密鑰組成的雙重DES對應(yīng)的映射不會出現(xiàn)在DES定義的映射中,這意味著雙重DES不會等價于DES。這說明雙重DES加密算法的密鑰空間要大于DES算法,所以其安全性優(yōu)于DES算法。如圖4-18所示,雙重

DES加密算法不能抵抗中間點匹配攻擊法。2.三重DES在眾多多重DES算法中,由Tuchman提出的三重DES算法是一種被廣泛接受的改進方法。在該加密算法中,加密過程用兩個不同的密鑰K1

和K2

對一個分組消息進行3次DES加密。首先使用第一個密鑰進行DES加密,然后使用第二個密鑰對第一次的結(jié)果進行DES解密,最后使用第一個密鑰對第二次的結(jié)果進行DES加密,即三重DES算法的加密流程如圖4-19所示。解密過程首先使用第一個密鑰進行DES解密,然后使用第二個密鑰對第一次的結(jié)果進行DES加密,最后使用第一個密鑰對第二次的結(jié)果進行DES解密,即三重DES算法的解密流程如圖4-20所示。以上這種加密模式稱為加密

解密

加密(EDE)模式。DES算法的密鑰長度是56位,所以三重DES算法的密鑰長度是112位。使用兩個密鑰的三重DES是一種較受歡迎的改進算法,目前三重DES已經(jīng)被用于密鑰管理標(biāo)準(zhǔn)ANSX9.17和ISO8732中。為了找到一種安全有效的DES替代算法。1997年4月15日,美國國家標(biāo)準(zhǔn)技術(shù)研究所發(fā)

起

了

征

集DES的

替

代

算法———AES算法的活動,希望找到一種非保密的可以公開和免費使用的新的分組密碼算法,使其成為21世紀(jì)秘密和公開部門的數(shù)據(jù)加密標(biāo)準(zhǔn)。經(jīng)過長達4年的算法征集和研究,最終確定了將兩名比利時人Daemen和Rijmen提出的Rijndael分組加密算法作為DES的替代算法。4.3高級數(shù)據(jù)加密標(biāo)準(zhǔn)(AES)自從DES加密算法問世以來,美國國家安全局(NationalSecurityAgency,NSA)以外的研究人員20年來嘗試破解56位DES,取得了不同程度的成功,為此,美國國家標(biāo)準(zhǔn)局提出了一項取代DES的投標(biāo)計劃,這就是高級加密標(biāo)準(zhǔn)AES。對于DES算法的改進工作從1997年開始公開進行。1997年9月12日,美國國家標(biāo)準(zhǔn)技術(shù)研究所(NIST)發(fā)布了征集算法的正式公告和具體細節(jié),其要求如下:(1)應(yīng)是對稱分組加密,具有可變長度的密鑰(128、192或256位),具有128位的分組長度。(2)應(yīng)比三重DES快,至少與三重DES一樣安全。(3)應(yīng)可應(yīng)用于公共領(lǐng)域并能夠在全世界范圍內(nèi)免費使用。(4)應(yīng)至少在30年內(nèi)是安全的。1998年8月20日,NIST在第一次AES候選大會上公布了滿足條件的來自10個不同國家的15個AES的候選算法。在確定最終算法之前,這些算法先經(jīng)歷了一個很長的公開分析過程。在第二次會議之后,NIST從這15個候選算法中選出了5個AES的候選算法,分別是IBM提交的MARS,RSA實驗室提交的RC6,Daemen和Rijmen提交的Rijndael,Anderson、Biham和Knudsen提

交

的Serpent,Schneier、Whiting、Wagner、Hall和Ferguson提交的Twofish。這5個候選算法都經(jīng)受了6個月的考驗,又經(jīng)過6個月的測試。到2000年10月2日,NIST正式宣布Rijndael(讀作“rain-doll”)勝出,Rijndael被選為高級數(shù)據(jù)加密標(biāo)準(zhǔn)。Rijndael能夠勝出，除了具有軟件實現(xiàn)速度和子密鑰生成時間的優(yōu)勢外，另一部分原因是它能用硬件有效地實現(xiàn)。加密速度和硬件實現(xiàn)的特性也是評估加密算法優(yōu)劣的重要因素。加密算法使用硬件實現(xiàn)主要有兩個原因:一是軟件實現(xiàn)太慢,不能滿足應(yīng)用需求;二是硬件實現(xiàn)在速度上的優(yōu)勢可以暴露加密算法的一些弱點。目前,將AES嵌入硬件有兩種方法:一種是使用ASIC(專用集成電路)實現(xiàn);另一種是使用FPGA(現(xiàn)場可編程邏輯門陣列)實現(xiàn)。這兩種方法中,FPGA更為靈活。4.3.1AES數(shù)學(xué)基礎(chǔ)AES中的運算是按字節(jié)或4字節(jié)的字定義的,并把1字節(jié)看成系數(shù)在GF(2)上的次數(shù)小于8的多項式,即把1字節(jié)看成有限域GF(28)中的一個元素,把一個4字節(jié)的字看成系數(shù)在GF(28)上且次數(shù)小于4的多項式。在有限域GF(28)上的字節(jié)運算中,把b7b6b5b4b3b2b1b0構(gòu)成的1字節(jié)看成系數(shù)在(0,1)中取值的多項式:例如,把十六進制數(shù)23對應(yīng)的二進制數(shù)00100011看成1字節(jié),則對應(yīng)的多項式為x5+x+1。1.多項式加法在多項式表示中,兩個元素的和是一個多項式,其系數(shù)是兩個元素的對應(yīng)系數(shù)的模2加。2.多項式乘法有限域GF(28)中兩個元素的乘法為模2元域GF(2)上的一個8次不可約多項式的多項式乘法。對于AES,這個8次不可約多項式為3.x乘法把b7b6b5b4b3b2b1b0

構(gòu)成的1字節(jié)看成系數(shù)在(0,1)中取值的多項式:用x乘以多項式B(x):如果b7=0,則構(gòu)成的字節(jié)為(b6b5b4b3b2b1b00)。如果b7=1,則構(gòu)成的字節(jié)為歸納如下:對應(yīng)的字節(jié)為則構(gòu)成的字節(jié)為4.系數(shù)在GF(28)上的多項式4個字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項式。多項式的加法就是對應(yīng)系數(shù)相加,換句話說,多項式的加法就是4字節(jié)向量的逐比特異或。規(guī)定多項式的乘法運算必須要取模M(x)=x4+1,這樣使得次數(shù)小于4的多項式的乘積仍然是一個次數(shù)小于4的多項式。將多項式的模乘運算記為“·”,設(shè)由于xjmod(x4+1)=xjmod4,所以可將上述計算表示為注意到M(x)不是GF(28)上的不可約多項式(甚至也不是GF(2)上的不可約多項式),因此非0多項式的這種乘法不是群運算。不過在Rijndael密碼中,對多項式b(x),這種乘法運算只限于乘一個固定的有逆元的多項式4.3.2AES的描述AES是作為DES的替代標(biāo)準(zhǔn)出現(xiàn)的,全稱為AdvancedEncryptionStandard,即高級加密標(biāo)準(zhǔn)。AES明文分組長度為128位,即16字節(jié),密鑰長度可以為16字節(jié)、24字節(jié)、32字節(jié),即128位密鑰、192位密鑰、256位密鑰。根據(jù)不同的密鑰長度,AES算法可以分為三個版本:AES-128、AES-192、AES-256。不同的密鑰長度,其加密輪數(shù)也不同,如AES-128的加密

輪

數(shù)

為10輪,AES-192的

加

密

輪

數(shù)

為12輪,AES-256的

加

密

輪

數(shù)

為14輪。與DES不同,AES算法沒有使用Feistel型結(jié)構(gòu),其結(jié)構(gòu)稱為SPN結(jié)構(gòu)。AES算法也由多個輪組成,其中每個輪分為BytesSub、ShiftRows、MixColumns、AddRoundKey4個步驟,即字節(jié)代換、行移位、列混淆和密鑰加。對于128位的消息分組,AES加密算法的執(zhí)行過程如下:(1)輸入長度為128位的分組明文x,將其按照一定的規(guī)則賦值給消息矩陣State,然后將對應(yīng)的輪密鑰矩陣Roundkey與消息矩陣State進行異或運算AddRoundkey(State,Roundkey)。(2)在加密算法的前N-1輪中,每一輪加密先對消息x應(yīng)用AES算法的S-盒進行一次字

節(jié)

代

換

操

作,稱

為ByteSubs(State);對

消

息

矩

陣State進

行

行

移

位

操

作,稱

為ShiftRows(State);然后對消息矩陣State進行列混淆操作,稱為MixColumns(State);最后與輪密鑰Roundkey進行密鑰加運算AddRoundkey(State,Roundkey)。(3)對前N-1輪加密的結(jié)果消息矩陣State再依次進行ByteSubs(State)、ShiftRows(State)和AddRoundkey(State,Roundkey)操作。(4)將輸出的結(jié)果消息矩陣State定義為密文y。AddRoundkey(State,Roundkey)、ByteSubs(State)、ShiftRows(State)和MixColumns(State)也被稱為AES算法的內(nèi)部函數(shù)。AES算法的具體加密流程如圖4-21所示。下面對AES算法加密過程中用到的相關(guān)操作進行詳細描述。AES中的操作都是以字節(jié)為對象的,操作所用到的變量是由一定數(shù)量的字節(jié)構(gòu)成的。輸入的明文消息x長度是128位,將其表示為16字節(jié)x0,x1,…,x15,初始化消息矩陣State如圖4-22所示。1.字節(jié)代換(ByteSubs)函數(shù)ByteSubs(State)對消息矩陣State中的每個元素(每個元素對應(yīng)每一個字節(jié))進行一個非線性替換,任一個非零元素x∈F28(即由不可約的8次多項式生成的伽羅瓦域)被下面的變換所代替:其中:這里b為固定的向量值63(用二進制表示)。上述變換的非線性性質(zhì)來自x-1(即x在階為8的伽羅瓦域F28

中的逆元),如果將該變換直接作用于變量x,那么該變換就是一個線性變換。另外,由于常數(shù)矩陣A是一個可逆矩陣,所以函數(shù)ByteSubs(State)是可逆的。上面給出的AES算法中的ByteSubs(State)操作相當(dāng)于DES算法中S-盒的作用。該代換矩陣也可以看作AES算法的S-盒。實際上,函數(shù)ByteSubs(State)對State中每一個字節(jié)進行的非線性代換與表42給出的AES算法的“S-盒”對x進行代換的結(jié)果是等價的。下面對表4-2給出的對應(yīng)關(guān)系的有效性進行簡單的驗證。設(shè)x=00001001,將其轉(zhuǎn)換成2個十六進制的數(shù)字形式x=09,通過表4-2給出的對應(yīng)關(guān)系可知,與x對應(yīng)的y=01。這個對應(yīng)關(guān)系如果按照公式(4-1)進行計算,相應(yīng)的過程為將其轉(zhuǎn)換成兩個十六進制的數(shù)字形式y(tǒng)=01(其中x-1=4F)?？梢园l(fā)現(xiàn)兩種方法的結(jié)果是一致的。2.行移位(ShiftRows)函數(shù)ShiftRows(State)在消息矩陣State的每行上進行操作,對于長度為128位的消息分組,它進行如圖4-23所示的變換。這個函數(shù)的運算結(jié)果實際上是對State進行一個簡單的換位操作,它重排了元素的位置而不改變元素本身的值,其中消息矩陣State的第1行元素不進行變化,第2行元素循環(huán)左移一位,第3行元素循環(huán)左移兩位,第4行元素循環(huán)左移三位,得到相應(yīng)的結(jié)果矩陣。所以函數(shù)ShiftRows(State)也是可逆的。3.列混淆(MixColumns)函數(shù)MixColumns(State)對State的每一列進行操作。以下只描述該函數(shù)對一列進行操作的詳細過程。首先取當(dāng)前的消息矩陣State中的一列,定義為把這一列表示成一個三次多項式:其中,S(x)的系數(shù)是字節(jié),所以多項式定義在F28

上。列S(x)上的運算定義為:將多

項

式S(x)乘

以

一

個

固

定

的

三

次

多

項

式C(x),使其與x4+1互素,然后和多項式x4+1進行取模運算。具體如下:其中:C(x)的系數(shù)也是F28

中的元素。式(4-2)中的乘法和一個四次多項式進行取模運算是為了使運算結(jié)果輸出一個三次多項式,從而保證獲得一個從一列(對應(yīng)一個三次多項式)到另一列(對應(yīng)另一個三次多項式)的變換,這個變換在本質(zhì)上是一個使用已知密鑰的代換。同時,由于F2[x](伽羅瓦域F2上的所有多項式集合)上的多項式C(x)與x4+1是互素的,所以C(x)在F2[x]中關(guān)于x4+1的C-1(x)mod(x4+1)存在,式(4-2)的乘法運算是可逆的。式(4-2)的乘法運算也寫為矩陣乘法:4.密鑰加(AddRoundkey)函數(shù)AddRoundkey(State,Roundkey)將Roundkey和State中的元素逐字節(jié)、逐位地進行異或運算。其中,Roundkey由一個固定的密鑰編排方案產(chǎn)生,每一輪的Roundkey是不同的。下面舉例說明AES的每一個迭代,注意觀察所有操作對輸出的影響。假設(shè)消息表示成十六進制:寫成4×4的消息矩陣,形式為該矩陣為AES的S-盒的輸入。第一個輸入為42,它指定了S-盒中行為4、列為2的單元,其內(nèi)容為2c。以此類推,在S-盒中查找出與每個輸入元素對應(yīng)的元素,從而生成輸出矩陣:這種替換實現(xiàn)了AES的第一次打亂。接下來的一個階段是旋轉(zhuǎn)各行:該操作通過混淆行的順序來實現(xiàn)AES的第一次擴散。接下來的一個階段進行乘法操作。對第一列進行如下轉(zhuǎn)換:根據(jù)以上運算過程,可以計算出消息矩陣與固定矩陣相乘的結(jié)果矩陣為接下來要用到子密鑰,將上畫的矩陣和子密鑰進行異或運算,得到將得到的第一輪輸出與初始輸入進行比較,轉(zhuǎn)換成二進制,可以發(fā)現(xiàn)在全部的128位中有76位發(fā)生了改變,而這僅僅是一輪,還要進行另外的10輪。經(jīng)過循環(huán)迭代,將得到最終的加密消息。4.3.3AES的密鑰生成本節(jié)討論AES的密鑰編排方案。對于需要進行N輪加密的AES算法,共需要N+1個子密鑰,其中一個為種子密鑰。我們以128位的種子密鑰key為例,給出產(chǎn)生11個輪密鑰的方法。初始密鑰key按照字節(jié)劃分為key[0],key[1],…,key[15],由于密鑰編排算法以字為基礎(chǔ)(每個字包含32位),所以每一個輪密鑰由4個字組成,11個輪密鑰共包含44個字,在此表示為w[0],w[1],…,w[43]。輪密鑰生成過程中,首先將密鑰按矩陣的列進行分組,然后添加40個新列進行擴充。如果前4個列(即由密鑰給定的那些列)為w[0],w[1],w[2],w[3],那么新列以遞歸方式產(chǎn)生。具體算法步驟如下:(1)初始化函數(shù)RCon[i](i=1,…,10):(2)當(dāng)0≤i≤3時,有(3)當(dāng)4≤i≤43且i≠0mod4時,有(4)當(dāng)4≤i≤43且i=0mod4時,有其中,是w[i-1]的一種轉(zhuǎn)換形式,其實現(xiàn)方式如下:首先,對w[i-1]中的元素進行循環(huán)移位,每次一個字節(jié)。這里操作RotWord(B0,B1,B2,B3)表示對4字節(jié)(B0,B1,B2,B3)進行循環(huán)移位操作,即其中,最后,將置換變換的結(jié)果與RCon[i/4]進行異或運算。如此,第i輪的輪密鑰組成了列w[4i],w[4i+1],w[4i+2],w[4i+3],該過程如圖4-24所示。舉例來說,如果初始的128位種子密鑰(以十六進制表示)為3ca10b2157f01916902e1380acc107bd那么4個初始值為下一個子密鑰段為w[4],由于4是4的倍數(shù),因此的計算過程如下：首先將w[3]的元素移位,acc107bd變成c107bdac。其次將c107bdac作為S-盒的輸入,輸出是78857a91。最后利用RCon[1]=01000000,與78857a91做異或運算,其結(jié)果為79857a91,于是其余的3個子密鑰的計算結(jié)果分別為于是第一輪的密鑰為452471b012d468a582fa7b252e3b7c98。以上是AES算法的整個加密過程。與DES算法相同的是,AES算法的解密也是加密的逆過程,由于AES算法的內(nèi)部函數(shù)都是可逆的,所以解密過程僅僅是將密文作為初始輸入,按照輪子密鑰相反的方向?qū)斎氲拿芪脑龠M行加密的過程,該過程加密的最終結(jié)果就可以恢復(fù)出相應(yīng)的明文。4.3.4AES的分析在AES算法中,每一輪加密常數(shù)不同可以消除可能產(chǎn)生的輪密鑰的對稱性,同時,輪密鑰生成算法的非線性特性消除了產(chǎn)生相同輪密鑰的可能性。加/解密過程中使用不同的變換可以避免出現(xiàn)類似DES算法中出現(xiàn)的弱密鑰和半弱密鑰的可能。經(jīng)過驗證,目前采用的AES加/解密算法能夠有效抵御已知的針對DES的攻擊方法,如部分差分攻擊、相關(guān)密鑰攻擊等。到目前為止,公開報道中對于AES算法所能采取的最有效的攻擊方法只能是窮盡密鑰搜索攻擊,所以AES算法是安全的。盡管如此,已經(jīng)出現(xiàn)了一些能夠破解輪數(shù)較少的AES的攻擊方法。這些攻擊方法是差分分析法和現(xiàn)行分析法的變體。不可能差分(ImpossibleDifferential)攻擊法已經(jīng)成功破解了6輪的AES-128,平方(Square)攻擊法已成功破解了7輪的AES-128和AES-192,沖突(Collision)攻擊法也已成功破解了7輪的AES-128和AES-192。以上這些攻擊方法對10輪的AES-128的破解都失敗了,但這表明AES可能存在有待發(fā)現(xiàn)的弱點。4.4IDEA算法IDEA(InternationalDataEncryptionAlgorithm,國際數(shù)據(jù)加密標(biāo)準(zhǔn))是由瑞士聯(lián)邦技術(shù)學(xué)院的中國學(xué)者來學(xué)嘉博士和著名密碼學(xué)家JamesMassey于1990年提出的一種對稱分組密碼,后經(jīng)修改于1992年最后完成。這是近年來提出的各種分組密碼中一個很成功的方案,目前它的主要用途是作為內(nèi)置于PGP(PrettyGoodPrivacy,完美隱私)中的一種加密算法。IDEA的優(yōu)點是解密和加密相同,只是密鑰各異,加/解密速度都非?？?能夠方便地用軟件和硬件實現(xiàn)。IDEA是一個分組長度為64位的分組密碼,它的密鑰長度是128位,加密過程共進行8輪。應(yīng)注意的是,IDEA的加密結(jié)構(gòu)沒有采用傳統(tǒng)的Feistel密碼結(jié)構(gòu),它使用了三種不同的操作:逐位異或

運算、模216整數(shù)加+運算、模216+1整數(shù)乘☉運算。這三種運算是不兼容的,即三種運算中任意兩種都不滿足分配率,例如,a+(b☉c)≠(a+b)☉(a+c);三種運算中任意兩種都不滿足結(jié)合律,例如,三種運算結(jié)合起來使用可對算法的輸入提供復(fù)雜的變換,使得對IDEA的密碼分析比僅對使用異或運算的DES更為困難。對

于

模216(即65536)整

數(shù)

加+,其

輸

入

和

輸

出

作

為16位

無

符

號

整

數(shù)

。例

如,當(dāng)a=(0110111001101001)2=28265,b=(0111000001101101)2=28781時,對于模216+1整數(shù)乘☉,其輸入、輸出中除16位全為0作為216處理外,其余的輸出序列均

作

為

長

為16位

的

無

符

號

整

數(shù)

處

理。例

如,當(dāng)a=(0000000000000000)2=216=65536,b=(10000000000000000)2=215=32768時,有當(dāng)a=(0111001101010100)2=29524,b=(0110111101100011)2=28515時,有DEA算法的強度主要是由有效的混淆和擴散特性保證的,算法中的擴散是由乘加結(jié)構(gòu)(MA盒)的基本單元實現(xiàn)的。如圖4-25所示,該結(jié)構(gòu)的輸入是2個16位的子段和2個16位的子密鑰,輸出也是2個16位的子段。這一結(jié)構(gòu)在算法中重復(fù)使用了8次,擴散效果非常好。這使得IDEA可以抵抗差分分析法和線性分析法的攻擊。IDEA算法的加密流程如圖426所示。根據(jù)IDEA算法的加密流程可知,64位的明文消息被分成4個16位的子分組X1,X2,X3和X4。加密算法以X1,X2,X3和X4

作為初始輸入,總共進行8輪加密。在每一輪加密過程中,這4個子分組之間相互進行逐位異或

運算、模216整數(shù)加+運算、模216+1整數(shù)乘☉運算,并且與16個16位的子密鑰進行逐位異或

運算、模216

整數(shù)加+運算、模216+1整數(shù)乘☉運算。每一輪加密的最后,第2個和第3個子分組交換,完成一輪加密過程。每一輪加密過程中,對應(yīng)于該輪的6個子密鑰,各個操作執(zhí)行順序如下:(1)X1

和第1個子密鑰相乘;(2)X2

和第2個子密鑰相加;(3)X3

和第3個字密鑰相加;(4)X4

和第4個子密鑰相乘;(5)將第(1)步和第(3)步的結(jié)果相異或;(6)將第(2)步和第(4)步的結(jié)果相異或;(7)將第(5)步的結(jié)果和第5個子密鑰相乘;(8)將第(6)步和第(7)步的結(jié)果相加;(9)將第(8)步的結(jié)果與第6個子密鑰相乘;(10)將第(7)步和第(9)步的結(jié)果相加;(11)將第(1)步和第(9)步的結(jié)果相異或;(12)將第(3)步和第(9)步的結(jié)果相異或;(13)將第(2)步和第(10)步的結(jié)果相異或;(14)將第(4)步和第(10)步的結(jié)果相異或。每一輪加密的結(jié)果,輸出的是第(11)(12)(13)和(14)步操作結(jié)果形成的4個長度為16位的子分組。將得到的4個分組的中間兩個分組值進行交換(最后一輪加密除外)后,即作為下一輪加密的輸入。經(jīng)過8輪加密操作后,依據(jù)最后一輪對應(yīng)的4個子密鑰得到最終的輸出變換:(1)X1

和第1個子密鑰相乘;(2)X2

和第2個子密鑰相加;(3)X3

和第3個子密鑰相加;(4)X4

和第4個子密鑰相乘。最后這4個子分組連接在一起產(chǎn)生密文(Y1,Y2,Y3,Y4)。IDEA加密算法中每一輪需要6個子密鑰,最后輸出過程需要4個子密鑰,所以進行加密所需的子密鑰共52個。對于子密鑰的產(chǎn)生,給定加密算法的一個128位的初始密鑰k=k1k2…k128,將其分成8個子密鑰,每一個子密鑰的長度都是16位;將初始密鑰分組產(chǎn)生的這8個子密鑰作為第一輪加密所需

的6個

子

密

鑰

和

第

二

輪

加

密

的

前

兩

個

子

密

鑰

即然后將128位的初始密鑰k左移25位,得到將它分成8個長度分別為16位的子密鑰,前4個作為第二輪加密的子密鑰后4個作為第三輪加密的前4個子密鑰

再將128位的初始密鑰k循環(huán)左移25位,同樣經(jīng)過分組產(chǎn)生接下來的8個子密鑰,以此類推,直到完全產(chǎn)生加密過程所需的52個子密鑰后,密鑰生成算法結(jié)束。IDEA算法的解密過程與加密過程基本一樣,只是需要將密文消息作為加密過程的輸入。同時,每一輪的子密鑰需要求逆運算,而且和加密過程的子密鑰有一些微小的差別,解密過程的子密鑰是加密子密鑰的mod216加法逆,或是mod(216+1)乘法逆。表4-3給出了IDEA算法中加密子密鑰和相應(yīng)的解密子密鑰,這里Z-1表示Zmod(216+1)的乘法逆,即-Z表示Zmod216的加法逆,即在IDEA中,對于模216+1的乘法運算,0子分組用216=-1來表示,所以0的乘法逆是0。例如,當(dāng)

Z=(1101010111000001)2=54721時,根據(jù)(54721)-1mod(216+1)≡46929,可以得到Z-1=46929=(1011011101010001)2;根據(jù)54721+10815=65536=216,可以得到-Z=(0010101000111111)2=10815。IDEA的密鑰長度是128位。假如采用窮舉搜索的方法對IDEA進行攻擊,那么要獲得密鑰需要進行2128次加密運算,設(shè)計一個每秒能測試10億個密鑰的計算機,并采用10億臺同樣的計算機來進行并行處理,也將花費1013年才能完成計算。所以目前雖然有許多人都在分析和研究IDEA算法,但是還沒有IDEA被攻破的報道。當(dāng)然,IDEA算法是一個相對較新的分組加密算法,算法本身還有許多問題有待進一步地深入研究。4.5SM4分組加密算法SM4算法是我國商用密碼算法的重要組成部分,是我國自主設(shè)計的分組對稱密碼算法。SM4算法于2006年公開發(fā)布,2012年3月成為國家密碼行業(yè)標(biāo)準(zhǔn)(GM/T0002—2012),2016年8月成為國家標(biāo)準(zhǔn)(GB/T32907—2016),2016年10月ISO/IECSC27會議專家組將SM4算法納入ISO標(biāo)準(zhǔn)的學(xué)習(xí)期,SM4算法開始了ISO標(biāo)準(zhǔn)化的歷程。SM4分組密碼算法主要用于無線局域網(wǎng)和可信計算系統(tǒng),是我國制定的WAPI(WirelessLANAuthenticationandPrivacyInfrastructure,無線局域網(wǎng)鑒別和保密基礎(chǔ)結(jié)構(gòu))標(biāo)準(zhǔn)的組成部分,同時也可以用于其他環(huán)境下的數(shù)據(jù)加密保護。4.5.1SM4算法的描述SM4分組密碼算法是一個迭代分組密碼算法,由加解密算法、密鑰擴展算法組成。SM4分組密碼算法采用非對稱Feistel分組密碼結(jié)構(gòu),明文分組長度為128位,密鑰長度也是128位。加密算法和密鑰擴展算法均采用32輪非線性迭代結(jié)構(gòu)。解密算法和加密算法的結(jié)構(gòu)相同,其中解密運算的輪密鑰的使用順序和加密運算剛好相反。1.密鑰參數(shù)SM4分組密碼算法的系統(tǒng)參數(shù)為其中,所有的fki和cki均為32位,這兩組系統(tǒng)參數(shù)主要用在密鑰擴展算法中計算加密的輪密鑰。SM4分組密碼算法的加密密鑰長度為128位,將其均分為4個32位的字,可以表示成其中,每一個mki為32位。SM4分組密碼算法的輪密鑰用在32輪加密中,輪密鑰表示為其中,每一個rki為32位。輪密鑰RK由加密密鑰MK和系統(tǒng)參數(shù)FK,CK共同生成。2.加密算法SM4的加密算法由32輪迭代運算和1次反序變換R組成。加密前首先將128位的明文輸入劃分為4組,即X=(X0,X1,X2,X3),其中每一個Xi都是32位,每一次參與迭代運算的輪密鑰為rki,加密過程如下:(1)執(zhí)行32輪迭代運算上式右端稱為SM4算法的加密輪函數(shù),其中

表示逐位模2加(或者逐位異或),T是一個32位到32位的可逆變換。(2)對最后一輪的迭代輸出進行反序變換,得到密文輸出迭代過程中用到的可逆變換T是由一個非線性變換τ和一個線性變換l復(fù)合而成,即T(x)=l(τ(x))。其中非線性變換τ由4個并行的S-盒構(gòu)成,將輸入τ的32位等分為4組,每一組8位,即A=(a0,a1,a2,a3),則τ的32位輸出為B=(b0,b1,b2,b3),其中S-盒的具體數(shù)據(jù)如圖4-27所示,表中的所有數(shù)據(jù)都用十六進制表示。輸入S-盒的前4位用來選擇表中的行,后