Improving Middle Square Method RNG Using Chaotic Map

ABSTRACT

One of the classic approaches in PRNGs is the middle square method in which with a simple mathe-matical model generating pseudorandom numbers in high speed and minimum correlation between output numbers. Despite these unique characteristics, the method contains weaknesses that a broader application of this algo- rithm will face. In this paper is studied middle square method and then a logistic chaotic map is introduced with its specific features and its improved weaknesses via using these characteristics. Finally the NIST tests suite s are presented, in order to detect the specific characteristics expected from truly random sequences.

One of the classic approaches in PRNGs is the middle square method in which with a simple mathe-matical model generating pseudorandom numbers in high speed and minimum correlation between output numbers. Despite these unique characteristics, the method contains weaknesses that a broader application of this algo- rithm will face. In this paper is studied middle square method and then a logistic chaotic map is introduced with its specific features and its improved weaknesses via using these characteristics. Finally the NIST tests suite s are presented, in order to detect the specific characteristics expected from truly random sequences.

Cite this paper

nullH. Rahimov, M. Babaie and H. Hassanabadi, "Improving Middle Square Method RNG Using Chaotic Map,"*Applied Mathematics*, Vol. 2 No. 4, 2011, pp. 482-486. doi: 10.4236/am.2011.24062.

nullH. Rahimov, M. Babaie and H. Hassanabadi, "Improving Middle Square Method RNG Using Chaotic Map,"

References

[1] Y. Hu, X. Liao, K. W. Wong and Q. Zhou, “A True Random Number Generator Based on Mouse Movement and Chaotic Cryptography,” Chaos, Solitons and Fractals, Vol. 40, No. 15, 2009, pp. 2286-2293. doi:10.1016/j.chaos.2007.10.022

[2] P. L. Ecuyer and J. Granger-Piché, “Combined Generators with Components from Different Families,” Mathematics and Computers in Simulation, Vol. 62, No. 3, 2003, pp. 395-404. doi:10.1016/S0378-4754(02)00234-3

[3] M. Orlov, “Optimized Random Number Generation in an Interval,” Information Processing Letters, Vol. 109, No. 13, 2009, pp. 722-725. doi:10.1016/j.ipl.2009.03.008

[4] Q. Zhou, X. Liao, K. W. Wong, Y. Hua and D. Xiao, “True Random Number Generator Based on Mouse Movement and Chaotic Hash Function,” Information Sciences, Vol. 179, No. 19, 2009, pp. 3442-3450. doi:10.1016/j.ins.2009.06.005

[5] K. Nakano, K. Kawakami and K. Shigemoto, “RSA Encryption and Decryption Using the Redundant Number System on the FPGA,” IEEE International Symposium on Parallel & Distributed Processing, Rome, 23-29 May 2009, pp. 1-8.

[6] I. Krykova, “Evaluating of Path-Dependent Securities with Low Discrepancy Methods,” Master of Science Thesis, Worce-Ster Polytechnic Institute, 2003.

[7] T. Stojanovski and L. C. Kocarev, “Chaos-Based Random Number Generators,” IEEE Transactions on Circuits and Systems, Vol. 48, No. 3, 2001, pp. 281-288.

[8] K. H. Tsoi, K. H. Leung and P. H. W. Leong, “High Performance Physical Random Number Generator,” IET Proceeding Computers & Digital Techniques, Vol. 1, No. 4, 2007, pp. 349-352. doi:10.1049/iet-cdt:20050173

[9] M. I. Youssef, M. Zahara, A. E. Emam and M. A. Elghany, “Image Encryption Using Pseudo Random Number and Chaotic Sequence Generators,” Radio Science Conference, New Cairo, 17-19 March 2009, pp. 1-15.

[10] C. Pellicer-Lostao and R. Lopez-Ruiz, “Pseudo-Random Bit Generation Based on 2D Chaotic Maps of Logistic Type and Its Applications in Chaotic Cryptography,” Journal of Computational Science and Its Applications, Vol. 5073, 2008, pp. 784-796.

[11] X.-J. Tong, M.-G. Cui and W. Jiang, “The Production Algorithm of Pseudo-Random Number Generator Based on Compound Non-Linear Chaos System,” Proceedings of the International Conference on Intelligent Information Hiding and Multimedia Signal Processing, California, 18-20 December 2006, pp. 685-688. doi:10.1109/IIH-MSP.2006.265094

[12] Q. Wang, C. Guyeux and J. M. Bahi, “A Novel Pseudo-Random Number Generator Based on Discrete Chaotic Iterations,” First International Conference on Evolving Internet, Cannes/La Bocca, 23-29 August 2009, pp. 71-76. doi:10.1109/INTERNET.2009.18

[13] H. P. Lü, S. H. Wang and G. Hu, “Pseudo-Random Number Generator Based on Coupled Map Lattices,” International Journal of Modern Physics B, Vol. 18, No. 17-19, 2004, pp. 2409-2414.

[14] X. M. Li, H. B. Shen and X. L. Yan, “Characteristic Analysis of a Chaotic Random Number Generator Using Piece-Wise-Linear Map,” Journal of Electronics and Information Technology, Vol. 27, No. 6, 2005, pp. 874-878.

[15] J. Liu, “Design of a Chaotic Random Sequence and Its Application,” Computer Engineering, Vol. 31, No. 18, 2005, pp. 150-152.

[16] Y. Wang, H. Shen and X. Yan, “Design of a Chaotic Random Number Generator,” Chinese Journal of Semi- conductors, Vol. 26, No. 12, 2005, pp. 2433-2439.

[17] L. Wang, F. P. Wang and Z. J. Wang, “Novel Chaos-Based Pseudo-Random Number Generator,” Acta Physica Sinica, Vol. 55, No. 8, 2006, pp. 3964-3968.

[18] M. Andrecut, “Logistic Map as a Random Number Generator,” International Journal of Modern Physics B, Vol. 12, No. 9, 1998, pp. 921-930. doi:10.1142/S021797929800051X

[19] J. A. Gonzalez and R. Pino, “Random Number Generator Based on Unpredictable Chaotic Functions,” Computer Physics Communications, Vol. 120, No. 2-3, 1999, pp. 109-114. doi:10.1016/S0010-4655(99)00233-7

[20] L. Kocarev and G. Jakimoski, “Pseudo-Random Bits Generated by Chaotic Maps,” IEEE Transactions on Circuits and Systems, Vol. 50, No. 1, 2003, pp. 123-126. doi:10.1109/TCSI.2002.804550

[21] S. M. Fu, Z. Y. Chen and Y. A. Zhou, “Chaos Based Random Number Generators,” Computer Research and Development, Vol. 41, No. 4, 2004, pp. 749-754.

[22] S. Ergun and S. Ozoguz, “Truly Random Number Generators Based on a Non-autonomous Chaotic Oscillator,” AEU-International Journal Electronics & Communications, Vol. 61, No. 4, 2007, pp. 235-242. doi:10.1016/j.aeue.2006.05.006

[23] V. V. Kolesov, R. V. Belyaev and G. M. Voronov, “A Digital Random-Number Generator Based on the Chaotic Signal Algorithm,” Journal of Communications Technology and Electronics, Vol. 46, No. 11, 2001, pp. 1258- 1263.

[24] T. Stojanovski and L. Kocarev, “Chaos-Based Random Number Generators,” IEEE Transactions on Circuits and Systems, Vol. 48, No. 3, 2001, pp. 281-288. doi:10.1109/81.915385

[25] T. Stojanovski, J. Pihl and L. Kocarev, “Chaos Based Random Number Generators,” IEEE Transactions on Circuits and Systems, Vol. 48, No. 3, 2001, pp. 382-385. doi:10.1109/81.915396

[26] S. Oishi and H. Inoue, “Pseudo-Random Number Generators and Chaos,” Transactions of the Institute of Electronics and Communication Engineers of Japan E, Vol. 65, No. 9, 1982, pp. 534-541.

[27] T. Lin and L. O. Chua, “New Class of Pseudo-Random Number Generator Based on Chaos in Digital Filters,” International Journal of Circuit Theory and Applications, Vol. 21, No. 5, 1993, pp. 473-480. doi:10.1002/cta.4490210506

[28] W. Gao, G. Y. Zhang, Y. M. Li and W. H. Chen, “Research and Realization of Random Encryption Algorithm,” International Conference on Internet Computing in Science and Engineering, Washington, 24 June 2008, pp. 23-26.

[29] J. Szczepa′nski and Z. Kotulski, “Pseudo-Random Number Generators Based on Chaotic Dynamical Systems,” Journal of Open Systems & Information Dynamics, Vol. 8, No. 2, 2001, pp. 137-146.

[1] Y. Hu, X. Liao, K. W. Wong and Q. Zhou, “A True Random Number Generator Based on Mouse Movement and Chaotic Cryptography,” Chaos, Solitons and Fractals, Vol. 40, No. 15, 2009, pp. 2286-2293. doi:10.1016/j.chaos.2007.10.022

[2] P. L. Ecuyer and J. Granger-Piché, “Combined Generators with Components from Different Families,” Mathematics and Computers in Simulation, Vol. 62, No. 3, 2003, pp. 395-404. doi:10.1016/S0378-4754(02)00234-3

[3] M. Orlov, “Optimized Random Number Generation in an Interval,” Information Processing Letters, Vol. 109, No. 13, 2009, pp. 722-725. doi:10.1016/j.ipl.2009.03.008

[4] Q. Zhou, X. Liao, K. W. Wong, Y. Hua and D. Xiao, “True Random Number Generator Based on Mouse Movement and Chaotic Hash Function,” Information Sciences, Vol. 179, No. 19, 2009, pp. 3442-3450. doi:10.1016/j.ins.2009.06.005

[5] K. Nakano, K. Kawakami and K. Shigemoto, “RSA Encryption and Decryption Using the Redundant Number System on the FPGA,” IEEE International Symposium on Parallel & Distributed Processing, Rome, 23-29 May 2009, pp. 1-8.

[6] I. Krykova, “Evaluating of Path-Dependent Securities with Low Discrepancy Methods,” Master of Science Thesis, Worce-Ster Polytechnic Institute, 2003.

[7] T. Stojanovski and L. C. Kocarev, “Chaos-Based Random Number Generators,” IEEE Transactions on Circuits and Systems, Vol. 48, No. 3, 2001, pp. 281-288.

[8] K. H. Tsoi, K. H. Leung and P. H. W. Leong, “High Performance Physical Random Number Generator,” IET Proceeding Computers & Digital Techniques, Vol. 1, No. 4, 2007, pp. 349-352. doi:10.1049/iet-cdt:20050173

[9] M. I. Youssef, M. Zahara, A. E. Emam and M. A. Elghany, “Image Encryption Using Pseudo Random Number and Chaotic Sequence Generators,” Radio Science Conference, New Cairo, 17-19 March 2009, pp. 1-15.

[10] C. Pellicer-Lostao and R. Lopez-Ruiz, “Pseudo-Random Bit Generation Based on 2D Chaotic Maps of Logistic Type and Its Applications in Chaotic Cryptography,” Journal of Computational Science and Its Applications, Vol. 5073, 2008, pp. 784-796.

[11] X.-J. Tong, M.-G. Cui and W. Jiang, “The Production Algorithm of Pseudo-Random Number Generator Based on Compound Non-Linear Chaos System,” Proceedings of the International Conference on Intelligent Information Hiding and Multimedia Signal Processing, California, 18-20 December 2006, pp. 685-688. doi:10.1109/IIH-MSP.2006.265094

[12] Q. Wang, C. Guyeux and J. M. Bahi, “A Novel Pseudo-Random Number Generator Based on Discrete Chaotic Iterations,” First International Conference on Evolving Internet, Cannes/La Bocca, 23-29 August 2009, pp. 71-76. doi:10.1109/INTERNET.2009.18

[13] H. P. Lü, S. H. Wang and G. Hu, “Pseudo-Random Number Generator Based on Coupled Map Lattices,” International Journal of Modern Physics B, Vol. 18, No. 17-19, 2004, pp. 2409-2414.

[14] X. M. Li, H. B. Shen and X. L. Yan, “Characteristic Analysis of a Chaotic Random Number Generator Using Piece-Wise-Linear Map,” Journal of Electronics and Information Technology, Vol. 27, No. 6, 2005, pp. 874-878.

[15] J. Liu, “Design of a Chaotic Random Sequence and Its Application,” Computer Engineering, Vol. 31, No. 18, 2005, pp. 150-152.

[16] Y. Wang, H. Shen and X. Yan, “Design of a Chaotic Random Number Generator,” Chinese Journal of Semi- conductors, Vol. 26, No. 12, 2005, pp. 2433-2439.

[17] L. Wang, F. P. Wang and Z. J. Wang, “Novel Chaos-Based Pseudo-Random Number Generator,” Acta Physica Sinica, Vol. 55, No. 8, 2006, pp. 3964-3968.

[18] M. Andrecut, “Logistic Map as a Random Number Generator,” International Journal of Modern Physics B, Vol. 12, No. 9, 1998, pp. 921-930. doi:10.1142/S021797929800051X

[19] J. A. Gonzalez and R. Pino, “Random Number Generator Based on Unpredictable Chaotic Functions,” Computer Physics Communications, Vol. 120, No. 2-3, 1999, pp. 109-114. doi:10.1016/S0010-4655(99)00233-7

[20] L. Kocarev and G. Jakimoski, “Pseudo-Random Bits Generated by Chaotic Maps,” IEEE Transactions on Circuits and Systems, Vol. 50, No. 1, 2003, pp. 123-126. doi:10.1109/TCSI.2002.804550

[21] S. M. Fu, Z. Y. Chen and Y. A. Zhou, “Chaos Based Random Number Generators,” Computer Research and Development, Vol. 41, No. 4, 2004, pp. 749-754.

[22] S. Ergun and S. Ozoguz, “Truly Random Number Generators Based on a Non-autonomous Chaotic Oscillator,” AEU-International Journal Electronics & Communications, Vol. 61, No. 4, 2007, pp. 235-242. doi:10.1016/j.aeue.2006.05.006

[23] V. V. Kolesov, R. V. Belyaev and G. M. Voronov, “A Digital Random-Number Generator Based on the Chaotic Signal Algorithm,” Journal of Communications Technology and Electronics, Vol. 46, No. 11, 2001, pp. 1258- 1263.

[24] T. Stojanovski and L. Kocarev, “Chaos-Based Random Number Generators,” IEEE Transactions on Circuits and Systems, Vol. 48, No. 3, 2001, pp. 281-288. doi:10.1109/81.915385

[25] T. Stojanovski, J. Pihl and L. Kocarev, “Chaos Based Random Number Generators,” IEEE Transactions on Circuits and Systems, Vol. 48, No. 3, 2001, pp. 382-385. doi:10.1109/81.915396

[26] S. Oishi and H. Inoue, “Pseudo-Random Number Generators and Chaos,” Transactions of the Institute of Electronics and Communication Engineers of Japan E, Vol. 65, No. 9, 1982, pp. 534-541.

[27] T. Lin and L. O. Chua, “New Class of Pseudo-Random Number Generator Based on Chaos in Digital Filters,” International Journal of Circuit Theory and Applications, Vol. 21, No. 5, 1993, pp. 473-480. doi:10.1002/cta.4490210506

[28] W. Gao, G. Y. Zhang, Y. M. Li and W. H. Chen, “Research and Realization of Random Encryption Algorithm,” International Conference on Internet Computing in Science and Engineering, Washington, 24 June 2008, pp. 23-26.

[29] J. Szczepa′nski and Z. Kotulski, “Pseudo-Random Number Generators Based on Chaotic Dynamical Systems,” Journal of Open Systems & Information Dynamics, Vol. 8, No. 2, 2001, pp. 137-146.