This article is cited in 2 papers

Computational Mathematics

An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis

V. G. Bulavintsev

Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences (Irkutsk, Russian Federation)

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.

Keywords: GPU, CUDA, cryptoanalysis, DPLL, SAT, SIMD.

UDC: 004.272.32, 004.832.25

Received: 10.04.2015

DOI: 10.14529/cmse150306

Bibliographic databases:

•