|
Frontiers of Information Technology & Electronic Engineering
ISSN 2095-9184 (print), ISSN 2095-9230 (online)
2022 Vol.23 No.10 P.1533-1545
On observability of Galois nonlinear feedback shift registers over finite fields
Abstract: 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.
Key words: Observability; Nonlinear feedback shift registers (NFSRs); Galois NFSRs; Semi-tensor product; Finite fields; Logical networks
1山东大学数学学院,中国济南市,250100
2明尼苏达大学双城分校计算机科学与工程系,美国明尼苏达州,55455
摘要:能观性可以确保任何两个不同初始状态都可以由它们的输出序列唯一确定,因此流密码必须避免不可观的非线性反馈移位寄存器,以防止等效密钥的出现。本文讨论了有限域上Galois型非线性反馈移位寄存器的能观性。通过半张量积,Galois型非线性反馈移位寄存器可被视为逻辑网络。本文介绍了状态转移矩阵的向量形式,据此提出一个充分必要条件以及判定一般Galois型非线性反馈移位寄存器能观性的算法。此外,本文定义了一个新的能观性矩阵,通过该矩阵可推导出计算复杂度较低的矩阵方法。此外,研究两种特殊类型的Galois型非线性反馈移位寄存器的能观性:全长Galois型非线性反馈移位寄存器和非奇异Galois型非线性反馈移位寄存器。提出两种方法确定这两种特殊类型的非线性反馈移位寄存器的能观性,并提供一些数值示例支持这些结果。
关键词组:
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/FITEE.2200228
CLC number:
O23
Download Full Text:
Downloaded:
4933
Download summary:
<Click Here>Downloaded:
274Clicked:
1698
Cited:
0
On-line Access:
2022-10-24
Received:
2022-05-24
Revision Accepted:
2022-10-24
Crosschecked:
2022-08-17