ОГЛЯД ЗАСТОСУВАННЯ МЕТАЕВРИСТИЧНОГО ПІДХОДУ В КРИПТОАНАЛІЗІ
DOI:
https://doi.org/10.35546/kntu2078-4481.2023.2.20Ключові слова:
криптоаналіз, криптографія, шифр, комбінаторна оптимізація, алгоритм, метаевристикаАнотація
Криптографічний захист інформації є важливою складовою інформаційної безпеки. Розробка нових методів криптоаналізу допомагає зрозуміти межі стійкості наявних криптосистем. Сучасний криптоаналіз опирається на різні математичні дисципліни, зокрема, на теорію та методи оптимізації. Враховучи загальновизнані вимоги до стійкості шифрів, задача розшифрування може розглядатися як задача комбінаторної оптимізації. Методи та алгоритми комбінаторної оптимізації сьогодні відіграють важливу роль у дослідженнях, пов’язаних з колом проблем, що безпосередньо впливають на інформаційну безпеку. Задача криптографічного захисту інформації вирішується створенням нових та вдосконаленням існуючих алгоритмів шифрування. З іншого боку, стрімко зростаючі можливості обчислювальної техніки відкривають практичні передумови впровадження технологій криптоаналізу, недоступних раніше. Зокрема, до актуальних технологій криптоаналізу можна віднести застосування оптимізаційних рандомізованих алгоритмів для інтелектуального дослідження простору пошуку з метою отримання прийнятного результату. Теоретично обгрунтовано, що такі алгоритми, за певних умов, дозволяють отримати розв’язок, коли ймовірність успіху дуже мала. Основним інструментом аналізу ефективності оптимізаційних рандомізованих алгоритмів є обчислювальний експеримент. Аналіз можливості, особливостей та меж застосування метаевристичних алгоритмів криптоаналітиками вказує на перспективу використання метаевристичного підходу як універсального методу криптоаналізу. В роботі обгрунтовується необхідність розвитку нових методів криптоаналізу із застосуванням метаевристик, міститься ретрспективний огляд публікацій за останній період в даній області. Число публікацій свідчить про актуальність напрямку досліджень.
Посилання
Гуляницький Л. Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. Київ: ВПЦ «Київський університет». 2016. 142 с.
Andrew Clark, Ed Dawson, Optimisation Heuristics for the Automated Cryptanalysis of Classical Ciphers. Journal of Combinatorial Mathematics and Combinatorial Computing. Vol. 28. 1998. pp. 63–86.
M. D. Russell, J. A. Clark and S. Stepney. Making the most of two heuristics: breaking transposition ciphers with ants. The 2003 Congress on Evolutionary Computation, 2003. CEC ‘03., Canberra, ACT, Australia Vol. 4. 2003. pp. 2653–2658. https://doi.org/10.1109/CEC.2003.1299423
Dimovski A., Gligoroski D. Attacks on the Transposition Ciphers Using Optimization Heuristics. International Scientific Conference on Information, Communication Energy Systems,Technologies. ICEST 2003.
Toemeh R., Arumugam S. Breaking Transposition Cipher with Genetic Algorithm. Elektronika Ir Elektrotechnika. 79(7). 2007. pp. 75–78. https://eejournal.ktu.lt/index.php/elt/article/view/10844
Uddin M. F., Youssef A. M. An artificial life technique for the cryptanalysis of simple substitution ciphers. Canadian Conference on Electrical and Computer Engineering. IEEE. 2006. pp. 1582–1585. http://dx.doi.org/10.1109%2FCCECE.2006.277769
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. pp. 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). 1. 2009. pp. 34–42. https://doi.org/10.48550/arXiv.1004.0574
Hu W. Cryptanalysis of TEA using quantum-inspired genetic algorithms. J. Softw. Eng. Appl. 3. 2010. pp. 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. pp. 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. 3(3). 2014. pp. 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. vol. 8398. 2014. 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. International Conference on Issues and Challenges in Intelligent Computing Techniques (ICICT), 2014, pp. 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. 4(2). 2014. pp. 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, Vol. 26. 2015. pp. 315–324. https://doi.org/10.1016/j.asoc.2014.10.004
Tahar, M. BAT algorithm for Cryptanalysis of Feistel cryptosystems. 3(2). 2015. pp. 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
Dworak, K., Nalepa, J., Boryczka, U., Kawulok, M. Cryptanalysis of SDES Using Genetic and Memetic Algorithms. In: Król, D., Madeyski, L., Nguyen, N. (eds) Recent Developments in Intelligent Information and Database Systems. Studies in Computational Intelligence. vol 642. 2016. Springer. Cham. https://doi.org/10.1007/978-3-319-31277-4_1
Dworak, K., Boryczka, U. Genetic Algorithm as Optimization Tool for Differential Cryptanalysis of DES6. In: Nguyen, N., Papadopoulos, G., Jędrzejowicz, P., Trawiński, B., Vossen, G. (eds) Computational Collective Intelligence. ICCCI 2017. Lecture Notes in Computer Science. vol. 10449. Springer. Cham. 2017. https://doi.org/10.1007/978-3-319-67077-5_11
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. IEEE: Balaclava. Mauritius. 2016. pp. 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. pp. 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, vol. 1(1). 2017. pp. 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. vol. 565. 2016. pp. 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. pp. 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. 9(5). 2019. pp. 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). 10(2). 2019. pp. 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. Vol. 863. 2019. pp. 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, Vol. 98. 15. 2020. pp. 2990–2999.
Sabonchi A. K. S., Akay B. Cryptanalysis of polyalphabetic cipher using differential evolution algorithm. Tehnički vjesnik. 27(4). 2020. pp. 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. 27(6). 2020. pp. 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, vol. 39. 1. 2021. pp. 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. pp. 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. vol. 23. 12. 2021. pp. 1697–1718. https://doi.org/10.3390/e23121697
