Weak RSA Key Discovery on GPGPU

• Autorzy: Russek Paweł , Karbownik Przemysław , Wiatr Kazimierz

Identyfikatory

DOI

10.24425/123561

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cryptography; internet security; intrusion prevention; accelerated computing; caching methods; big numbers computing

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2019
• Tom: Vol. 65, No. 1
• Strony: 25--31
• Opis fizyczny: Bibliogr. 12 poz., tab., wykr.

Twórcy

autor

Russek Paweł

• AGH UST in Department of Electronics at Faculty of Computer Science, Electronics and Telecommunication AGH; and in Academic Computing Centre ‘Cyfronet’ AGH, Poland

autor

Karbownik Przemysław

• Faculty of Computer Science, Electronics and Telecommunication at AGH Univeristy of Science and Technology, Cracow, Poland

autor

Wiatr Kazimierz

• AGH UST in Department of Electronics at Faculty of Computer Science, Electronics and Telecommunication AGH, Poland
• Academic Computing Centre "Cyfronet" AGH, Poland

Bibliografia

• [1] A. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung, and C. Wachter, “Ron was wrong, whit is right,” IACR, Tech. Rep., 2012.
• [2] D. J. Bernstein, “How to find smooth parts of integers,” URL: http://cr. yp. to/papers. html# smoothparts. ID 201a045d5bb24f43f0bd0d97fcf5355a. Citations in this document, vol. 20, 2004.
• [3] N. Heninger, Z. Durumeric, E. Wustrow, and J. A. Halderman, “Mining your ps and qs: Detection of widespread weak keys in network devices.” in USENIX Security Symposium, vol. 8, 2012, p. 1.
• [4] M. Wielgosz, G. Mazur, M. Makowski, E. Jamro, P. Russek, and K. Wiatr, “Analysis of the basic implementation aspects of hardwareaccelerated density functional theory calculations,” Computing and Informatics, vol. 29, no. 6, pp. 989–1000, 2012.
• [5] P. Russek and K. Wiatr, “The enhancement of a computer system for sorting capabilities using fpga custom architecture,” Computing and Informatics, vol. 32, no. 4, pp. 859–876, 2014.
• [6] K. Scharfglass, D. Weng, J. White, and C. Lupo, “Breaking weak 1024bit rsa keys with cuda,” in Parallel and Distributed Computing, Applications and Technologies (PDCAT), 2012 13th International Conference on. IEEE, 2012, pp. 207–212.
• [7] T. Fujita, K. Nakano, and Y. Ito, “Bulk gcd computation using a gpu to break weak rsa keys,” in Parallel and Distributed Processing Symposium Workshop (IPDPSW), 2015 IEEE International. IEEE, 2015, pp. 385– 394.
• [8] W. Diffie and M. Hellman, “New directions in cryptography,” IEEE transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.
• [9] J. Stein, “Computational problems associated with racah algebra,” Journal of Computational Physics, vol. 1, no. 3, pp. 397–405, 1967.
• [10] “Cuda occupancy calculator,” https://developer.download.nvidia.com, accessed: 2018-08-16.
• [11] “Weak keys discovery git repository,” https://git.plgrid.pl/scm/˜plgrussek/weak keys discovery.git, accessed: 2018-08-17.
• [12] “Ack cyfronet agh,” http://www.cyfronet.krakow.pl, accessed: 2018-0818.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).