An Efficient PRBG Based on Chaotic Map and Engel Continued Fractions

Atef Masmoudi, William Puech, Mohamed Salim Bouhlel
DOI: 10.4236/jsea.2010.312133                

Abstract

In recent years, a variety of chaos-based cryptosystems have been proposed. Some of these systems are used in designing a pseudo random bit generator (PRBG) for stream cipher applications. Most of the chaotic systems used in cryptography have good chaotic properties like ergodicity, sensitivity to initial values and sensitivity to control parameters. However, some of them are not very suitable for use in cryptography because of their non-uniform density function, and their relatively small key space. To be used in cryptography, a PRBG may need to meet stronger requirements than for other applications. In particular, various statistical tests can be applied to the outputs of such generators to conclude whether the generator produces a truly random sequence or not. In this paper, we propose a PRBG based on the use of the standard chaotic map with large key space and the Engle Continued Fractions (ECF) map. The outputs of the standard map are used as the inputs of ECF-map. The chaotic nature of the standard map and the good statistical properties of the ECF map motivate us to design a new PRBG for stream cipher applications. The numerical simulation analysis indicates that our PRBG produces bit sequences possessing excellent statistical and cryptographic properties.

Keywords

Cryptography, Continued Fraction, Statistical Tests, PRBG, Chaotic Map

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Li and X. Mou, “Improving Security of a Chaotic Encryption Approach,” Physics Letters A, Vol. 290, No. 3-4, 2001, pp. 127-133. doi:10.1016/S0375-9601(01)00612-0
[2]	X. G. Wu, H. P. Hu and B. L. Zhang, “Analyzing and Improving a Chaotic Encryption Method,” Chaos, Solitons and Fractals, Vol. 22, No. 2, 2004, pp. 367-373. doi:10.1016/j.chaos.2004.02.009
[3]	T. Yang, “A Survey of Chaotic Secure Communication Systems,” Journal of Computational Cognition, Vol. 2, No. 2, 2004, pp. 81-130.
[4]	T. Yang, L. B. Yang and C. M. Yang, “Cryptanalyzing Chaotic Secure Communications Using Return Maps,” Physics Letters, Section A: General, Atomic and Solid State Physics, Vol. 245, No. 6, 1998, pp. 495-510.
[5]	H. Zhou and X. T. Ling, “Problems With the Chaotic Inverse System Encryption Approach,” IEEE Circuits and Systems, Vol. 44, No. 3, 1997, pp. 268-271. doi:10.1109/81.557386
[6]	P. Li, Z. Li, W. A. Halang and G. Chen, “A Stream Cipher Based on a Spatiotemporal Chaotic System,” Chaos, Solitons & Fractals, Vol. 32, No. 7, 2007, pp. 1867-1876. doi:10.1016/j.chaos.2005.12.021
[7]	K. M. Short, “Signal Extraction from Chaotic Communications”. International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, Vol. 7, No. 7, 1997, pp. 1579-1597. doi:10.1142/S0218127497001230
[8]	L. Zhang, X. Liao and X. Wang, “An Image Encryption Approach Based on Chaotic Maps,” Chaos, Solitons and Fractals, Vol. 24, No.3, 2005, pp. 759-765. doi:10.1016/ j.chaos.2004.09.035
[9]	S. J. Li, X. Q. Mou and Y. L. Cai, “Pseudo-Random Bit generator Based on Couple Chaotic Systems and its Application in Stream-Ciphers Cryptography,” Progress in Cryptology-INDOCRYPT, Lecture Notes in Computer Science, Vol. 2247, 2001, pp. 316-329.
[10]	V. Patidar, N. K. Parekk and K. K. Sud, “A New Substitution-Diffusion Based Image Cipher Using Chaotic Standard and Logistic Maps,” Communications in Nonlinear Science and Numerical Simulation, Vol. 14, No. 7, 2009, pp. 3056-3075. doi:10.1016/j.cnsns.2008.11.005
[11]	V. Patidar and K. K. Sud, “A Novel Pseudo Random Bit Generator Based on Chaotic Standard Map and its Testing,” Electronic Journal of Theoretical Physics, Vol. 6, No. 20, 2009, pp. 327-344.
[12]	X. Y. Wanga and Q. Yu, “A Block Encryption Algorithm Based on Dynamic Sequences of Multiple Chaotic Systems,” Communications in Nonlinear Science and Numerical Simulation, Vol. 14, No. 2, 2009, pp. 574-581. doi:10.1016/j.cnsns.2007.10.011
[13]	G. Chen, Y. Mao and C. K. Chui, “A Symmetric Image Encryption Scheme Based on 3D Chaotic Cat Maps,” Chaos, Solitons and Fractals, Vol. 21, No. 3, 2004, pp. 749-761. doi:10.1016/j.chaos.2003.12.022
[14]	P. Garcia, A. Parravano, M. G. Cosenza, J. Jiménez and A. Marcano, “Coupled Map Networks as Communication Schemes,” Physical Review E, Vol. 65, No. 4, 2002, pp. 045201.1-045201.4.
[15]	H. Li and J. Zhang, “A Secure and Efficient Entropy Coding Based on Arithmetic Coding,” Communications in Nonlinear Science and Numerical Simulation, Vol. 14 No. 12, 2009, pp. 4304-4318. doi:10.1016/j.cnsns.2009.03.003
[16]	K. Fallahi, R. Raoufi and H. Khoshbin, “An Application of Chen System for Secure Chaotic Communication Based on Extended Kalman Filter and Multi-Shift Cipher Algorithm,” Communications in Nonlinear Science and Numerical Simulation, Vol. 13, No. 4, 2008, pp. 763-781. doi:10.1016/j.cnsns.2006.07.006
[17]	B. Mi, X. Liao and Y. Chen, “A Novel Chaotic Encryption Scheme Based on Arithmetic Coding,” Chaos, Solitons and Fractals, Vol. 38, No. 5, 2008, pp. 1523-1531, 2008.
[18]	A. Kanso and N. Smaoui, “Logistic Chaotic Maps for Binary Numbers Generations,” Chaos, Solitons and Fractals, Vol. 40, No. 5, 2009, pp. 2557-2568. doi: 10.1016/j.chaos.2007.10.049
[19]	G. Alvarez, F. Montoya, M. Romera and G. Pastor, “Cryptanalysis of a Discrete Chaotic Cryptosystem Using External Key,” Physics Letters A, Vol. 319, No. 3-4, 2003, pp. 334-339. doi:10.1016/j.physleta.2003.10.044
[20]	G. A. Alvarez and L. B. Shujun, “Cryptanalyzing a Nonlinear Chaotic Algorithm (NCA) for Image Encryption,” Communications in Nonlinear Science and Numerical Simulation, Vol. 14, No. 11, 2009, pp. 3743-3749. doi:10.1016/j.cnsns.2009.02.033
[21]	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, “A Statistical Test Suite for Random and Pseudo Random Number Generators for Cryptographic Applications,” National Institute of Standards and Technology Special Publication 800-22, 2001.
[22]	G. Marsaglia, “DIEHARD: A Battery of Tests of Randomness,” 1997. http://stat.fsu.edu/geo/diehard.html.
[23]	L. Lorentzen and H. Waadeland, “Continued Fractions with Applications,” North Holland, Amsterdam, 1992.
[24]	R. B. Seidensticker, “Continued Fractions for High-Speed and High-Accuracy Computer Arithmetic,” Proceedings of the 6th IEEE Symposium on Computer Arithmetic, 1983, pp. 184-193.
[25]	J. Vuillemin, “Exact Real Computer Arithmetic with Continued Fractions,” INRIA Report 760, Le Chesnay, 1987.
[26]	H. S. Wall. “Analytic Theory of Continued Fractions”. Chelsea, 1973.
[27]	Y. Hartono, C. Kraaikamp and F. Schweiger, “Algebraic and Ergodic Properties of a New Continued Fraction Algorithm with Non-Decreasing Partial Quotients,” Journal de théorie des nombres de 9 Bordeaux, Vol. 14, No. 2, 2002, pp. 497-516.
[28]	X. Di, X. Liao and P. Wei, “Analysis and Improvement of a Chaos-Based Image Encryption Algorithm,” Chaos, Solitions and Fractals, Vol. 40, No. 5, 2009, pp. 2191-2199. doi:10.1016/j.chaos.2007.10.009
[29]	W. H. Press. “Numerical Recipes in C: The Art of Scientific Computing,” Cambridge University Press, Cambridge, 1992, pp. 169-173.
[30]	M. Abramowitz and I. Stegun, “Handbook of Mathematical Functions,” Applied Mathematics Series, Vol. 55, 1968, pp. 2286-2293.