隨機分組密碼算法框架及實現
2008-01-01 00:00:00羅平宋濤
計算機應用研究 2008年5期
摘要： 針對現有的對分組密碼的攻擊方法對于未知結構的密碼算法是無效的特點，提出了一個根據已有分組密碼算法生成隨機密碼算法的框架，其密碼算法是由隨機控制密鑰生成的，因而算法是隨機的，能抵抗針對固定結構的密碼算法的線性密碼分析和差分密碼分析。同時還提出了一個具體的AES的隨機化算法，該算法具有可證明的安全性，其安全性高于原始的AES，性能與原始的AES算法接近。
關鍵詞：分組密碼算法;線性密碼分析;差分密碼分析;AES
中圖分類號：TP309．7文獻標志碼：A
文章編號：1001-3695(2008)05-1556-04
0引言
分組密碼屬于單鑰密碼算法，具有簡捷快速的特點，并且容易標準化， 是目前軟硬件加密標準的主流。這種密碼算法的缺點是安全性比較難以證明，且存在一些比較成熟的攻擊方法，如差分密碼分析和線性密碼分析。對于分組密碼，密碼學家提出了許多設計方案，如著名的DES算法、AES算法等。其設計方法多種多樣，如DES使用S盒和Feistel網絡， IDEA使用多種群運算， AES使用寬軌跡策略等。這些算法的基本特點都是使用相同或相似的輪函數， 通過輪函數的多次迭代達到所需要的安全性。由于這些算法的結構都是固定的，也就產生了一些密碼分析方法，如差分密碼分析、線性密碼分析和能量攻擊等。這些攻擊方法均針對已知固定結構的分組密碼算法， 即密碼算法是已知的；對于未知結構的密碼算法不能達到理想的效果。針對這一特點，本文提出了一個隨機生成密碼算法的框架。其密碼算法是在密鑰的控制下生成的，不知道密鑰也就推不出算法，即密碼算法是由密鑰隨機生成的，而密鑰是保密的。由于攻擊者不知道算法結構，就比較難以進行密碼分析。本文提出的方法也不同于具體密碼算法的隨機化方法[1]，它可以是幾種算法的組合，因此可以避免單一密碼算法的固有問題，如AES的GF域上代數結構引起的代數攻擊和滲透攻擊。
眾所周知，隨機密碼算法與固定結構的密碼算法不同，其比較難以分析。目前的分析方法僅限于信息論方式， 它是將生成算法與等長的隨機置換相比較，算法的安全性證明是通過有限次明文、密文對的查詢以及不能區分生成的算法與等長的隨機置換來保證的。文獻[2]中使用滿足特定條件的隨機置換代替AES的S盒，給出了線性概率和差分概率的界(10輪差分概率小于2-128)， 并指出使用隨機置換安全性要優于原始的AES，由此可以看出使用隨機密碼算法可以得到更高的安全性。而文獻[2]中構造的隨機置換實際上不滿足其提出的條件，所以其安全性證明存在問題。本文提出的一種隨機置換可以證明滿足其條件， 從而給出了一個具有可證明安全性的AES隨機化算法。
1隨機分組密碼算法框架
通常的分組密碼輪函數，通過輸入明文和輪密鑰， 使用某種子密鑰生成算法生成每一輪的子密鑰，使用固定的輪函數和對應的子密鑰進行運算， 經過足夠多的輪數后輸出密文。該輪函數具有固定結構，所以容易受到現有密碼分析方法的攻擊。為了抵抗這些攻擊，本文提出一種隨機分組密碼算法框架。其基本思想是將密鑰分成兩部分，即控制密鑰和加密密鑰。控制密鑰用于生成密碼算法，因而算法是隨機的，它隨著密鑰的不同而變化；加密密鑰用于生成子密鑰，用于加密算法。控制密鑰選取方法要保證能生成足夠多不同的隨機密碼算法，同時生成的密碼算法能達到足夠的安全性使其密碼分析人員難以進行靜態分析。控制密鑰又可以細分為加密算法控制密鑰和密鑰擴展算法控制密鑰兩部分。加密算法控制密鑰由若干個輪函數控制密鑰所組成，用于生成各輪的輪函數，輪函數控制密鑰的個數即為加密算法的輪數；密鑰擴展算法控制密鑰用于生成密鑰擴展算法。加密密鑰由所使用的密鑰擴展函數決定。加密時通過加密算法控制密鑰生成加密算法，通過使用加密密鑰得到的子密鑰進行加密；解密時通過加密算法控制密鑰生成解密算法，使用加密密鑰得到的子密鑰進行解密，其具體步驟如下：
a）系統初始化
（a）確定整個加密系統公用的一些參數(wb，we，wz，wr，ws，t)。其中：wb為明、密文分組長度(假定明、密文長度相等)；we為加密算法密鑰長度；wz為算法每輪的子密鑰長度；wr為輪函數控制密鑰的比特數；ws為密鑰擴展函數控制密鑰的比特數；t為安全級別， 即生成該隨機算法需要的最大差分概率至多為2-t， 最大線性相關度至多為2-t。
整個加密算法密鑰k由三部分組成，即加密算法密鑰k1（長度為we）、輪函數生成算法控制密鑰k2（長度為wr的整數倍）和密鑰擴展函數控制密鑰k3（長度為ws），即k = k1‖k2‖k3。其中符號‖表示級聯。
（b）確定輪函數生成算法和密鑰擴展生成算法。在控制密鑰k2的控制下，由輪函數生成算法生成加密算法所需各輪的輪函數以及通過逆輪函數生成算法生成解密所需各輪的輪函數。在控制密鑰k3的作用下產生密鑰擴展函數生成算法生成密鑰擴展函數。
（c）確定合法密鑰需要滿足的條件。為了能夠生成滿足本文要求的算法，需要對控制密鑰作一些限制。設滿足條件的輪函數控制密鑰全體構成的集合為Kr， 密鑰擴展函數控制密鑰全體構成的集合為Ks。如何生成滿足條件的密鑰不在本文的討論范圍之內。
2有可證明安全性的AES隨機算法
2．1AES算法
設明文分組長為32×n bit，將輸入再分成8 bit的組， 那么明文分組可記為p0，…，p4n-1。將明文對應到狀態數組A:ai，j=pi+4j(0≤i≤3，0≤j≤n-1)，則稱(ai，0，…，ai，n)為A的第i+1行， (a0， j，…，an， j)為A的第j+1列。定義四種基本運算AddRoundKey(與子密鑰異或)、SubByte(字節變換)、SiftRows(行位移變換)和MixColumns(列混合變換)。算法的輪函數為ρ=σ。θ。π。γ。其中：γ為SubByte變換即S盒， 它是作用在狀態字節上的非線性置換，主要提供非線性性；π為SiftRows變換，它是行上狀態字節的移位操作；θ為MixColumns變換， 它作用在4 Byte的列上， 是(GF(28))4上的一個線性變換；σ為AddRoundKey變換，它是與子密鑰的逐位異或。整個AES算法就是使用上面所描述的輪函數ρ對狀態數組進行運算， 通過迭代多次后得到密文c0，…，c4n-1。
在AES算法的設計中使用寬軌跡策略， 突出線性運算的擴散性質， 使用小的S盒提供局部的非線性，這樣做既可以提高效率，又可以具有簡單的結構， 便于分析多輪安全性。在文獻[3]中證明了采用AES的結構， 對于四輪的加密算法， 最大差分概率為2-96。
2．2Thomas提出的具有可證明安全性的AES隨機化算法
文獻[2]通過使用相互獨立且均勻分布的隨機置換S代替AES固定的S盒， 構造了一個具有可證明安全性的分組密碼算法AES。證明了對于進行10輪的AES在二階非自適應攻擊下是安全的。由于(GF(2))8上所有隨機置換S的個數很多，且很難統一描述，在實際使用中需要找到一種替代方法。為此，文獻[2]證明了S可以用相互獨立且滿足ES[LPS(a，b)]=δ-1的隨機置換S替換。其中：ES是對S的所有取值求期望；LPS(a，b)是S的某一固定取值的線性差分概率；a是輸入差分；b是輸出差分；δ是S盒的所有可能非零輸入的個數。對于AES有δ=28-1。同時文獻[2]給出一個如何隨機化的方案，即在與子密鑰異或之前，將輸入按8 bit為單位乘以按8 bit為單位分組的子密鑰。
在該方案中的隨機化有兩個缺陷:a）沒有注意到相互獨立性。它的子密鑰并不能保證相互獨立，是由一個子密鑰生成方案得到的， 而在安全性的證明中都是按照相互獨立的隨機置換來計算線性軌跡的概率，因此該方案的隨機化證明失效。b）由于算法使用了乘法，它必須保證按8 bit為單位分組的子密鑰每一段都不能為0，否則分組密碼算法將不可逆。但AES的子密鑰生成算法并不能保證這一點。如果按平均分布的隨機子密鑰流進行10輪來計算，出現這種情況的概率為1-(1-2-8)160≈0.47，即有一半的可能會出現加密結果不能被解出，因此這種方案根本無法使用。
本文將給出一種替代方案，構造了另外一種隨機置換的分布， 減少了隨機置換的個數，并且便于描述和實現， 同時滿足文獻[2]中提出的可證明條件，即替代方案生成的AES隨機化算法也具有可證明的安全性。
2．3本文提出的具有可證明安全性的AES隨機化算法
本文設計的方法與文獻[2]中思路基本相同，只改變AES的S盒，其他不變。將固定的S盒改為具有特定分布的隨機置換。與AES中的S盒設計一樣，筆者構造的隨機S盒形式為S=AX-1+B。其中：A為均勻分布的隨機8×8可逆矩陣；B為均勻分布的8 bit長隨機列向量，且A和B相互獨立。
1)系統初始化
a)設 (wb，we，wz，wr，ws，t)=(128，128，128，72，0，128)， 即明文、密文、加密密鑰的長度都是128 bit，描述一個輪函數需要72 bit，無須描述密鑰擴展函數(只有一個)， 要求最大差分概率小于2-128。
隨機選擇一個密鑰k=k1‖k2‖k3。其中：k1為128 bit；k2為720 bit；k3長度為0（即無該項），并且要求k2滿足每個輪函數中的矩陣A是可逆的（見下面）。
通過上述分析可知，上面構造的算法可證明是安全的。
3．2算法復雜度分析
在算法時間復雜度方面， 上述提出的AES隨機化算法的密鑰擴展與AES一致，輪函數與AES的輪函數相近，運行時間也相仿。其主要區別在于生成輪函數所用時間。由輪函數選取算法可知需要選取的元素有矩陣A和向量B。其中矩陣A和向量B都是通過取比特位運算構造出來的， 因此輪函數選取算法的時間可以忽略。所以本文提出的算法與AES運行時間基本相同。
在算法空間復雜度方面， 密鑰長度w=848 bit， 大于AES的128 bit， 不過仍然可以放在一個以太網幀中進行傳輸，需要加解密雙方預存的數據為X-1的對應表，與AES相同，加解密過程中需要的臨時空間與AES相同。總體來說，具有與AES相似的空間復雜度。
3．3密鑰選取算法及復雜度分析
本文提出的框架不提供密鑰生成的方法，只是提出密鑰需要滿足的條件。在實際應用中，有可能需要實時生成密鑰，如SSL的會話建立期間，需要用公鑰算法加密臨時生成的會話密鑰（分組密碼密鑰），并發送給對方，之后的通信都使用臨時的會話密鑰。這時密鑰選取算法會影響整個協議的效率。
下面對于本文提出的AES隨機化算法的例子，提出一種密鑰選取算法。
3．3．1非線性置換γ選取算法
由前面的算法描述，AES變種算法的輪函數控制密鑰長度為72 bit用于確定γ。因此需要確定非線性置換γ的選取算法，描述如下：
a)隨機選取8×8 bit長的數a，使用2.3節的方法生成GF(2)上的8×8矩陣A，判斷A是否可逆。如果A可逆，則選取a為γ中線性置換A的表達，否則重新選取。
b)隨機選取8 bit數b，作為γ中列向量B的表達。
c)輸出一輪的輪函數控制密鑰k′=a‖b。
3．3．2密鑰選取算法
根據上面的非線性置換γ選取算法，生成密鑰選取算法，描述如下：
a)隨機生成128 bit作為加密密鑰k1。
b)使用3.3.1節的非線性置換γ選取算法生成10個輪函數控制密鑰k(1)，…，k(10)。
c)輸出密鑰k=k1‖k2。其中k2=k(1)，…，k(10)。
3．3．3復雜度分析
由文獻[4]可知GF(2)上n階可逆矩陣的個數為Nn(2)=(2n-1)(2n-2)…(2n-2n-1)，一次選取成功的概率為Pn(2)=Nn(2)/2n×n=∏(1-2i)；i=1，…，n。可證明Pn(2)存在非零極限，Pn(2)>0．28，因此非線性置換γ選取算法平均選取次數< 1/0．28≈3．58。
選取一次的時間等于判斷GF(2)上的8×8矩陣A是否可逆的時間，設該時間為T。下面使用一種簡單的方式進行判斷。
由于矩陣A可逆等價于所有行向量線性無關，其又等價于所有行向量的任意線性組合都不為零。而對于GF(2)上的8×8矩陣行向量的線性組合只有28-1=255種，且行向量相加等價于8 bit的異或操作，因此判定一次最多只需作255×8/2=1 020次8 bit的異或運算，即T=1 020，并且注意到對于幾個不同矩陣的同樣線性組合可以合在一起計算；對于32位的處理器，最多可以4個矩陣合在一起計算，因此密鑰選取算法的平均計算時間<(10/4)×3．58 T=9 129次32 bit異或運算的時間，所需時間非常短。
4結束語
對AES算法來說，隨機S盒有助于提高算法的安全性，對于除了AES之外的密碼算法，隨機S盒帶來的影響有待證明。另一方面，文獻[2]中的證明只針對有S盒隨機化的情況，而對于束換位和局部線性變換的隨機化會導致證明中分類的個數呈指數增長，因此需要采用新的計算方式來判斷束換位和局部線性變換的隨機化會對AES安全性帶來的影響。
參考文獻：
［1］胡予濮，陳愷.分組密碼的隨機算法[J].通信保密，2000（3）：53-55.
[2]BAIGNRES T，VAUDENAY S.Proving the security of AES substitution－permutation network[M].Berlin：Springer－Verlag，2006:65-81.
[3]DEAMEN J，KNUDSEN L R，RIJMEN V.Linear frameworks for block ciphers[J].Designs， Codes and Cryptography，2001，22（1）：65-87.
[4]張勝元.Zn上m階可逆矩陣的計數[J].福建師范大學學報，1999，15（1）：13－15.
[5]VAUDENAY S.Decorrelation: a theory for block cipher security[J].Journal of Cryptology，2003，16(4):249-286.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
