密碼學(xué)基礎(chǔ)課件：第八講 對(duì)稱密碼學(xué)-3

1、第八講 對(duì)稱密碼學(xué)-3AESAES 1997年1月，美國NIST向全世界密碼學(xué)界發(fā)出征集21世紀(jì)高級(jí)加密標(biāo)準(zhǔn)（AESAdvanced Encryption Standard）算法的公告，并成立了AES標(biāo)準(zhǔn)工作研究室，1997年4月15日的例會(huì)制定了對(duì)AES的評(píng)估標(biāo)準(zhǔn)。 AES的標(biāo)準(zhǔn)提綱：（1）AES是公開的；（2）AES為單鑰體制分組密碼；（3）AES的密鑰長(zhǎng)度可變，可按需要增大；（4）AES適于用軟件和硬件實(shí)現(xiàn)；（5）AES可以自由地使用，或按符合美國國家標(biāo)準(zhǔn)（ANST）策略的條件使用；（6）滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣：a. 安全性，b. 計(jì)算效率， c. 內(nèi)存要求， d

2、. 使用簡(jiǎn)便性，e. 靈活性。 AES 1998年4月15日全面征集AES算法的工作結(jié)束。1998年8月20日舉行了首屆AES討論會(huì)，對(duì)涉及14個(gè)國家的密碼學(xué)家所提出的候選AES算法進(jìn)行了評(píng)估和測(cè)試，初選并公布了15個(gè)被選方案，供大家公開討論。 15個(gè)候選算法有：CAST-256，RC-6，CRYPTON-128，DEAL-128，F(xiàn)ROG，簡(jiǎn)易布丁密碼，LOKI-97，MAGENTA，MARS，Vaudenay的抗相關(guān)快速密碼, RIJNDAEL，SAFER+，SERPENT，E-2，TWOFISH。這些算法設(shè)計(jì)思想新穎，技術(shù)水平先進(jìn)，算法的強(qiáng)度都超過3-DES，實(shí)現(xiàn)速度快于3-DES。 1

3、999年8月9日NIST宣布第二輪篩選出的5個(gè)候選算法為：MARS(C.Burwick等,IBM），RC6TM（R. Rivest等,RSA Lab.)，RIJNDEAL(J. Daemen,比)，SERPENT(R. Anderson等，英、以、挪威)，TWOFISH(B. Schiener)。AES2000年4月13日，第三次AES會(huì)議上，對(duì)這5個(gè)候選算法的各種分析結(jié)果進(jìn)行了討論。 2000年10月，由比利時(shí)的Joan Daemen和Vincent Rijmen提出的算法最終勝出。2001年11月，NIST完成了評(píng)估并發(fā)布了最終標(biāo)準(zhǔn)(FIPS PUB 197)，選擇Rijndeal作為AE

4、S算法。AES的設(shè)計(jì)原則能抵抗所有已知的攻擊；在各種平臺(tái)上易于實(shí)現(xiàn)，速度快；設(shè)計(jì)簡(jiǎn)單。 Rijndael是一個(gè)分組密碼算法，其分組長(zhǎng)度和密鑰長(zhǎng)度相互獨(dú)立，都可以改變。分組長(zhǎng)度（bit）128192256密鑰長(zhǎng)度（bit）128192256表 1. 分組長(zhǎng)度和密鑰長(zhǎng)度的不同取值A(chǔ)ES算法結(jié)構(gòu) AES 算法加密部分的實(shí)現(xiàn)1. 明文分組和密鑰的組織排列方式 01234567891011121314150481215913261014371115Fig 1.1. 以明文分組為128bits為例組成的陣列04812159132610143711150481216201591317212610141822

5、3711151923048121620242815913172125292610141822263037111519232731Fig 1.2. 以明文分組（或密鑰）為128bits、192bits 、256bits為例組成的陣列一些相關(guān)的的術(shù)語定義和表示狀態(tài)（State）：密碼運(yùn)算的中間結(jié)果稱為狀態(tài)。State的表示：狀態(tài)用以字節(jié)為基本構(gòu)成元素的矩陣陣列來表示，該陣列有4行，列數(shù)記為Nb。 Nb=分組長(zhǎng)度（bits） 32 Nb可以取的值為4，6，8，對(duì)應(yīng)的分組長(zhǎng)度為128， 192， 256 bits。密碼密鑰（Cipher Key）的表示： Cipher Key類似地用一個(gè)4行的矩陣陣列

6、來表示，列數(shù)記為Nk。 Nk=密鑰長(zhǎng)度（bits）32 Nk可以取的值為4，6，8，對(duì)應(yīng)的密鑰長(zhǎng)度為128， 192， 256 bits。Fig 1.3. 當(dāng)Nb=6時(shí)的狀態(tài)和Nk=4時(shí)的密鑰布局a0,0a0,1a0,2a0,3a0,4a0,5a1,0a1,1a1,2a1,3a1,4a1,5a2,0a2,1a2,2a2,3a2,4a2,5a3,0a3,1a3,2a3,3a3,4a3,5Nb = 6Block Length = 192 bitsK0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3Nk = 4Key Len

7、gth = 128 bitsFig 1.4. 分組長(zhǎng)度和密鑰長(zhǎng)度均為128 bits時(shí)的Rijndael加密算法框圖Data / Key AdditionRnd0Rnd1Rnd8FinalRndKeyScheduleCipherTextKeyPlainText表 1.2. 圈數(shù)（Round）的不同取值圈數(shù)（Round）Block Length=128Block Length=192Block Length=256Key Length=128101214Key Length=192121214Key Length=256141414Fig 1.5. Rijndael Round的構(gòu)成ByteSu

8、bstitutionByteRotationMixColumn+RoundKey一般的圈變換ByteSubstitutionByteRotation+RoundKey最后一圈的圈變換用偽代碼表示的Rijndael圈變換一般的圈變換Round(State, RoundKey) ByteSubstitution; ByteRotation; MixColumn; AddRounKey; 結(jié)尾圈的變換FinalRound(State, RoundKey) ByteSubstituion; ByteRotation; AddRoundKey; ByteSubstitution(字節(jié)替代) ByteSu

9、bstitution是一個(gè)非線性的字節(jié)替代，獨(dú)立地在每個(gè)狀態(tài)字節(jié)上進(jìn)行運(yùn)算。它包括兩個(gè)變換。 1. 在有限域GF(28)上求乘法逆，00映射到它自身。 2. 在GF(2)上進(jìn)行下面的仿射變換： y0 1 1 1 1 1 0 0 0 x0 0y1 0 1 1 1 1 1 0 0 x1 1y2 0 0 1 1 1 1 1 0 x2 1y3 0 0 0 1 1 1 1 1 x3 0y4 1 0 0 0 1 1 1 1 x4 0y5 1 1 0 0 0 1 1 1 x5 0y6 1 1 1 0 0 0 1 1 x6 1y7 1 1 1 1 0 0 0 1 x7 1例3.5Fig 1.6. ByteSu

10、bstitution該變換可以用一個(gè)256字節(jié)的表來實(shí)現(xiàn)B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3取逆仿射變換那個(gè)256字節(jié)的表ByteRotation(字節(jié)移位) 在ByteRotation變換中，狀態(tài)陣列的后3行循環(huán)移位不同的偏移量。第1行循環(huán)移位C1字節(jié)，第2行循環(huán)移位C2字節(jié)，第3行循環(huán)移位C3字節(jié)。 偏移量C1、C2、C3與分組長(zhǎng)度Nb有關(guān)，如下表所示：NbC1C2C341

11、2361238134Fig 1.7. ByteRotation04812159132610143711150481259131101426153711循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)MixColumn(列混合) 將狀態(tài)的列看作是有限域GF(28)上的多項(xiàng)式a(x)，與多項(xiàng)式c(x) = 03 x3 + 01 x2 + 01 x +02相乘(模x41)。 令b(x) = c(x) a(x)，寫成矩陣形式為： b0 02 03 01 01 a0 b1 = 01 02 03 01 a1 b2 01 01 02 03 a2 b3 03 01 01 02 a3例子 04 02 03 01 01

12、 d4 66 = 01 02 03 01 bf 81 01 01 02 03 5d e5 03 01 01 02 30Fig 1.8. MixColumn這一運(yùn)算作用在每一列上A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3 C(X)評(píng)價(jià)一個(gè)比特變化，導(dǎo)致不同的逆元，該逆元的比特統(tǒng)計(jì)特性進(jìn)行了擴(kuò)散。（字節(jié)代換）一個(gè)字節(jié)變化，導(dǎo)致一列變化。（列混合）一列字節(jié)變化，導(dǎo)致4列變化（行移位）Add

13、RoundKey(圈密鑰加) 將圈密鑰與狀態(tài)按比特異或。圈密鑰是通過Key Schedule過程從密碼密鑰中得到的，圈密鑰長(zhǎng)度等于分組長(zhǎng)度。A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A3,3 K3,3 B3,3 (mod 2)Fig 1.7. Rijndae

14、l加密及解密的標(biāo)準(zhǔn)結(jié)構(gòu)Block , Key Length = 128 bitsPlaintext(128 bits)ByteSubstitutionMixColumnCiphertext(128 bits) K0Kii=10ByteRotationfor i=1 to 10Ciphertext(128 bits) K10InvMixCoumnInvByteRotationInvByteSubstitution KiPlaintext(128 bits)i = 9for i=9 to 0加密解密Rijndael密碼的構(gòu)成一個(gè)初始圈密鑰相加；(Rnd1)圈；一個(gè)結(jié)尾圈。Rijndael密碼由以下

15、三個(gè)部分組成：用偽代碼表示的Rijndael加密算法Rijndael ( State, CipherKey ) KeyExpansion ( CipherKey, ExpandedKey ); AddRoundKey ( State, ExpandedKey ); For ( i=1; iRnd; i+ ) Round ( State, ExpandedKey + Nb*i ); FinalRound ( State, ExpandedKey + Nb*Rnd ); 提前進(jìn)行密鑰擴(kuò)展后的Rijndael加密算法描述Rijndael ( State, ExpandedKey ) AddRound

16、Key ( State, ExpandedKey ); For ( i=1; iRnd; i+ ) Round ( State, ExpandedKey + Nb*i ); FinalRound ( State, ExpandedKey + Nb*Rnd ); AES 算法的密鑰調(diào)度 密鑰調(diào)度包括兩個(gè)部分：密鑰擴(kuò)展和圈密鑰選取密鑰bit的總數(shù)分組長(zhǎng)度（圈數(shù)Round1）例如當(dāng)分組長(zhǎng)度為128bits和圈數(shù)Round為10時(shí)，圈密鑰長(zhǎng)度為128(101)1408bits。將密碼密鑰擴(kuò)展成一個(gè)擴(kuò)展密鑰。從擴(kuò)展密鑰中取出圈密鑰：第一個(gè)圈密鑰由擴(kuò)展密鑰的第一個(gè)Nb個(gè)4字節(jié)字，第二個(gè)圈密鑰由接下來的Nb

17、個(gè)4字節(jié)字組成，以此類推。密鑰擴(kuò)展K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0K1K2K3K0K1K2K3K4K5K6K7+K0K1K2K3K4K5K6K7ByteSubstitutionByteRotate+RconWi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotate+Rcons+Key expansion4 = i 4 ( Rnd + 1 )i mod 4 = 0i mod 4 != 0圈密鑰選取K0K1K2K3K4K5K6K7K8K9K10K11K12圈密鑰0圈密鑰1

18、圈密鑰2AES 算法的在軟硬件上的實(shí)現(xiàn)首先對(duì)算法的各步驟進(jìn)行合并處理： ButeSubstitution變換： bi,j = S ai,j ShiftRow變換： c0,j b0,j c1,j = b1,j-1 c2,j b2,j-2 c3,j b3,j-3MixColumn變換： d0,j 02 03 01 01 c0,j d1,j = 01 02 03 01 c1,j d2,j 01 01 02 03 c2,j d3,j 03 01 01 02 c3,jAddRoundKey: e0,j d0,j k0,j e1,j = d1,j + k1,j e2,j d2,j k2,j e3,j d3,j k3,j將以上各步合并： e 02 03 01 01 s a k e = 02 03 01 01 s a + k e 02 03 01 01 s a k e 02 03 01 01 s a k改寫成向量的線性組合： e 02 03 01 01 k e =sa 01 + sa 02 +sa