细胞自动机理论及其在密码中的应用
|
摘要
本文主要对细胞自动机的基本理论、利用细胞自动机构造密码的各种方式及其安全性进行了研究。文章首先介绍了序列密码及细胞自动机的相关知识；然后对一类简单的加法细胞自动机的周期性、拓扑结构以及各状态之间的相互关系进行了研究；对利用细胞自动机构造序列密码和分组密码的方式及其安全性进行了研究；最后实现了一类简单的CA和LFSR，分析了细胞自动机在硬件实现上的优点。
本文得到的主要成果如下：
1．深入地讨论了一类加法细胞自动机的代数性质，如：状态特征、周期性、拓扑结构等。
2．对一类简单的加法细胞自动机，给出了利用其长度计算其最大周期的方法。
3．研究了利用细胞自动机构造序列密码的方式，并对它们进行了安全性分析。指出了如何利用PCA技术构造序列密码。
4．根据有些细胞自动机的所有状态可以构成一个循环群这一特点，指出了利用细胞自动机构造分组密码的方式。
5．实现了一类CA和LFSR，结果表明：细胞自动机算法与LFSR比较，其优势在于时延小，速度快，实现方便。
The basic theory of cellular automata, the ways how algorithms are designed based on cellular automata and the security of the algorithms have been discussed in this thesis. At first, some basic knowledge in stream cipher and cellular automata has been introduced; second, properties of one kind of cellular automata such as its periodicity, its topologies and the connection between its states have been deeply researched; third, the algorithms base on cellular automata and their security have been discussed; finally, I have implemented one simple cellular automata and one simple linear feedback shift register, and have analyzed the advantage and the disadvantage of cellular automata.
The main results of this thesis are as follows:
1. One kind of cellular automata has been researched. Its algebraic properties such as characters of states, periodicity, and topology have been deeply discussed.
2. To the simple additive cellular automata, a method to compute its maximal cycle lengths has been presented.
3. Many methods to designed stream cipher based on cellular automata and their security have been studied. How to designed stream cipher based on PCA has been studied.
4. According to the property that all states of a certain cellular automata can build a permutation group, we can design block cipher based on this property.
5. One simple cellular automata and one simple linear feedback shift register have been implemented. The result has shown that: CA compared with LFSR, its advantages is that it need little time, it is faster, and it is easy to implement.
本文得到的主要成果如下：
1．深入地讨论了一类加法细胞自动机的代数性质，如：状态特征、周期性、拓扑结构等。
2．对一类简单的加法细胞自动机，给出了利用其长度计算其最大周期的方法。
3．研究了利用细胞自动机构造序列密码的方式，并对它们进行了安全性分析。指出了如何利用PCA技术构造序列密码。
4．根据有些细胞自动机的所有状态可以构成一个循环群这一特点，指出了利用细胞自动机构造分组密码的方式。
5．实现了一类CA和LFSR，结果表明：细胞自动机算法与LFSR比较，其优势在于时延小，速度快，实现方便。
The basic theory of cellular automata, the ways how algorithms are designed based on cellular automata and the security of the algorithms have been discussed in this thesis. At first, some basic knowledge in stream cipher and cellular automata has been introduced; second, properties of one kind of cellular automata such as its periodicity, its topologies and the connection between its states have been deeply researched; third, the algorithms base on cellular automata and their security have been discussed; finally, I have implemented one simple cellular automata and one simple linear feedback shift register, and have analyzed the advantage and the disadvantage of cellular automata.
The main results of this thesis are as follows:
1. One kind of cellular automata has been researched. Its algebraic properties such as characters of states, periodicity, and topology have been deeply discussed.
2. To the simple additive cellular automata, a method to compute its maximal cycle lengths has been presented.
3. Many methods to designed stream cipher based on cellular automata and their security have been studied. How to designed stream cipher based on PCA has been studied.
4. According to the property that all states of a certain cellular automata can build a permutation group, we can design block cipher based on this property.
5. One simple cellular automata and one simple linear feedback shift register have been implemented. The result has shown that: CA compared with LFSR, its advantages is that it need little time, it is faster, and it is easy to implement.
引文
1 S. Wolfram, Random sequence generation by cellular automata, Advances in Applied Mathematics, vol.7, pp127-169, 1986.
2 S. Wolfram, Cryptography with Cellular Automata, Advances in Cryptology-Crypto'85, pp429-432, Springer-Verlag, 1986.
3 Blackbum, S. Murephy, and K. G.Paterson, Comments on "Theory and Application of Cellular Automata in Cryptography", IEEE Trans. Computers, vol.46, no.5 pp637-638, May 1997.
4 M. Tomassini, M. Sipper, and M. Perrenoud, On the Generation of High-Quality Random Numbers by Two-Dimensional Cellular Automata, IEEE Trans. Computers, vol.49, no.10 pp1146-1151, Oct. 2000.
5 H. Beker and F. Piper, Cipher Systems The Protection of Communications, Northwood Books, London, 1982.
6 Bruce Schneier, Applied Cryptography Second Edition: protocols, algorithms, and source code, C. John Wiley & Sons Inc., 1996.
7 S. Wolfram, Origins of Randomness in Physical System, Physical Review Letters, Vol.55, No.5, pp449-452, July 1985.
8 D. Roy Chowdhury, E Subbaro, Characterization of Two-Dimensional Cellular Automata Using Matrix Algebra, Information Sciences 71,289-314 (1993)
9 Kevin Cattell, Shujian Zhang, Micaela Serra, Jon C. Muzio, 2-by-n Hybrid Cellular Automata with Regular Configuration: Theory and Application, IEEE Trans. Compu., Vol.48, No.3, pp.285-295, March 1999
10 Werner Pries, Adonios Thanailakis, and Howard C. Card, Group Properties of Cellular Automata and VLSI Application, IEEE Trans. Computers, Vol. C-35, No.12, pp.1013-1024, 1986
11 S. Wolfram, Statistical Mechanics of Cellular Automata, Rev. Mod. Phys., Vol.55, No.3, pp.601-644, 1983
12 S. Zhang, D. M. Miller, and J. C. Muzio, The Determination of Minimum Cost One-Dimensional Linear Cellular Automata with Maximum Length Cycles, Electronics Letters, Vol.27, No.18, 1991
13 FIPS PUB 140-2 Security Requirements for Cryptographic Modules, 1999
14 A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC press, 1996
15 赖溪松、韩亮、张真诚著，张玉清、肖国镇改编，《计算机密码学及其应用》，国防工业出版社，2001年7月(ISBN7-118-02514-3／TP.595)。
16 Peter D. Hortensius, Robert D. Mcleod, Howard C. Card, Cellular automata-based signature analysis for built-in self-test, IEEE Trans. Compu., Vol. C-39, No. 10, pp. 1273-1283, 1990
17 S. Wolfram, Theory and Application of Cellular Automata, World Scientific, Singapore, 1986
18 K. Gulik II, L.P. Hurd, and S. Yu, Computation theoretic aspects of cellular automata, Physica D, Vol.45, pp.357-378, 1990
19 James L. Massey, Shift-Register Synthesis and BCH Decoding, IEEE Transactions on Information Theory, Vol.IT-15, No.1, pp.122-127, January 1969
20 杨波，《网络安全理论与应用》，电子工业出版社，2001年，(ISBN7-5053-7008-1)
21 王新梅、肖国镇，《纠错码-原理与方法》，西安电子科技大学出版社，1991年12月(ISBN7-5606-0163-4／TN．0059)
22 Vishwani D. Agrawal, Charles R. Kime, and Kewal K. Saluja, A Tutorial on Built-In Self-Test, IEEE Design & Test of Computers, Vol.10, No.3, 1993
23 Ph. Tsalides, T.A. York, A. Thanailakis, Pseudorandom Number Generators for VLSI Systems Based on Linear Cellular Automata, IEE Proceedings E, Vol. 138, No. 4, pp.241-249, July 1991
24 S. Wolfram, Computation Theory of Cellular Automata, Communications in Mathematical Physics, 96 (November 1984), 15-57
25 Thomas W. Williams, Wilfried Daehn, Matthias Gruetzner, and Cord W. Starke, Bound and analysis of aliasing errors in linear feedback shift registers, IEEE Trans. CAD, Vol.7, No. 1, 1988
26 Peter C. Maxwell, Comparative Analysis of Different Implementations of Multiple-Input Signature Analyzers, IEEE Trans. Computers, Vol.37, No. 11, 1988
27 Maurizio Damiani, Piero Olivo, etc., Alliasing in Signature Analysis Testing with Multiple Input Shift Register, IEEE Trans. CAD, Vol.9, No. 12, 1990
28 John P. Robinson, Aliasing Probabilities for Feedback Signature Compression of Test Data, IEEE Trans. Computers, Vol.40, No.7, 1991
29 Micaela Serra, Terry Slater, Jon C. Muzio, and D. Michael Miller, The Analysis of One-Dimensional Linear Cellular Automata and Their Aliasing Properties, IEEE Trans. CAD, Vol.9, No.7, 1990
30 Farmer D., Toffoli T., and Stephen Wolfram, Cellular Automata, Physica D Vol.10, No.1, 1984
31 Peter D. Hortensius, Robert D. Mcleod, Werner Pries, D. Michael Miller, and Howard C. Card, Cellular Automata-Based Pseudorandom Number Generator for Built-In Self-Test, IEEE Trans. Computer Aided Design, Vol.8, No.8 August 1989
32 N. H. Packard and S. Wolfram, Journal of Statistical Physics, 38 (March 1985) 901-946
33 Arif Merchant,Benjamin Melamed, "Analysis of a Control Mechanism for a Variable Speed Processor", IEEE Transactions on Computers VOL 45,No.7, July 1996.
34 Dipanwita Roy Chowdhury, Saugata Basu, Indranil Sen Gupta,and Parimal Pal Chaudhuri,Design of CAECC-Cellular Automata Based Error Correcting Code, IEEE Transctions on Computers, Vol.43, No.6, June 1994.
35 Supratik Chakraborty, Dipanwita Roy Chowdhury, and Parimal Pal Chaudhuri, "Theory and Application of Nongroup Cellular Automata for Synthesis of Easily Testable Finite State Machines, IEEE Transactions on Computers, Vol.45, No.7, July 1996.
36 R D. Hortensius, R. D. Mcleod, and H. C. Card, Parallel Random Number Generation for VLSI Systems Using Cellular Automata, IEEE Transactions on Computers, Vol.38, No.10, Octorber 1989.
37 S. Wolfram, Complex Systems Theory, http://www.stephenwolfram.com/publications/articles/ca/.
38 J. L. Massey, R. A. Rueppel, "Linear Ciphers and Random Sequence Generators with Multiple Clocks", presented at Eurocrypt 84, Paris, France, April 9-11,1984.
39 Supratik Chakraborty, Dipanwita Roy Chowdhury, and Parimal Pal Chaudhuri, "Theory and Application of Nongroup Cellular Automata for Synthesis of Easily Testable Finite State Machines, IEEE Transactions on Computers, Vol.45, No.7, July 1996.
40 Kevin Cattell and Jon C.Muzio, Analysis of One-Dimensional Linear Hybrid Cellular Automata over GF(q), IEEE Transcations on Computers, Vol.45, No.7 July 1996.
41 M. Delorme, An introduction to cellular automata, 《Cellular Automata——A Parallel Model》,Kluwer Academic Publishers, ISBN 0-7923-5493-1.
42 O. Ibarra, Computational complexity of cellular automata: an overview, 《Cellular Automata A Parallel Model》, Kluwer Academic Publishers, ISBN 0-7923-5493-1.
43 王培春，李毅，朱甫臣，利用细胞自动机构造密钥流发生器，《西电学报》，V01．29，No．5，2002．
44 张文政，细胞自动机在序列密码中的应用，《中国计算机学会信息保密专业委员会论文集》，Vol．11．
45 张传武，彭启琮，李玉柏，细胞自动机伪随机序列的线性复杂度分析，《电子测量与仪器学报》，已录用．
46 王育民，何大可，《保密学——基础与应用》，西安电子科技大学出版社，ISBN 7-5606-0142-1／TN．0051．
47 王育民，刘建伟，《通信网的安全——理论与技术》，西安电子科技大学出版社，ISBN 7-5606-0711-X／TN 0129．
48 Zhang Chuanwu, Peng Qicong, Li Yubo, Encryption Based on Reversible Cellular Automata, 2002 International Conference on Communications Circuits and Systems and West Sino Expositions Proceedings, Volume Ⅱ: Signal Processing, Circuits and Systems, pp.1223-1226, Tibet Hotel, Chengdu, China, June 29, July 1, 2002.
49 张传武，彭启琮，朱甫臣，细胞自动机置换群加密技术研究，《计算机科学》，己录用．
50 Rainer A，Rueppel著，《通信保密》杂志社译，《序列密码的分析与设计》，1988年2月．
51 丁存生，肖国镇，《流密码学及其应用》，国防工业出版社，ISBN 7-118-01258-0／TN．198．
52 万哲先，《代数与编码》，科学出版社，13031．356．
53 柯召，孙琦，《数论讲义》，高等教育出版社，ISBN 7-04-008831-2．
2 S. Wolfram, Cryptography with Cellular Automata, Advances in Cryptology-Crypto'85, pp429-432, Springer-Verlag, 1986.
3 Blackbum, S. Murephy, and K. G.Paterson, Comments on "Theory and Application of Cellular Automata in Cryptography", IEEE Trans. Computers, vol.46, no.5 pp637-638, May 1997.
4 M. Tomassini, M. Sipper, and M. Perrenoud, On the Generation of High-Quality Random Numbers by Two-Dimensional Cellular Automata, IEEE Trans. Computers, vol.49, no.10 pp1146-1151, Oct. 2000.
5 H. Beker and F. Piper, Cipher Systems The Protection of Communications, Northwood Books, London, 1982.
6 Bruce Schneier, Applied Cryptography Second Edition: protocols, algorithms, and source code, C. John Wiley & Sons Inc., 1996.
7 S. Wolfram, Origins of Randomness in Physical System, Physical Review Letters, Vol.55, No.5, pp449-452, July 1985.
8 D. Roy Chowdhury, E Subbaro, Characterization of Two-Dimensional Cellular Automata Using Matrix Algebra, Information Sciences 71,289-314 (1993)
9 Kevin Cattell, Shujian Zhang, Micaela Serra, Jon C. Muzio, 2-by-n Hybrid Cellular Automata with Regular Configuration: Theory and Application, IEEE Trans. Compu., Vol.48, No.3, pp.285-295, March 1999
10 Werner Pries, Adonios Thanailakis, and Howard C. Card, Group Properties of Cellular Automata and VLSI Application, IEEE Trans. Computers, Vol. C-35, No.12, pp.1013-1024, 1986
11 S. Wolfram, Statistical Mechanics of Cellular Automata, Rev. Mod. Phys., Vol.55, No.3, pp.601-644, 1983
12 S. Zhang, D. M. Miller, and J. C. Muzio, The Determination of Minimum Cost One-Dimensional Linear Cellular Automata with Maximum Length Cycles, Electronics Letters, Vol.27, No.18, 1991
13 FIPS PUB 140-2 Security Requirements for Cryptographic Modules, 1999
14 A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC press, 1996
15 赖溪松、韩亮、张真诚著，张玉清、肖国镇改编，《计算机密码学及其应用》，国防工业出版社，2001年7月(ISBN7-118-02514-3／TP.595)。
16 Peter D. Hortensius, Robert D. Mcleod, Howard C. Card, Cellular automata-based signature analysis for built-in self-test, IEEE Trans. Compu., Vol. C-39, No. 10, pp. 1273-1283, 1990
17 S. Wolfram, Theory and Application of Cellular Automata, World Scientific, Singapore, 1986
18 K. Gulik II, L.P. Hurd, and S. Yu, Computation theoretic aspects of cellular automata, Physica D, Vol.45, pp.357-378, 1990
19 James L. Massey, Shift-Register Synthesis and BCH Decoding, IEEE Transactions on Information Theory, Vol.IT-15, No.1, pp.122-127, January 1969
20 杨波，《网络安全理论与应用》，电子工业出版社，2001年，(ISBN7-5053-7008-1)
21 王新梅、肖国镇，《纠错码-原理与方法》，西安电子科技大学出版社，1991年12月(ISBN7-5606-0163-4／TN．0059)
22 Vishwani D. Agrawal, Charles R. Kime, and Kewal K. Saluja, A Tutorial on Built-In Self-Test, IEEE Design & Test of Computers, Vol.10, No.3, 1993
23 Ph. Tsalides, T.A. York, A. Thanailakis, Pseudorandom Number Generators for VLSI Systems Based on Linear Cellular Automata, IEE Proceedings E, Vol. 138, No. 4, pp.241-249, July 1991
24 S. Wolfram, Computation Theory of Cellular Automata, Communications in Mathematical Physics, 96 (November 1984), 15-57
25 Thomas W. Williams, Wilfried Daehn, Matthias Gruetzner, and Cord W. Starke, Bound and analysis of aliasing errors in linear feedback shift registers, IEEE Trans. CAD, Vol.7, No. 1, 1988
26 Peter C. Maxwell, Comparative Analysis of Different Implementations of Multiple-Input Signature Analyzers, IEEE Trans. Computers, Vol.37, No. 11, 1988
27 Maurizio Damiani, Piero Olivo, etc., Alliasing in Signature Analysis Testing with Multiple Input Shift Register, IEEE Trans. CAD, Vol.9, No. 12, 1990
28 John P. Robinson, Aliasing Probabilities for Feedback Signature Compression of Test Data, IEEE Trans. Computers, Vol.40, No.7, 1991
29 Micaela Serra, Terry Slater, Jon C. Muzio, and D. Michael Miller, The Analysis of One-Dimensional Linear Cellular Automata and Their Aliasing Properties, IEEE Trans. CAD, Vol.9, No.7, 1990
30 Farmer D., Toffoli T., and Stephen Wolfram, Cellular Automata, Physica D Vol.10, No.1, 1984
31 Peter D. Hortensius, Robert D. Mcleod, Werner Pries, D. Michael Miller, and Howard C. Card, Cellular Automata-Based Pseudorandom Number Generator for Built-In Self-Test, IEEE Trans. Computer Aided Design, Vol.8, No.8 August 1989
32 N. H. Packard and S. Wolfram, Journal of Statistical Physics, 38 (March 1985) 901-946
33 Arif Merchant,Benjamin Melamed, "Analysis of a Control Mechanism for a Variable Speed Processor", IEEE Transactions on Computers VOL 45,No.7, July 1996.
34 Dipanwita Roy Chowdhury, Saugata Basu, Indranil Sen Gupta,and Parimal Pal Chaudhuri,Design of CAECC-Cellular Automata Based Error Correcting Code, IEEE Transctions on Computers, Vol.43, No.6, June 1994.
35 Supratik Chakraborty, Dipanwita Roy Chowdhury, and Parimal Pal Chaudhuri, "Theory and Application of Nongroup Cellular Automata for Synthesis of Easily Testable Finite State Machines, IEEE Transactions on Computers, Vol.45, No.7, July 1996.
36 R D. Hortensius, R. D. Mcleod, and H. C. Card, Parallel Random Number Generation for VLSI Systems Using Cellular Automata, IEEE Transactions on Computers, Vol.38, No.10, Octorber 1989.
37 S. Wolfram, Complex Systems Theory, http://www.stephenwolfram.com/publications/articles/ca/.
38 J. L. Massey, R. A. Rueppel, "Linear Ciphers and Random Sequence Generators with Multiple Clocks", presented at Eurocrypt 84, Paris, France, April 9-11,1984.
39 Supratik Chakraborty, Dipanwita Roy Chowdhury, and Parimal Pal Chaudhuri, "Theory and Application of Nongroup Cellular Automata for Synthesis of Easily Testable Finite State Machines, IEEE Transactions on Computers, Vol.45, No.7, July 1996.
40 Kevin Cattell and Jon C.Muzio, Analysis of One-Dimensional Linear Hybrid Cellular Automata over GF(q), IEEE Transcations on Computers, Vol.45, No.7 July 1996.
41 M. Delorme, An introduction to cellular automata, 《Cellular Automata——A Parallel Model》,Kluwer Academic Publishers, ISBN 0-7923-5493-1.
42 O. Ibarra, Computational complexity of cellular automata: an overview, 《Cellular Automata A Parallel Model》, Kluwer Academic Publishers, ISBN 0-7923-5493-1.
43 王培春，李毅，朱甫臣，利用细胞自动机构造密钥流发生器，《西电学报》，V01．29，No．5，2002．
44 张文政，细胞自动机在序列密码中的应用，《中国计算机学会信息保密专业委员会论文集》，Vol．11．
45 张传武，彭启琮，李玉柏，细胞自动机伪随机序列的线性复杂度分析，《电子测量与仪器学报》，已录用．
46 王育民，何大可，《保密学——基础与应用》，西安电子科技大学出版社，ISBN 7-5606-0142-1／TN．0051．
47 王育民，刘建伟，《通信网的安全——理论与技术》，西安电子科技大学出版社，ISBN 7-5606-0711-X／TN 0129．
48 Zhang Chuanwu, Peng Qicong, Li Yubo, Encryption Based on Reversible Cellular Automata, 2002 International Conference on Communications Circuits and Systems and West Sino Expositions Proceedings, Volume Ⅱ: Signal Processing, Circuits and Systems, pp.1223-1226, Tibet Hotel, Chengdu, China, June 29, July 1, 2002.
49 张传武，彭启琮，朱甫臣，细胞自动机置换群加密技术研究，《计算机科学》，己录用．
50 Rainer A，Rueppel著，《通信保密》杂志社译，《序列密码的分析与设计》，1988年2月．
51 丁存生，肖国镇，《流密码学及其应用》，国防工业出版社，ISBN 7-118-01258-0／TN．198．
52 万哲先，《代数与编码》，科学出版社，13031．356．
53 柯召，孙琦，《数论讲义》，高等教育出版社，ISBN 7-04-008831-2．