密码分析中加法运算的异或逼近

XOR Approximation of Modulo Addition for Cryptanalysis

现代密码组件中常用到不同群上的混合运算.在密码分析中,常用异或运算线性逼近加法运算对密码算法进行区分攻击,此时就会产生噪声变量概率分布的求解问题.该文利用自由幺半群上的有理形式幂级数理论,构造出该概率分布的约化线性表示,从而完全解决了噪声变量的概率分布计算问题.同时,将结果推广到模p^n剩余类环上,这就为该类组件的线性密码分析提供了重要的理论支持.

Modern cipher components usually combine mixed operations of different groups. In cryptanalysis, one always uses the XOR operation to linearly approximate modular addition, which requires calculation of the distribution of noise. In this paper, we propose a reduced linear representation of such distribution based on the formal power series on free monoid which can be easily used to calculate the probability distribution. We also extend the result to the addition modulo p^n. This provides a solid basis for linear cryptanalysis.