The applicability of the bionic techniques of artificial bee colonies for the implementation of the classical transposition cipher cryptanalysis is considered. The problem is a classical optimization problem to the solution of which the known techniques of artificial bee colonies fallen within a relatively new class of bioinspired optimization methods are applied. It is shown that this is a subproblem of allocation, and it can be solved with an artificial bee colony algorithm, as the bee behavior principle is a self-organization delivering a collective swarm goal. Аt the first stage, a set of promising areas-sources is formed with the aid of scout-bees, at the second stage, the neighborhood of these areas is explored with the aid of foraging bees. At this, the main goal of the bee colony is to find a source with a maximum amount of nectar. Solution representation methods (positions in search space) are considered, a formula for determining an object function value (amount of nectar) is given. It is shown that the target search is the determination of an optimal symbol combination with the highest value of the objective function. Principle stages of the artificial bee colony algorithm, as well as an example of its application, are given.
cryptanalysis, problem of allocation, bioinspired methods, artificial bee colony algorithm, worker-bees (foragers), scout-bee, transposition cipher
Введение. В последние годы интенсивно разрабатывается новое научное направление под названием «природные вычисления», объединяющее математические методы, в которых заложен принцип природных механизмов принятия решений. Как отмечено в [1], научное направление «природные вычисления» объединяет такие разделы, как эволюционное программирование, нейросетевые вычисления, алгоритмы роевого интеллекта, муравьиные и генетические алгоритмы. В моделях и алгоритмах эволюционных вычислений ключевым элементом является построение начальной модели и правил, по которым она может изменяться (эволюционировать). В течение последних лет были предложены разнообразные схемы эволюционных вычислений, в том числе генетические алгоритмы, генетическое программирование, эволюционные стратегии, эволюционное программирование. Общие концепции и методологический подход к построению эволюционных вычислений, основанных на природных системах, а также основные гипотезы, закономерности и положения концепции эволюционных вычислений отмечены в [2, 3]. В настоящее время известны применения генетических алгоритмов для оптимизации широкого круга задач, в том числе задач криптоанализа. В [4‒9] авторами рассматривались методы организации криптографических атак на традиционные симметричные криптосистемы, использующие шифры перестановки и замены, а также на блочные криптосистемы с использованием биоинспирированных методов. Следует заметить, что задачи такого типа относятся к переборным задачам с экспоненциальной временной сложностью. Побудительным мотивом для разработок новых алгоритмов являются возникшие потребности в решении задач большой размерности [10]. Анализ исследований показывает, что наиболее успешными в данных условиях являются методы, в которых заложены принципы природных механизмов принятия решений. Недостатком генетических алгоритмов является наличие «слепого» поиска, что приводит к увеличению времени поиска, генерации большого количества одинаковых и плохо приспособленных решений, что может привести к попаданию в локальный оптимум [11]. Поэтому представляет интерес применение эвристических мето-
1. Makkonel, D. Osnovy sovremennykh algoritmov / D. Makkonel. — Moskva : Tekhnosfera, 2004. — 368 s.
2. Rodzin, S. I. Intellektual´nye sistemy. O nekotorykh algoritmakh, inspirirovannykh prirodnymi sistemami : kollektivnaya monografiya / S. I. Rodzin. — Moskva : Fizmatlit, 2009. — S. 34‒45.
3. Kureychik, V. V. Kontseptsiya prirodnykh vychisleniy, inspirirovannykh prirodnymi sistemami / V. V. Kureychik, V. M. Kureychik, S. I. Rodzin. Izvestiya YuFU. — 2009. — № 4. — S. 16‒24.
4. Sergeev, A. S. Issledovanie vozmozhnosti organizatsii kriptograficheskoy ataki s ispol´zovaniem evolyutsionnoy optimizatsii i kvantovogo poiska pri razrabotke sistem peredachi i zashchity informatsii / A. S. Sergeev. Teoreticheskie i prikladnye voprosy sovremennykh informatsionnykh tekhnologiy : mat-ly 6 Vserossiyskoy NTK. — Ulan-Ude, 2005. — S. 61‒65.
5. Bioinspirirovannye algoritmy kriptoanaliza asimmetrichnykh algoritmov shifrovaniya na osnove faktorizatsii sostavnykh chisel / A. S. Sergeev [i dr.]. Informatsionnaya bezopasnost´ — aktual´naya problema sovremennosti. Sovershenstvovanie obrazovatel´nykh tekhnologiy podgotovki spetsialistov v oblasti informatsionnoy bezopasnosti : sb. trudov. — Krasnodar, 2011. — S. 41‒47.
6. Sergeev, A. S. Primenenie metodov geneticheskogo poiska dlya organizatsii kriptoanaliza blochnykh kriptosistem na primere standarta DES / A. S. Sergeev. Nauchnaya mysl´ Kavkaza : Prilozhenie. — 2006. — № 15. — S. 185‒193.
7. Sergeev, 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 / A. S. Sergeev. Tret´ya Mezhdunarodnaya konferentsiya po problemam upravleniya : Plenarnye doklady i izbrannye trudy. — Moskva : In-t problem upravleniya, 2006. — S. 328‒335.
8. Fatkhi, V. A. Issledovanie vozmozhnosti primeneniya algoritma murav´inykh koloniy dlya realizatsii kriptoanaliza shifrov perestanovok / V. A. Fatkhi, A. S. Sergeev. Vestnik Don. gos. tekhn. un-ta. — 2011. — T. 11, № 1 (52). — S. 10‒20.
9. Chernyshev, Yu. O. Issledovanie i razrabotka metodov geneticheskogo poiska dlya realizatsii kriptoanaliza algoritma IDEA i resheniya osnovnykh teoretiko-chislovykh zadach kriptografii / Yu. O. Chernyshev, A. S. Sergeev, N. N. Ventsov. Vestnik RGUPS. — 2009. — № 3 (35). — S. 70‒79.
10. Lebedev, V. B. Modeli adaptivnogo povedeniya kolonii pchel dlya resheniya zadach na grafakh / V. B. Lebedev. Izvestiya YuFU. — 2012. — № 7. — S. 42‒49.
11. Lebedev, O. B. Trassirovka v kanale metodom murav´inoy kolonii / O. B. Lebedev. Izvestiya YuFU. — 2009. — № 4. — S. 46‒52.
12. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre. Cardiff University, UK, 2005.
13. An IDEA based on honey bee swarm for numerical optimization, technical report. Erciyes University, Engineering Faculty. Computer Engineering Department, 2005.
14. The Bees Algorithm. — A Novel Tool for Complex Optimisation Problems. Manufacturing Engineering Centre. — Cardiff University, Cardiff CF24 3AA, UK.
15. Algoritm pchel dlya optimizatsii funktsii [Elektronnyy resurs]. — Rezhim dostupa http://jenyay.net/Programming/Bees (data obrashcheniya : 24.05.2013).
16. Algoritm pchel dlya optimizatsii funktsii [Elektronnyy resurs]. — Rezhim dostupa : http://lit999.narod.ru/soft/ga/index.html (data obrashcheniya : 24.05.2013).
17. Kureychik, V. V. Roevoy algoritm v zadachakh optimizatsii / V. V. Kureychik, D. Yu. Zaporozhets. Izvestiya YuFU. — 2010. — № 7 (108). — S. 28‒32.
18. Kureychik, V. M. Ispol´zovanie pchelinykh algoritmov dlya resheniya kombinatornykh zadach [Elektronnyy resurs] / V. M. Kureychik, A. A. Kazharov. — Rezhim dostupa : http://archive.nbuv.gov.ua/portal/natural/ii/2010_3/AI_2010_3/6/00_Kureychik_Kazharov.pdf (data obrashcheniya : 24.05.2013).
19. Kureychik, V. M. Primenenie pchelinykh algoritmov dlya raskraski grafov / V. M. Kureychik, A. A. Kazharov. Izvestiya YuFU. — 2010. — № 12 (113). — S. 7‒12.
20. Lebedev, B. K. Razmeshchenie na osnove metoda pchelinoy kolonii / B. K. Lebedev, V. B. Lebedev. Izvestiya YuFU. — 2010. — № 12 (113). — S. 12‒19.
21. Kureychik, V. V. Evolyutsionnaya optimizatsiya na osnove algoritma kolonii pchel / V. V. Kureychik, E. E. Polupanova. Izvestiya YuFU. — 2009. — № 12 (101). — S. 41‒46.
22. Bioinspirirovannye metody kriptoanaliza asimmetrichnykh algoritmov shifrovaniya na osnove faktorizatsii sostavnykh chisel / A. S. Sergeev [i dr.]. Vestnik Don. gos. tekhn. un-ta. — 2011. — T. 11, № 9 (60). — S. 1544‒1554.
23. Chernyshev, Yu. O. Primenenie bioinspirirovannykh metodov optimizatsii dlya realizatsii kriptoanaliza klassicheskikh simmetrichnykh i asimmetrichnykh kriptosistem / Yu. O. Chernyshev, A. S. Sergeev, E. O. Dubrov. Sistemnyy analiz v proektirovanii i upravlenii : sb. nauch. trudov 16-y Mezhdunar. nauch.-prakt. konf. — Sankt-Peterburg, 2012. — S. 112‒122.
24. Zaytsev, A. A. Obzor evolyutsionnykh metodov optimizatsii na osnove roevogo intellekta / A. A. Zaytsev, V. V. Kureychik, A. A. Polupanov. Izvestiya YuFU. — 2010. — № 12 (113). — S. 7‒12.
25. Romanets, Yu. V. Zashchita informatsii v komp´yuternykh sistemakh i setyakh / Yu. V. Romanets, P. A. Timofeev, V. F. Shan´gin. — Moskva : Radio i svyaz´, 2001. — 376 s.
26. Osnovy kriptografii / A. P. Alferov [i dr.]. — Moskva : Gelios ARV, 2002. — 480 s.
27. Chernyshev, Yu. O. Primenenie algoritma murav´inykh koloniy dlya realizatsii kriptoanaliza shifrov perestanovok / Yu. O. Chernyshev, A. S. Sergeev, E. O. Dubrov. Nauchnaya sessiya, posvyashchennaya Dnyu radio : sb. dokladov 67-y Vserossiyskoy konferentsii s Mezhdunarodnym uchastiem. — Moskva, 2012. — S. 71‒75.
28. Morozenko, V. V. Geneticheskiy algoritm dlya kriptoanaliza shifra Vizhinera [Elektronnyy resurs] / V. V. Morozenko, G. O. Eliseev. — Rezhim dostupa : http://vestnik.psu.ru/files/articles/132_6410.p (data obrashcheniya : 24.05.2013).
29. Gorodilov, A. Yu. Kriptoanaliz trigonometricheskogo shifra s pomoshch´yu geneticheskogo algoritma [Elektronnyy resurs] / A. Yu. Gorodilov, A. A. Mitrakov. — Rezhim dostupa : http://vestnik.psu.ru/files/articles/260_27019.p (data obrashcheniya : 24.05.2013).
30. Gorodilov, A. Yu. Kriptoanaliz perestanovochnogo shifra s pomoshch´yu geneticheskogo algoritma [Elektronnyy resurs] / A. Yu. Gorodilov. — Rezhim dostupa : http://vestnik.psu.ru//files/articles/8_83883 (data obrashcheniya : 24.05.2013).
