Vestnik of Don State Technical UniversityVestnik of Don State Technical UniversityВестник Донского государственного технического университета1992-5980662410.12737/12599Информатика, вычислительная техника и управлениеINFORMATION TECHNOLOGY, COMPUTER SCIENCE AND MANAGEMENTИнформатика, вычислительная техника и управлениеFeasibility study of genetic algorithms application for implementation of block cryptosystem cryptanalysisИсследование возможности применения генетических алгоритмов для реализации криптоанализа блочных криптосистемЧернышёв Юрий ОлеговичChernyshev Yuriy ОлеговичСергеев Александр СергеевичSergeev Aleksandr Сергеевичsergeev00765@mail.ruРязанов Александр НиколаевичRyazanov Aleksandr НиколаевичВенцов Николай НиколаевичVentsov Nikolay Николаевичmyvnn@list.ru30092015300920151536572https://naukaru.ru/en/nauka/article/6624/view
Рассматривается возможность применения алгоритмов генетического поиска для реализации криптоанализа блочных методов шифрования. Отличительной особенностью применения биоинспирированных методов
криптоанализа (в частности, генетических методов) является возможность использования самого алгоритма шифрования (или расшифрования) в качестве целевой функции для оценки пригодности ключа, определенного с помощью генетических операций. Вследствие этого при использовании биоинспирированных методов криптоанализа процесс определения секретного ключа (например, при криптоанализе второго типа) зависит не столько от сложности шифрующих преобразований, сколько от самого биоинспирированного метода, который должен обеспечивать достаточное разнообразие генерации ключей,
что свидетельствует об актуальности задачи исследования возможности применения биоинспирированных алгоритмов (в частности, методов генетического поиска) для криптоанализа блочных криптосистем. Отмечается также, что поскольку отличительной особенностью как блочных методов шифрования, так и генетических алгоритмов,
является их внутренний параллелизм, то задача разработки алгоритма криптоанализа на основе параллельной реализации составляющих этапов является актуальной.
Предлагается алгоритм криптоанализа блочных методов на примере стандарта DES на основе его параллельной версии, приводятся результаты эксперимента при определении
квазиоптимального ключа, полученные при параллельной реализации алгоритма на 8-буквенных блоках текста. Отмечается, что временные затраты алгоритма не превосходят временных затрат при реализации известных
методов криптоанализа.
F easibility of genetic search algorithms application for implementation of the cryptanalysis of block cipher methods is considered. A distinctive feature of the bioinspired cryptanalysis methods application (in particular, genetic
methods) is the possibility of using the encryption (or decryption) algorithm as an objective function for the suitability evaluation of the key defined by genetic operations. Consequently, when using the bioinspired cryptanalysis methods, the S key definition (for example, when using type 2
cryptanalysis) depends not so much on the complexity of the ciphering transformations, as on the bioinspired method which is to provide a sufficient variety of key generation that shows
the significance of the research task of the bioinspired algorithms feasibility (in particular, genetic search methods) for the block cryptosystem cryptanalysis. It is noted also that as the distinctive feature of both block cipher methods, and the genetic algorithms is their internal parallelism, then the task of developing a cryptanalysis algorithm based on the parallel
implementation of the constituent stages is relevant. An algorithm of the block methods cryptanalysis on the example of the DES standard on the basis of its parallel version is offered;
the experiment results of the quasioptimal key determination obtained at the parallel algorithm implementation on the 8- letter text blocks are given. It is noted that time costs of the
algorithm realization do not exceed the time of the known cryptanalysis implementation.
Введение. В настоящее время при разработке компьютерных технологий, обеспечивающих информационнуюбезопасность и защиту информации, широкое применение находят криптографические методы защиты. Для решениязадач криптоанализа, относящихся к классу NP-полных, в последние годы применяются алгоритмы, основанные наприродных системах. К ним относятся методы моделирования отжига, генетические алгоритмы (ГА), эволюционныеметоды, алгоритмы роевого интеллекта и т.д. В моделях и алгоритмах эволюционных вычислений ключевымэлементом является построение начальной модели и правил, по которым она может изменяться (эволюционировать).В течение последних лет были предложены разнообразные схемы эволюционных вычислений, в т.ч. генетическийалгоритм, генетическое программирование, эволюционные стратегии, эволюционное программирование.
Чернышев, Ю. О. Криптографические методы и генетические алгоритмы решения задач криптоанализа / Ю. О. Чернышев, А. С. Сергеев, Е. О. Дубров, О. П. Третьяков. - Краснодар : ФВАС, 2013. - 138 с.Chernyshev, Y.О., Sergeyev, A.S., Dubrov, E.O., Tretyakov, O.P. Kriptograficheskie metody i geneticheskie algoritmy resheniya zadach kriptoanaliza. [Cryptographic methods and genetic algorithms for solving cryptanalysis problems.] Krasnodar: FVAS, 201, 138 p. (in Russian).Авдошин, С. М. Криптоанализ : современное состояние и перспективы развития / С. М. Авдошин, А. А. Савельева // Информационные технологии. - 2007. - № 3. - С. 1-32.Avdoshin, S.М., Savelieva, A.A. Kriptoanaliz: sovremennoe sostoyanie i perspektivy razvitiya. [Cryptanalysis: Current State and Future Trends.] Information Technologies, 2007, no. 3, pp. 1-32 (in Russian).Бабенко, Л. К. Современные алгоритмы блочного шифрования и методы их анализа / Л. К. Бабенко, Е. А. Ищукова. - Москва : Гелиос АРВ, 2006. - 376 c.Babenko, L.K., Ishchukova, E.A. Sovremennye algoritmy blochnogo shifrovaniya i metody ikh analiza. [Modern block encryption algorithms and methods of their analysis.] Moscow: Gelios ARV, 2006, 376 p. (in Russian).Чернышев, Ю. О. Обзор алгоритмов решения задач криптоанализа на основе биоинспирированных технологий искусственного интеллекта / Ю. О. Чернышев, А. С. Сергеев, Е. О. Дубров // Вестник Воронеж. гос. ун-та. - 2014. - № 2. - С. 83-89.Chernyshev, Y.О., Sergeev, A.S., Dubrov, E.O. Obzor algoritmov resheniya zadach kriptoanaliza na osnove bioinspirirovannykh tekhnologiy iskusstvennogo intellekta. [Review of the algorithms cryptanalysis on the basis bioinspired methods of artificial intelligence.] Proceedings of Voronezh State University, 2014, no. 2, pp. 83-89 (in Russian).Сергеев, А. С. О возможности применения методов генетического поиска для реализации криптоанализа асимметричного алгоритма шифрования данных RSA / А. С. Сергеев // Известия ВУЗов. Сев.-Кавк. регион. Технические науки. - 2008. - № 3. - С. 48-52.Sergeyev, A.S. O vozmozhnosti primeneniya metodov geneticheskogo poiska dlya realizatsii kriptoanaliza asimmetrichnogo algoritma shifrovaniya dannykh RSA. [On applicability of genetic search methods for the implementation of asymmetric data RSA encryption algorithm cryptanalysis.] Izvestiya vuzov. Severo- Kavkazskiy region. Technical Sciences. 2008, no. 3, pp. 48-52 (in Russian).Чернышев, Ю. О. Применение биоинспирированных алгоритмов оптимизации для реализации криптоанализа классических и асимметричных криптосистем / Ю. О. Чернышев, А. С. Сергеев, Е. О. Дубров // Информатика : проблемы, методология, технологии : материалы XIV междунар. науч.-метод. конф. - Воронеж, 2014.- С. 206-210.Chernyshev, Y.О., Sergeyev, A.S., Dubrov, E.O. Primenenie bioinspirirovannykh algoritmov optimizatsii dlya realizatsii kriptoanaliza klassicheskikh i asimmetrichnykh kriptosistem. [Application of bioinspired optimization algorithms for the implementation of classic and asymmetric cryptosystem cryptanalysis.] Informatika: problemy, metodologiya, tekhnologii: materialy XIV mezhdunar. nauch.-metod. konf. [Computer science: problems, methodology, technologies: Proc. XIV Int. Sci.- Method. Conf.] Voronezh, 201, pp. 206-210 (in Russian).Сергеев, А. С. Биоинспирированные методы криптоанализа асимметричных алгоритмов шифрования на основе факторизации составных чисел / А. С. Сергеев, О. П. Третьяков, А. Е. Васильев, Ю. О. Чернышев // Вестник Дон. гос. техн. ун-та. - 2011. - T. 11, № 9(60). - С. 1544-1554.Sergeyev, A.S., Chernyshev, Y.О. Bioinspirirovannye metody kriptoanaliza asimmetrichnykh algoritmov shifrovaniya na osnove faktorizatsii sostavnykh chisel. [Cryptanalysis bioinspired meth ods of asymmetric key on the basis of composite number factorization.] Vestnik of DSTU, 2011, vol. 11, no. 9(60), pp. 1544-1554 (in Russian).Чернышев, Ю. О. Исследование возможности применения бионических методов пчелиных колоний для реализации криптоанализа классических шифров перестановок / Ю. О. Чернышев, А. С. Сергеев, Е. О. Дубров, А. Н. Рязанов // Вестник Дон. гос. техн. ун-та. - 2014. - T. 14, № 1(76). - С. 62-75.Chernyshev, Y.О., Sergeyev, A.S., Dubrov, E.O., Ryazanov, A.N. Issledovanie vozmozhnosti primeneniya bionicheskikh metodov pchelinykh koloniy dlya realizatsii kriptoanaliza klassicheskikh shifrov perestanovok. [Research on applicability of bionic techniques of artificial bee colonies for implementation of classical transposition cipher cryptanalysis.]Vestnik of DSTU, 2014, vol. 14, no. 1(76), pp. 62-75 (in Russian).Сергеев, А. С. Исследование и разработка методов генетического поиска для организации криптоанализа блочных криптосистем в системах управления безопасностью и защиты информации на примере стандарта шифрования DES / А. С. Сергеев // Третья междунар. конф. по проблемам управления : пленарные доклады и избранные труды. - Москва, 2006. - С. 328-335.Sergeyev, A.S. Issledovanie i razrabotka metodov geneticheskogo poiska dlya organizatsii kriptoanaliza blochnykh kriptosistem v sistemakh upravleniya bezopasnost´yu i zashchity informatsii na primere standarta shifrovaniya DES. [Research and development of genetic search methods for the organization of block cryptosystem cryptanalysis in the safety management systems and data protection using an example of the standard DES encryption.] Tret´ya mezhdunar. konf. po problemam upravleniya : plenarnye doklady i izbrannye trudy. [III Int. Conf. on control problems: plenary paperss and selecta.] Moscow, 2006, pp. 328-335 (in Russian).Барский, А. Б. Планирование параллельных вычислительных процессов / А. Б. Барский. - Москва : Машиностроение, 1980. - 191 с.Barskiy, А.B. Planirovanie parallel´nykh vychislitel´nykh protsessov. [Planning of parallel computing processes.] Moscow: Mashinostroenie, 198, 191 p. (in Russian).Сергеев, А. С. Параллельное программирование / А. С. Сергеев. - Ростов-на-Дону : Издательский центр ДГТУ, 2002. - 77 с.Sergeyev, A.S. Parallel´noe programmirovanie. [Parallel programming.] Rostov-on-Don: DSTU Publ. Centre, 2002, 77 p. (in Russian).Воеводин, В. В. Математические модели и методы в параллельных процессах / В. В. Воеводин. - Москва : Наука, 1986. - 296 с.Voyevodin, V.V. Matematicheskie modeli i metody v parallel´nykh protsessakh. [Mathematical models and methods in parallel processes.] Moscow: Nauka, 1986, 296 p. (in Russian).Сергеев, А. С. Разработка генетического метода криптоанализа блочных криптосистем и исследование возможности их параллельной реализации в системах защиты информации на примере стандарта DES / А. С. Сергеев // Системный анализ в проектировании и управлении : тр. 10 междунар. науч.-практ. конф. - Санкт-Петербург, 2006. - С. 258-265.Sergeyev, A.S. Razrabotka geneticheskogo metoda kriptoanaliza blochnykh kriptosistem i issledovanie vozmozhnosti ikh parallel´noy realizatsii v sistemakh zashchity informatsii na primere standarta DES. [Development of the genetic method of block cryptosystem cryptanalysis and feasibility study of their parallel implementation in information security systems on the example of DES standard.] Sistemnyy analiz v proektirovanii i upravlenii: tr. 10 mezhdunar. nauch.- prakt. konf. [System analysis in the design and management: Proc. X Int.-Pract. Conf.] St. Petersburg, 2006, pp. 258-265 (in Russian).Бабенко, Л. К. Применение параллельных вычислений при решении задач защиты информации / Л. К. Бабенко, Е. А. Ищукова, И. Д. Сидоров // Программные системы : теория и приложения. - 2013. - № 3(17). - С. 25-42.Babenko, L.K. Ishchukova, E.A., Sidorov, I.D. Primenenie parallel´nykh vychisleniy pri reshenii zadach zashchity informatsii. [Application of parallel calculations at the solution of information protection problems.] Program Systems: Theory and Applications, 2013, no. 3(17), pp. 25-42 (in Russian).Морозенко, В. В. Генетический алгоритм для криптоанализа шифра Вижинера / В. В. Морозенко, Г. О. Елисеев // Вестник Пермск. гос. ун-та. Серия : Математика. Механика. Информатика. - 2010. - № 1. - С. 75- 80.Morozenko, V.V., Eliseev, G.O. Geneticheskiy algoritm dlya kriptoanaliza shifra Vizhinera. [A genetic algorithm for cryptoanalysis of Vigener’s cipher.]Bulletin of Perm University. Mathematics. Mechanics. Computer Science. 2010, no. 1, pp. 75-80 (in Russian).