密码算法中的循环移位“异或”运算实质性研究

成 彬 ，王冬艳 ，韩宪生 ，胡 波

(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.