马猛，赵亚群



简化版Trivium算法的线性逼近研究

马猛，赵亚群

（信息工程大学数学工程与先进计算国家重点实验室，河南郑州 450001）

针对初始化轮数为288个时钟的简化版Trivium算法（又称2轮Trivium）进行了线性逼近研究，设计了搜索最佳线性近似式算法，并通过对第1轮关于密钥、初始化向量和密钥流比特的表达式做非线性逼近，结合该算法，在同等条件下给出了2轮Trivium 16个偏差为的线性近似式，使通过多线性攻击去识别2轮Trivium的一个具有特定比特的密钥所需要的数据量降为个选择，为Turan方案所需数据量的，且成功率保持不变。

流密码；Trivium算法；多线性密码分析；线性逼近

1 引言

由Canniàre和Preneel[1]于2005年设计的Trivium算法是2004年欧洲序列密码计划最终胜选的标准算法之一，该算法面向硬件实现，具有设计简洁、安全、速度快和灵活性好等特点。因此，Trivium在发布之初就引起了广泛关注，针对Trivium的安全性分析一直是流密码的热点研究方向之一。

目前针对Trivium的主要攻击方法有线性攻击、区分攻击、代数攻击、滑动攻击、立方攻击、错误引入攻击等。Maximov和Biryukov[2]在2007年提出了Trivium的代数攻击方法，攻击的计算复杂度为，其中，常数是求解线性方程组的复杂度。2009年，Dinur和Shamir[3]针对初始化轮数为767个时钟的简化版 Trivium提出了立方攻击，攻击的计算复杂度为。2010年，Stankovski[4]对初始化轮数为1 078个时钟的简化版Trivium 进行了区分攻击，攻击的计算复杂度为。2011年，Hu等[5]通过重复错误注入的方式，提出了一种校验部分原始密钥流和部分错误密钥流的方法，确定错误注入时间及位置，进而说明Trivium在故障攻击下的脆弱性，较Hojsík等的故障攻击方法[6]，该模型有更弱的假设条件。……