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.展开更多
For nonlinear feedback shift registers (NFSRs), their greatest common subfamily may be not unique. Given two NFSRs, the authors only consider the case that their greatest common subfamily exists and is unique. If th...For nonlinear feedback shift registers (NFSRs), their greatest common subfamily may be not unique. Given two NFSRs, the authors only consider the case that their greatest common subfamily exists and is unique. If the greatest common subfamily is exactly the set of all sequences which can be generated by both of them, the authors can determine it by Grobner basis theory. Otherwise, the authors can determine it under some conditions and partly solve the problem.展开更多
基金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.
基金supported by the Natural Science Foundation of China under Grant Nos.61272042,61100202and 61170235
文摘For nonlinear feedback shift registers (NFSRs), their greatest common subfamily may be not unique. Given two NFSRs, the authors only consider the case that their greatest common subfamily exists and is unique. If the greatest common subfamily is exactly the set of all sequences which can be generated by both of them, the authors can determine it by Grobner basis theory. Otherwise, the authors can determine it under some conditions and partly solve the problem.