摘要
差分分析是一种常用的重要密码分析方法.差分分析通常针对于分组加密算法,但是对于流密码算法和哈希函数同样适用.模2k加法运算是分组密码和流密码设计中常用到的基本运算,在分组密码,流密码算法和构造轻量级的认证协议中都有应用.在实际的分析过程中,为了得到特定差分对的出现概率,需要对所有可能的差分对进行枚举计算.当k的取值比较大时,差分对的样本空间很大,直接进行穷举计算是很困难的,因此需要针对差分对具体结构进行分析,找到一种快速的计算方法.本文给出了模2k加法运算的差分概率分布及其统计特性.对于固定的差分a,本文给出了计算该差分发生概率的公式:当a作为一个随机变量时,我们给出了其差分概率的期望,并且得到了差分概率的方差.当k增加时,差分概率是关于k的一个可忽略不计的函数.本文中的结论,对于研究基于模2k加运算的密码算法和相关的认证协议的区分攻击是有帮助的.
Differential cryptanalysis is one of the most important and popular cryptanalytic method. Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, and it also applies to stream ciphers and cryptographic hash functions. Modulo 2k addition is a common arithmetic operation that is often used in the design of stream ciphers, block ciphers and lightweight authentication protocols. In practical analysis, inorder to obtain the probabilities of occurrence of a particular differential pair, it needs to enumerate all possible differential pairs. When k is large, the sample space of the differential pairs is very large, so the exhaustive search is difficult. It requires to design a fast algorithm according to the specific structure of the function. This paper gives the probability distribution and the statistical property of the differential of the modulo 2k addition. For a fixed differential a, this paper gives a formula to compute the probability when such a differential occurs: when a is treated as a random variable, we give the probability expectation and variance of the differential. When k is increasing, the differential probability is a negligible function about k. The conclusions in this paper are helpful in studying the differential attacks on cryptographic algorithms and lightweight authentication protocols that use modulo 2k addition.
出处
《密码学报》
CSCD
2015年第2期122-138,共17页
Journal of Cryptologic Research
基金
国家863课题"物联网安全关键技术及仿真平台研究"(2013AA014002)
中科院海云先导专项(XDA06010701)
关键词
差分分析
模2k加
伪随机函数
differential analysis
modulo 2k addition
pseudo-random function
