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.
摘要
能观性可以确保任何两个不同初始状态都可以由它们的输出序列唯一确定, 因此流密码必须避免不可观的非线性反馈移位寄存器, 以防止等效密钥的出现. 本文讨论了有限域上Galois型非线性反馈移位寄存器的能观性. 通过半张量积, Galois型非线性反馈移位寄存器可被视为逻辑网络. 本文介绍了状态转移矩阵的向量形式, 据此提出一个充分必要条件以及判定一般Galois型非线性反馈移位寄存器能观性的算法. 此外, 本文定义了一个新的能观性矩阵, 通过该矩阵可推导出计算复杂度较低的矩阵方法. 此外, 研究两种特殊类型的Galois型非线性反馈移位寄存器的能观性: 全长Galois型非线性反馈移位寄存器和非奇异Galois型非线性反馈移位寄存器. 提出两种方法确定这两种特殊类型的非线性反馈移位寄存器的能观性, 并提供一些数值示例支持这些结果.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aumasson JP, Dinur I, Meier W, et al., 2009. Cube testers and key recovery attacks on reduced-round MD6 and Trivium. Int Workshop on Fast Software Encryption, p.1–22. https://doi.org/10.1007/978-3-642-03317-9_1
Cheng DZ, Qi HS, Li ZQ, 2011. Analysis and Control of Boolean Networks: a Semi-tensor Product Approach. Springer London. https://doi.org/10.1007/978-0-85729-097-7
Cheng DZ, Qi HS, Zhao Y, 2012. An Introduction to Semi Tensor Product of Matrices and Its Applications. Hackensack: World Scientific. https://doi.org/10.1142/8323
Deepthi PP, Sathidevi PS, 2009. Design, implementation and analysis of hardware efficient stream ciphers using LFSR based hash functions. Comput Secur, 28(3–4):229–241. https://doi.org/10.1016/j.cose.2008.11.006
Dubrova E, 2009. A transformation from the Fibonacci to the Galois NLFSRs. IEEE Trans Inform Theory, 55(11):5263–5271. https://doi.org/10.1109/TIT.2009.2030467
Dubrova E, 2010. Finding matching initial states for equivalent NLFSRs in the Fibonacci and the Galois configurations. IEEE Trans Inform Theory, 56(6):2961–2966. https://doi.org/10.1109/TIT.2010.2046250
Fornasini E, Valcher ME, 2013. Observability, reconstructibility and state observers of Boolean control networks. IEEE Trans Autom Contr, 58(6):1390–1401. https://doi.org/10.1109/TAC.2012.2231592
Golomb SW, 1967. Shift Register Sequences. San Francisco: Holden-Day.
Hellebrand S, Rajski J, Tarnick S, et al., 1995. Built-in test for circuits with scan based on reseeding of multiple-polynomial linear feedback shift registers. IEEE Trans Comput, 44(2):223–233. https://doi.org/10.1109/12.364534
Huang C, Ho DWC, Lu JQ, et al., 2022. Synchronization of an array of coupled probabilistic Boolean networks. IEEE Trans Syst Man Cybern Syst, 52(6):3834–3846. https://doi.org/10.1109/TSMC.2021.3073201
Kong WH, Zhong JH, Lin DD, 2022. Observability of Galois nonlinear feedback shift registers. Sci China Inform Sci, 65(9):192206. https://doi.org/10.1007/s11432-021-3346-6
Lai XJ, 1987. Condition for the nonsingularity of a feedback shift-register over a general finite field (Corresp.). IEEE Trans Inform Theory, 33(5):747–749. https://doi.org/10.1109/TIT.1987.1057338
Li R, Yang M, Chu TG, 2014. Observability conditions of Boolean control networks. Int J Robust Nonl Contr, 24(17):2711–2723. https://doi.org/10.1002/rnc.3019
Li YF, Zhu JD, 2020. Cascading decomposition of Boolean control networks: a graph-theoretical method. Front Inform Technol Electron Eng, 21(2):304–315. https://doi.org/10.1631/FITEE.1900422
Limniotis K, Kolokotronis N, Kalouptsidis N, 2006. New results on the linear complexity of binary sequences. Proc IEEE Int Symp on Information Theory, p.2003–2007. https://doi.org/10.1109/ISIT.2006.261900
Limniotis K, Kolokotronis N, Kalouptsidis N, 2008. On the linear complexity of sequences obtained by state space generators. IEEE Trans Inform Theory, 54(4):1786–1793. https://doi.org/10.1109/TIT.2008.917639
Ljung L, Sèoderstrèom T, 1983. Theory and Practice of Recursive Identification. Cambridge: MIT Press.
Lu JQ, Li ML, Liu Y, et al., 2018a. Nonsingularity of Grainlike cascade FSRs via semi-tensor product. Sci China Inform Sci, 61(1):010204. https://doi.org/10.1007/s11432-017-9269-6
Lu JQ, Li ML, Huang TW, et al., 2018b. The transformation between the Galois NLFSRs and the Fibonacci NLFSRs via semi-tensor product of matrices. Automatica, 96:393–397. https://doi.org/10.1016/j.automatica.2018.07.011
Lu JQ, Li BW, Zhong J, 2021. A novel synthesis method for reliable feedback shift registers via Boolean networks. Sci China Inform Sci, 64(5):152207. https://doi.org/10.1007/s11432-020-2981-4
Massey J, 1969. Shift-register synthesis and BCH decoding. IEEE Trans Inform Theory, 15(1):122–127. https://doi.org/10.1109/TIT.1969.1054260
Meier W, Staffelbach O, 1989. Fast correlation attacks on certain stream ciphers. J Cryptol, 1(3):159–176. https://doi.org/10.1007/BF02252874
Roger AH, Johnson CR, 1991. Topics in Matrix Analysis. Cambridge University Press. https://doi.org/10.1017/CBO9780511840371
Shen YW, Guo YQ, Gui WH, 2021. Stability of Boolean networks with state-dependent random impulses. Front Inform Technol Electron Eng, 22(2):222–231. https://doi.org/10.1631/FITEE.1900454
Wang B, Feng JE, 2019. On detectability of probabilistic Boolean networks. Inform Sci, 483:383–395. https://doi.org/10.1016/j.ins.2019.01.055
Wang HY, Zhong JH, Lin DD, 2017. Linearization of multivalued nonlinear feedback shift registers. J Syst Sci Complexity, 30(2):494–509. https://doi.org/10.1007/s11424-016-5156-7
Wang QY, Jin CH, 2013. Nonsingularity decision of Trivium-like cascade connection of feedback shift registers. J Inform Eng Univ, 14(5):519–523 (in Chinese). https://doi.org/10.3969/j.issn.1671-0673.2013.05.002
Wang XJ, Tian T, Qi WF, 2022. A necessary and sufficient condition for a class of nonsingular Galois NFSRs. Finit Fields Their Appl, 77:101952. https://doi.org/10.1016/j.ffa.2021.101952
Yu YY, Meng M, Feng JE, et al., 2021. Observability criteria for Boolean networks. IEEE Trans Autom Contr, early access. https://doi.org/10.1109/TAC.2021.3131436
Zhang QL, Wang B, Feng JE, 2021. Solution and stability of continuous-time cross-dimensional linear systems. Front Inform Technol Electron Eng, 22(2):210–221. https://doi.org/10.1631/FITEE.1900504
Zhao XY, Wang B, Yan YY, et al., 2021. The equivalence transformation between Galois NFSRs and Fibonacci NFSRs. Asian J Contr, 23(6):2865–2873. https://doi.org/10.1002/asjc.2390
Zheng YT, Feng JE, 2020. Output tracking of delayed logical control networks with multi-constraint. Front Inform Technol Electron Eng, 21(2):316–323. https://doi.org/10.1631/FITEE.1900376
Zhong J, Li BW, Liu Y, et al., 2020. Output feedback stabilizer design of Boolean networks based on network structure. Front Inform Technol Electron Eng, 21(2):247–259. https://doi.org/10.1631/FITEE.1900229
Zhong JH, Lin DD, 2015. A new linearization method for nonlinear feedback shift registers. J Comput Syst Sci, 81(4):783–796. https://doi.org/10.1016/j.jcss.2014.12.030
Zhong JH, Lin DD, 2016a. Driven stability of nonlinear feedback shift registers with inputs. IEEE Trans Commun, 64(6):2274–2284. https://doi.org/10.1109/TCOMM.2016.2557330
Zhong JH, Lin DD, 2016b. Stability of nonlinear feedback shift registers. Sci China Inform Sci, 59(1):1–12. https://doi.org/10.1007/s11432-015-5311-0
Zhong JH, Lin DD, 2018. On minimum period of nonlinear feedback shift registers in Grain-like structure. IEEE Trans Inform Theory, 64(9):6429–6442. https://doi.org/10.1109/TIT.2018.2849392
Zhong JH, Lin DD, 2019a. Decomposition of nonlinear feedback shift registers based on Boolean networks. Sci China Inform Sci, 62(3):39110. https://doi.org/10.1007/s11432-017-9460-4
Zhong JH, Lin DD, 2019b. On equivalence of cascade connections of two nonlinear feedback shift registers. Comput J, 62(12):1793–1804. https://doi.org/10.1093/comjnl/bxz057
Author information
Authors and Affiliations
Contributions
Zhe GAO and Yongyuan YU designed the research. Zhe GAO and Jun’e FENG processed the data. Zhe GAO drafted the paper. Jun’e FENG and Yanjun CUI helped organize the paper. Zhe GAO and Yongyuan YU revised and finalized the paper.
Corresponding author
Ethics declarations
Zhe GAO, Jun’e FENG, Yongyuan YU, and Yanjun CUI declare that they have no conflict of interest.
Additional information
Project supported by the National Natural Science Foundation of China (No. 61877036)
Rights and permissions
About this article
Cite this article
Gao, Z., Feng, J., Yu, Y. et al. On observability of Galois nonlinear feedback shift registers over finite fields. Front Inform Technol Electron Eng 23, 1533–1545 (2022). https://doi.org/10.1631/FITEE.2200228
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.2200228
Key words
- Observability
- Nonlinear feedback shift registers (NFSRs)
- Galois NFSRs
- Semi-tensor product
- Finite fields
- Logical networks