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

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