基于循环移位和异或运算的对合线性变换研究

在对称密码算法的设计中,为达到良好的扩散作用,设计者一般均选择分支数较大的线性变换。基于循环移位和异或运算的线性变换由于其实现效率较高,已经在很多密码算法中被采用,比如分组密码SMS4、HIGHT,Hash函数SHA-2、MD6等。此外,如果线性变换是对合的,还为解密带来了方便。研究了基于循环移位和异或运算设计的对合线性变换,给出了这类线性变换的计数公式,指出它们的分支数上界为4,并讨论了循环移位的参数与分支数之间的关系,从而为基于这类运算设计的线性变换提供了理论依据。

基于SAT的线性扩散层分支数的快速计算方法

将线性扩散层差分和线性分支数的计算问题转化为布尔可满足性问题(Boolean Satisfiability Problem,SAT),提出了一种通用的快速计算分组密码线性扩散层分支数的方法,该方法可以在较短的时间内求解出分组大于32比特线性扩散层的分支数。为了检验本方法的实际应用效果,测试了一批随机构造的循环异或(Rotation-XOR,RX)结构分组为64比特线性扩散层的分支数。结果显示,所提方法均能在较短的时间内计算出分支数,并且当线性扩散层的分组为64比特、分块为8、异或项数为9时,首次得到分支数达到8的RX结构的扩散层。

模2~n剩余类环上线性变换的异或线性分支数

异或线性分支数是衡量分组密码扩散结构的扩散性能的一个重要指标,它对分组密码抵抗线性密码分析的能力有重要的影响.二元域上的非线性变换也常用作分组密码的扩散结构,本文给出了此类扩散结构的异或线性分支数的一个定义及其与分组密码抗线性逼近攻击能力的关系,证明了以模2n剩余类环上的线性变换为扩散结构的异或线性分支数等于将其奇系数换成1、偶系数换成0且将模2n加换成模2加所得的二元域上线性变换的异或线性分支数,从而将这类扩散结构的异或线性分支数归结为二元域上线性变换的异或线性分支数.

构造分支数为4的对合线性变换

扩散层是分组密码的一个重要组件,特别是SPN型结构的密码以及轮函数为SPN型的Feistel结构密码,都要用到一个非退化的线性变换作为其扩散层。好的分支数以及线性变换的对合性质对分组密码的扩散性以及实现效率都有很大的提高。本文基于循环移位和异或运算构造了三种线性变换。并证明了这三种线性变换是分支数为4的次最优的线性变换,同时在一定条件下,还证明了它们均是对合的线性变换。