分組密碼對稱置換算法設計

摘要：證明了對稱置換的圈結構與計數，提出并設計了一種以特定對稱結構作為分組密碼算法的置換部分，以減小加密算法硬件空間，提高加/解密速度。指出了分組密碼的多次迭代使對稱置換結構復雜化，可以選擇對稱置換作為分組密碼算法的擴散部分來設計。

關鍵詞：對稱置換； 分組密碼算法； 圈結構與計數

中圖法分類號：TP309．7文獻標識碼：A

文章編號：1001－3695(2007)01-0186－02

分組密碼是網絡上廣泛使用的一類密碼，也是國際上公開密碼算法中最活躍的一個分支。其設計理念是保密依賴于密鑰，而算法大多公開，設計結構分為FEISTEL、代替/置換（SubstitutionPermutation ，SP）兩大類。

FEISTEL網絡結構是Horst Feistel 在設計Lucifer分組密碼時發明的，并在數據加密標準（Data Encryption Standard，DES）中得以使用。還有許多密碼體制如GOST，FEAL，RC5，CAMELLIA等均采用了FEISTEL網絡結構。SP網絡結構的輪變換分為兩層：第一層為S混亂層，是由密鑰控制的非線性置換，通常由并行查表（S盒）實現；第二層為P擴散層，通常由與密鑰無關的可逆線性變換實現。SP結構分組密碼的抗線性攻擊和抗差分攻擊的能力容易衡量，而且擴散速度快，因此許多著名的密碼算法都采用了SP結構，如高級加密標準（Advanced Encryption Standard，AES）。傳統的SP網絡結構通常用文獻[1]的方法構造S盒，并且用與密鑰無關的可逆置換實現P結構。分組密碼算法的設計，由于其網絡的使用環境，要求有應用數學、密碼學和工程實現等方面的系統指標，對密碼算法強度和執行效率之間的取舍視安全要求級別而定。本文就對稱置換作為分組密碼擴散部分，論述圈枝結構基本特征，及其設計的可行性和優勢。

1對稱置換圈結構基本特征

在兩類分組密碼設計中，置換是必備的一個環節。討論對稱置換的密碼學理論基礎如下：設A為有限集，Sn為A上的n元置換群。

2分組密碼算法的對稱置換設計

由定義可知，如果對稱置換中的元素Ni映射到Nj，那么元素Nj必然映射到Ni。顯然，對稱置換中的一半元素就可以決定置換全體。這樣，算法的加/解密硬件實現電路可以簡化，提高了運算速度。由定理1、定理2可知，對稱置換雖然自身結構簡單，但是通過多次迭代，置換的輪換擴張能力較強；由定理3可知，對稱置換有廣泛的選擇范圍。對稱置換在分組密碼設計中使用時，必須考慮算法在混亂與擴散中的效率。以現行網絡使用的128bits（16Bytes）標準分組來看，存在16！，即2．09×1013種對稱置換可供選擇。事實上，從2．09×1013種對稱置換中選取高效、擴散速度快的置換工程量很大。以下是通過選擇得到的一個對稱置換在SP結構分組密碼中的應用以及與高級加密標準AES[4]擴散性能的比較。

對某一128bits SP結構分組密碼算法進行對稱置換設計，單輪加密如圖1所示。

圖1SP結構分組密碼單輪加密圖

第三圈運算后N0字節信息已經完全融入各個字節

采用上述對稱置換的設計，從擴散的角度來看，與原有AES具備相同級別強度的效果。而且無論在軟件實現或硬件實現時，運算速度提高，硬件空間減小。更重要的是，采取對稱置換設計的分組密碼在一定程度上破壞了原有的代數線性特征，使算法抗線性攻擊性能增強。

3結論

對稱置換的乘積圈結構與其不動點的個數、位置以及輪換的位置、連接結構有關。在迭代過程中，圈結構具有多樣性。分組密碼的迭代設計方法恰好克服了對稱置換本身圈結構的簡單化。由于對稱置換只需一半的映射關系就可以反映所有特點，在加/解密時使用同一非線性變化，因此在分組密碼設計中，使用對稱置換可使算法在硬件實現時節約空間，同時能夠提高加/解密速度。把這種設計嵌入標準分組密碼中，替換其原有的置換算法，可得到一個新的分組算法。通過檢測，可以證明這種設計具有抗差值攻擊、線性攻擊、差分攻擊和代數攻擊的能力。

參考文獻：

［1］K Nyberg.Differentially Uniform Mappings for Cryptography[A]. T Helleseth.Advances in Cryptology Proceedings of EUROCRYPT’93[C]. SpringerVerlag，1994.5564.

［2］王樹禾. 離散數學引論[M].合肥：中國科學技術大學出版社，2001.1822.

［3］沈世鎰. 組合密碼學[M].杭州：浙江科學技術出版社，1992.911.

［4］Joan Daemen， Vincent Rijmen. AES Proposal: Rijndeal[EB/OL].http://www.nist.gov/aes， 20-0409.

作者簡介：

羅嵐，女，北京人，副研究員，博士研究生，研究方向為信息安全與計算機應用；

范明鈺，女，四川成都人，博導，博士，研究方向為信息安全；

魏正耀，男，院士，博導，研究方向為信息安全；

王光衛，男，四川成都人，工程師，研究方向為信息安全；

瞿澤輝，男，四川德陽人，博士研究生，研究方向為信息安全與計算機應用。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文