A Fibonacci View on the Galois NFSR Used in Trivium  

作　　者：WANG Hongyu ZHENG Qunxiong QI Wenfeng 

机构地区：[1]PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China

出　　处：《Journal of Systems Science & Complexity》2024年第3期1326-1350,共25页系统科学与复杂性学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant Nos.12371526,61872383,61802430,and 62202494。

摘　　要：Trivium is an international standard of lightweight stream ciphers(ISO/IEC 29192-3:2012).In this paper,the Trivium-like NFSRs,a class of Galois NFSRs generalized from the Galois NFSR of Trivium,are studied from the perspective of Fibonacci NFSRs.It is shown that an n-stage Trivium-like NFSR cannot be equivalent to an n-stage Fibonacci NFSR,which is proved by showing the existence of“collision initial states”.As an intermediate conclusion,a necessary and sufficient condition for a kind of linear degeneracy of a Trivium-like NFSR is obtained from the persepective of interleaved sequences.Moreover,the smallest stage number of a Fibonacci NFSR that can generate all the output sequences of an n-stage Trivium-like NFSR is shown to be greater than n-7 and this value is no less than 371=287+min{93,84,111}specifically for the 288-stage Galois NFSR used in Trivium.These results contradict the existence of a equivalent Fibonacci model of Trivium NFSR of small stage,which implies that Trivium algorithm possesses a fair degree of immunity against“structure attack”.

关 键 词：Fibonacci NFSR galois NFSR interleaved sequence linear degeneracy trivium 

分 类 号：TP332.11[自动化与计算机技术—计算机系统结构] TN918.4[自动化与计算机技术—计算机科学与技术]