Real-Time Optimization of a Pseudo-Random Number Generator Using Particle Swarm Optimization Method

Abstract

Random number generation, which has a critical importance for system design and cryptographic methods; with the emergence of computers with high processing power, security comes to the fore even more. In order to solve this problem, real random number generators that aim to generate random numbers with a physical operation can be used, as well as pseudo-random number generators (PRNG), which are easier to implement because they are software-based. PRNG cannot provide real randomness because they generally have a known algorithm and give predictable results under the same conditions. As a matter of fact, they are frequently preferred because they provide various randomness conditions, number generation speed and cost. In this study, it is aimed to achieve maximum randomness with minimum resource consumption under variable system conditions by using Particle Swarm Optimization (PSO) of a PRNG algorithm, which is preferred due to its ease of implementation and application environment. Randomness was measured using the Runs Test and the Null Hypothesis, and it was concluded that significant gains can be achieved, especially in terms of space complexity, by optimizing a PRNG using PSO.

Keywords

• Pseudo-random Number Generator (PRNG)
• Particle Swarm Optimization (PSO)
• Runs Test
• Cryptography

Bir Sözde Rassal Sayı Üreticinin Parçacık Sürü Optimizasyonu Yöntemi Kullanılarak Gerçek Zamanlı Optimizasyonu

Abstract

Sistem tasarımı ve kriptografik yöntemler için kritik bir öneme sahip olan rassal sayı üretimi; işlem gücü yüksek bilgisayarların ortaya çıkmasıyla güvenlik açısından daha da ön plana çıkmaktadır. Bu problemin çözülmesi için fiziksel bir işleyiş ile rassal sayı üretimini hedefleyen gerçek rassal sayı üreteçleri kullanılabileceği gibi yazılım tabanlı olduğu için uygulanması daha kolay olan sözde rassal sayı üreteçleri (SRSÜ) de kullanılabilmektedir. SRSÜ, genellikle bilinen bir algoritmaya sahip olmaları ve aynı şartlar altında tahmin edilebilen sonuçlar vermeleri sebebiyle gerçek manada rassallık sağlayamamaktadırlar. Nitekim çeşitli rassallık şartlarını sağlamaları, sayı üretim hızı ve maliyet gibi sebeplerden dolayı sıkça tercih edilmektedirler. Bu çalışmada, uygulama kolaylığı ve uygulama ortamı sebebiyle tercih edilen bir SRSÜ algoritmasının Parçacık Sürüsü Optimizasyonu (PSO) kullanılarak değişken sistem şartlarında asgari kaynak tüketimi ile azami rassallığa ulaştırılması amaçlanmıştır. Rassallık, Tekrarlama Sınaması ve Sıfır Hipotezi kullanılarak ölçülmüş ve PSO kullanılarak bir SRSÜ’nün optimize edilmesi yoluyla özellikle alan karmaşıklığı açısından ciddi kazanımlar elde edilebileceği sonucuna ulaşılmıştır.

Keywords

• Sözde Rassal Sayı Üreteci (SRSÜ)
• Parçacık Sürü Optimizasyonu (PSO)
• Koşu Testi
• Kriptografi

References

1. Agin, M. A., & Godbole, A. P. (1992). A new exact runs test for randomness. In Computing Science and Statistics (pp. 281-285). Springer, New York, NY.
2. Akhshani, A., Akhavan, A., Mobaraki, A., Lim, S. C., & Hassan, Z. (2014). Pseudo random number generator based on quantum chaotic map. Communications in Nonlinear Science and Numerical Simulation, 19(1), 101-111.
3. Almardeny, Y., Benavoli, A., Boujnah, N., & Naredo, E. (2022). A Reinforcement Learning System for Generating Instantaneous Quality Random Sequences. IEEE Transactions on Artificial Intelligence.
4. Bakiri, M., Guyeux, C., Couchot, J. F., & Oudjida, A. K. (2018). Survey on hardware implementation of random number generators on FPGA: Theory and experimental analyses. Computer Science Review, 27, 135-153.
5. Bouillaguet, C., Martinez, F., & Sauvage, J. (2020). Practical seed-recovery for the PCG pseudo-random number generator. IACR Transactions on Symmetric Cryptology, 175-196.
6. Boyar, J. (1989). Inferring sequences produced by a linear congruential generator missing low-order bits. Journal of Cryptology, 1(3), 177-184.
7. Bradley, J. V. (1968). Distribution-free statistical tests.
8. Bujang, M. A., & Sapri, F. E. (2018). An application of the runs test to test for randomness of observations obtained from a clinical survey in an ordered population. The Malaysian Journal of Medical Sciences: MJMS, 25(4), 146.

9. Clerc, M. (2010). Particle swarm optimization (Vol. 93). John Wiley & Sons.
10. Demchik, V. (2011). Pseudo-random number generators for Monte Carlo simulations on ATI Graphics Processing Units. Computer Physics Communications, 182(3), 692-705.
11. Ding, K., & Tan, Y. (2014, July). Comparison of random number generators in particle swarm optimization algorithm. In 2014 IEEE Congress on Evolutionary Computation (CEC) (pp. 2664-2671). IEEE.
12. Dodis, Y., Pointcheval, D., Ruhault, S., Vergniaud, D., & Wichs, D. (2013, November). Security analysis of pseudo-random number generators with input: /dev/random is not robust. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security (pp. 647-658).
13. Dorrendorf, L., Gutterman, Z., & Pinkas, B. (2009). Cryptanalysis of the random number generator of the windows operating system. ACM Transactions on Information and System Security (TISSEC), 13(1), 1-32.
14. Downey, R. G., & Hirschfeldt, D. R. (2010). Algorithmic randomness and complexity. Springer Science & Business Media.
15. Galton, F. (1890). Dice for statistical experiments. Nature, 42(1070), 13-14.
16. Hong, S. L., & Liu, C. (2015). Sensor-based random number generator seeding. IEEE Access, 3, 562-568.
17. L'ecuyer, P., & Simard, R. (2007). TestU01: AC library for empirical testing of random number generators. ACM Transactions on Mathematical Software (TOMS), 33(4), 1-40.
18. Lee, W. K., Cheong, H. S., Phan, R. C. W., & Goi, B. M. (2016). Fast implementation of block ciphers and PRNGs in Maxwell GPU architecture. Cluster Computing, 19(1), 335-347.
19. Luengo, E. A., & Villalba, L. J. G. (2021). Recommendations on statistical randomness test batteries for cryptographic purposes. ACM Computing Surveys (CSUR), 54(4), 1-34.
20. Ma, Z., & Vandenbosch, G. A. (2012, March). Impact of random number generators on the performance of particle swarm optimization in antenna design. In 2012 6th European conference on antennas and propagation (EUCAP) (pp. 925-929). IEEE.
21. McCullough, B. D. (2006). A review of TESTU01.
22. Mishra, M., & Mankar, V. H. (2015). Text encryption algorithms based on pseudo random number generator. International Journal of Computer Applications, 111(2).
23. Moreau, T. (1997). Pseudo-random generators, a high-level survey-in-progress. Published on the internet: http://www. cabano. com/connotech/RNG. HTM.
24. Murillo-Escobar, M. A., Cruz-Hernández, C., Cardoza-Avendaño, L., & Méndez-Ramírez, R. (2017). A novel pseudorandom number generator based on pseudorandomly enhanced logistic map. Nonlinear Dynamics, 87(1), 407-425.
25. Park, S., Kim, K., Kim, K., & Nam, C. (2022). Dynamical Pseudo-Random Number Generator Using Reinforcement Learning. Applied Sciences, 12(7), 3377.
26. Pasqualini, L., & Parton, M. (2020). Pseudo random number generation: A reinforcement learning approach. Procedia Computer Science, 170, 1122-1127.
27. Pluhacek, M., Senkerik, R., & Zelinka, I. (2014). Particle swarm optimization algorithm driven by multichaotic number generator. Soft Computing, 18(4), 631-639.
28. Poorghanad, A., Sadr, A., & Kashanipour, A. (2008, December). Generating high quality pseudo random number using evolutionary methods. In 2008 international conference on computational intelligence and security (Vol. 1, pp. 331-335). IEEE.
29. Poschmann, A. Y. (2009). Lightweight cryptography: cryptographic engineering for a pervasive world. In Ph. D. Thesis.
30. Rukhin, A., Soto, J., Nechvatal, J., Barker, E., Leigh, S., Levenson, M., ... & Iii, L. E. B. (2002). A statistical test suite for random and pseudorandom number generators for cryptographic applications,” NIST Special Publication 800-22 (revised May 15.
31. Said, O., & Masud, M. (2013). Towards internet of things: Survey and future vision. International Journal of Computer Networks, 5(1), 1-17.
32. Sathya, K., Premalatha, J., & Rajasekar, V. (2021, February). Investigation of strength and security of pseudo random number generators. In IOP Conference Series: materials Science and Engineering (Vol. 1055, No. 1, p. 012076). IOP Publishing.
33. Savicky, P. (2006). A strong nonrandom pattern in Matlab default random number generator. Manuscript available from http://www2. cs. cas. cz/~ savicky/papers.
34. Savicky, P. (2006). A strong nonrandom pattern in Matlab default random number generator. Manuscript available from http://www2. cs. cas. cz/~ savicky/papers.
35. Silva, R. M., Crespo, R. G., & Nunes, M. S. (2009). LoBa128, a Lorenz-based PRNG for wireless sensor networks. International Journal of Communication Networks and Distributed Systems, 3(4), 301-318.
36. Tippett, L. H. C. (1927). Random sampling numbers.
37. Toolbox, S. M. (1993). Matlab. Mathworks Inc.
38. Tutueva, A. V., Nepomuceno, E. G., Karimov, A. I., Andreev, V. S., & Butusov, D. N. (2020). Adaptive chaotic maps and their application to pseudo-random numbers generation. Chaos, Solitons & Fractals, 133, 109615.
39. Vigna, S. (2016). An experimental exploration of Marsaglia's xorshift generators, scrambled. ACM Transactions on Mathematical Software (TOMS), 42(4), 1-23.
40. Wortman, P., Yan, W., Chandy, J., & Tehranipoor, F. (2018). P2M‐based security model: security enhancement using combined PUF and PRNG models for authenticating consumer electronic devices. IET Computers & Digital Techniques, 12(6), 289-296.
41. Zaman, J. K. M. S., & Ghosh, R. (2012). Review on fifteen Statistical Tests proposed by NIST. Journal of Theoretical Physics and Cryptography, 1, 18-31.
42. Zhang, Y., Agarwal, P., Bhatnagar, V., Balochian, S., & Zhang, X. (2014). Swarm intelligence and its applications 2014. The Scientific World Journal, 2014.
43. Zhang, Y., Balochian, S., Agarwal, P., Bhatnagar, V., & Housheya, O. J. (2014). Artificial intelligence and its applications. Mathematical problems in Engineering, 2014.
44. Zhang, Y., Wang, S., & Ji, G. (2015). A comprehensive survey on particle swarm optimization algorithm and its applications. Mathematical problems in engineering, 2015.