SPECIALITIES OF THE APPLICATION OF THE ACO ALGORITHM TO SOME CRYPTANALYSIS PROBLEMS
DOI:
https://doi.org/10.18372/2310-5461.58.17650Keywords:
cryptanalysis, ACO, optimization, heuristics, metaheuristics, fitness functionAbstract
Requirements for information security dictate the necessity of developing new methods of cryptanalysis. Modern cryptanalysis depend on mathematics, in particular on theory and optimization methods. Taking into account the generally recognized requirements for attack resistance of ciphers, the decryption problem should be considered as a combinatorial optimization problem
The paper proves the necessary of the development of new methods of cryptanalysis using metaheuristics, contains a retrospective review of publications in the last period in this area. The number of publications indicates the relevance of the research direction.
Specialities of the application of the Ant Colony Optimization algorithm to cryptanalysis problems, in particular, factorization problem, are considered. The structure and general principles of the ACO algorithm are described, as well as the adaptation of this algorithm to the solution of a specific problem of combinatorial optimization. Various variants of the fitness function, features of their application, methods of narrowing the search space, rules for choosing the direction of movement on the graph, modification of local search are discussed. The addition of genetic operators of crossover, mutation, and selection is considered as one of the modification options. The conditions for stopping the operation of the algorithm are described.
The various facts of using metaheuristics for solving combinatorial optimization problems arising in numerous subject areas, in particular, in cryptanalysis, are described. It is emphasized that since theoretical studies of combinatorial optimization algorithms rarely allow obtaining results that can be applied in practice. The main tool for analyzing their effectiveness is a computational experiment.
References
Гуляницький Л. Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. Київ. 2016. 142 с.
Ho Yean Li, A. S. Heuristic cryptanalysis of classical and modern ciphers. 2005 13th IEEE International Conference on Networks Jointly held with the 2005 IEEE 7th Malaysia International Conf on Communic. 2005. 2. 710–715. https://doi.org/10.1109/ICON.2005.1635595
Toemeh R., Arumugam S. Breaking Transposition Cipher with Genetic Algorithm. Elektronika Ir Elektrotechnika. 2007. 79(7). 75 78. https://eejournal.ktu.lt/index.php/elt/article/view/10844
Song, J.; Zhang, H.; Meng, Q.; Zhangyi, W. Cryptanalysis of Four-Round DES Based on Genetic Algorithm. Wirel. Commun. Netw. Mob. Comput. IEEE. 2007. 10. 2326–2329. https://doi.org/10.1109/WICOM.2007.580
Garg P. A Comparison between Memetic algorithm and Genetic algorithm for the cryptanalysis of Simplified Data Encryption Standard algorithm. Int. J. Netw. Secur. Its Appl. (IJNSA). 2009. 1. 34–42. https://doi.org/10.48550/arXiv.1004.0574
Hu W. Cryptanalysis of TEA using quantum-inspired genetic algorithms. J. Softw. Eng. Appl. 2010. 3. 50–57. http://dx.doi.org/10.4236/jsea.2010.31006
Abd-Elmonim W.G., Ghali N.I., Hassanien A.E., Abraham. A. Known-Plaintext Attack of DES16 Using Particle Swarm Optimization. In Proceedings of the Third IEEE World Congress on Nature and Biologically Inspired Computing, Salamanca, Spain. 2011. 12–16. https://doi.org/10.1109/NaBIC.2011.6089410
Mekhaznia T., Menai M. Cryptanalysis of classical ciphers with ant algorithms. International Journal of Metaheuristics. 2014. 3(3). 175-198. https://doi.org/10.1504/IJMHEUR.2014.065159
Boryczka U., Dworak K. Genetic Transformation Techniques in Cryptanalysis. In: Nguyen, N.T., Attachoo, B., Trawiński, B., Somboonviwat, K. (eds) Intelligent Information and Database Systems. ACIIDS 2014. Lecture Notes in Computer Science. 2014. vol. 8398. Springer, Cham. https://doi.org/10.1007/978-3-319-05458-2_16
Dadhich A., Gupta A., Yadav S. Swarm Intelligence based linear cryptanalysis of four-round Data Encryption Standard algorithm. In 2014 International Conference on Issues and Challenges in Intelligent Computing Techniques (ICICT). 2014. 378 – 383. http://dx.doi.org/10.1109%2FICICICT.2014.6781312
Sadeghzadeh M, Taherbaghal M. A new method for decoding an encrypted text by genetic algorithms and its comparison with tabu search and simulated annealing.Management Science Letters. 2014. 4(2). 213 220. https://doi.org/10.5267/j.msl.2013.12.037
Teytaud F., Fonlupt, C. A Critical Reassessment of Evolutionary Algorithms on the cryptanalysis of the simplified data encryption standard algorithm. 2014. ArXiv, abs/1407.1993. https://doi.org/10.5121/IJCIS.2014.4201
Ashok K. Bhateja, Aditi Bhateja, Santanu Chaudhury, P.K. Saxena, Cryptanalysis of Vigenere cipher using Cuckoo Search. Applied Soft Computing. 2015. Vol. 26. 315 324. https://doi.org/10.1016/j.asoc.2014.10.004
Tahar, M. BAT algorithm for Cryptanalysis of Feistel cryptosystems. International Journal of Intelligent Systems and Applications in Engineering. 2015. 3(2). 82 85. https://doi.org/10.18201/ijisae.82426
Dworak K., Boryczka U. Differential Cryptanalysis of FEAL4 Using Evolutionary Algorithm. In: Nguyen, N., Iliadis, L., Manolopoulos, Y., Trawiński, B. (eds) Computational Collective Intelligence. ICCCI 2016. Lecture Notes in Computer Science. 2016. vol. 9876. Springer, Cham. https://doi.org/10.1007/978-3-319-45246-3_10
Amic S., Soyjaudah K.S., Mohabeer H., Ramsawock. G. Cryptanalysis of DES16 using binary firefly algorithm. In Proceedings of the 2016 IEEE International Conference on Emerging Technologies and Innovative Business Practices for the Transformation of Societies, Balaclava, Mauritius, 3–6 August 2016; IEEE: Balaclava, Mauritius. 2016. 94–99. https://doi.org/10.1109/EmergiTech.2016.7737318
Amic S., Soyjaudah K.S., Ramsawock G. Binary cat swarm optimization for cryptanalysis. In Proceedings of the 2017 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), Bhubaneswar, India. 2017. 1–6. https://doi.org/10.1109/ANTS.2017.8384120
Candra A., Budiman M.A., Rachmawati D. On Factoring The RSA Modulus Using Tabu Search. Journal of Computing and Applied Informatics. 2017. vol. 1. n. 1. 30-37. https://doi.org/10.32734/JOCAI.V1.I1-65
Grari H., Azouaqui A., Zine-Dine K., Bakhouya M., Gaber J. Cryptanalysis of Knapsack Cipher Using Ant Colony Optimization. Smart Application and Data Analysis for Smart Cities. 2018. http://dx.doi.org/10.2139/ssrn.3185322
Grari H., Azouaoui A., Zine-Dine K. A Novel Ant Colony Optimization Based Cryptanalysis of Substitution Cipher. In: Abraham, A., Haqiq, A., Ella Hassanien, A., Snasel, V., Alimi, A. (eds) Proceedings of the Third International Afro-European Conference for Industrial Advancement AECIA 2016. Advances in Intelligent Systems and Computing. 2016. vol. 565. 180–187 https://doi.org/10.1007/978-3-319-60834-1_19
Grari H., Azouaoui A., Zine-Dine K. Ant colony optimization for cryptanalysis of simplified-DES. In Advanced Intelligent Systems for Sustainable Development (AI2SD’2018) Vol 2: Advanced Intelligent Systems Applied to Energy. 2019. 111 121. https://doi.org/10.1007/978-3-030-12065-8_11
Grari H., Azouaoui A., Zine-Dine K. A cryptanalytic attack of simplified-AES using ant colony optimization. International Journal of Electrical & Computer Engineering. 2019. 9(5). 4287 4295. https://doi.org/10.11591/ijece.v9i5.pp4287-4295
Jain A., Chaudhari N. S. An improved genetic algorithm and a new discrete cuckoo algorithm for solving the classical substitution cipher. International Journal of Applied Metaheuristic Computing (IJAMC). 2019. 10(2), 109 130. DOI: 10.4018/IJAMC.2019040105
Amic S., Soyjaudah K.S., Ramsawock G. Dolphin swarm algorithm for cryptanalysis. In Information Systems Design and Intelligent Applications; Satapathy, S., Bhateja, V., Somanah, R., Yang, X.S., Senkerik, R., Eds.; Advances in Intelligent Systems and Computing.2019. Vol. 863. 149–163. https://doi.org/10.1007/978-981-13-3338-5_15
D. Rachmawati, H. Tamara, S. Sembiring, M. Budiman. RSA public key solving technique by using genetic algorithm. Journal of Theoretical and Applied Information Technology. 2020. Vol. 98. No. 15. 2990 2999. https://www.scopus.com/inward/record.uri?eid=2-s2.0-85053419786&partnerID=40&md5=1072f49ab20414f2288933fefbef056e
Sabonchi A. K. S., Akay B. Cryptanalysis of polyalphabetic cipher using differential evolution algorithm. Tehnički vjesnik. 2020. 27(4). 1101 1107. https://doi.org/10.17559/TV-20190314095054
Akay B. A binomial crossover based artificial bee colony algorithm for cryptanalysis of polyalphabetic cipher. Tehnički vjesnik. 2020. 27(6). 1825 1835. https://doi.org/10.17559/TV-20190422225110
Sabonchi A. K. S., Akay B. A survey on the Metaheuristics for Cryptanalysis of Substitution and Transposition Ciphers. Computer Systems Science And Engineering. 2021. vol. 39. no. 1. 87 106. http://doi.org/10.32604/csse.2021.05365
Grari H., Lamzabi S., Azouaoui A., Zine-Dine K. Cryptanalysis of Merkle-Hellman cipher using ant colony optimization. Int J Artif Intell. 2021. 490 500. DOI: 10.11591/ijai.v10.i2
Dworak K., Boryczka U. Breaking Data Encryption Standard with a Reduced Number of Rounds Using Metaheuristics Differential Cryptanalysis. Entropy. 2021. vol. 23. no. 12: 1697. https://doi.org/10.3390/e23121697
Jain A., Sharma P.C., Vishwakarma S.K., Gupta N.K., Gandhi V.C. Metaheuristic Techniques for Automated Cryptanalysis of Classical Transposition Cipher: A Review. In: Somani, A.K., Mundra, A., Doss, R., Bhattacharya, S. (eds) Smart Systems: Innovations in Computing. Smart Innovation, Systems and Technologies. 2022. vol. 235. https://doi.org/10.1007/978-981-16-2877-1_43 .
