密碼算法中的循環移位“異或”運算實質性研究

成 彬 ，王冬艷 ，韓憲生 ，胡 波

(1.河北省科學院應用數學研究所，河北 石家莊 050081；2.河北華燁冀科信息技術公司，河北 石家莊 050081；3.河北省科學院，河北 石家莊 050081)

在計算機網絡信息傳輸中，保證信息在發送方和接收方之間傳送時不被竊密者竊取破譯最成功有效的方法是采用加密機制來保護通信信息。針對保密算法中所采用密鑰的特點，Simmons[1]將密碼體制區分為對稱密碼和非對稱密碼。對稱密碼也稱為私鑰或傳統密碼體制，非對稱密碼又稱為公鑰密碼體制。在對稱密碼體制中，加密密鑰能夠根據解密密鑰推算出來，反之也成立。此外按加密方式，對稱密碼體制又分為流密碼和分組密碼。在流密碼算法中，明文消息是按字符逐位加密。而在分組密碼中，明文消息分成多個分組(每組含有多個字符)，逐組進行加密。分組密碼具有較強的抗攻擊能力、易于偽造偽隨機數生成器、流密碼、消息認證函數和雜湊函數，并且容易實現，速度快，適合大量數據加密。本文對移位和“異或”運算的復合運算進行了研究，指出了“異或”和移位運算的數學本質，對設計分組密碼算法具有一定的指導作用。

1 二進制數的多項式表示

一個n bit的二進制數可以用一個多項式表示[2-3]：

c={cn-1，cn-2，c1，c0}?c(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0(1)其中 xi表示第 i個位置 (從 c的右邊起從 0數)，ci∈{0，1}是第 i bit的值。 其中{0，1}=GF(2)是模 2剩余類環，它是特征為2的素域。即任何一個二進制數可以用GF(2)的多項式表示。如果 c中第i比特是 1，再往左都是0，則稱c(x)為 i次多項式。m bit二進制數對應最多m-1次多項式。

注意：把二進制數對應到多項式時，有左右順序的問題。這個問題并無實質差別，只要約定清楚即可。缺省假設向量中的bit從左到右對應多項式從高到低的系數。二進制情況下，次數不超過m-1的多項式c(x)總共有 2m個[4-5]。

如同整系數多項式、實系數多項式，稱式(1)中這個多項式為系數在GF(2)上的多項式。

2 移位和循環移位操作

按照式(1)的對應關系，兩個二進制數的“異或”運算對應GF(2)上的多項式的加法運算。左移一位運算對應多項式的乘以x運算。左移k位對應多項式的乘以xk運算。

循環移位操作分循環左移和循環右移兩種。假定循環移位的位數為m，那么循環移位的位數k在 1～m-1之間。對于一個m位數，循環右移k位等價循環左移m-k位。因此，循環右移可以轉化為循環左移來實現(這里只考慮循環左移)。

以下用a<<

對m位的二進制數的循環左移k位就是整個m位二進制數左移k位，若有移出的bit則從右邊環回。它等價于多項式乘以xk然后對多項式xm+1取模，即：

循環移位后多項式的次數不會超出m-1。

對m位的二進制數的左移k位就是整個m位二進制數左移k位，若有移出的bit將其截去。它等價于多項式乘以xk然后對多項式xm取模，即：

這樣移位后多項式的次數不會超出m-1。

定義 1：對 m 位的二進制數 a={am-1，am-2，…，a1，a0}，ai∈{0，1}，的線性變換。

其中0≤ki

定義 2：對 m 位的二進制數 a={am-1，am-2，…，a1，a0}，ai∈{0，1}，的線性變換。

其中 0≤hi

3 循環移位“異或”變換和移位“異或”變換的表示

定理 1：對 m 位的二進制數 a={am-1，am-2，…，a1，a0}，ai∈{0，1}，的每個循環移位“異或”變換。

同樣可得：

定理 2：對 m 位的二進制數 a={am-1，am-2，…，a1，a0}，ai∈{0，1}的每個移位“異或”變換。

由定理1和定理2可知，討論m位二進制數的循環移位“異或”變換和移位“異或”變換變成了討論 GF(2)上多項式乘法了。

在計算機中一般都取8 bit為一個字節，16 bit為一個字，32 bit為一個雙字，64 bit為一個長整形數。它們共同特點是位長度為2的某次方冪。在這種情況下，多項式x2k+1可以完全分解成x2k+1=(x+1)2k。它除了x+1外沒有其他因子，同樣xm也除了x外沒有其他因子。因此，判斷以x2k+1為模的重模多項式環中元素存在逆元就變成了被判斷的多項式是否有x+1因子；判斷以xm為模的重模多項式環中元素存在逆元就變成了被判斷的多項式是否有x因子；判斷是否有x因子，看多項式的常數項是否為0即可。判斷φ(x)是否有x+1因子，只需判斷φ(1)=0與否，轉化φ(x)的系數為1的奇偶性，如果 φ(x)有偶數個為 1的系數，那么 φ(1)=0，否則 φ(1)≠0。得到如下定理：

定理3：在長度為2的方冪的二進制位串中，循環移位“異或”變換中，如果有奇數項，那么這個變換是可逆的，有偶數項則不可逆。

定理4：不論多長的二進制位串移位“異或”變換，只要包含不移位的項，該變換就是可逆的，否則就是不可逆的。

根據定理3，選擇了SMS4密碼算法標準里的線性變換[6-7]，它是一個循環移位“異或”變換：

為了解密，必須求出其逆變換，為此，從這個變換對應的重模多項式入手，計算其逆多項式。這個變換對應的多項式為：

L變換有5項，其逆變換有11項，符合定理3的結論。

本文對密碼算法中循環移位“異或”運算的本質進行了探討，并且給出了這種變換的可逆性判斷的充分必要條件，對設計新的密碼算法具有一定的指導作用。

[1]SIMMONS G J，Symmetric and asymmetric encryption[J].Computing Surveys， 1979，11(4)：305-330.

[2]馮克勤，余紅兵.整數與多項式[M].北京：高等教育出版社，1999.

[3]萬哲先.代數和編碼(第三版)[M].北京：高等教育出版社，2007.

[4]胡波，趙紅芳，馮春雨.一種新的重模剩余類環中元素逆的求法[J].河北省科學院學報，2009，26(1)：1-3.

[5]趙紅芳，胡波，馮春雨.重模多項式環中逆元素的存在性判斷及求法[J].中國科技信息，2009(8)：45-47.

[6]李大為，趙旭鑫，武萌.SMS4密碼算法的高速流水線實現[J].電子器件，2007，30(2)：590-592.

[7]鄭秀林，金麗娜.SMS4算法在DSP中的實現研究[J].北京電子科技學院學報，2006，14(4)：34-37.