Algorytmy inspirowane naturą w kryptoanalizie

• Autorzy: Polak I. , Boryczka M.

Warianty tytułu

EN

Cryptanalysis using nature-inspired algorithms

• Języki publikacji: PL

Abstrakty

PL

W dzisiejszych czasach ochrona informacji jest niezwykle istotna, a jednym z elementów zapewniających ową ochronę jest kryptografia. Tu z kolei ważną rolę odgrywa kryptoanaliza, która pozwala badać bezpieczeństwo używanych szyfrów. Oprócz typowo analitycznego podejścia do łamania szyfrów (jak kryptoanaliza różnicowa, kryptoanaliza liniowa czy analiza statystyczna) od kilkunastu lat do tego celu zaprzęga się różnego rodzaju niedeterministyczne systemy inspirowane naturą. Użycie takich technik nie jest do końca intuicyjne – w kryptoanalizie często ważne jest znalezienie jednego konkretnego klucza (rozwiązania optymalnego), a każde inne rozwiązanie daje kiepskie rezultaty, nawet jeśli jest blisko optimum globalnego.

EN

Nowadays protection of information is very crucial and cryptography is a significant part of keeping information secure. Here in turn cryptanalysis plays an important role by examining the safety of ciphers used. Besides the analytical approach to ciphers breaking (eg. differential cryptanalysis, linear cryptanalysis, statistical analysis) for this purpose there are several kinds of non-deterministic, inspired by nature systems applied. It is not intuitive - as in cryptanalysis often it is important to find the exact key used (optimal solution) and every other solution is giving poor results, even if it is near global optimum.

Słowa kluczowe

PL

kryptoanaliza; metaheurystyka; algorytmy optymalizacji; kryptografia

EN

cryptanalysis; metaheuristic; optimization algorithms; cryptology

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 185--197
• Opis fizyczny: Bibliogr. 39 poz., rys., schem., tab.

Twórcy

autor

Polak I.

• Uniwersytet Śląski, Instytut Informatyki

autor

Boryczka M.

• Uniwersytet Śląski, Instytut Informatyki

Bibliografia

• [1] A. A. Abd, H. A. Younis, W. S., Awad, it Attacking of stream Cipher Systems Using a Genetic Algorithm, Journal of the University of Thi Qar, Volume 6, pp.1–6, 2011.
• [2] A. Almarimi, A. Kumar, I. Almerhag, N. Elzoghbi, A new approach for data encryption using genetic algorithms, 2006.
• [3] A. G. Bafghi, R. Safabakhsh, B. Sadeghiyan, Finding the differential characteristics of block ciphers with neural networks, Information Sciences, Vol. 178, No 15, pp. 3118–3132, 2008.
• [4] K. P. Bergmann, Cryptanalysis Using Nature-Inspired Optimization Algorithms (master’s thesis), 2007.
• [5] L. Blum, M. Blum, M. Shub, A Simple Unpredictable Pseudo Random Number Generator, SIAM J. Comput. 15, 2, pp. 364–383, 1986.
• [6] V. Cerny, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications, pp. 41–51, 1985.
• [7] J. A. Clark, Invited paper. Nature-inspired cryptography: Past, present and future, Proceedings of the 2003 Congress on Evolutionary Computation CEC2003, pp. 1647–1654, 2003.
• [8] M. Dorigo, D. Di Caro, L. M. Gambardella, Ant Algorithms for Discrete Optimization, Artificial Life, pp. 137–172, 1999.
• [9] P. Garg, A. Shastri, An Improved Cryptanalytic Attack on Knapsack Cipher using Genetic Algorithm, World Academy of Science, Engineering and Technology, pp.553–560, 2007.
• [10] p. Garg, A Comparison between Memetic algorithm and Genetic algorithm for the cryptanalysis of Simplified Data Encryption Standard algorithm, International Journal of Network Security & Its Applications (IJNSA), Vol.1, No 1, pp.34–42, April 2009.
• [11] F. Glover, Future Paths for Integer Programming and Links to Artificial Intelligence, Comput. Oper. Res., pp. 533–549, 1986.
• [12] F. Glover, Tabu Search Part I, ORSA Journal on Computing, pp. 190–206, 1989.
• [13] G. Hospodar, B. Gierlichs, E. D. Mulder, I. Verbauwhede, J. Vandewalle, Machine learning in side-channel analysis: a first study, J Cryptogr Eng (2011), pp.293–302, 2011.
• [14] P. Itaima, M. C. Riffa, Applying Differential Cryptanalysis for XTEA using a Genetic Algorithm, 2008.
• [15] J. Kennedy, R. Eberhart, Particle swarm optimization, IEEE International Conference on Neural Networks, Proceedings, pp. 1942–1948, 1995.
• [16] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing, Science, Number 4598, pp. 671–680, 1983 .
• [17] E. C. Laskari, G. C. Meletiou, Y. C. Stamatiou, M. N. Vrahatis, Applying evolutionary computation methods for the cryptanalysis of Feistel ciphers, Applied Mathematics and Computation 184(1), pp. 63–72, 2007.
• [18] E. C. Laskari, G. C. Meletiou, Y. C. Stamatiou, D. K. Tasoulis, M. N. Vrahatis, Assessing the effectiveness of artificial neural networks on problems related to elliptic curve cryptography, Mathematical and Computer Modelling, Vol.46, No 12, pp.174–179, 2007.
• [19] J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory, Vol.15, No 1, pp.122–127, 1969.
• [20] Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne, Warszawa, Wydawnictwa Naukowo-Techniczne, 2003.
• [21] Z. Michalewicz, D. B. Fogel, Jak to rozwiązać czyli Nowoczesna heurystyka, Warszawa, Wydawnictwa Naukowo-Techniczne, 2006.
• [22] W. Millan, A. Clark, E. Dawson, Heuristic design of cryptographically strong balanced Boolean functions, Advances in Cryptology EUROCRYPT’98, Lecture Notes in Computer Science, pp. 489–499, 1998.
• [23] T. M. Mitchell, Machine Learning, McGraw-Hill Inc., New York, NY, USA, 1997.
• [24] P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, California Institute of Technology, 1989.
• [25] N. Nalini, G. Raghavendra Rao, A new encryption and decryption algorithm combining the features of genetic algorithm (GA) and cryptography, 1999.
• [26] N. Nalini, G. Raghavendra Rao, Cryptanalysis of Simplified Data Encryption Standard via Optimisation Heuristics, 2006.
• [27] N. Nalini, G. Raghavendra Rao, Experiments on Cryptanalysing Block Ciphers via Evolutionary Computation Paradigms, 2006.
• [28] A. M. Odlyzko, The rise and fall of knapsack cryptosystems, Cryptology and Computational Number Theory, pp. 75–88, 1990.
• [29] K. M. Passino, Bacterial Foraging Optimization, Int. J. Swarm. Intell. Res., vol. 1, no 1, pp. 1–16, 2010.
• [30] D. T. Pham i inni, The bees algorithm, Technical report, Manufacturing Engineering Centre, Cardiff University, UK, 2005.
• [31] I. Polak, M. Boryczka, Breaking LFSR Using Genetic Algorithm, Computational Collective Intelligence, Technologies and Applications, pp. 731–738, 2013.
• [32] M. D. Russell, J. A. Clark, S. Stepney, Making the Most of Two Heuristics: Breaking Transposition Ciphers with Ants, Evolutionary Computation, CEC ’03, Vol. 4, pp. 2653–2658, 2003.
• [33] B. Schneier, Kryptografia dla praktyków, Wyd. 2, Warszawa, Wydawnictwa Naukowo-Techniczne, 2002.
• [34] G. Selvi, T. Purusothaman, Cryptanalysis of Simple Block Ciphers using Extensive Heuristic Attacks, European Journal of Scientific Research, Vol.78 No.2 (2012), pp.198–221, 2012.
• [35] M. Srinivas, L. M. Patnaik, Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE Transactions on Systems, Man, and Cybernetics, 4, pp. 656–667, 1994.
• [36] J. Song, H. Zhang, Q. Meng, Z. Wang, Cryptanalysis of Four-Round DES Based on Genetic Algorithm International Conference on Wireless Communications, Networking and Mobile Computing. WiCom. pp. 2326–2329, 2007.
• [37] R. Storn, K. Price, Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, J. of Global Optimization, vol. 11, no 4, pp. 341–359, 1997.
• [38] X. -S. Yang, S. Deb, Cuckoo Search via Lvy Flights, NaBIC, IEEE, pp. 210–214, 2009.
• [39] I. F. T. Yaseen, H. V. Sahasrabuddhe, Breaking multiplicative knapsack ciphers using a genetic algorithm, Proceedings of the International Conference on Knowledge Based Computer Systems, p.129–139, 1998.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).