Применение комбинированных биоинспирированных стратегий (генетический алгоритм и алгоритм пчелиных колоний) для реализации криптоанализа классических шифров перестановок

Ранее в [25] было показано, что при использовании комбинированных биоинспирированных алгоритмов вероятность улучшения частичного решения на каждой итерации не может быть меньше вероятности улучшения частичного решения при использовании каждого классического биоинспирированного алгоритма. Отметим здесь еще раз этот существенный момент. Пусть - группа операторов комбинированного алгоритма, соответствующая операторам алгоритма пчелиных колоний (операторы 1-9, 17-21), - группа операторов, соответствующая операторам генетического алгоритма (операторы 10-16). Пусть - вероятность того, что при реализации пчелиного алгоритма на итерации получено решение, лучшее, чем на итерации . Аналогично, пусть - вероятность того, что реализации генетического алгоритма на итерации получено решение, лучшее, чем на итерации . Поскольку эти события совместны (улучшение частичного решения может иметь место одновременно при реализации обоих групп операторов), то, используя аппарат теории вероятностей, получим, что при реализации комбинированного алгоритма вероятность получения на итерации частичного решения, лучшего, чем на итерации, составит . Поскольку все значения удовлетворяют условию ,, , то, очевидно, произведение будет удовлетворять условию . В то же время имеет место очевидное соотношение . Отсюда следует, что будет иметь место соотношение .

Таким образом, мы еще раз показали (аналогично [25]) применительно к комбинированному алгоритму пчелиных колоний), что при реализации комбинированного биоинспирированного алгоритма вероятность улучшения частичного решения на итерации по сравнению с итерацией удовлетворяет условию , где - вероятности улучшения частичного решения при использовании классических биоинспирированных алгоритмов. При этом увеличение вероятности может быть определено из соотношения . Данные расчеты показывают, что при использовании комбинированных биоинспирированных алгоритмов вероятность улучшения частичного решения на каждой итерации не может быть меньше вероятности улучшения частичного решения при использовании каждого классического биоинспирированного алгоритма, что подтверждает целесообразность разработки и использования комбинированных биоинспирированных стратегий и их применения для решения оптимизационных одно- и многоэкстремальных задач. Очевидно, что данные рассуждения справедливы для любого числа биоинспирированных алгоритмов и вероятностей .

Основные выводы

Таким образом, основные результаты работы заключаются в следующем:

- исследована возможность применения комбинированного биоинспирированного алгоритма (генетический алгоритм и алгоритм пчелиных колоний) для реализации задачи криптоанализа систем шифрования; представлены описания основных операций комбинированного биоинспирированного алгоритма;

- представлен демонстрационный пример реализации комбинированного алгоритма криптоанализа, показана возможность получения оптимального варианта решения за конечное число итераций;

- применительно к данному алгоритму показано, что вероятность получения оптимального варианта решения при реализации комбинированных алгоритмов криптоанализа не может быть меньше вероятности получения оптимального решения при использовании классических биоинспирированных алгоритмов, что подтверждает целесообразность использования комбинированных биоинспирированных методов для решения оптимизационных задач.

Работа выполнена при финансовой поддержке РФФИ (проекты 17-01-00375, 15-01-05129).

Литература

1. Чернышев Ю.О., Сергеев А.С., Дубров Е.О., Крупенин А.В., Третьяков О.П. Криптографические методы и генетические алгоритмы решения задач криптоанализа: монография. - Краснодар: ФВАС, 2013. - 138 с.

2. Чернышев Ю.О., А.С. Сергеев, Дубров Е.О., Крупенин А.В., Капустин С.А., Рязанов А.Н. Биоинспирированные алгоритмы решения задач криптоанализа классических и асимметричных криптосистем: монография. - Краснодар: КВВУ, 2015. - 132 с.

3. Чернышев Ю.О., Сергеев А.С., Дубров Е.О., Рязанов А.Н. Применение биоинспирированных методов оптимизации для реализации криптоанализа блочных методов шифрования: монография. - Ростов-на-Дону: издательство ДГТУ, 2016. - 177 с.

4. Лебедев В. Б. Модели адаптивного поведения колонии пчел для решения задач на графах // Известия ЮФУ, 2012, № 7, С. 4249.

5. Орловская Н.М. Анализ эффективности биоинспирированных методов глобальной оптимизации // Труды МАИ: электронный научный журнал, 2014, № 73, С. 4.

6. Лебедев О. Б. Трассировка в канале методом муравьиной колонии // Известия ЮФУ, 2009, № 4, С. 4652.

7. Фатхи В.А., Сергеев А.С. Исследование возможности применения алгоритма муравьиных колоний для реализации криптоанализа шифров перестановок // Вестник ДГТУ, том 11, № 1(52), 2011, с. 10-20.

8. Чернышев Ю.О., Сергеев А.С., Дубров Е.О., Рязанов А.Н. Исследование возможности применения бионических методов пчелиных колоний для реализации криптоанализа классических шифров перестановок // Вестник ДГТУ. - 2014.- Т. 14. - № 1(76). - с. 62-75.

9. Чернышев Ю.О., Сергеев А.С. Дубров Е.О. Обзор алгоритмов решения задач криптоанализа на основе биоинспирированных технологий искусственного интеллекта. - Вестник Воронежского государственного университета, № 2, сер. «Системный анализ и информационные технологии», Воронеж, 2014, с. 83-89.

10. Чернышев Ю.О., Сергеев А.С., Дубров Е.О. Информационная безопасность и биоинспирированные алгоритмы решения задач криптоанализа. - Труды Международного симпозиума «Надежность и качество - 2014». -Пенза: ПГУ, 2014, с. 342-346.

11. Чернышев Ю. О., Сергеев А.С., Рязанов А.Н., Дубров Е.О. Обзор авторских методов решения задач криптоанализа блочных криптосистем на основе биоинспирированных технологий искусственного интеллекта // Наука и образование - 2016: материалы всероссийской научно-практической конференции. - Мурманск: Изд-во МГТУ, 2016, С. 184-190.

12. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. - М.: Радио и связь, 2001, 376 с.

13. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. - М.: Гелиос АРВ, 2002, 480 с.

14. Васильев Е.М., Cвистунов А.А. Решение комбинаторных задач моделированием поведения муравьиных колоний // Электротехнические комплексы и системы управления: научно-технический журнал, 2008, № 1, С. 54-55.

15. Holland J. H. Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence. University of Michigan, 1975, 183 p.

16. Goldberd David E. Genetic Algorithms in Search, Optimization and Machine Learning. Addision-Wesley Publishing Company, Inc. 1989, 432 p.

17. Сергеев А.С. Методы оптимизации: учебное пособие. - Ростов н/Д: Издательский центр ДГТУ, 2005, 113 C.

18. Сергеев A.C., Рязанов A.H., Дубров E.O. Применение алгоритмов пчелиных колоний для реализации криптоанализа блочных методов шифрования. // Инженерный вестник Дона, 2016, №2 URL: ivdon.ru/ru/magazine/archive/n2y2016/3621.

19. Курейчик В. В., Жиленков М.А. Пчелиный алгоритм для решения оптимизационных задач с явно выраженной целевой функцией //Информатика, вычислительная техника и инженерное образование, 2015, № 1(21), С. 1-8.

20. Гладков Л. А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учебное пособие. - М: Физматлит, 2006. - 320 с.

21. Курейчик В.М. Модифицированные генетические операторы // Известия ЮФУ, сер. «Технические науки», тем. выпуск «Интеллектуальные САПР», 2009, № 12, С. 7-14.

22. Дискретная математика: алгоритмы. URL: rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005 (дата обращения: 09.12.2017).

23. Тимченко С.В. Сравнение трех подходов к построению параллельных генетических алгоритмов на примере некоторых задач функциональной оптимизации и генетического программирования. URL: botik.ru/PSI/RCMS/publications/publ-texts/2005/grishagine.pdf (дата обращения 09.12.2017).

24. Вероятности биграмм в тексте. URL: hakinfo.narod.ru/cripto/kr8.html (дата обращения: 09.12.2017).

25. Чернышев Ю.О., Сергеев А.С. Применение комбинированных биоинспирированных алгоритмов для реализации криптоанализа симметричных алгоритмов шифрования // ХХ международная конференция по мягким вычислениям и измерениям: сборник научных трудов. - С-Пб.: Изд-во СПбГЭТУ «ЛЭТИ», 2017, С. 497-500.

26. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы вдохновленные природой. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2017, 446 с.

27. Венцов Н.Н. Эволюционный подход к моделированию распределительных процессов // Инженерный вестник Дона, 2013, № 4 URL: ivdon.ru/ru/magazine/archive/n4y2013/1886.

References

1. Chernyshev Ju.O., Sergeev A.S., Dubrov E.O., Krupenin A.V., Tret'jakov O.P. Kriptograficheskie metody i geneticheskie algoritmy reshenija zadach kriptoanaliza: monografija [Cryptographic methods and genetic algorithms of the solution of problems of cryptanalysis: monograph.]. Krasnodar: FVAS, 2013, 138 р.

2. Chernyshev Ju.O., Sergeev A.S., Dubrov E.O., Krupenin A.V., Kapustin S.A., Rjazanov A.N. Bioinspirirovannye algoritmy reshenija zadach kriptoanaliza klassicheskih i asimmetrichnyh kriptosistem: monografija [The bioinspired algorithms of the solution of problems of cryptanalysis of classical and asymmetric cryptosystems: monograph.]. Krasnodar: KVVU, 2015, 132 p.

3. Chernyshev Ju.O., Sergeev A.S., Dubrov E.O., Rjazanov A.N. Primenenie bioinspirirovannyh metodov optimizacii dlja realizacii kriptoanaliza blochnyh metodov shifrovanija: monografija [The application of bioinspired optimization techniques for the implementation of the cryptanalysis of block encryption methods: monograph]. Rostov-na-Donu, DGTU, 2016, 177 р.

4. Lebedev V. B. Izvestija JuFU. 2012. № 7. pp. 42-49.

5. Orlovskaja N. M. Trudy MAI: jelektronnyj nauchnyj zhurnal, 2014, № 73, p. 4.

6. Lebedev O. B. Izvestija JuFU. 2009. № 4. pp. 46-52.

7. Fathi V.A., Sergeev A.S. Vestnik DGTU, T. 11, № 1(52), 2011, pp. 10-20.

8. Chernyshev Ju.O., Sergeev A.S., Dubrov E.O., Rjazanov A.N. Vestnik DGTU, T. 14, № 1(76), 2014, pp. 62-75.

9. Chernyshev Ju.O., Sergeev A.S. Dubrov E.O. Vestnik Voronezhskogo gosudarstvennogo universiteta, № 2, 2014, pp. 83-89.

10. Chernyshev Ju.O., Sergeev A.S. Dubrov E.O. Informacionnaja bezopasnost' i bioinspirirovannye algoritmy reshenija zadach kriptoanaliza [Information security and bioinspired algorithms for solving problems of cryptanalysis]. Trudy Mezhdunarodnogo simpoziuma «Nadezhnost' i kachestvo - 2014». Penza: PGU, 2014, pp. 342-346.

11. Chernyshev Ju. O., Sergeev A.S., Rjazanov A.N., Dubrov E.O. Obzor avtorskih metodov reshenija zadach kriptoanaliza blochnyh kriptosistem na osnove bioinspirirovannyh tehnologij iskusstvennogo intellekta [Review of author's methods for solving problems of cryptanalysis of block cryptosystems based on bioinspired artificial intelligence technologies]. Nauka i obrazovanie - 2016: materialy vserossijskoj nauchno-prakticheskoj konferencii. Murmansk: Izd-vo MGTU, 2016, рр. 184-190.

12. Romanec Ju.V., Timofeev P.A., Shan'gin V.F. Zashhita informacii v komp'juternyh sistemah i setjah [Protection of information in computer systems and networks]. M.: Radio i svjaz', 2001, 376 p.

13. Alferov A.P., Zubov A.Ju., Kuz'min A.S., Cheremushkin A.V. Osnovy kriptografii [The basics of cryptography.]. M.: Gelios ARV, 2002, 480 p.

14. Vasil'ev E.M., Svistunov A.A. Jelektrotehnicheskie kompleksy i sistemy upravlenija: nauchno-tehnicheskij zhurnal, 2008, № 1, pp. 54-55.

15. Holland J. H. Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence. University of Michigan, 1975, 183 p.

16. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. Addision-Wesley Publishing Company, Inc. 1989, 432 p.

17. Sergeev A.S. Metody optimizacii: uchebnoe posobie [Optimization techniques: a tutorial]. Rostov n/D: Izdatel'skij centr DGTU, 2005. 113 p.

18. Sergeev A.C., Rjazanov A.H., Dubrov E.O. Inћenernyj vestnik Dona (Rus), 2016, № 2, URL: ivdon.ru/ru/magazine/archive/n2y2016/3621.

19. Kurejchik V. V., Zhilenkov M.A. Informatika, vychislitel'naja tehnika i inzhenernoe obrazovanie, 2015, № 1(21), pp. 1-8.

20. Gladkov L. A., Kurejchik V.V., Kurejchik V.M. Geneticheskie algoritmy: uchebnoe posobie [Genetic algorithms: a tutorial.]. M: Fizmatlit, 2006. 320 р.

21. Kurejchik V.M. Izvestija JuFU, ser. «Tehnicheskie nauki», tem. vypusk «Intellektual'nye SAPR», 2009, № 12, pp. 7-14.

22. Diskretnaja matematika: algoritmy [Discrete mathematics: algorithms]. URL: rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005 (accessed 09.12.2017).

23. Timchenko S.V. Sravnenie treh podhodov k postroeniju parallel'nyh geneticheskih algoritmov na primere nekotoryh zadach funkcional'noj optimizacii i geneticheskogo programmirovanija [Comparison of three approaches to parallel genetic algorithms on the example of some problems of functional optimization and genetic programming]. URL: www.botik.ru/PSI/RCMS/publications/publ-texts/2005/grishagine.pdf (accessed 09.12.2017).

24. Verojatnosti bigramm v tekste [The probability of bigrams in the text]. URL: hakinfo.narod.ru/cripto/kr8.html (accessed 09.12.2017).

25. Chernyshev Ju.O., Sergeev A.S. Primenenie kombinirovannyh bioinspirirovannyh algoritmov dlja realizacii kriptoanaliza simmetrichnyh algoritmov shifrovanija [The use of combined bioinspired algorithms for the implementation of the cryptanalysis of symmetric encryption algorithms]. XX mezhdunarodnaja konferencija po mjagkim vychislenijam i izmerenijam: sbornik nauchnyh trudov. S-Pb.: Izd-vo SPbGJeTU «LJeTI», 2017, pp. 497-500.

26. Karpenko A.P. Sovremennye algoritmy poiskovoj optimizacii. Algoritmy vdohnovlennye prirodoj [Modern algorithms of search engine optimization. Algorithms inspired by nature]. M.: Izd-vo MGTU im. N.Je. Baumana, 2017, 446 р.

27. Vencov N.N. Inћenernyj vestnik Dona (Rus), 2013, № 4. URL: ivdon.ru/ru/magazine/archive/n4y2013/1886.

Размещено на Allbest.ru