分組密碼對稱置換算法設(shè)計(jì)

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

關(guān)鍵詞：對稱置換； 分組密碼算法； 圈結(jié)構(gòu)與計(jì)數(shù)

中圖法分類號(hào)：TP309．7文獻(xiàn)標(biāo)識(shí)碼：A

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

分組密碼是網(wǎng)絡(luò)上廣泛使用的一類密碼，也是國際上公開密碼算法中最活躍的一個(gè)分支。其設(shè)計(jì)理念是保密依賴于密鑰，而算法大多公開，設(shè)計(jì)結(jié)構(gòu)分為FEISTEL、代替/置換（SubstitutionPermutation ，SP）兩大類。

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

1對稱置換圈結(jié)構(gòu)基本特征

在兩類分組密碼設(shè)計(jì)中，置換是必備的一個(gè)環(huán)節(jié)。討論對稱置換的密碼學(xué)理論基礎(chǔ)如下：設(shè)A為有限集，Sn為A上的n元置換群。

2分組密碼算法的對稱置換設(shè)計(jì)

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

對某一128bits SP結(jié)構(gòu)分組密碼算法進(jìn)行對稱置換設(shè)計(jì)，單輪加密如圖1所示。

圖1SP結(jié)構(gòu)分組密碼單輪加密圖

第三圈運(yùn)算后N0字節(jié)信息已經(jīng)完全融入各個(gè)字節(jié)

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

3結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

作者簡介：

羅嵐，女，北京人，副研究員，博士研究生，研究方向?yàn)樾畔踩c計(jì)算機(jī)應(yīng)用；

范明鈺，女，四川成都人，博導(dǎo)，博士，研究方向?yàn)樾畔踩?/p>

魏正耀，男，院士，博導(dǎo)，研究方向?yàn)樾畔踩?/p>

王光衛(wèi)，男，四川成都人，工程師，研究方向?yàn)樾畔踩?/p>

瞿澤輝，男，四川德陽人，博士研究生，研究方向?yàn)樾畔踩c計(jì)算機(jī)應(yīng)用。

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