English

应用科学学报

• 论文 • 上一篇    下一篇

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

周 悦 李瑞林 李 超   

  1. 国防科学技术大学 数学与系统科学系，湖南 长沙 410073
  • 收稿日期:2007-09-18 修回日期:2007-12-20 出版日期:2008-03-31 发布日期:2008-03-31

XOR Approximation of Modulo Addition for Cryptanalysis

ZHOU Yue, LI Rui-lin, LI Chao   

  1. Department of Mathematics and System Science, National University of Defense Technology, Changsha 410073,China
  • Received:2007-09-18 Revised:2007-12-20 Online:2008-03-31 Published:2008-03-31

被引次数

2

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

关键词: 密码分析, 约化线性表示, 概率分布, 混合运算

Abstract: Modern cipher components ususlly combine mixed operations of different groups. In cryptanalysis,one alwalys 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 pobability diatribution.We also extend the result to the addition modulo p^n.This provides a solid basis for linear cryptanalysis.

Key words: cryptanalysis, reduced linear representation, probability distribution, mixed operations