Novel way to research nonlinear feedback shift register
详细信息 查看全文
- 作者：DaWei Zhao (1) (2) (3) (4)
HaiPeng Peng (1) (2) (3)
LiXiang Li (1) (3)
SiLi Hui (1)
YiXian Yang (1) (3) - 关键词：nonlinear feedback shift register ; semi ; tensor product ; Boolean network ; full ; length nNLFSR ; binary sequence
- 刊名：SCIENCE CHINA Information Sciences
- 出版年：2014
- 出版时间：September 2014
- 年：2014
- 卷：57
- 期：9
- 页码：1-14
- 全文大小：416 KB
- 参考文献：1. Golomb S W, Welch L R, Goldstein R M, et al. Shift Register Sequences. Laguna Hills: Aegean Park Press, 1982
2. Hellebrand S, Rajski J, Tarnick S, et al. Built-in test for circuits with scan based on reseeding of multiple-polynomial linear feedback shift registers. IEEE Trans Comput, 1995, 44: 223鈥?33 CrossRef
3. Paar C, Fleischmann P, Soria-Rodriguez P. Fast arithmetic for public-key algorithms in Galois fields with composite exponents. IEEE Trans Comput, 1999, 48: 1025鈥?034 CrossRef
4. Moon T K, Veeramachaneni S. Linear feedback shift registers as vector quantisation codebooks. Electron Lett, 1999, 35: 1919鈥?920 CrossRef
5. Deepthi P P, Sathidevi P S. Design, implementation and analysis of hardware efficient stream ciphers using LFSR based hash functions. Comput Secur, 2009, 28: 229鈥?41 CrossRef
6. Khashandarag A S, Navin A H, Mirnia M K, et al. An optimized color image steganography using LFSR and DFT techniques. In: Lin S, Huang X, eds. Advanced Research on Computer Education, Simulation and Modeling. Berlin/Heidelberg: Springer, 2011. 247鈥?53 CrossRef
7. Choy J, Chew G, Khoo K, et al. Cryptographic properties and application of a generalized unbalanced Feistel network structure. Cryptogr Commun, 2011, 3: 141鈥?64 CrossRef
8. Gebotys C H. Security in Embedded Devices. Springer US, 2010. 111鈥?42 CrossRef
9. Klein A. Attacks on the RC4 stream cipher. Designs Codes Cryptogr, 2008, 48: 269鈥?86 CrossRef
10. Zhang B, Feng D G. Improved multi-pass fast correlation attacks with applications. Sci China Inf Sci, 2011, 54: 1635鈥?644 CrossRef
11. Golic J D. On the linear complexity of functions of periodic GF( / q) sequences. IEEE Trans Inf Theory, 1989, 35: 69鈥?5 CrossRef
12. De Bruijn N G, Erdos P. A combinatorial problem. Indag Math, 10, 1948: 421鈥?23
13. Wan Z X, Dai Z D, Liu M L, et al. Nonlinear Feedback Shift Register. Beijing: Science Press, 1978
14. Rizomiliotis P, Kalouptsidis N. Results on the nonlinear span of binary sequences. IEEE Trans Inf Theory, 2005, 51: 1555鈥?563 CrossRef
15. Rizomiliotis P, Kolokotronis N, Kalouptsidis N. On the quadratic span of binary sequences. IEEE Trans Inf Theory, 2005, 51: 1840鈥?848 CrossRef
16. Limniotis K, Kolokotronis N, Kalouptsidis N. On the nonlinear complexity and LempelCZiv complexity of finite length sequences. IEEE Trans Inf Theory, 2007, 53: 4293鈥?302 CrossRef
17. Jansen C J A, Franx W G, Boekee D E. An efficient algorithm for the generation of DeBruijn cycles. IEEE Trans Inf Theory, 1991, 37: 1475鈥?478 CrossRef
18. Annexstein F S. Generating de Bruijn sequences: an efficient implementation. IEEE Trans Comput, 1997, 46: 198鈥?00 CrossRef
19. Cheng D, Dong Y. Semi-tensor product of matrices and its some applications to physics. Meth Appl Anal, 2003, 10: 565鈥?88
20. Cheng D, Qi H. A linear representation of dynamics of Boolean networks. IEEE Trans Automat Contr, 2010, 55: 2251鈥?258 CrossRef
21. Cheng D, Qi H, Li Z. Analysis and Control of Boolean Networks: a Semi-Tensor Product Approach. London: Springer, 2011 CrossRef
22. Cheng D, Qi H, Li Z. Model construction of Boolean network via observed data. IEEE Trans Neural Netw, 2011, 22: 525鈥?36
23. Cheng D. Disturbance decoupling of Boolean control networks. IEEE Trans Automat Contr, 2011, 56: 2鈥?0 CrossRef
24. Cheng D, Qi H. Controllability and observability of Boolean control networks. Automatica, 2009, 45: 1659鈥?667 CrossRef
25. Cheng D, Li Z, Qi H. Realization of Boolean control networks. Automatica, 2010, 46: 62鈥?9 CrossRef
26. Kauffman S A. Metabolic stability and epigenesis in randomly constructed genetic nets. J theor biol, 1969, 22: 437鈥?67 CrossRef
27. Blumer A, Blumer J, Ehrenfeucht A, et al. Linear size finite automata for the set of all subwords of a word-an outline of results. Bull EATCS, 1983, 21: 12鈥?0
28. Jansen C J A, Boekee D E. The shortest feedback shift register that can generate a given sequence. In: Proceedings of Advances in Cryptology. New York: Springer, 1990. 90鈥?9 CrossRef - 作者单位：DaWei Zhao (1) (2) (3) (4)
HaiPeng Peng (1) (2) (3)
LiXiang Li (1) (3)
SiLi Hui (1)
YiXian Yang (1) (3)
1. Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China
2. Zhejiang Provincial Key Lab of Data Storage and Transmission Technology, Hangzhou Dianzi University, Hangzhou, 310018, China
3. National Engineering Laboratory for Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing, 100876, China
4. Shandong Provincial Key Laboratory of Computer Network, Shandong Computer Science Center, Jinan, 250014, China - ISSN：1869-1919
文摘
In this paper, we regard the nonlinear feedback shift register (NLFSR) as a special Boolean network, and use semi-tensor product of matrices and matrix expression of logic to convert the dynamic equations of NLFSR into an equivalent algebraic equation. Based on them, we propose some novel and generalized techniques to study NLFSR. First, a general method is presented to solve an open problem of how to obtain the properties (the number of fixed points and the cycles with different lengths) of the state sequences produced by a given NLFSR, i.e., the analysis of a given NLFSR. We then show how to construct all \(2^{2^n - (l - n)} /2^{2^n - l}\) shortest n-stage feedback shift registers (nFSR) and at least \(2^{2^n - (l - n) - 1} /2^{2^n - l - 1}\) shortest n-stage nonlinear feedback shift registers (nNLFSR) which can output a given nonperiodic/periodic sequence with length l. Besides, we propose two novel cycles joining algorithms for the construction of full-length nNLFSR. Finally, two algorithms are presented to construct \(2^{2^{n - 2} - 1}\) different full-length nNLFSRs, respectively.