臺灣博碩士論文加值系統

混沌理論已經在密碼學領域中被廣泛應用，近來很多應用混沌理論的串流加密器也相繼被提出。本論文中，我們提出了基於混沌理論的新型複合式金鑰流產生器。我們使用一維混沌系統來減少系統運算的負載，此外，為了增加輸出金鑰流的亂度與線性複雜度，我們融合不同的一維混沌系統來建構此複合式金鑰流產生器。首先，我們使用線性組合元件Exclusive OR元件來結合不同之混沌系統；再來，我們利用Dawson’s Summation Generator (DSG) 和交換式架構當作其非線性組合元件來結合不同的混沌映射。接著我們分析所輸出之金鑰流的線性複雜度、進行亂度測試，並利用已知的攻擊方法驗證所提出的架構之安全性。我們提出之複合式金鑰流產生器在亂度測試部分，經FIPS PUB 140-1測試有100%的通過率，在NIST SP800-22的亂度測試中，依線性組合、非線性DSG組合以及非線性交換式架構分別有至少86%、96%和97%的通過率。因此，我們可以發現，使用非線性交換式架構的組合擁有更好的亂度特性。

In recent years, chaotic theorem has been applied in cryptography, and many stream ciphers based on chaos were proposed. In this thesis, we propose the new hybrid keystream generators based on chaos. We use the one-dimensional chaotic maps to reduce the operation load. In addition, to increase the randomness and the linear complexity of output sequence, we merge different one-dimensional chaotic system to build the structure of the hybrid keystream generators. First we apply the linear Exclusive OR as the combining element. Besides, we exploit the Dawson’s Summation Generator (DSG), and switching structure as a nonlinear combining function to merge different chaotic maps. We analyze the proposed keystream generator against some known attacks, measure their linear complexity, and present some experimental results of statistical random number tests for the output keystream. For the statistical test of FIPS PUB 140-1, all the pass rates of the proposed keystream generator are 100%. For the pass rates of statistical test of NIST SP800-22, the proposed keystream generators with linear combination, DSG, and switching structure are at least about 86%, 96%, and 97%, respectively. Therefore, we can find that the randomness of the combination with switching structure are better than the combination with linear operation and DSG nonlinear systems.

摘要 i
Abstract iii
Contents iv
List of Figures vi
List of Tables viii
Chapter 1 Introduction 1
Chapter 2 Background Knowledge 3
2.1 Overview of Cryptography and Network Security 3
2.2 Stream Cipher and Block Cipher 4
2.3 Introduction of Chaos Theory 5
2.3.1 Logistic Map 6
2.3.2 Tent Map 7
2.3.3 Sine Square Map 8
2.4 Feedback with Carry Shift Register 9
2.4.1 Galois Architecture of FCSR 9
2.5 The Dawson’s Summation Generator 10
2.5.1 The Dawson’s Summation Generator 10
Chapter 3 The Related Stream Cipher based on Chaos 12
3.1 Binary Numbers Generation Based on Chaotic Map 12
3.2 Chaotic Encryption Algorithm Based on Stream Cipher by Kanso 14
3.3 Chaotic Encryption Algorithm Based on Stream Cipher by Hu 15
3.4 Chaotic Stream Cipher Based on Symbolic Dynamic Description and Synchronization 17
3.5 Pseudo-random Number Generator Based on Mixing of Three Chaotic Maps 19
Chapter 4 The Proposed Keystream Generator Based on Hybrid Chaos 21
4.1 The Hybrid Keystream Generator Based on Chaos with Linear Combination 21
4.1.1 The Linear Combination of Logistic Map and FCSR 22
4.1.2 The Linear Combination of Tent Map and FCSR 23
4.1.3 The Linear Combination of Sine Map and FCSR 24
4.1.4 The Linear Combination of logistic Map and Tent Map 24
4.1.5 The Linear Combination of logistic Map and Sine Map 25
4.1.6 The Linear Combination of Tent Map and Sine Map 25
4.2 The Keystream Generator Based on Hybrid Chaos with DSG 26
4.2.1 The Combination of Logistic Map and Tent Map Using DSG 26
4.2.2 The Combination of Logistic Map and Sine Map Using DSG 26
4.2.3 The Combination of Logistic Map and Sine Map Using DSG 27
4.3 The Keystream Generator Based on Switching Chaos 27
4.3.1 The Switching Chaos Controlled by Logistic Map 28
4.3.2 The Switching Chaos Controlled by Tent Map 28
4.3.3 The Switching Chaos Controlled by Sine Map 29
Chapter 5 Security Analysis and Experimental Results 30
5.1 The Linear Complexity of the Proposed Keystream Generator 30
5.2 Attack Analysis 33
5.2.1 Brute-Force Attack 33
5.2.2 Chosen Ciphertext Attack 33
5.2.3 Resynchronization attack 34
5.3 Statistical Random Number Tests 37
5.3.1 Introduction to FIPS PUB 140-1 37
5.3.2 Random Test Results under FIPS PUB 140-1 39
5.3.3 NIST SP800-22 Description 43
5.3.4 Random Test Result under SP800-22 45
Chapter 6 Conclusions 53
References 54

[1]N. W. Abderrahim, F. Z. Benmansour, O. Seddiki, “A Chaotic Stream Cipher Based on Symbolic Dynamic Description and Synchronization,” Science Business Media Dordrecht, April 2014.
[2]G. Alvarez, S. Li, “Some Basic Cryptographic Requirements for Chaos-based Cryptosystems,” International Journal of Bifurcation and Chaos, 2006.
[3]S. Anand and Gurumurthi V. Ramanan. “Periodicity, Complementarity and Complexity of 2-adic FCSR Combiner Generators,” ASIACCS ’06, March 21–24, Taipei, Taiwan, 2006.
[4]François Arnault, Thierry P. Berger, and Marine Minier, “On the Security of FCSR-based Pseudorandom Generators,” ECRYPT Network of Excellence – SASC Workshop, 2007.
[5]Alex Biryukov, “Resynchronization attack,” Encyclopedia of Cryptography and Security, pp. 1042–1043, 2011.
[6]Chen, Li Zhang, Yifang Weng, “A Data Encryption Algorithm based on Dual Chaotic System,” International Conference on Computer Application and System Modeling, pp. 431–435, Dec. 2010.
[7]E. Dawson, “Cryptanalysis of Summation Generator,” Advances in Cryptology-AUSCRYPT’92, Lecture Notes in Computer Science, Springer, Berlin, pp. 209–215, 1993.
[8]Y. Feng J. Li and X. Yang, “Discrete Chaotic Based 3D Image Encryption Scheme,” Sympos on Photonics and Optoelectronics, pp. 1–4, Aug. 2009.
[9]M. François, T. Grosgesa D, and Barchiesia R. Errac. “Pseudo-random Number generator Based on Mixing of Three Chaotic Maps,” Volume 19, Issue 4, pp. 887–895 April 2014.
[10]J. Fridrich, “Symmetric Ciphers Based on Two-Dimensional Chaotic Maps,” Int. J. Bifurcat Chaos, volume 8, pp. 1259–1284, 1998.
[11]Mark Goresky, Andrew Klapper, “Fibonacci and Galois Representations of Feedback with Carry Shift Registers,” Information Theory, IEEE Transactions, December 4, 2004.
[12]HanPing Hu, LingFeng Liu, NaiDa Ding, “Pseudorandom Sequence Generator Based on the Chen Chaotic System,” Computer Physics Communications, Volume 184, Issue 3, pp. 765–768, March 2013.
[13]Hu, H., Wu, X., Zhang, B, “Parameter Estimation Only from the Symbolic Sequences Generated by Chaos System,” Chaos Solitons, Fractals 22, pp 359–366, 2004.
[14]Ali Kanso, Nejib Smaoui, “Logistic Chaotic Maps for Binary Numbers Generations,” Chaos Solitons & Fractals, Volume 40, pp. 2557–2568, June 2009.
[15]Ali Kanso, “Self-shrinking chaotic stream ciphers,” Communications in Nonlinear Science and Numerical Simulation, Volume 16, Issue 2, pp. 822–836, February 2011.
[16]Klapper A., Goresky M., “2-Adic shift registers In： Fast Software Encryption,” Cambridge SecurityWorkshop Lecture Notes in Computer Science, volume 809, pp. 174–178. Springer, New York, 1993.
[17]C. S. Laih, L. Harn and C. C. Chang, “Contemporary Cryptography and Its Applications,” Flag Publishing Co., LTD, Taipei, Taiwan, R.O.C., 2004.
[18]Lian, S., Sun, J., Wang, Z. “A Block Cipher Based on a Suitable Use of the Chaotic Standard Map,” Chaos Solitons and Fractals. Elsevier, Berlin, 2005.
[19]Meng-Hui Lim, Bok-Min Goi, SangGon Lee, and HoonJae Lee, “Hierarchical Dawson’s Summation Generator,” International Conference on Convergence Information Technology, 2007
[20]E. N. Lorenz, “Deterministic Non-periodic Flow,” J. of Atmos. Sci., volume 20, pp. 130–141, 1963.
[21]Yongyi Mao,Xiang Chen, “An Encryption Algorithm of Chaos Based on Sine Square Mapping,” Computational Intelligence and Design (ISCID), Fourth International Symposium, volume 1, pp. 131–134, 2011.
[22]G. L. Mayhew, “A Low Cost, High Speed Encryption System and Method,” Proc. of the 1994 IEEE Sysmposium on Security and Privacy, May. 1994, pp. 147–154.
[23]Hiroyuki Nagashima and Yoshikazu Baba, “Intoduction to Chaos, Physics and Mathematics of Chaotic Phenomena,” CRC Press, January, 1998.
[24]L. M. Pecora and T.L. Carroll, “Synchronized Chaotic Signals and Systems,” Proceeding of IEEE ICASSP, pp. 137–140, 1992.
[25]Pierre Collett, Jean-Pierre, Eckmann, “Iterated Maps on the Interval as Dynamical Systems,” Birkhauser, 1980.
[26]Rivest, Ronald L. “Cryptology,” In J. Van Leeuwen. Handbook of Theoretical Computer Science, Volume 1, 1990.
[27]A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray and S. Vo, “Special Publication 800-22 Revision 1: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications”, National Institute of Standards and Technology, Aug. 2008.
[28]Wang, K., Pei, W., Hou, X., Shen, Y., He, Z, “Symbolic Dynamics Approach to Parameter Estimation Without Initial Value,” Physics Letters A, Volume 374, Issue 1, pp. 44–49, 2009.
[29]K. W. Wong, “A Fast Chaotic Cryptographic Scheme With Dynamic Look-up Table,” Physics Letters A, Volume 298, Issue 4, pp. 238–242, 2002.
[30]Yu Zheng, Xiaohu Tang, Dake He, and Lixing Xu, “Investigation on Pseudorandom Properties of FCSR Sequence,” International Conference of Communications, Circuits and Systems, China, 2005.
[31]National Institute of Standards and Technology, “Security Requirements for Cryptographic Modules,” Federal Information Processing Standards Publication 140-1, Jan. 1994.
[32]National Institute of Standard Technology, “Announcing the Advanced Encryption Standard (AES) ,” Federal Information Processing Standards Publication 197, Nov. 2001.