基于循环移位和异或运算的线性变换的逆变换求解方法

学过密码学的都知道，对称加密算法的两大设计准则是混淆性(S盒提供)和扩散性(P盒提供)。关于常见对称加密算法所使用的S盒和P盒设计细节详见对称加密算法中的混淆层(S盒)大盘点和对称加密算法中的扩散层(P盒)大盘点这两篇文章，这里不再讲解。通过参考各大对称加密算法的设计文档，我们容易发现，有不少的对称加密算法采用循环移位和异或运算作为扩散层(也即线性变换)，因为该类变换可以提供良好的扩散性(分支数大)和软件实现上的高效性(效率高)。

接下来本文将给出求解该类线性变换的逆变换的2个方法，然而这可能也并没什么卵用。(弱弱的说一句：我写什么样的文章，不是看你们想看什么样的文章，而是要看我会什么。嘿嘿嘿！！！)

采用循环移位和异或运算作为线性扩散变换的对称加密算法(包含分组加密算法，序列密码算法，密码杂凑算法，认证加密算法和消息鉴别算法)如下图所示：

本文将会给出两个求解该类线性变换的逆变换的方法。

方法1

（1）对于FFF(X)=(X<<<a)⊕(X<<<b)⊕(X<<<c)

(其中X∈(F2)^32,0≤a<b<c<32(a,b,c均为正整数))

(FFF(X))^1=(X<<<a)⊕(X<<<b)⊕(X<<<c)=(a,b,c)

(FFF(X))^2=(X<<<2a)⊕(X<<<2b)⊕(X<<<2c)=(2a,2b,2c)

(FFF(X))^4=(X<<<4a)⊕(X<<<4b)⊕(X<<<4c)=(4a,4b,4c)

(FFF(X))^8=(X<<<8a)⊕(X<<<8b)⊕(X<<<8c)=(8a,8b,8c)

(FFF(X))^16=(X<<<16a)⊕(X<<<16b)⊕(X<<<16c)=(16a,16b,16c)

(FFF(X))^32=(X<<<32a)⊕(X<<<32b)⊕(X<<<32c)=(32a,32b,32c)=X(由此可以看出FFF变换为双射，故其存在逆变换。)

故(FFF(X))^-1=(FFF(X))^31，又因为

将243个循环移位项对32求模之后，删除出现偶数次的项(出现偶数次的项会两两抵消)，再将剩余的项按照从小到大的顺序排列即可得到FFF的逆变换FFF^-1。

（2）对于FFFFF(X)=(X<<<a)⊕(X<<<b)⊕(X<<<c)⊕(X<<<d)⊕(X<<<e)

(其中X∈(F2)^32,0≤a<b<c<d<e<32(a,b,c,d,e均为正整数))

(FFFFF(X))^1=(X<<<a)⊕(X<<<b)⊕(X<<<c)⊕(X<<<d)⊕(X<<<e)=

(a,b,c,d,e)

(FFFFF(X))^2=(X<<<2a)⊕(X<<<2b)⊕(X<<<2c)⊕(X<<<2d)⊕(X<<<2e)=

(2a,2b,2c,2d,2e)

(FFFFF(X))^4=(X<<<4a)⊕(X<<<4b)⊕(X<<<4c)⊕(X<<<4d)⊕(X<<<4e)=

(4a,4b,4c.4d,4e)

(FFFFF(X))^8=(X<<<8a)⊕(X<<<8b)⊕(X<<<8c)⊕(X<<<8d)⊕(X<<<8e)=

(8a,8b,8c,8d,8e)

(FFFFF(X))^16=(X<<<16a)⊕(X<<<16b)⊕(X<<<16c)⊕(X<<<16d)⊕(X<<<16e)=

(16a,16b,16c,16d,16e)

(FFFFF(X))^32=(X<<<32a)⊕(X<<<32b)⊕(X<<<32c)⊕(X<<<32d)⊕(X<<<32e)=

(32a,32b,32c,32d,32e)=X(由此可以看出FFFFF变换为双射，故其存在逆变换。)

故(FFFFF(X))^-1=(FFFFF(X))^31，又因为

将3125个循环移位项对32求模之后，删除出现偶数次的项(出现偶数次的项会两两抵消)，再将剩余的项按照从小到大的顺序排列即可得到FFFFF的逆变换FFFFF^-1。

方法2

（1）对于FFF(X)=(X<<<a)⊕(X<<<b)⊕(X<<<c)

(其中X∈(F2)^32,0≤a<b<c<32(a,b,c均为正整数))

设字长为 n，循环左移为 <<<，异或为 ⊕。令

把 n位字看成 GF(2)上的多项式，循环左移等价于乘以 z，则

记

若 gcd(F(z),z^n-1)=1，则逆变换存在。设

则逆变换为

即

其中 gi∈{0,1}由

冰与火的战歌：Windows内核攻防实战高级班！从零到实战，融合AI与Windows内核攻防全技术栈，打造具备自动化能力的内核开发高手。