密碼學基礎與應用——AES演算法分析

密碼學基礎與應用——AES演算法分析

AES的英文為Advanced Encryption Standard，高級加密標準，是美國政府採用的一種加密標準。在密碼學當中又稱作為RIJNDAEL演算法，這是一種密碼長度與數據塊長度都可以變化的分組分組加密演算法，這個標準由於安全、性能好、效率高、實用、靈活而被用來替代原先的DES，已經被多方分析且廣為全世界所使用。這個演算法由比利時的密碼學家Joan Daemen和Vincent Rijmen提出，發佈於2001年11月26日並在2002年成為有效的標準。

　　美國頒布的AES演算法中有規定密鑰長度可以選擇128位，192位或者256位，數據塊的長度是128位、而RIJNDAEL演算法的密鑰長度以及數據塊長度的選定區間為大於等於128位且小於等於256位的32位的任意倍數。

　　在RIJNDAEL演算法當中，它依然採用來自分組密碼的一種通用結構:對輪函數實施迭代的結構。只是輪函數結構採用的是代替/置換網路結構(SP結構)，沒有採用DES的Feistel結構。如下圖，RIJNDAEL的演算法結構由以下三層組成：

圖1-1 RIJNDAEL的演算法結構

　　（1）非線性層：進行非線性S盒變換ByteSub，由16個S盒並置而成，起到混淆的作用。

　　（2）線性混合層：進行行移位變換ShiftRow和列混合變換MixColumn以確保多圈之上的高度擴散。

（3）密鋁加層：進行圈密鑰加變換AddRoundKey，將圈密鑰簡單地異或到中問狀態上，實現密鑰的加密控制作用。

狀態

　　演算法中間的結果也需要分組，這個就稱之為狀態，狀態可以用以二維位元組數組(每一個元素為一個位元組)的矩陣陣列來表示，該陣列有4行，列數Nb為分組長度除32。

　　比如，數據塊長度為128的狀態，它就有Nb=4列。如此算下來，當數據塊長度為192時， Nb=6;當數據塊長度為256時，Nb=8。由於狀態數組有四行，每個元素為一個位元組，因此狀態的每一列便也是一個四位元組的字。

表1-2數據塊長度為128的狀態

數據塊長度為128的狀態在進行加密處理的時候，數據塊需按照列優先的順序來寫入狀態，也就是說要按a0,0,a1,0,a2,0,a3,0,a0,1,a1,1,a2,1,a3,1,a0,2,a1,2,a2,2,a3,2,a0,3,a1,3,a2,3,a3,3的順序寫入狀態中。當加密的操作結束時，密文也需要按照同樣的順序從狀態中取出。

又比如，密鑰長度為128二維位元組數組的密鑰也是按照列優先的順序存儲到密鑰二維位元組數組中，即按k0,0,k1,0,k2,0,k3,0,k0,1,k1,1,k2,1,k3,1,k0,2,k1,2,k2,2,k0,3,k1,3,k2,3,k3,3的順序把它放到密鑰二維位元組數組中存儲起來。如下表：

表1-3密鑰長度為128二維位元組數組

RIJNDAEL演算法的迭代圈數Nr由Nb和Nk共同決定，具體取值列在表1-4中。

表1-4演算法迭代圈數Nr

輪函數

RIJNDAEL加密演算法的輪函數是由列混合變換MixColumn、S盒變換ByteSub、圈密鑰加變換AddRoundKey、行移位變換ShiftRow組成，採用代替/置換網路結構(SP 結構)。

1.列混合變換MixColumn

　　MixColumn變換是對狀態的列進行一個混合變換。在MixColumn的變換中,狀態中的每一列均可以看作GF（2

8

）上的一個多項式，然後與一個固定多項式c(x)相乘後模多項式x

4

+1其中c(x)為:

　　c(x) =『03x

3

+『01x

2

+『01x+02 (1-5)

　　由於c(x)與x

4

+1是互素的，從而可以保證c(x)存在著逆多項式d（x），而c(x)d(x)=l mod x

4

+1。只有在逆多項式d(x)存在的情況下才能夠進行正確的解密。

2.S盒變換ByteSub

　　ByteSub需要對狀態的每個位元組進行替換，也稱為S盒變換。而為了確保加密演算法是可逆的，ByteSub的變換必須是可逆的。它可以在狀態中每個位元組上的一種非線性位元組變換當中起到作用。

其步驟為：

　　①用乘法逆來代替位元組的值，其中00的逆就是它自己。

②經過①的處理後，位元組值再進行下面定義的仿射變換：

（6）

　　需要注意的是:

　　(1)S盒變換的第一步是用乘法逆來代替位元組的值，是一種非線性變換。

　　(2) 由於式(1-6)的係數矩陣中每列都有5個1，也就是說如果改變輸入中的任意一位，都會使得輸出中的5位發生變化。

　　(3)由於式((1-6)的係數矩陣中每行都有5個1，也就是說輸出中的每一位與輸入中的5位都有關係。

　　(4) ByteSub的變換與DES中得到S盒子相當，是一種8位輸入、8位輸出的非線性變換，加密演算法安全性的關鍵也是為加密演算法提供非線性。

3.圈密鑰加變換AddRoundKey

　　AddRoundKey變換是利用圈密鑰對狀態進行模2相加的變換。在這個操作中，圈密鑰被簡單地異或到狀態中去。圈密鑰根據圈密鑰產生演算法通過密鑰得到。圈密鑰長度等於數據塊長度，即與會話密鑰KOEXOR,得到B=Nb× 4個S-box,每個S-box有s=8bit。

4.行移位變換ShiftRow

　　對狀態的行進行循環移位變換就是ShiftRowd的變換。在ShiftRowd變換中，狀態的後三行用不同的移位值循環"左"移。第O行不移位，第1行移C1位元組，第2行移C2位元組，第3行移C3位元組。

移位值C1，C2和C3與M有關，具體為

表1-7移位值

　　RIJNDAEL加密演算法的輪函數用偽C語言可寫為:

　　Round(State, RoundKey)

　　( ByteSub(State);

　　ShiftRow(State);

　　MixColumn(State);

　　AddRoundKey(State, RoundKey);

　　加密演算法中的最後一圈的輪函數與上面的標準輪函數略有不同。定義如下:

　　FinalRound(State, RoundKey)

　　( ByteSub(State);

　　ShiftRow(State);

　　AddRoundKey(State , RoundKey);

　　容易看出，最後一圈的輪函數與標準輪函數相比，去掉了列混合變換MixColumn(State) 。

圈密鑰產生演算法

圈密鑰是根據圈密鑰產生演算法由用戶密鑰產生得到。它的產生分兩步進行:密鑰擴展和圈密鑰選擇。

1、密鑰擴展

用一個字(四個位元組)元素的一維數組W[b*(Nr+1)]存儲擴展密鑰。用戶密鑰包含在數組W最開始的Nk個字中，其他的字由它前面的字經過處理後得到。有Nk小於等於6 和Nk大於6 兩種密鑰擴展策略.

　　(1)對於Nk≤6，有下面密鑰擴展策略:

　　符號說明: CipherKey表示用戶的密鑰，它是一個有Nk個密鑰字的一維數組。W為存儲擴展密鑰的一維數組。

　　KeyExpansion(CipherKey, W)

　　{ For(I=O; I<NK;I++) p ;< CipherKey[工] W[I]>

　　For(I=O; 1< Nb*(Nr+1); 1++)

　　{Temp=W[I-1];

　　IF(I%Nk= =0)

　　Temp=SubByte(Rot1(Temp) ^Rcon[I!Nk]);

　　W[I] =W[I-Nk] ^Temp;

　　}

　　可以看出，最前面的Nk個字是由用戶密鑰填充的。這之後的每一個字W[I]等於前面的字W[I斗與Nk個位置之前的字W[I-1]進行的異或。如果I是Nk的整數倍，在異或之前，要先對W[I-l]進行Rotl變換和ByteSub變換，再異或一個圈常數Rcon。

　　其中，Rotl是對一個字里的位元組以位元組為單位進行循環移位的函數，設W=(A,B,C,D)，則Rotl(W)=(B,C,D,A)。

　　圈常數Rcon與Nk無關，且定義為:

　　Rcon[i]=(RC [i],00,00, 00 )

　　RC[0]=01

　　RC[i]=xtime(RC[i-1])

　　(2)對於Nk>6，有下面的密鑰擴展策略:

　　KeyExpansion(CipherKey，W)

　　{For(I=0;I<NK;I++) W[I]="CipherKey[I];

　　For(I=0; I<NB*(NR+1);I++)< p>

　　{Temp=W[I-1];

　　IF(I%Nk= =0)

　　Temp=SubByte (Rotl (Temp) ^Rcon[I!Nk]);

　　ELSE 工F(I 宅Nk= =4)

　　Temp=SubByte(Temp);

　　W[I]=W[I-Nk] ^Temp;

}

　　Nk>6的密鑰擴展策略與Nk ≤6的密鑰擴展策略相比，區別在於當I是4的整數倍時，需要先將W[I-l]進行ByteSub變換。這樣就在擴展密鑰中增加了部分字的ByteSub變換，從而提高了擴展密鑰的安全性。這是因為當Nk>6時密鑰很長，僅僅對M的整數倍的位置處的字進行ByteSub變換，就顯得ByteSub變換的密度較稀，安全程度不夠強。

2、圈密鑰選擇

　　圈密鑰I由圈密鑰緩衝區W[Nb*I]到W[Nb*(I+l)]的字組成。例如，Nb=4且Nk=4的圈密鑰選擇如圖1-8所示。

圖1-8 Nb=4且Nk=4的圈密鑰選擇

RIJNDAEL加密與解密演算法

　　1.加密演算法

　　一個初始圈密鑰加、Nr-l 圈的標準輪函數以及最後一圈的非標準輪函數就組成了加密的演算法

　　用偽碼來表示則讓如下:

　　Rijndael(State, CipherKey)

　　KeyExpansion(CipherKey, ExpandedKey)

　　AddRoundKey(State, ExpandedKey)

　　For(I=l;I

　　Round(State，ExpandKey+Nb*I)

　　{ByteSub(state);

　　ShiftRow(State);

　　MixColumn(State);

　　AddRoundKey(State,ExpandedKey+Nb*I)}

　　FinalRound(State,ExpandedKey+Nb*Nr)

　　{ByteSub(State);

　　ShiftRow(State);

　　AddRoundKey(State , ExpandedKey+Nb*Nr); }

　　注意第一步和最後一步都用了圈密鑰加，因為任何沒有密鑰參與的變換都是容易被攻破的。

2.解密演算法

RIJNDAEL演算法不是對合演算法，所以它的的解密演算法與加密演算法不同。

　　只要略稍改變一下密鑰擴展策略，便可以得到等價的解密演算法，等價解密演算法的結構與加密演算法的結構相同，從而方便了工程實現。等價解密演算法中的變換為加密演算法中相應變換的逆變換。

（1）逆變換

　　ShiftRow的逆是狀態的後三行分別移動Nb-C1,Nb-C2和Nb-C3個位元組。

　　MixColumn的逆類似於MixColumn，把狀態的每列都乘以一個固定的多項式d(x):

　　d(x)=『OBX3+ODX2+09x+『OE （1-9）

　　容易驗證，式1-5的c(x)與式1-9的d(x)的積等於單位元01。所以d(x)是c(x)的逆多項式。

　　AddRoundKey的逆就是它自己。

　　ByteSub的逆是把S_box的逆作用到狀態的每個位元組上。ByteSub的逆變換按如下方法得到，首先進行式(18)的逆變換，然後再取GF(28)上的乘法逆。式(1-10)是根據式(1-8)推出的，兩式中的矩陣互為逆矩陣。　　

（1-10）

（2）逆輪函數的定義

　　逆輪函數的定義如下:

　　Inv_Round(State，Inv RoundKey)

　　{ InvByteSub(State);

　　InvShiftRow(State);

　　InvMixColunm(State);

　　AddRoundKey(State,Inv_RoundKey); }

　　最後一圈的非標準逆輪函數如下:

　　Inv_Fina1Round(State, Inv_RoundKey)

　　{InvByteSub(State);

　　InvShiftRow(State);

　　AddRoundKey(State, Inv_RoundKey);}

(3解密演算法

　　利用逆輪函數可將解密演算法表述如下:

Inv_Rijndae1(State,CipherKey)

{

　　{Inv_KeyExpansion(CipherKey，Inγ_ExpandedKey) ;

　　AddRoundKey(State，Inv_ExpandedKey+Nb*Nr);

　　For(I= Nr-1;I>0; I--)

　　Inv_Round(State，Inv_ExpandedKey+Nb*I) ) ;

　　{InvByteSub(State);

　　InvShiftRow(State);

　　InvMixCo1umn(State);

　　AddRoundKey(State, Inv_ExpandedKey+Nb*I); }

　　Inv_Fina1Round(State，Inv_ExpandedKey)

　　{InvByteSub(State);

　　InvShiftRow(State);

AddRoundKey(State，Inv_ExpandedKey); }

}

　　注意:解密演算法與加密演算法使用的圈密鋁的順序相反。

　　其中解密演算法的密鑰擴展定義為:

　　(1)加密演算法的密鑰擴展。

　　(2) 把InvMixColumn應用到除第一圈和最後一圈之外的所有圈密鑰上。

　　用偽C碼錶示如下z

　　Inv_KeyExpansion(CipherKey，Inv_ExpandedKey)

　　Key_Expansion(CipherKey,Inv_ExpandedKey);

　　For(I=1; I<Nr; I++); InvMixCo1umn(Inv_ExpandedKey+Nb*I++) }

RIJNDEAEL的安全性

　　RIJNDEAEL的數據塊長度和密鑰長度都可變，因此能夠適應不同的安全應用環境。安全設計策略是寬軌跡策略(Wide Trai1 Strategy) 。寬軌跡策略是針對差分攻擊和線性攻擊提出來的。由於RIJNDEAEL演算法的最短密鑰是128位，窮舉攻擊在這上面並不起作用，所以它的密碼安全使用期較長。而由於寬軌跡策略設計，它能抵抗目前所有已經知道的攻擊，比如線性攻擊、插值攻擊、差分攻擊等。而且RIJNDEAEL在其設計上還有設計簡單、在多個平台上速度快，編碼緊湊等優點。

　　當然，就算現在還沒有發現RIJNDEAEL的嚴重的缺陷，但你也不能說它就是完美無缺的，有優點也會有缺點，這世界上哪有事物是真正意義上的完美呢。但RIJNDEAEL對比DES來講，其安全性肯定是比較較強的，不然也不會用它來替代DES了。

推薦閱讀：