ПІДХІД ДО КРИПТОАНАЛІЗУ З ВИКОРИСТАННЯМ ЕВОЛЮЦІЙНИХ ОБЧИСЛЕНЬ
DOI:
https://doi.org/10.32782/mathematical-modelling/2026-9-1-18Ключові слова:
криптоаналіз, еволюційні обчислення, генетичний алгоритм, задача факторизації, шифр простої заміниАнотація
Розглянуто можливість застосування еволюційних обчислень у криптоаналізі, зокрема використання генетичних алгоритмів (ГА) для розв’язання задачі факторизації. Актуальність дослідження зумовлена тим, що надійність криптосистеми RSA базується саме на обчислювальній складності задачі факторизації. Оскільки сучасні класичні субекспоненційні алгоритми (наприклад, GNFS, QS) стикаються з критичними труднощами при обробці чисел великої розрядності, виникає потреба в альтернативних евристичних підходах. Головною метою роботи є практична перевірка спроможності ГА вирішувати задачу факторизації. В основу методології дослідження покладено формалізацію задачі факторизації як задачі комбінаторної оптимізації, де пошук дільників зводиться до мінімізації цільової функції помилки (розглянуто два її варіанти). Вибір ГА як інструменту дослідження зумовлений його математичними властивостями, підтримкою дискретного кодування, а також успішним досвідом застосування до інших задач криптоаналізу. Для підтвердження ефективності методу алгоритм було попередньо протестовано на задачі частотного криптоаналізу шифру простої заміни, де він показав високу точність розшифрування для текстів довжиною понад 200 символів. Результати практичної факторизації за допомогою ГА подано в порівнянні з класичним методом пробного ділення. Для невеликих чисел (до 106) ГА працює стабільно, хоча й поступається у швидкості класичному методу. Для більших чисел (до 109) алгоритм демонструє конкурентоспроможність, випереджаючи пробне ділення у 8 % випадків, проте виявляє нестабільність. Для ще більших чисел (до 1018) алгоритм давав хибні результати через обмеження точності стандартного типу float. Використання підвищеної точності (decimal) у середовищі Python усунуло передчасну зупинку алгоритму, але не дозволило ГА знайти розв’язок у межах прийнятного ліміту часу. Отже, генетичний алгоритм наразі не можна розглядати як повноцінну заміну субекспоненційним алгоритмам для факторизації криптографічно значущих чисел. Проте його застосування як допоміжного евристичного інструменту є цілком доцільним. Попереднє використання ГА дозволяє потенційно звузити простір пошуку перед застосуванням потужних субекспоненційних алгоритмів, таких як GNFS, QS чи ECM.
Посилання
Matthews R. A. The Use of Genetic Algorithms in Cryptanalysis. Cryptologia. 1993. Vol. 17. P. 187–201. DOI: https://doi.org/10.1080/0161-119391867863
Spillman R., Janssen M., Nelson B., Kepner M. Use Of A Genetic Algorithm In The Cryptanalysis Of Simple Substitution Ciphers. Cryptologia. 1993. Vol. 17, iss. 1. P. 31–44. DOI: https://doi.org/10.1080/0161-119391867746
Spillman R. Cryptanalysis Of Knapsack Ciphers Using Genetic Algorithms. Cryptologia. 1993. Vol. 17, iss. 4. P. 367–377. DOI: https://doi.org/10.1080/0161-119391867999
Clark A., Dawson E. A Parallel Genetic Algorithm For Cryptanalysis Of The Polyalphabetic Substitution Cipher. Cryptologia. 1997. Vol. 21, iss. 2. P. 129–138. DOI: https://doi.org/10.1080/0161-119791885850
Clark A., Dawson E. Optimisation Heuristics for the Automated Cryptanalysis of Classical Ciphers. Journal of Combinatorial Mathematics and Combinatorial Computing. 1998. Vol. 28. P. 63–86.
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 : Proceedings 6th Asian Conference, Bangkok, Thailand, April 7–9, 2014). Lecture Notes in Computer Science. 2014. Vol. 8398. P. 147–156. Cham : Springer. https://doi.org/10.1007/978-3-319-05458-2_16
Forhad M. S., Hossain M. S., Rahman M. O., Rahaman M., Haque M. M., Patwary M. K. An improved fitness function for automated cryptanalysis using genetic algorithm. Indonesian Journal of Electrical Engineering and Computer Science. 2019. Vol. 13. № 2. P. 643–648. DOI: https://doi.org/10.11591/ijeecs.v13.i2.pp643-648
Rachmawati D., Tamara H., Sembiring S., Budiman M. RSA public key solving technique by using genetic algorithm. Journal of Theoretical and Applied Information Technology. 2020. Vol. 98, no. 15. P. 2990–2999. URL : https://www.jatit.org/volumes/ninetyeight15.php
Sabonchi A. K. S., Akay B. Cryptanalysis of polyalphabetic cipher using differential evolution algorithm. Tehnički vjesnik. 2020. Vol. 27, no. 4. P. 1101–1107. DOI: https://doi.org/10.17559/TV-20190314095054
Mobin M. A., Kamrujjaman M. Cryptanalysis of RSA Cryptosystem: Prime Factorization using Genetic Algorithm. International Journal of Intelligent Systems and Applications in Engineering. 2024. Vol. 12, no. 1s. P. 456–468. DOI: https://doi.org/10.48550/arXiv.2407.05944
Кубайчук О. О. Особливості застосування алгоритму АСО до деяких задач криптоаналізу. Наукоємні технології. 2023. № 2(58). С. 141–148. DOI: https://doi.org/10.18372/2310-5461.58.17650
Кубайчук О. О. Огляд застосування метаевристичного підходу в криптоаналізі. Вісник Херсонського національного технічного університету. 2023. № 2(85). С. 147–153. DOI: https://doi.org/10.35546/kntu2078-4481.2023.2.20
Crandall R., Pomerance C. Prime numbers: A computational perspective. 2nd ed. New York : Springer, 2005. 597 р. DOI: https://doi.org/10.1007/0-387-28979-8
Eiben A. E., Smith J. E. Introduction to evolutionary computing. 2nd ed. Berlin : Springer, 2015. 287 р. DOI: https://doi.org/10.1007/978-3-662-44874-8
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
