Rijndael密鑰生成方案

RijndaeI 算法是一種分組長和密鑰長都可變的疊代分組密碼算法。

基本介紹

• 中文名：Rijndael密鑰生成方案
• 外文名：Rijndael key generation scheme

Rijndael密鑰生成步驟

Rijndael密鑰的輪密鑰生成經過了密鑰擴展和輪密鑰選擇兩個步驟，其基本原則是：

（1）輪密鑰的總位數等於分組長乘以（1 + Nr），如分組長為128bit，輪數為 Nr = 10，則輪密鑰的總長為 128 *（10 + 1）=1408bit；

（2）種子密鑰擴展為擴展密鑰，種子密鑰長度為 4*Nk 個位元組 ，Nk 是種子密鑰字長；

（3）輪密鑰由以下方法從擴展密鑰中獲得：對第 1 輪密鑰由前 Nb 個字構成；第 2 輪密鑰由第二個 Nb 個字即第 Nb + 1 個字到第 2Nb 個字構成；以下依次類推⋯。

密鑰擴展

擴展密鑰用數組 w [Nb*（Nr + 1）]表示，前 Nk 個字是種子密鑰，其它的密鑰字通過遞歸定義生成。由於密鑰擴展函式取決於 Nk 的值，根據 Nk 的值分了 Nk " 6 和 Nk> 6 兩種情況。

（1）Nk " 6 時，用類 C 語言描述為：

KeyExpansion （byte Key [4 ! Nk]，word w [Nb ! （Nr + 1）]）{for（i = 0；i < Nk；i ++ ）w [i]=（key [4 ! i]，key [4 ! i + 1]，key [4 ! i + 2]，key [4 ! i + 3]）；for（i = Nk；i < Nb ! （Nr + 1）；i + + ）{temp = w [i - 1]；if （i%Nk = = 0）temp = Subbyte （Rotbyte （temp）） # Rcon [i/Nk]；w [i]= w [i - Nk] # temp；} }

Subbyte （w）是一個返回 4 個位元組的函式，每個位元組都是它輸入字中相應位置位元組通過 S 盒作用後的結果；而函式 Rotbyte （w）返回的是這 4 個位元組經循環置換後的字，這個循環置換為：若輸入字為（a,b,c,d），則輸出字為（b,c,d,a）。可以看出：擴展密鑰的前 Nk 個字由種子密鑰構成，隨後的字w[i]等於字 w[i-1]經一些變換後得到的字 temp 和字[i -Nk]異或而成；而且對位置為 Nk 倍數的字變換中不僅運用了循環左移變換 Rotbyte 和子位元組變換 Subbyte，還運用了輪常數Rcon。輪常數定義為：Rcon [i]=（Rc [i]， ‘00’， ‘00’， ‘00’）其中 Rc [i]表示在有限域 GF （2 8 ）中 x i-1的值，即：Rc [1]= 1 （即‘01’）Rc [i]= x·（Rc[i-1]= xi-1 （即‘02’·（Rc[i-1]））

（2）Nk> 6 時，用類 C 語言描述為：

Keyexpansion （byte Key [4 ! Nk]，word w [Nb ! （Nr + 1）]）{for（i = 0；i < Nk；i ++ ）w [i]=（key [4 ! i]，key [4 ! i + 1]，key [4 ! i + 2]，key [4 ! i + 3]）；for（i = Nk；i < Nb ! （Nr + 1）；i ++ ）{temp = w [i - 1]；if（i%Nk = = 0）temp = Subbyte （Rotbyte （temp）） " Rcon [i/Nk]；else if（i%Nk = = 4）temp = Subbyte ! （temp）；w [i]= w [i - Nk] " temp；}}

這與 Nk # 6 的區別在於對指數滿足 i - 4 是 Nk 的倍數的字，在異或前只對 w[i-1]進行了子位元組變換。

新密鑰生成方案

Rijndael 算法的子密鑰的前 Nk 個字完全由種子密鑰填充而成，這樣做雖然密鑰的離散性非常好，減少了密鑰間的線性關係，但是密鑰的雪崩效應就減弱了，同時它的輪密鑰是通過遞歸定義生成的，也就是說，對某一輪的密鑰可以由前一輪或幾輪的輪密鑰推導而來。如果我們知道了這前 Nk 個字的部分密鑰字，就可以根據遞推公式得到與這些部分密鑰字相關的密鑰字。當泄露的密鑰信息達到一定程度時，其它的種子密鑰或許就可以通過窮舉法獲得，進而獲得全部輪子密鑰。對於公開的算法來說，如果密鑰已知，我們輕而易舉地就可以由密文譯出明文，信息的保密就受到了威脅。那么，怎樣在最佳化線性關係和雪崩效應的同時提高密鑰的保密性呢？從安全的角度來分析，為了使攻擊者更難於找到加密密鑰特別是種子密鑰，我們應該提高密鑰生成算法的混淆性來有效抵抗密碼攻擊。

新的密鑰生成算法

取種子密鑰的最後一個字的信息，並從低位開始逐次取這個字的四個 bit 進行幻常數運算，幻常數定義為：
Pt = odd （（pi- 2）2 t ）其中，t 是種子密鑰的最後一個字中的四個 bit，函式 odd （x）是與x最近的奇整數，pi 是圓周率，pi = 3.1415926⋯。這樣依次得到8 個 16 位的數組，記為 pt [0]，pt [1]，⋯，pt [7]。接著，將種子密鑰的 Nk 個字與前 Nk 個幻常數數組進行異或，並將結果賦值給輪子密鑰的前 Nk 個字，然後用種子密鑰去產生第二個 Nk 個字的輪子密鑰，以後的輪子密鑰用前 Nk 個位元組遞歸生成。生成方法為：對第 Nk 個字用種子密鑰進行向左循歪移 5 位，再進行子位元組運算得到，而對後 Nk- 1 個字則為前一個字與種子密鑰進行異或；以後的每 Nk 個字的輪子密鑰都由前 Nk 個字遞歸生成，使用的運算方法和產生第二個 Nk 個字運算方法一樣。這個密鑰生成算法用類 C 語言描述為：
（1）Nk <6 時

Keyexpansion （word Key [Nk]，word w [Nb ! （Nr + 1）]）{ for（i = 0；i < Nk；i ++ ）w [i]= key [i] " pt [i]；for（i = Nk；i < 2 ! Nr；i ++ ）{temp = key [i - 1]；if（i%Nk = = 0）temp = Subbyte （temp < < 5）；w [i]= key [i - Nk] " temp；}for（i = 2 ! Nk；i < Nb ! （Nr + 1）；i ++ ）{temp = w [i - 1]；if（i%Nk = = 0）temp = Subbyte （temp < < < 5）；w [i]= w [i - Nk] " temp；} }

（2）Nk> 6 時

Keyexpansion （word Key [Nk]，word w [Nb ! （Nr + 1）]）{ for（i = 0；i < Nk；i + + ）w [i]= key [i] " pt [i]；for（i = Nk；i < 2 ! Nr；i ++ ）{ temp = key [i - 1]；if（i%Nk = = 0）w [i]= Subbyte （temp < < 5）；else if（i%Nk = = 4）w [i]= Subbyte ! （temp）；w [i]= key [i - Nk] " temp；}for（i = 2 ! Nk；i < Nb ! （Nr + 1）；i ++ ）{temp = w [i - 1]；if（i%Nk = = 0）temp = Subbyte （temp < < < 5）；else if（i%Nk == 4）w [i]= Subbyte （temp）；w [i]= w [i - Nk] " temp；} }

新密鑰生成算法的分析

新密鑰生成算法克服了 Rijndael 算法的密鑰生成方案易暴露種子密鑰的特點，這是由於新的密鑰生成方法生成的輪子密鑰的前 Nk 個字不是種子密鑰，而是取了種子密鑰的最後的一個字信息進行幻常數計算，再與種子密鑰進行異或運算，這樣即使有人獲得了輪子密鑰的前 Nk 個字的部分字，也不能得到大量的種子密鑰的信息。同時，幻常數的計算也不再是 RC6 中對 t 取固定值 16、32 或 64，而是取種子密鑰的一部分。為了計算的便利並儘可能使輪密鑰不泄露更多的種子密鑰信息，我們取了四個 bit 並採用了常數π，這樣幻常數的最大值為 37405 （十六進制為 921D）。為了避免出現和 Rijndael 一樣的問題，新的密鑰擴展算法的第二個 Nk 個字不是由第一個 Nk 個字生成，而是由種子密鑰生成，這樣也增強了密鑰間的相關性，進一步改善了密鑰的雪崩效應。隨後密鑰的生成遵從了原密鑰擴展算法的思想：簡單、快速，同時在兼顧抗線性和具有良好的雪崩效應之間有最優的選擇。

新密鑰生成算法的另一個優點是：對密鑰字進行向左循環移 5 位，增強了密鑰的抗差分分析的能力。市場上根據對密鑰擴展算法的研究開發了許多軟體工具，這些軟體工具能從大量數據中非常有效、迅速地找到密鑰。儘管這些軟體是針序為 AC、CB、BA 的循環。