密碼算法中的循環(huán)移位“異或”運(yùn)算實(shí)質(zhì)性研究

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

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

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

1 二進(jìn)制數(shù)的多項(xiàng)式表示

一個(gè)n bit的二進(jìn)制數(shù)可以用一個(gè)多項(xiàng)式表示[2-3]：

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

注意：把二進(jìn)制數(shù)對(duì)應(yīng)到多項(xiàng)式時(shí)，有左右順序的問(wèn)題。這個(gè)問(wèn)題并無(wú)實(shí)質(zhì)差別，只要約定清楚即可。缺省假設(shè)向量中的bit從左到右對(duì)應(yīng)多項(xiàng)式從高到低的系數(shù)。二進(jìn)制情況下，次數(shù)不超過(guò)m-1的多項(xiàng)式c(x)總共有 2m個(gè)[4-5]。

如同整系數(shù)多項(xiàng)式、實(shí)系數(shù)多項(xiàng)式，稱(chēng)式(1)中這個(gè)多項(xiàng)式為系數(shù)在GF(2)上的多項(xiàng)式。

2 移位和循環(huán)移位操作

按照式(1)的對(duì)應(yīng)關(guān)系，兩個(gè)二進(jìn)制數(shù)的“異或”運(yùn)算對(duì)應(yīng)GF(2)上的多項(xiàng)式的加法運(yùn)算。左移一位運(yùn)算對(duì)應(yīng)多項(xiàng)式的乘以x運(yùn)算。左移k位對(duì)應(yīng)多項(xiàng)式的乘以xk運(yùn)算。

循環(huán)移位操作分循環(huán)左移和循環(huán)右移兩種。假定循環(huán)移位的位數(shù)為m，那么循環(huán)移位的位數(shù)k在 1～m-1之間。對(duì)于一個(gè)m位數(shù)，循環(huán)右移k位等價(jià)循環(huán)左移m-k位。因此，循環(huán)右移可以轉(zhuǎn)化為循環(huán)左移來(lái)實(shí)現(xiàn)(這里只考慮循環(huán)左移)。

以下用a<<

對(duì)m位的二進(jìn)制數(shù)的循環(huán)左移k位就是整個(gè)m位二進(jìn)制數(shù)左移k位，若有移出的bit則從右邊環(huán)回。它等價(jià)于多項(xiàng)式乘以xk然后對(duì)多項(xiàng)式xm+1取模，即：

循環(huán)移位后多項(xiàng)式的次數(shù)不會(huì)超出m-1。

對(duì)m位的二進(jìn)制數(shù)的左移k位就是整個(gè)m位二進(jìn)制數(shù)左移k位，若有移出的bit將其截去。它等價(jià)于多項(xiàng)式乘以xk然后對(duì)多項(xiàng)式xm取模，即：

這樣移位后多項(xiàng)式的次數(shù)不會(huì)超出m-1。

定義 1：對(duì) m 位的二進(jìn)制數(shù) a={am-1，am-2，…，a1，a0}，ai∈{0，1}，的線性變換。

其中0≤ki

定義 2：對(duì) m 位的二進(jìn)制數(shù) a={am-1，am-2，…，a1，a0}，ai∈{0，1}，的線性變換。

其中 0≤hi

3 循環(huán)移位“異或”變換和移位“異或”變換的表示

定理 1：對(duì) m 位的二進(jìn)制數(shù) a={am-1，am-2，…，a1，a0}，ai∈{0，1}，的每個(gè)循環(huán)移位“異或”變換。

同樣可得：

定理 2：對(duì) m 位的二進(jìn)制數(shù) a={am-1，am-2，…，a1，a0}，ai∈{0，1}的每個(gè)移位“異或”變換。

由定理1和定理2可知，討論m位二進(jìn)制數(shù)的循環(huán)移位“異或”變換和移位“異或”變換變成了討論 GF(2)上多項(xiàng)式乘法了。

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

定理3：在長(zhǎng)度為2的方冪的二進(jìn)制位串中，循環(huán)移位“異或”變換中，如果有奇數(shù)項(xiàng)，那么這個(gè)變換是可逆的，有偶數(shù)項(xiàng)則不可逆。

定理4：不論多長(zhǎng)的二進(jìn)制位串移位“異或”變換，只要包含不移位的項(xiàng)，該變換就是可逆的，否則就是不可逆的。

根據(jù)定理3，選擇了SMS4密碼算法標(biāo)準(zhǔn)里的線性變換[6-7]，它是一個(gè)循環(huán)移位“異或”變換：

為了解密，必須求出其逆變換，為此，從這個(gè)變換對(duì)應(yīng)的重模多項(xiàng)式入手，計(jì)算其逆多項(xiàng)式。這個(gè)變換對(duì)應(yīng)的多項(xiàng)式為：

L變換有5項(xiàng)，其逆變換有11項(xiàng)，符合定理3的結(jié)論。

本文對(duì)密碼算法中循環(huán)移位“異或”運(yùn)算的本質(zhì)進(jìn)行了探討，并且給出了這種變換的可逆性判斷的充分必要條件，對(duì)設(shè)計(jì)新的密碼算法具有一定的指導(dǎo)作用。

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

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

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

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

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

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

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