一类模加差分方程系统解个数的期望与方差

The expectation and variance of the number of solutions of a class of differential system of modular addition

模2~n加法是一个非常重要的密码运算部件,它已经被广泛用于各种对称密码算法的设计,如MD5、SNOW 3G、SPECK和ZUC等.差分故障攻击是针对密码算法实现的一种通用的安全性分析方法,该攻击假设攻击者能在算法运行过程中动态注入故障.在对采用模加运算的密码算法进行差分故障分析时,攻击者往往会导出一个模加差分方程系统,该方程系统中,方程的个数恰好等于法注入故障的次数,其与方程系统的解个数密切相关.由于注入故障次数和方程系统解个数是评估故障攻击复杂度的两个关键参数,因此,研究它们之间的关系非常有意义.本文讨论了上述模加差分方程系统中一类特殊方程系统(即模加差分相互独立且服从均匀分布)的解个数的统计特性.作为结果,本文给出了它们的期望和方差.本文的结果表明,对一般的模加差分方程系统,平均意义下,需要注入大约log_2(n)+5个故障可以确定方程系统的候选解.

The modular addition is an important nonlinear operation in symmetric ciphers, and has been widely used in the design of cryptographic primitives, such as MD5, SNOW 3G, SPECK, ZUC and so on. Differential fault attack is a general cryptanalytic method for cipher implementations with the assumption that an adversary is able to inject faults into the registers on the fly. A digerential equation system of modular addition （DESMA, in short） is usually deduced during differential fault cryptanalysis of these ciphers. In this paper we present the relationship between the number of solutions of the DESMA and the number of injected faults, and give their expectation and variance. Our result shows that about log2 （n） ＋ 5 faults are required to determine the candidate solutions of the DESMA.