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

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

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

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

4.4IDEA算法

4.5SM4分組加密算法

4.6分組密碼的工作模式

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

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

和R0

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

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

和Rn

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

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

數(shù)

還

應(yīng)

滿

足

的

另

一

個(gè)

準(zhǔn)

則

是

位

獨(dú)

立

準(zhǔn)

則

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

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

了

公

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

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

和Ri

分別是Bi

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

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

密

鑰

循

環(huán)

左

移

以

后,通

過(guò)

如

圖4-8所

示

的

壓

縮

置

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

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

擴(kuò)展變換針對(duì)32位輸入序列提供了一個(gè)48位的結(jié)果,使得在接下來(lái)的替代運(yùn)算中能進(jìn)行壓縮,從而達(dá)到更好的安全性;③

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

個(gè)48位

的

結(jié)

果

序

列,接

下

來(lái)

應(yīng)

用S-盒

對(duì)

該

序

列

進(jìn)

行

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

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

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

譯

機(jī)。該

破

譯

機(jī)

可

用

兩

天

多

時(shí)

間

破

譯

一

份DES加密的密文,而整個(gè)破譯機(jī)的研

制

經(jīng)

費(fèi)

不

到25萬(wàn)

美

元。DES破

譯

機(jī)

采

用

的

破

譯

方

法

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

戰(zhàn)DES”比

賽

中,強(qiáng)

破

譯

攻

擊

法

僅

用2個(gè)

小

時(shí)

就

破

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

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

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

和K2

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

解密

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

起

了

征

集DES的

替

代

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

交

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

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

輪

數(shù)

為10輪,AES-192的

加

密

輪

數(shù)

為12輪,AES-256的

加

密

輪

數(shù)

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

節(jié)

代

換

操

作,稱

為ByteSubs(State);對(duì)

消

息

矩

陣State進(jìn)

行

行

移

位

操

作,稱

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

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

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

項(xiàng)

式S(x)乘

以

一

個(gè)

固

定

的

三

次

多

項(xiàng)

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

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

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

于

模216(即65536)整

數(shù)

加+,其

輸

入

和

輸

出

作

為16位

無(wú)

符

號(hào)

整

數(shù)

。例

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

作

為

長(zhǎng)

為16位

的

無(wú)

符

號(hào)

整

數(shù)

處

理。例

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

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

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

運(yùn)算、模216

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

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

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

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

和第4個(gè)子密鑰相乘;(5)將第(1)步和第(3)步的結(jié)果相異或;(6)將第(2)步和第(4)步的結(jié)果相異或;(7)將第(5)步的結(jié)果和第5個(gè)子密鑰相乘;(8)將第(6)步和第(7)步的結(jié)果相加;(9)將第(8)步的結(jié)果與第6個(gè)子密鑰相乘;(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個(gè)長(zhǎng)度為16位的子分組。將得到的4個(gè)分組的中間兩個(gè)分組值進(jìn)行交換(最后一輪加密除外)后,即作為下一輪加密的輸入。經(jīng)過(guò)8輪加密操作后,依據(jù)最后一輪對(duì)應(yīng)的4個(gè)子密鑰得到最終的輸出變換:(1)X1

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

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

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

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

的6個(gè)

子

密

鑰

和

第

二

輪

加

密

的

前

兩

個(gè)

子

密

鑰

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

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

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

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