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 pe...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”.展开更多
Observability ensures that any two distinct initial states can be uniquely determined by their outputs,so the stream ciphers can avoid unobservable nonlinear feedback shift registers(NFSRs)to prevent the occurrence of...Observability ensures that any two distinct initial states can be uniquely determined by their outputs,so the stream ciphers can avoid unobservable nonlinear feedback shift registers(NFSRs)to prevent the occurrence of equivalent keys.This paper discusses the observability of Galois NFSRs over finite fields.Galois NFSRs are treated as logical networks using the semi-tensor product.The vector form of the state transition matrix is introduced,by which a necessary and sufficient condition is proposed,as well as an algorithm for determining the observability of general Galois NFSRs.Moreover,a new observability matrix is defined,which can derive a matrix method with lower computation complexity.Furthermore,the observability of two special types of Galois NFSRs,a full-length Galois NFSR and a nonsingular Galois NFSR,is investigated.Two methods are proposed to determine the observability of these two special types of NFSRs,and some numerical examples are provided to support these results.展开更多
基金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”.
基金the National Natural Science Foundation of China(No.61877036)。
文摘Observability ensures that any two distinct initial states can be uniquely determined by their outputs,so the stream ciphers can avoid unobservable nonlinear feedback shift registers(NFSRs)to prevent the occurrence of equivalent keys.This paper discusses the observability of Galois NFSRs over finite fields.Galois NFSRs are treated as logical networks using the semi-tensor product.The vector form of the state transition matrix is introduced,by which a necessary and sufficient condition is proposed,as well as an algorithm for determining the observability of general Galois NFSRs.Moreover,a new observability matrix is defined,which can derive a matrix method with lower computation complexity.Furthermore,the observability of two special types of Galois NFSRs,a full-length Galois NFSR and a nonsingular Galois NFSR,is investigated.Two methods are proposed to determine the observability of these two special types of NFSRs,and some numerical examples are provided to support these results.
