电子学报 ›› 2018, Vol. 46 ›› Issue (9): 2075-2080.DOI: 10.3969/j.issn.0372-2112.2018.09.005

• 学术论文 • 上一篇    下一篇

非线性反馈移存器型序列密码的完全性通用算法

李俊志, 关杰   

  1. 信息工程大学, 河南郑州 450000
  • 收稿日期:2017-08-29 修回日期:2017-12-07 出版日期:2018-09-25 发布日期:2018-09-25
  • 通讯作者: 关杰
  • 作者简介:李俊志 男,1990年生于河南新乡.现为信息工程大学博士研究生.主要研究方向为序列密码.E-mail:lijunzhi1998@163.com
  • 基金资助:
    国家自然科学基金(No.61572516,No.61272488)

Universal Algorithm of Full Diffusion of Stream Cipher Based on Nonlinear Feedback Shift Register

LI Jun-zhi, GUAN Jie   

  1. Information Engineering University, Zhengzhou, Henan 450000, China
  • Received:2017-08-29 Revised:2017-12-07 Online:2018-09-25 Published:2018-09-25

摘要: 非线性反馈移存器型序列密码被使用于智能卡、射频识别标签(RFID)和无线传感器等硬件资源受限设备的信息加密中,其典型代表为Trivium算法、Grain v1算法和Mickey算法,然而现有的完全性算法在应用于此类序列密码时存在分析轮数较少及对依赖关系区分不清楚等问题.本文提出了一种考察此类序列密码完全性的通用算法,将算法内部状态表示成线性集合和非线性集合,将序列密码每轮更新转化为集合的运算,通过迭代计算可给出算法达到非线性完全性所需轮数的下界,克服了现有完全性算法的不足.应用此通用算法给出Trivium算法更优的1比特差分区分器并完成对Trivium-B算法的实时攻击.本方法可为此类序列密码的设计提供一定的理论依据.

关键词: 序列密码, 非线性反馈移位寄存器, 安全性指标, 完全性, Trivium, 区分攻击, 分别征服攻击

Abstract: Stream ciphers based on nonlinear feedback shift register are used in information security of hardware restricted devices such as smart cards,radio frequency identification(RFID) and wireless sensor network.Typical examples of these ciphers are Trivium,Grain v1 and Mickey.Previous algorithms of full diffusion have disadvantages such as few analyzing rounds and indistinct dependent relationship.This paper proposes an algorithm for full diffusion of stream cipher based on nonlinear feedback shift register.The internal states of cipher are represented as linear sets and nonlinear sets.Then round functions of stream cipher are converted to operations of sets.So we can estimate the lower bound of rounds which a stream cipher needs to reach full nonlinear diffusion.Using this algorithm,this paper presents an improved one bit differential distinguisher of Trivium and a real-time attack on full rounds of Trivium-B.Moreover,this method can provide certain theory basis for the design of this kind of stream cipher.

Key words: stream cipher, nonlinear feedback shift register, security index of stream ciphers, full diffusion, Trivium, distinguishing attack, divide-and-conquer attack

中图分类号: