摘要 “模2n数乘运算”——y=c×x mod 2n是一个常用的密码算法编码环节，在许多密码算法中有广泛的应用，如Sosemanuk, RC6, MARS等。当常数c取奇数时，该运算环节是一个具有很强的非线性性质和良好实现效率的非线性置换。目前没有公开文献对此环节进行差分分析。该文对y=c×x mod 2n(c是任意固定的正整数)的差分性质进行了研究，给出了差分转移概率为1时，输入差、输出差及常数c的结构，并给出计数公式。然后该文给出了其进位计数之间的递归关系，基于这种递归关系给出了计算该运算的差分转移概率的平均复杂度为O(n)的算法。
Abstract：Multiplied by constant on modulo 2n operation, a building block, is widely used in the ciphers like Sosemanuk, RC6, MARS, and so on. This code link is recognized as a permutation with strong nonlinear property and fine realization efficiency, when the constant c is odd. But there is no published paper analyzed it with differential cryptanalysis. In this paper, the differential property of the operation is studied. And the characters of structure, counts of the input and output differentials and the constant are given for the first time, when the differential probability is to be 1. Then the recursive connection of its carries’ counts is given. Based on that, an algorithm of this operation’s differential probability is given, which time complexity is O(n) on average.
2011, Vol. 33 
