ОСОБЛИВОСТІ ЗАСТОСУВАННЯ АЛГОРИТМУ АСО ДО ДЕЯКИХ ЗАДАЧ КРИПТОАНАЛІЗУ
DOI:
https://doi.org/10.18372/2310-5461.58.17650Ключові слова:
криптоаналіз, АСО, оптимізація, евристика, метаевристика, фітнес-функціяАнотація
Вимоги до інформаційної безпеки диктують неохідність розвитку нових методів криптоаналізу. Сучасний криптоаналіз спирається на математику, зокрема на теорію та методи оптимізації. Враховучи загальновизнані вимоги до зламостійкості шифрів, задача розшифрування мусить розглядатися, як задача комбінаторної оптимізації.
В роботі обґрунтовується необхідність розвитку нових методів криптоаналізу із застосуванням метаевристик, міститься ретрспективний огляд публікацій за останній період в даній області. Кількість публікацій свідчить про актуальність напрямку досліджень.
Розглядаються особливості застосування алгоритму АСО (Ant Colony Optimization) до задач криптоаналізу, зокрема, задачі факторизації. Описується структура і загальні принципи роботи алгоритму АСО, адаптація даного алгоритму до розв’язання конкретної задачі комбінаторної оптимізації. Розглянуто різні варіанти фітнес-функції, особливості їх застосування, способи звуження простору пошуку, правила вибору напрямку руху на графі, модифікація локального пошуку. Як один із варіантів модифікації розглядається додавання генетичних операторів кросоверу, мутації, селекції. Описано умови припинення роботи алгоритму.
Обґрунтовано доцільність застосування метаевристик для розв’зання задач комбінаторної оптимізації що виникають у різних предметних областях, зокрема, у криптоаналізі. Підкреслюється, що так як теоретичні дослідження алгоритмів комбінаторної оптимізації рідко дозволяють отримувати результати, які можуть бути застосовані на практиці, то основним інструментом аналізу їх ефективності є обчислювальний експеримент.
Посилання
Гуляницький Л. Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. Київ. 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 .
