一种改进的线性化技术及其应用

A Modified Linearization Technique and Its Application

线性密码分析方法是一种重要的密码分析方法,它的一个关键步骤是寻找密码算法中的非线性变换的有效线性逼近式.对于非线性变换表达式已知的情况可利用线性化技术得到线性逼近式.通过研究我们发现,目前利用一般的线性化技术所做的假设条件并不一定都成立,从而导致计算得到的线性偏差与实际值之间存在一定误差.本文提出了一种改进的线性化技术——分解消项线性化法.对于一个明确的非线性表达式,在进行线性逼近时,通过利用非线性项之间的相关性,合并约减表达式中非线性项,能够提高线性偏差.使用此方法,本文对初始化为288轮的简化版Trivium算法和它的修改版本Trivium-M1算法进行了线性分析,在固定10个IV比特和10密钥比特为0的条件下,分别找到了线性偏差为2-20和2-43的线性逼近式,改进了原有的线性分析结果.

Linear cryptanalysis is a very important method of cryptanalysis. A key step of linear cryptanalysis is searching for an effective approximation of nonlinear transform of crypto systems. When the nonlinear transformation has an known explicit representation, the linearization can be used to get the linear approximation. Our study found that the common assumptions for linearization may not hold, which may result in some error between the computed linear bias and the real value. A modified linearization technique is presented in this paper, which can reduce the number of nonlinear terms and increase the linear bias effectively when the nonlinear transform expression is known. Then we apply this method to the linear cryptanalysis of the reduced Trivium and its modified version Trivium-M1. Using this new method, we found linear approximations of reduced Triviumwith the linear bias 2-20 and reduced Trivium-M1 with the linear bias 2-43 on the condition that10 bits of the key and 10 bits of the IV are fixed, which are better than the previous results of linear cryptanalysis.