Разработка и исследование параллельной модели алгоритмов пчелиных колоний для решения задач криптоанализа

Введение. Научное направление «природные вычисления» в последнее время широко используется для решения оптимизационных NP-полных задач, в том числе комбинаторных задач криптоанализа. В статье приводится краткий обзор публикаций, посвященных применению природных (биоинспирированных) методов для криптоанализа. Основной целью работы является исследование возможности применения алгоритмов пчелиных колоний для реализации криптоанализа блочных шифров. Материалы и методы. Для решения данной оптимизационной задачи применяются известные методы пчелиных колоний, относящиеся к сравнительно новому классу биоинспирированных оптимизационных методов, имитирующих процессы, протекающие в живой природе. Приводится описание и структурная схема алгоритма колонии пчел для решения задачи криптоанализа, отмечаются основные операции, выполняемые параллельно на глобальном уровне. Далее определяется множество независимых операторов, допускающих параллельное выполнение. С этой целью строятся информационно-логические граф-схемы алгоритма с введенными связями по управлению и по информации, а также формируются матрицы следования, логической несовместимости и независимости. По данной матрице независимости возможно определение множества операторов алгоритма, которые допускают параллельное выполнение. При этом размерность максимального внутренне устойчивого множества определяет максимальное число процессоров, используемых для реализации алгоритма. Результаты исследования. Основными результатами являются теоретические оценки временной сложности алгоритма пчелиных колоний. Кроме того, приводится решение задачи: для алгоритма криптоанализа на основе построенного информационно-логического графа и для заданного времени найти необходимое наименьшее число процессоров однородной вычислительной системы и план выполнения операторов на них. Приводится оценка необходимого минимального числа процессоров для реализации алгоритма криптоанализа, а также оценка общего Обсуждение и заключения. Основными результатами исследования являются: разработка алгоритма колонии пчел, используемого для решения задачи криптоанализа; описание его структурной схемы и основных параллельно выполняемых этапов; построение матрицы независимости; оценка числа процессоров для реализации алгоритма. Следует заметить (и это отмечалось в предыдущих работах), что отличительной особенностью применения биоинспирированных методов криптоанализа является возможность использования самого алгоритма шифрования (или расшифрования) в качестве целевой функции для оценки пригодности ключа, определенного с помощью операций биоинспирированного метода. Поэтому можно утверждать, что при использовании биоинспирированных методов процесс определения секретного ключа зависит не столько от сложности шифрующих преобразований, сколько от самого биоинспирированного метода, который должен обеспечивать достаточное разнообразие генерации ключей. времени реализации алгоритма

криптоанализ, пчелиный алгоритм, пчелы-фуражиры, пчелы-разведчики, информационно-логический граф, матрица независимости, cryptanalysis, bee colony algorithm, bee foragers, scout bees, information-logical graph, matrix of independence

1. Криптографические методы и генетические алгоритмы решения задач криптоанализа / Ю. О. Чернышев [и др.]. - Краснодар : ФВАС, 2013. - 138 с.

2. Курейчик, В. В. Алгоритм параметрической оптимизации на основе модели поведения роя светлячков / В. В. Курейчик, Д. В. Заруба, Д. Ю. Запорожец // Известия ЮФУ. Технические науки. ¾ 2015. ¾ № 6 (167). ¾ С. 6-15.

3. Биоинспирированные алгоритмы решения задач криптоанализа классических и асимметричных криптосистем / Ю. О. Чернышев [и др.]. - Краснодар. высш. воен. училище им. ген. армии С. М. Штеменко, 2015. - 132 с.

4. Исследование возможности применения генетических алгоритмов для реализации криптоанализа блочных криптосистем / Ю. О. Чернышев [и др.] // Вестник Дон. гос. техн. ун-та. - 2015. - № 3 (82). - С. 65-72.

5. Исследование возможности применения методов эволюционной оптимизации для реализации криптоанализа блочных методов шифрования / Ю. О. Чернышев [и др.] // Изв. СПбГЭТУ «ЛЭТИ». - 2015. - № 10. - С. 32-40.

6. Лебедев, Б. К. Модели адаптивного поведения колонии пчел для решения задач на графах / Б. К. Лебедев, О. Б. Лебедев // Известия ЮФУ. Технические науки. ¾ 2012. ¾ № 7. ¾ С. 42-49.

7. Лебедев, О. Б. Трассировка в канале методом муравьиной колонии / О. Б. Лебедев // Известия ЮФУ. Технические науки. ¾ 2009. ¾ № 4. ¾ С. 46-52.

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

9. Чернышев, Ю. О. Исследование и разработка методов криптоанализа шифров перестановок на основе биоинспирированных методов пчелиных колоний / Ю. О. Чернышев, А. С. Сергеев, Е. О. Дубров // Системный анализ в проектировании и управлении. Часть 1 : сб. науч. тр. 17-й Междунар. науч.-практ. конф. - Санкт-Петербург : Изд-во Политехн. ун-та, 2013. - С. 143-150.

10. Биоинспирированные методы криптоанализа асимметричных алгоритмов шифрования на основе факторизации составных чисел / А. С. Сергеев [и др.] // Вестник Дон. гос. техн. ун-та. - 2011. - Т. 11, № 9 (60). - С. 1544-1554.

11. Чернышев, Ю. О. Применение биоинспирированных методов оптимизации для реализации криптоанализа классических симметричных и асимметричных криптосистем / Ю. О. Чернышев, А. С. Сергеев, Е. О. Дубров // Системный анализ в проектировании и управлении : сб. науч. тр. 16-й Междунар. науч.-практ. конф. - Санкт-Петербург : Изд-во Политехн. ун-та, 2012. - С. 112-122.

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

13. Сергеев, А. С. Параллельное программирование / А. С. Сергеев. - Ростов-на-Дону : Изд. центр ДГТУ, 2002. - 77 с.

14. Ахо, А.-В. Структуры данных и алгоритмы / А.-В. Ахо, Дж.-Е. Хопкрофт, Дж.-Д. Ульман. - Москва : Вильямс, 2003. - 384 с.

15. Применение биоинспирированных методов оптимизации для реализации криптоанализа блочных методов шифрования: монография / Ю. О. Чернышев [и др.]. - Ростов-на-Дону : Изд-во ДГТУ, 2016. - 177 с.

16. Применение методов эволюционной оптимизации для реализации криптоанализа блочного метода шифрования AES / С. А. Капустин [и др.] // Известия СПбГЭТУ «ЛЭТИ». - 2016. - № 8. - С. 25-40.

17. Chernyshev, Y.O., et al. Kriptograficheskie metody i geneticheskie algoritmy resheniya zadach kriptoanaliza. [Cryptographic techniques and genetic algorithms for solving cryptanalysis problems.] Krasnodar: FVAS, 2013, 138 p. (in Russian).

18. Kureichik, V.V., Zaruba, D.V., Zaporozhets, D.Y. Algoritm parametricheskoy optimizatsii na osnove modeli povedeniya roya svetlyachkov. [Parametric optimization algorithm based on the model of glowworm swarm behavior] Izvestiya SFedU. Engineering Sciences. 2015, no. 6 (167), pp. 6-15 (in Russian).

19. Chernyshev, Y.O., et al. Bioinspirirovannye algoritmy resheniya zadach kriptoanaliza klassicheskikh i asimmetrichnykh kriptosistem. [Bioinspired algorithms for solving cryptanalysis problems of classic and asymmetric cryptosystems.] Krasnodar higher military school named after army general S. M. Shtemenko, 2015, 132 p. (in Russian).

20. Chernyshev, Y.O., et al. Issledovanie vozmozhnosti primeneniya geneticheskikh algoritmov dlya realizatsii kriptoanaliza blochnykh kriptosistem. [Feasibility study of genetic algorithms application for implementation of block cryptosystem cryptanalysis.] Vestnik of DSTU, 2015, no. 3 (82), pp. 65-72 (in Russian).

21. Chernyshev, Y.O., et al. Issledovanie vozmozhnosti primeneniya metodov evolyutsionnoy optimizatsii dlya realizatsii kriptoanaliza blochnykh metodov shifrovaniya. [Research of possibility of application of evolutionary optimization methods for realization of cryptanalysis of enciphering block methods.] Izvestiya SPbGETU “LETI”, 2015, no. 10, pp. 32-40 (in Russian).

22. Lebedev, B.K., Lebedev, O.B. Modeli adaptivnogo povedeniya kolonii pchel dlya resheniya zadach na grafakh. [Modeling of an ant colony adaptive behavior by search of the decisions interpreted by trees.] Izvestiya SFedU. Engineering Sciences. 2012, no. 7, pp. 42-49 (in Russian).

23. Lebedev, O.B. Trassirovka v kanale metodom murav'inoy kolonii. [Chanel routing bases on method of ant colony optimization.] Izvestiya SFedU. Engineering Sciences. 2009, no. 4, pp. 46-52 (in Russian).

24. Chernyshev, Y.O., et al. Issledovanie vozmozhnosti primeneniya bionicheskikh metodov pchelinykh koloniy dlya realizatsii kriptoanaliza klassicheskikh shifrov perestanovok. [Research on applicability of bionic techniques of bee colonies for implementation of classical transposition cipher cryptanalysis.] Vestnik of DSTU, 2014, vol. 14, no. 1 (76), pp. 62-75 (in Russian).

25. Chernyshev, Y.O., Sergeev, A.S., Dubrov, E.O. Issledovanie i razrabotka metodov kriptoanaliza shifrov perestanovok na osnove bioinspirirovannykh metodov pchelinykh koloniy. [Research and development of cryptanalysis methods of cipher transpositions based on bioinspired bee colony methods.] Sistemnyy analiz v proektirovanii i upravlenii. Chast' 1 : sb. nauch. tr. 17-y Mezhdunar. nauch.-prakt. konf. [System analysis in design and management. Part 1: Coll.of sci.papers 17th Int. Sci.-Pract. Conf.] St. Petersburg: Polytechnic University Publ. House, 2013, pp. 143-150 (in Russian).

26. Sergeev, A.S., et al. Bioinspirirovannye metody kriptoanaliza asimmetrichnykh algoritmov shifrovaniya na osnove faktorizatsii sostavnykh chisel. [Cryptanalysis bioinspired methods of asymmetric key on the basis of composite number factorization.] Vestnik of DSTU, 2011, vol. 11, no. 9 (60), pp. 1544-1554 (in Russian).

27. Chernyshev, Y.O., Sergeev, A.S., Dubrov, E.O. Primenenie bioinspirirovannykh metodov optimizatsii dlya realizatsii kriptoanaliza klassicheskikh simmetrichnykh i asimmetrichnykh kriptosistem. [Application of bioinspired optimization methods for implementation of cryptanalysis of classical symmetric and asymmetric cryptosystems.] Sistemnyy analiz v proektirovanii i upravlenii : sb. nauch. tr. 16-y Mezhdunar. nauch.-prakt. konf. [System analysis in design and management: Coll.of sci.papers 16th Int. Sci.-Pract. Conf.] St. Petersburg: Polytechnic University Publ. House, 2012, pp. 112-122 (in Russian).

28. Kureichik, V.V., Zhilenkov, M.A. Pchelinyy algoritm dlya resheniya optimizatsionnykh zadach s yavno vyrazhennoy tselevoy funktsiey. [Bee algorithms for solving optimization problems with the explicit objective function.] Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie, 2015, no. 1 (21), pp. 1-8 (in Russian).

29. Sergeev, A.S. Parallel'noe programmirovanie. [Concurrent programming.] Rostov-on-Don: DSTU Publ. Centre, 2002,77 p. (in Russian).

30. Aho, A.V., Hopkroft, J.E., Ullman, J.D. Struktury dannykh i algoritmy. [Data Structures and Algorithms. ] Moscow: Williams, 2003, 384 p. (in Russian).

31. Chernyshev, Y.O., et al. Primenenie bioinspirirovannykh metodov optimizatsii dlya realizatsii kriptoanaliza blochnykh metodov shifrovaniya. [Application of bioinspired optimization methods for implementation of cryptanalysis block encryption methods.] Rostov-on-Don: DSTU Publ. Centre, 2016, 177 p. (in Russian).

32. Kapustin, S.A., et al. Primenenie metodov evolyutsionnoy optimizatsii dlya realizatsii kriptoanaliza blochnogo metoda shifrovaniya AES. [Application of evolutionary optimization methods for implementation of cryptanalysis of the block cryptography technique AES.] Izvestiya SPbGETU “LETI”, 2016, no. 8, pp. 25-40 (in Russian).