Abstract:
In this work we assess performance of CPU and GPU implementations of some widely-used cryptanalytic combinatorial algorithms. In particular, we analyze obstacles for effective GPU im-plementation of “smart” combinatorial algorithms. Next, to alleviate performance problems arising from inefficient processing of conditional expressions in SIMD-devices we devise some special control flow graph transformation techniques. Finally, we demonstrate that contemporary GPU's memory access schemes are incompatible with typical memory access patterns of “smart” combinatorial algorithms studied. We use DES and A5/1 cryptographic functions as test cases.
Citation:
V. G. Bulavintsev, “An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis”, Vestn. YuUrGU. Ser. Vych. Matem. Inform., 4:3 (2015), 67–84
\Bibitem{Bul15}
\by V.~G.~Bulavintsev
\paper An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis
\jour Vestn. YuUrGU. Ser. Vych. Matem. Inform.
\yr 2015
\vol 4
\issue 3
\pages 67--84
\mathnet{http://mi.mathnet.ru/vyurv6}
\crossref{https://doi.org/10.14529/cmse150306}
\elib{https://elibrary.ru/item.asp?id=23790225}
Linking options:
https://www.mathnet.ru/eng/vyurv6
https://www.mathnet.ru/eng/vyurv/v4/i3/p67
This publication is cited in the following 2 articles:
Alexandr Alexandrovich Kuznetsov, Oleksandr Volodymyrovych Potii, Nikolay Alexandrovich Poluyanenko, Yurii Ivanovich Gorbenko, Natalia Kryvinska, Studies in Systems, Decision and Control, 375, Stream Ciphers in Modern Real-time IT Systems, 2022, 379
Vadim Bulavintsev, Dmitry Zhdanov, “Constructing K-d Tree on GPU through Treelet Restructuring”, Proceedings of the 30th International Conference on Computer Graphics and Machine Vision (GraphiCon 2020). Part 2, 2020, short56-1