有限域上Galois型非线性移位寄存器的能观性

高哲; 冯俊娥; 于永渊; 崔彦君

doi:10.1631/FITEE.2200228

Your Location：

Home >

Browse articles >

有限域上Galois型非线性移位寄存器的能观性

常规文章 | Updated：2022-10-28

- 有限域上Galois型非线性移位寄存器的能观性
- On observability of Galois nonlinear feedback shift registers over finite fields
- 信息与电子工程前沿（英文） 2022年23卷第10期页码：1533-1545
- Affiliations：
  
  1.School of Mathematics, Shandong University, Jinan 250100, China
  2.Department of Computer Science & Engineering, University of Minnesota Twin Cities, Minneapolis, MN 55455, USA
- Author bio：
  
  E-mail: gaoz_0202@163.com
  ‡Corresponding author
  yyyu@sdu.edu.cn
  cui00022@umn.edu
- Funds：
  
  National Natural Science Foundation of China(61877036)
- DOI：10.1631/FITEE.2200228
  中图分类号： O23
- 收稿：2022-05-24，
  
  修回：2022-09-07，
  
  录用：2022-08-17，
  
  网络出版：2022-09-28，
  
  纸质出版：2022-10-0
- Accepted：
Scan QR Code
高哲, 冯俊娥, 于永渊, 等. 有限域上Galois型非线性移位寄存器的能观性[J]. 信息与电子工程前沿（英文）, 2022,23(10):1533-1545.

Zhe GAO, Jun'e FENG, Yongyuan YU, et al. On observability of Galois nonlinear feedback shift registers over finite fields[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(10): 1533-1545.
高哲, 冯俊娥, 于永渊, 等. 有限域上Galois型非线性移位寄存器的能观性[J]. 信息与电子工程前沿（英文）, 2022,23(10):1533-1545. DOI： 10.1631/FITEE.2200228.

Zhe GAO, Jun'e FENG, Yongyuan YU, et al. On observability of Galois nonlinear feedback shift registers over finite fields[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(10): 1533-1545. DOI： 10.1631/FITEE.2200228.

摘要

能观性可以确保任何两个不同初始状态都可以由它们的输出序列唯一确定，因此流密码必须避免不可观的非线性反馈移位寄存器，以防止等效密钥的出现。本文讨论了有限域上Galois型非线性反馈移位寄存器的能观性。通过半张量积，Galois型非线性反馈移位寄存器可被视为逻辑网络。本文介绍了状态转移矩阵的向量形式，据此提出一个充分必要条件以及判定一般Galois型非线性反馈移位寄存器能观性的算法。此外，本文定义了一个新的能观性矩阵，通过该矩阵可推导出计算复杂度较低的矩阵方法。此外，研究两种特殊类型的Galois型非线性反馈移位寄存器的能观性：全长Galois型非线性反馈移位寄存器和非奇异Galois型非线性反馈移位寄存器。提出两种方法确定这两种特殊类型的非线性反馈移位寄存器的能观性，并提供一些数值示例支持这些结果。

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.

关键词

Keywords

references

JP Aumasson , , I Dinur , , W Meier , , 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 https://doi.org/10.1007/978-3-642-03317-9_1 , .

DZ Cheng , , HS Qi , , ZQ Li , . 2011 . . Analysis and Control of Boolean Networks: a Semi-tensor Product Approach . , : Springer London . https://doi.org/10.1007/978-0-85729-097-7 https://doi.org/10.1007/978-0-85729-097-7 , .

DZ Cheng , , HS Qi , , Y Zhao , . 2012 . . An Introduction to Semi Tensor Product of Matrices and Its Applications . , : Hackensack : World Scientific . , https://doi.org/10.1142/8323 https://doi.org/10.1142/8323 , .

PP Deepthi , , PS Sathidevi , . 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 https://doi.org/10.1016/j.cose.2008.11.006 , .

E Dubrova , . 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 https://doi.org/10.1109/TIT.2009.2030467 , .

E Dubrova , . 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 https://doi.org/10.1109/TIT.2010.2046250 , .

E Fornasini , , ME Valcher , . 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 https://doi.org/10.1109/TAC.2012.2231592 , .

SW Golomb , . 1967 . . Shift Register Sequences . , : San Francisco : Holden-Day , . .

S Hellebrand , , J Rajski , , S Tarnick , , 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 https://doi.org/10.1109/12.364534 , .

C Huang , , DWC Ho , , JQ Lu , , 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 https://doi.org/10.1109/TSMC.2021.3073201 , .

WH Kong , , JH Zhong , , DD Lin , . 2022 . . Observability of Galois nonlinear feedback shift registers . . Sci China Inform Sci , , 65 ( ( 9 ): ): 192206 . https://doi.org/10.1007/s11432-021-3346-6 https://doi.org/10.1007/s11432-021-3346-6 , .

XJ Lai , . 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 https://doi.org/10.1109/TIT.1987.1057338 , .

R Li , , M Yang , , TG Chu , . 2014 . . Observability conditions of Boolean control networks . . Int J Robust Nonl Contr , , 24 ( ( 17 ): ): 2711 - - 2723 . . https://doi.org/10.1002/rnc.3019 https://doi.org/10.1002/rnc.3019 , .

YF Li , , JD Zhu , . 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 https://doi.org/10.1631/FITEE.1900422 , .

K Limniotis , , N Kolokotronis , , N Kalouptsidis , . 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 https://doi.org/10.1109/ISIT.2006.261900 , .

K Limniotis , , N Kolokotronis , , N Kalouptsidis , . 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 https://doi.org/10.1109/TIT.2008.917639 , .

L Ljung , , T Sèoderstrèom , . 1983 . . Theory and Practice of Recursive Identification . , : Cambridge : MIT Press , . .

JQ Lu , , ML Li , , Y Liu , , et al. , . 2018a . . Nonsingularity of Grain-like cascade FSRs via semi-tensor product . . Sci China Inform Sci , , 61 ( ( 1 ): ): 010204 . https://doi.org/10.1007/s11432-017-9269-6 https://doi.org/10.1007/s11432-017-9269-6 , .

JQ Lu , , ML Li , , TW Huang , , 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 https://doi.org/10.1016/j.automatica.2018.07.011 , .

JQ Lu , , BW Li , , J Zhong , . 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 https://doi.org/10.1007/s11432-020-2981-4 , .

J Massey , . 1969 . . Shift-register synthesis and BCH decoding . . IEEE Trans Inform Theory , , 15 ( ( 1 ): ): 122 - - 127 . . https://doi.org/10.1109/TIT.1969.1054260 https://doi.org/10.1109/TIT.1969.1054260 , .

W Meier , , O Staffelbach , . 1989 . . Fast correlation attacks on certain stream ciphers . . J Cryptol , , 1 ( ( 3 ): ): 159 - - 176 . . https://doi.org/10.1007/BF02252874 https://doi.org/10.1007/BF02252874 , .

AH Roger , , CR Johnson , . 1991 . . Topics in Matrix Analysis . , Cambridge University Press . , https://doi.org/10.1017/CBO9780511840371 https://doi.org/10.1017/CBO9780511840371 , .

YW Shen , , YQ Guo , , WH Gui , . 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 https://doi.org/10.1631/FITEE.1900454 , .

B Wang , , JE Feng , . 2019 . . On detectability of probabilistic Boolean networks . . Inform Sci , , 483 : 383 - - 395 . . https://doi.org/10.1016/j.ins.2019.01.055 https://doi.org/10.1016/j.ins.2019.01.055 , .

HY Wang , , JH Zhong , , DD Lin , . 2017 . . Linearization of multi-valued nonlinear feedback shift registers . . J Syst Sci Complexity , , 30 ( ( 2 ): ): 494 - - 509 . . https://doi.org/10.1007/s11424-016-5156-7 https://doi.org/10.1007/s11424-016-5156-7 , .

QY Wang , , CH Jin , . 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 https://doi.org/10.3969/j.issn.1671-0673.2013.05.002 , .

XJ Wang , , T Tian , , WF Qi , . 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 https://doi.org/10.1016/j.ffa.2021.101952 , .

YY Yu , , M Meng , , JE Feng , , et al. , . 2021 . . Observability criteria for Boolean networks . . IEEE Trans Autom Contr , , early access . https://doi.org/10.1109/TAC.2021.3131436 https://doi.org/10.1109/TAC.2021.3131436 , .

QL Zhang , , B Wang , , JE Feng , . 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 https://doi.org/10.1631/FITEE.1900504 , .

XY Zhao , , B Wang , , YY Yan , , 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 https://doi.org/10.1002/asjc.2390 , .

YT Zheng , , JE Feng , . 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 https://doi.org/10.1631/FITEE.1900376 , .

J Zhong , , BW Li , , Y Liu , , 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 https://doi.org/10.1631/FITEE.1900229 , .

JH Zhong , , DD Lin , . 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 https://doi.org/10.1016/j.jcss.2014.12.030 , .

JH Zhong , , DD Lin , . 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 https://doi.org/10.1109/TCOMM.2016.2557330 , .

JH Zhong , , DD Lin , . 2016b . . Stability of nonlinear feedback shift registers . . Sci China Inform Sci , , 59 ( ( 1 ): ): 1 - - 12 . . https://doi.org/10.1007/s11432-015-5311-0 https://doi.org/10.1007/s11432-015-5311-0 , .

JH Zhong , , DD Lin , . 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 https://doi.org/10.1109/TIT.2018.2849392 , .

JH Zhong , , DD Lin , . 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 https://doi.org/10.1007/s11432-017-9460-4 , .

JH Zhong , , DD Lin , . 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 https://doi.org/10.1093/comjnl/bxz057 , .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Analysis of the Pareto equilibrium in multi-objective games using semi-tensor product

A joint image compression and encryption scheme based on a novel coupled map lattice system and DNA operations

State space optimization of finite state machines from the viewpoint of control theory

Output tracking of delayed logical control networks with multi-constraint

Cascading decomposition of Boolean control networks: a graph-theoretical method