High-speed parallel implementations of the rainbow method based on perfect tables in a heterogeneous system

The computing power of graphics processing units GPU has increased rapidly, and there has been extensive research on general-purpose computing on GPU GPGPU for cryptographic algorithms such as RSA, Elliptic Curve Cryptosystem ECC, NTRU, and Advanced Encryption Standard. With the rise of GPGPU, commodity computers have become complex heterogeneous GPU+CPU systems. This new architecture poses new challenges and opportunities in high-performance computing. In this paper, we present high-speed parallel implementations of the rainbow method based on perfect tables, which is known as the most efficient time-memory trade-off, in the heterogeneous GPU+CPU system. We give a complete analysis of the effect of multiple checkpoints on reducing the cost of false alarms and take advantage of it for load balancing between GPU and CPU. For GTX460, our implementation is about 1.86 and 3.25 times faster than other GPU-accelerated implementations, RainbowCrack and Cryptohaze, respectively, and for GTX580, 1.53 and 2.40 times faster. Copyright © 2014 John Wiley & Sons, Ltd.