Weak RSA Key Discovery on GPGPU

Authors

  • Paweł Russek AGH University of Science and Technology, Cracow, Poland
  • Przemysław Karbownik AGH University of Science and Technology, Cracow, Poland
  • Kazimierz Wiatr AGH University of Science and Technology, Cracow, Poland

Abstract

We address one of the weaknesses of the RSA ciphering systems \textit{i.e.} the existence of the private keys that are relatively easy to compromise by the attacker. The problem can be mitigated by the Internet services providers, but it requires some computational effort. We propose the proof of concept of the GPGPU-accelerated system that can help detect and eliminate users' weak keys.
We have proposed the algorithms and developed the GPU-optimised program code that is now publicly available and substantially outperforms the tested CPU processor. The source code of the OpenSSL library was adapted for GPGPU, and the resulting code can perform both on the GPU and CPU processors.
Additionally, we present the solution how to map a triangular grid into the GPU rectangular grid \textendash{} the basic dilemma in many problems that concern pair-wise analysis for the set of elements.
Also, the comparison of two data caching methods on GPGPU leads to the interesting general conclusions.
We present the results of the experiments of the performance analysis of the selected algorithms for the various RSA key length, configurations of GPU grid, and size of the tested key set.

References

ACK Cyfronet AGH. http://www.cyfronet.krakow.pl. Accessed: 2018-08-18.

CUDA Occupancy Calculator. https://developer.download.nvidia.com/compute/cuda/CUDA_Occupancy_calculator.xls. Accessed: 2018-08-16.

Bernstein D.J.: How to find smooth parts of integers. In: URL: http://cr. yp.to/papers. html# smoothparts. ID 201a045d5bb24f43f0bd0d97fcf5355a. Citations in this document, vol. 20, 2004.

Diffie W., Hellman M.: New directions in cryptography. In: IEEE transactions on Information Theory, vol. 22(6), pp. 644–654, 1976.

Fujita T., Nakano K., Ito Y.: Bulk GCD computation using a GPU to break weak RSA keys. In: Parallel and Distributed Processing Symposium Workshop (IPDPSW), 2015 IEEE International, pp. 385–394. IEEE, 2015.

Heninger N., Durumeric Z., Wustrow E., Halderman J.A.: Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. In: USENIX Security Symposium, vol. 8, p. 1. 2012.

Lenstra A., Hughes J.P., Augier M., Bos J.W., Kleinjung T., Wachter C.: Ron was wrong, Whit is right. Tech. rep., IACR, 2012.

Scharfglass K., Weng D., White J., Lupo C.: Breaking weak 1024-bit RSA keys with CUDA. In: Parallel and Distributed Computing, Applications and Technologies (PDCAT), 2012 13th International Conference on, pp. 207–212. IEEE, 2012.

Stein J.: Computational problems associated with Racah algebra. In: Journal of Computational Physics, vol. 1(3), pp. 397–405, 1967.

Downloads

Published

2019-02-16

Issue

Section

Applied Informatics