Development and investigation of parallel model of bee colony algorithms for cryptanalysis problem solving

Introduction. The research area of “natural calculation” is now widely used for the solution to optimization NP-complete problems including combinatorial tasks of cryptanalysis. A quick overview of the publications devoted to the application of the natural (bioinspired) methods for cryptanalysis is provided. The main work objective is to investigate a possibility of applying bee colony algorithms to the realization of block cipher cryptanalysis. Materials and Methods . The known bee colony techniques belonging to a relatively new class of the bioinspired optimization methods that simulate the processes occurring in wildlife are applied to solve this optimization problem. The description and the block diagram of the bee colony algorithm for the solution to a cryptanalysis task are provided; basic operations performed in parallel at the global level are noted. In the following, a set of independent operators allowing for the concurrent execution is defined. For this purpose, information-logical flowgraphs of the algorithm with the input control and information links are built, as well as matrices of succession, logical incompatibility, and independence are formed. This matrix of independence allows the definition of a set of algorithm operators admitting parallel execution. At that, the dimensionality of the maximal internally stable sets defines the maximum number of the processors used for the algorithm implementation. Research Results . Theoretical estimates of time complexity of the bee colony algorithm are given as the key data. Besides, the problem solution is provided: to find the required smallest number of processors of the homogeneous parallel computing systems with distributed memory, and a uniform plan for the implementation of operators for them, for the cryptanalysis algorithm based on the constructed information-logical graph data-logical graph, and for the preset time. The assessment of the wanted smallest number of processors for the cryptanalysis algorithm implementation, and the evaluation of the total time of the algorithm realization are given. Discussion and Conclusions. The basic research results are: the development of the bee colony algorithm used for the cryptanalysis task solution; the description of its flowchart and the principal par-allel executed stages; the construction of a matrix of independence; the evaluation of the number of processors for the algorithm imple-mentation. It should be noted (and it was observed in the previous works) that the distinctive feature of applying the bioinspired meth-ods of cryptanalysis is the applicability of the encryption-decryption algorithm as a criterion function for the evaluation of the key ac-ceptability defined by the bioinspired method operations. Thus, it can be affirmed that when using the bioinspired methods, the secret key definition process depends not so much on the complexity of the encryption transformations, as on the bioinspired method itself which should provide a sufficient diversity of the key generation

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

1. 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).

2. 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).

3. 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).

4. 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).

5. 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).

6. 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).

7. 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).

8. 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).

9. 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).

10. 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).

11. 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).

12. 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).

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

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

15. 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).

16. 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).