AES加密算法原理(圖文).doc

AES加密算法原理（圖文）隨著對(duì)稱密碼的發(fā)展,DES數(shù)據(jù)加密標(biāo)準(zhǔn)算法由于密鑰長(zhǎng)度較小(56位),已經(jīng)不適應(yīng)當(dāng)今分布式開放網(wǎng)絡(luò)對(duì)數(shù)據(jù)加密安全性的要求，因此1997年NIST公開征集新的數(shù)據(jù)加密標(biāo)準(zhǔn),即AES1。經(jīng)過三輪的篩選,比利時(shí)Joan Daeman和Vincent Rijmen提交的Rijndael算法被提議為AES的最終算法。此算法將成為美國新的數(shù)據(jù)加密標(biāo)準(zhǔn)而被廣泛應(yīng)用在各個(gè)領(lǐng)域中。盡管人們對(duì)AES還有不同的看法,但總體來說,AES作為新一代的數(shù)據(jù)加密標(biāo)準(zhǔn)匯聚了強(qiáng)安全性、高性能、高效率、易用和靈活等優(yōu)點(diǎn)。AES設(shè)計(jì)有三個(gè)密鑰長(zhǎng)度:128,192,256位，相對(duì)而言，AES的128密鑰比DES的56密鑰強(qiáng)1021倍2。AES算法主要包括三個(gè)方面：輪變化、圈數(shù)和密鑰擴(kuò)展。 AES 是一個(gè)新的可以用于保護(hù)電子數(shù)據(jù)的加密算法。明確地說，AES 是一個(gè)迭代的、對(duì)稱密鑰分組的密碼，它可以使用128、192 和 256 位密鑰，并且用 128 位（16字節(jié)）分組加密和解密數(shù)據(jù)。與公共密鑰密碼使用密鑰對(duì)不同，對(duì)稱密鑰密碼使用相同的密鑰加密和解密數(shù)據(jù)。通過分組密碼返回的加密數(shù)據(jù) 的位數(shù)與輸入數(shù)據(jù)相同。迭代加密使用一個(gè)循環(huán)結(jié)構(gòu)，在該循環(huán)中重復(fù)置換（permutations ）和替換(substitutions）輸入數(shù)據(jù)。Figure 1 顯示了 AES 用192位密鑰對(duì)一個(gè)16位字節(jié)數(shù)據(jù)塊進(jìn)行加密和解密的情形。Figure 1 部分?jǐn)?shù)據(jù) AES算法概述 AES 算法是基于置換和代替的。置換是數(shù)據(jù)的重新排列，而代替是用一個(gè)單元數(shù)據(jù)替換另一個(gè)。AES 使用了幾種不同的技術(shù)來實(shí)現(xiàn)置換和替換。為了闡明這些技術(shù)，讓我們用 Figure 1 所示的數(shù)據(jù)討論一個(gè)具體的 AES 加密例子。下面是你要加密的128位值以及它們對(duì)應(yīng)的索引數(shù)組： 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 192位密鑰的值是: 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 170 1 2 3 4 5 67 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23 Figure 2 S-盒（ Sbox ） 當(dāng) AES 的構(gòu)造函數(shù)（constructor）被調(diào)用時(shí)，用于加密方法的兩個(gè)表被初始化。第一個(gè)表是代替盒稱為S-盒。它是一個(gè)1616的矩陣。S-盒的前五行和前五列如 Figure 2 所示。在幕后，加密例程獲取該密鑰數(shù)組并用它來生成一個(gè)名為w的密鑰調(diào)度表，F(xiàn)igure 3 所示。 Figure 3 密鑰調(diào)度表（Key Sched） w 最初的 Nk (6) 行被作為種子，用原始密鑰值（0x00 到0x17）。剩余行從種子密鑰來產(chǎn)生。變量 Nk 代表以 32 位字為單位的種子密鑰長(zhǎng)度。稍后我分析 AES 實(shí)現(xiàn)時(shí)你將清楚地看到 w 是怎樣產(chǎn)生的。 關(guān)鍵是這里現(xiàn)在有許多密鑰使用而不只是一個(gè)。這些新的密鑰被稱為輪密鑰（round keys）以將它們與原始種子密鑰區(qū)別開來。 Figure 4 State （態(tài)）數(shù)組 AES 加密例程開始是拷貝 16 字節(jié)的輸入數(shù)組到一個(gè)名為 State （態(tài)）的 44 字節(jié)矩陣中。（參見 Figure 4）。AES 加密算法 取名為 Cipher，它操作 State，其過程描述的偽代碼參見 Figure 5 。 在規(guī)范中，加密算法實(shí)現(xiàn)的一個(gè)預(yù)備的處理步驟被稱為 AddRoundKey（輪密鑰加）。AddRoundKey 用密鑰調(diào)度表中的前四行對(duì) State 矩陣實(shí)行一個(gè)字節(jié)一個(gè)字節(jié)的異或（XOR）操作，并用輪密鑰表 wc,r 異或 輸入 Stater,c。 舉個(gè)例子，如果 State 矩陣的第一行保存的字節(jié)是 00, 44, 88, cc ，第一列密鑰調(diào)度表是 00, 04, 08, 0c ，那么新的 State0,2 值是用 w2,0( 0x08 或 0x80 )異或 State0,2(0x88)的結(jié)果： 1 0 0 0 1 0 0 00 0 0 0 1 0 0 0 XOR1 0 0 0 0 0 0 0 AES 算法的主循環(huán)對(duì) State 矩陣執(zhí)行四個(gè)不同的操作，在規(guī)范中被稱為 SubBytes（字節(jié)替換）、ShiftRows（行位移變換）、MixColumns（列混合變換） 和 AddRoundKey。除了每次循環(huán) AddRoundKey 都被調(diào)用并使用密鑰調(diào)度表的下面四行外，AddRoundKey 與預(yù)備處理步驟中的 AddRoundKey 相同。SubBytes 例程是一個(gè)代替操作，它將 State 矩陣中的每個(gè)字節(jié)替換成一個(gè)由 Sbox 決定的新字節(jié)。比如，如果 State0,1的值是 0x40 如果你想找到它的代替者，你取 State0,1 的值 (0x40) 并讓 x 等于左邊的數(shù)字(4)并讓 y 等于右邊的數(shù)字(0)。然后你用 x 和 y 作為索引 進(jìn)到 Sbox 表中尋找代替值，如 Figure 2 所示。 ShiftRows 是一個(gè)置換操作，它將 State 矩陣中的字節(jié)向左旋轉(zhuǎn)。Figure 6 示范了 ShiftRows 如何操作 State。State 的第0行被向左旋轉(zhuǎn)0個(gè)位置，State 的第1行被向左旋轉(zhuǎn)1個(gè)位置，State 的第2行被向左旋轉(zhuǎn)2個(gè)位置，而 State 的第3行被向左旋轉(zhuǎn)3個(gè) 位置。 Figure 6 對(duì) State 進(jìn)行 ShiftRows 操作 MixColumns 是一個(gè)代替操作，它是理解 AES 算法時(shí)最具技巧（或者說是最需要?jiǎng)幽X筋的部分）的部分。它用 State 字節(jié)列的值進(jìn)行數(shù)學(xué)域加和域乘的結(jié)果代替每個(gè)字節(jié)。我將在下一節(jié)中 詳細(xì)解釋專門的域加和域乘細(xì)節(jié)。 假設(shè) State0,1 的值是0x09，并且列1上的其它值分別為 0x60，0xe1 和 0x04，那么State0,1的新值計(jì)算如下： cppview plaincopy1. State0,1=(State0,1*0x01)+(State1,1*0x02)+(State2,1*0x03)+(State3,1*0x01)=(0x09*0x01)+(0x60*0x02)+(0xe1*0x03)+(0x04*0x01)=0x57 此處加法和乘法是專門的數(shù)學(xué)域操作，而不是平常整數(shù)的加法和乘法。 SubBytes、ShiftRows、MixColumns 和 AddRoundKey 四個(gè)操作在一個(gè)執(zhí)行 Nr 次的循環(huán)里被調(diào)用，Nr 為給定密鑰大小的輪數(shù)減 1。加密算法使用的輪數(shù)要么是10，12，要么是14，這依賴于種子密鑰長(zhǎng)度是128位、192 位還是 256 位。在這個(gè)例子中，因?yàn)?Nr 等于12， 則這四個(gè)操作被調(diào)用11次。該迭代完成后，在拷貝 State 矩陣到輸出參數(shù)前，加密算法調(diào)用 SubBytes、ShiftRows 和 AddRoundKey 后結(jié)束。 大致說來，AES 加密算法的核心有四個(gè)操作。AddRoundKey 使用從種子密鑰值中生成的輪密鑰代替 4 組字節(jié)。SubBytes 替換用一個(gè)代替表 替換單個(gè)字節(jié)。ShiftRows 通過旋轉(zhuǎn) 4字節(jié)行 的 4 組字節(jié)進(jìn)行序列置換。MixColumns 用域加和域乘的組合來替換字節(jié)。 有限域GF(28)的加法和乘法 正如你所看到的，AES 加密算法使用相當(dāng)簡(jiǎn)單明了的技術(shù)來代替和置換，除 MixColumns 例程以外。MixColumns 使用特殊的加法和乘法。AES 所用的加法和乘法是基于數(shù)學(xué)（譯者注：近世代數(shù)）的域論。尤其是 AES 基于有限域GF(28)。 GF(28)由一組從 0x00 到 0xff 的256個(gè)值組成，加上加法和乘法，因此是(28)。GF代表伽羅瓦域，以發(fā)明這一理論的數(shù)學(xué)家的名字命名。GF(28) 的一個(gè)特性是一個(gè)加法或乘法的操作的結(jié)果必須是在0x00 . 0xff這組數(shù)中。雖然域論是相當(dāng)深?yuàn)W的，但GF(28)加法的最終結(jié)果卻很簡(jiǎn)單。GF(28) 加法就是異或（XOR）操作。 然而，GF(28)的乘法有點(diǎn)繁難。正如你稍后將在 C# 實(shí)現(xiàn)中所看到的，AES的加密和解密例程需要知道怎樣只用七個(gè)常量 0x01、0x02、0x03、0x09、0x0b、0x0d 和 0x0e 來相乘。所以我不全面介紹GF(28)的乘法，而只是針對(duì)這七種特殊情況進(jìn)行說明。 在GF(28)中用0x01的乘法是特殊的；它相當(dāng)于普通算術(shù)中用1做乘法并且結(jié)果也同樣任何值乘0x01等于其自身。 現(xiàn)在讓我們看看用0x02做乘法。和加法的情況相同，理論是深?yuàn)W的，但最終結(jié)果十分簡(jiǎn)單。只要被乘的值小于0x80，這時(shí)乘法的結(jié)果就是該值左移1比特位。如果被乘的值大于或等于0x80，這時(shí)乘法的結(jié)果就是左移1比特位再用值0x1b異或。它防止了“域溢出”并保持乘法的乘積在范圍以內(nèi)。 一旦你在GF(28)中用0x02建立了加法和乘法，你就可以用任何常量去定義乘法。用0x03做乘法時(shí)，你可以將 0x03 分解為2的冪之和。為了用 0x03 乘以任意字節(jié)b， 因?yàn)?0x03 = 0x02 + 0x01，因此： b * 0x03 = b * (0x02 + 0x01) = (b * 0x02) + (b * 0x01) 這是可以行得通的，因?yàn)槟阒廊绾斡?0x02 和 0x01 相乘和相加，同哩，用0x0d去乘以任意字節(jié)b可以這樣做：cppview plaincopy1. b*0x0d2. =b*(0x08+0x04+0x01)3. =(b*0x08)+(b*0x04)+(b*0x01)4. =(b*0x02*0x02*0x02)+(b*0x02*0x02)+(b*0x01) 在加解密算法中，AES MixColumns 例程的其它乘法遵循大體相同的模式，如下所示：cppview plaincopy1. b*0x092. =b*(0x08+0x01)3. =(b*0x02*0x02*0x02)+(b*0x01)b*0x0b4. =b*(0x08+0x02+0x01)=(b*0x02*0x02*0x02)+(b*0x02)+(b*0x01)b*0x0e5. =b*(0x08+0x04+0x02)6. =(b*0x02*0x02*0x02)+(b*0x02*0x02)+(b*0x02) 總之，在GF(28)中，加法是異或操作。其乘法將分解成加法和用0x02做的乘法，而用0x02做的乘法是一個(gè)有條件的左移1比特位。AES規(guī)范中包括大量 有關(guān)GF(28)操作的附加信息。 密鑰擴(kuò)展 AES加密和解密算法使用了一個(gè)由種子密鑰字節(jié)數(shù)組生成的密鑰調(diào)度表。AES規(guī)范中稱之為密鑰擴(kuò)展例程（KeyExpansion）。從本質(zhì)上講，從一個(gè)原始密鑰中生成多重密鑰以代替使用單個(gè)密鑰大大增加了比特位的擴(kuò)散。雖然不是無法抵御的困難，但理解 KeyExpansion 仍是 AES 算法中的一個(gè)難點(diǎn)。KeyExpansion 例程高級(jí)偽代碼如下所示： KeyExpansion(byte key, byte4 w) copy the seed key into the first rows of w for each remaining row of w use two of the previous rows to create a new row “用前面兩行來產(chǎn)生一個(gè)新行”（“use two of the previous rows to create a new row”）的例程用到了兩個(gè)子 例程，RotWord 和 SubWord 以及一個(gè)名為“Rcon”的常數(shù)表（作為“輪常數(shù)”）。讓我們先來逐個(gè)看一下這三東西，然后再回到整個(gè) KeyExpansion 的討論中來。 RotWord 例程很簡(jiǎn)單。它接受一個(gè)4個(gè)字節(jié)的數(shù)組并將它們向左旋轉(zhuǎn)一個(gè)位置。因?yàn)檩喺{(diào)度表 w 有四列，RotWord 將 w的1行左旋。注意 KeyExpansion 使用的這個(gè) RotWord 函數(shù)與加密算法使用的 ShiftRows （行位移變換）例程非常相似，只是它 處理的是單行密鑰調(diào)度 w，而不是整個(gè)加密狀態(tài)表 State。 SubWord 例程使用替換表 Sbox 對(duì)一給定的一行密鑰調(diào)度表 w 進(jìn)行逐字節(jié)替換。KeyExpansion 操作中的替換實(shí)際上就像在加密算法中的 替換一樣。被代替的輸入字節(jié)被分成 (x,y) 對(duì)，它被當(dāng)作進(jìn)入替換表 Sbox 的索引。舉例來說，0x27的代替結(jié)果是 x2 和 y7，并且 Sbox2,7 返回 0xcc。 KeyExpansion 例程使用一個(gè)被稱為輪常數(shù)表的數(shù)組 Rcon。這些常數(shù)都是4個(gè)字節(jié)，每一個(gè)與密鑰調(diào)度表的某一行相匹配。AES 的 KeyExpansion 例程需要11個(gè)輪常數(shù)。你可以在 Figure 7 中看到這些常數(shù)清單。 每個(gè)輪常數(shù)的最左邊的字節(jié)是GF(28)域中2的冪次方。它的另一個(gè)表示方法是其每個(gè)值是前一個(gè)值乘上0x02，正如前一部分討論 GF(28) 乘法 時(shí)所描述的那樣。注意 0x80 0x02 = 0x1b 是 0x80 左移1個(gè)比特位后緊接著與 0x1b 進(jìn)行異或，如前所述。 現(xiàn)在讓我們更進(jìn)一步看看 KeyExpansion 內(nèi)幕中的循環(huán)。這里所用的偽碼比以前更為詳細(xì)，這個(gè)循環(huán)是：cppview plaincopy1. for(row=Nk;row(4*Nr+1);+row)2. 3. temp=wrow-14. if(row%Nk=0)5. temp=SubWord(RotWord(temp)xorRconrow/Nk6. elseif(Nk=8androw%Nk=4)temp=SubWord(temp)wrow=wrow-Nkxortemp7. 先不要去看if子句，你將看到密鑰調(diào)度表 w 的每一行都是前面一行與行 Nk 異或的結(jié)果（4, 6, 或 8 取決于密鑰的長(zhǎng)度）。if條件的第一部分用 SubWord、RotWord 以及與輪常數(shù)的異或修改密鑰調(diào)度表的每個(gè)第4、第6或第8行，取決于是否密鑰的長(zhǎng)度是128、192或256位。這個(gè)條件的第二部分將修改行 12、20 和 28 等等對(duì)于256位密鑰而言每 一個(gè)第8行都將添加密鑰調(diào)度額外的可變性。 讓我們用本文開頭所舉的例子來考察 KeyExpansion 是如何開始的。種子密鑰是192-bit / 6-word 值： 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 密鑰調(diào)度字節(jié)表 w 的維數(shù)是 4 列并且 Nb (Nr + 1) 等于 4 (12 + 1)，或 52 行。KeyExpansion 將種子密鑰的值拷貝到密鑰調(diào)度字節(jié)表 w 的第一行。因?yàn)槲业姆N子密鑰是 192 位（24字節(jié)），并且 w 表總是 4 列，在這種情況下KeyExapansion 將種子密鑰拷貝到 w 的前面 6 行?，F(xiàn)在讓我們看看 KeyExapansion 例程是如何填充密鑰調(diào)度表其余部分的。在我的例子里，第一個(gè)被計(jì)算的行是第 6 行 ，因?yàn)榈?-5行已被種子密鑰的值填上了： temp = wrow-1 = 14 15 16 17 條件 (row % Nk = 0)為真，因此首先 RotWord 子程序被應(yīng)用： temp = 15 16 17 14 這時(shí) SubWord 被應(yīng)用： temp = 59 47 f0 fa 用 Rconrow / Nk = Rcon6 / 6 = 01 00 00 00 進(jìn)行異或： temp = 58 47 f0 fa 這時(shí)用 wrow-Nk = w6-6 = 00 01 02 03 異或，產(chǎn)生了下面結(jié)果： w6 = 58 46 f2 f9 密鑰調(diào)度表 w 中其余所有行來重復(fù)這個(gè)過程本身。 總而言之，AES 加密和解密的一個(gè)重要部分就是從最初的種子密鑰中生成多重輪密鑰。這個(gè) KeyExapansion 算法生成一個(gè)密鑰調(diào)度并 以某種方式進(jìn)行替代和置換，在這種方式中，加密和解密算法極其相似。一. AES對(duì)稱加密: AES加密分組二. 分組密碼的填充 分組密碼的填充 PKCS#5填充方式三. 流密碼 四. 分組密碼加密中的四種模式:3.1 ECB模式 優(yōu)點(diǎn):1.簡(jiǎn)單；2.有利于并行計(jì)算；3.誤差不會(huì)被傳送；缺點(diǎn):1.不能隱藏明文的模式；2.可能對(duì)明文進(jìn)行主動(dòng)攻擊； 3.2 CBC模式： 優(yōu)點(diǎn)：1.不容易主動(dòng)攻擊,安全性好于ECB,適合傳輸長(zhǎng)度長(zhǎng)的報(bào)文,是SSL、IPSec的標(biāo)準(zhǔn)。缺點(diǎn)：1.不利于并行計(jì)算；2.誤差傳遞；3.需要初始化向量IV 3.3 CFB模式： 優(yōu)點(diǎn):1.隱藏了明文模式;2.分組密碼轉(zhuǎn)化為流模式;3.可以及時(shí)加密傳送小于分組的數(shù)據(jù);缺點(diǎn):1.不利于并行計(jì)算;2.對(duì)明文的主動(dòng)攻擊是可能的;3.誤差傳送：一個(gè)明文單元損壞影響多個(gè)單元; 優(yōu)點(diǎn)：1.隱藏了明文模式;2.分組密碼轉(zhuǎn)化為流模式;3.可以及時(shí)加密傳送小于分組的數(shù)據(jù);缺點(diǎn):1.不利于并行計(jì)算;2.誤差傳送：一個(gè)明文單元損壞影響多個(gè)單元;3.唯一的IV; 3.4 OFB模式：下面是示例代碼 ：javaview plaincopy1. packagemini.code.test.t20120810;2. 3. importjavax.crypto.*;4. importjavax.crypto.spec.*;5. 6. publicclassAES7. 8. publicstaticStringasHex(bytebuf)9. 10. StringBufferstrbuf=newStringBuffer(buf.length*2);11. inti;12. for(i=0;ibuf.length;i+)13. 14. if(int)bufi&0xff)0x10)15. strbuf.append(0);16. strbuf.append(Long.toString(int)bufi&0xff,16);17. 18. returnstrbuf.toString();19. 20. 21. publicstaticvoidmain(Stringargs)throwsException22. 23. 24. Stringmessage=這是個(gè)加密的例子;25. System.out.println(原文:+message);26. System.out.println(原文轉(zhuǎn)換格式顯示：+asHex(me