An evaluation of the RSA private keys and the presence of weak keys

Almazari, Mahmoud M.; Taqieddin, Eyad; Shatnawi, Ahmed S.; Al-Shara, Zakarea

doi:10.47974/JDMSC-1670

Open Access Research Article

An evaluation of the RSA private keys and the presence of weak keys

^*Mahmoud M. AlmazariCorresponding authormmalmazari16@cit.just.edu.joDepartment of Network EngineeringJordan University of Science and TechnologyIrbid, 21110, JordanView full profile → , Eyad TaqieddinDepartment of Network EngineeringJordan University of Science and TechnologyIrbid, 21110, JordanView full profile → , Ahmed S. ShatnawiDepartment of Software EngineeringJordan University of Science and TechnologyIrbid, 21110, JordanView full profile → , Zakarea Al-SharaDepartment of Software EngineeringJordan University of Science and TechnologyIrbid, 21110, JordanView full profile →

* Corresponding author · click or hover a name for details

pp. 2273–2284Vol. 26Issue 8December 2023DOI: 10.47974/JDMSC-1670 Crossmark XML

Received:: 06 Apr 2022
Accepted:: 18 Aug 2022
Published Online:: 17 Nov 2023
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-1670
Pages:: 2273–2284

Abstract

Numerous applications that rely on asymmetric cryptography use the RSA algorithm. It can be applied to digital signatures and the encryption of sensitive data. The secure storage of the private key is essential for the algorithm’s strength. Finding ways to use factorization or other heuristics to determine the value of the private key, was the goal of several academic efforts. Both the Euler totient and the Carmichael functions are used in this study to analyze the private key properties and demonstrate the existence of many private keys for the same public key. We further demonstrate that a universal private key that complies with the FIPS standard exists. Moreover, by taking advantage of a condition imposed by FIPS recommendations, we present a new method for attacking the RSA modulus (N).

Keywords

Cryptanalysis RSA attacks Two private keys Universal RSA key RSA factorization Weak RSA keys RSA FIPS conditions

Subject Classifications

(2010) 68P2594A6094A62

References

[1] Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 21(2) : 120–126 (1978).
[2] Ibrishimova M. Proving the existence of a second private key that decrypts a message encrypted with the RSA encryption algorithm [https://marinaibrishimova.net/docs/otherkeys.pdf]; 2017. (Accessed on 03/19/2022).
[3] Mumtaz M, Ping L. Forty years of attacks on the RSA cryptosystem: A brief survey. Journal of Discrete Mathematical Sciences and Cryptography. 22(1) : 9–29 (2019).
[4] Wiener MJ. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory. 36(3) : 553–558 (1990).
[5] Meng X, Bi J. Weak keys in RSA with primes sharing least significant bits. In: International Conference on Information Security and Cryptology; Springer. p. 278–287 (2009).
[6] Abd Rahman NN, Ariffin MRK. New practical attack on RSA modulus of type n = p2q. International Journal of Pure and Applied Mathematics. 110(4) : 587–607 (2016).
[7] Boneh D, Durfee G, Frankel Y. An attack on RSA given a small fraction of the private key bits. In: International Conference on the Theory and Application of Cryptology and Information Security; Springer. p. 25–34 (1998).
[8] Susilo W, Tonien J, Yang G. Divide and capture: An improved cryptanalysis of the encryption standard algorithm RSA. Computer Standards & Interfaces. 74 : 103470 (2021).
[9] Boneh D, Durfee G. Cryptanalysis of RSA with private key d less than n/sup 0.292. IEEE transactions on Information Theory. 46(4) : 1339–1349 (2000).
[10] Mumtaz M, Ping L. Cryptanalysis of a special case of RSA large decryption exponent using lattice basis reduction method. In: 2021 IEEE 6th International Conference on Computer and Communication Systems (ICCCS); IEEE. p. 714–720 (2021).
[11] Scharfglass K, Weng D, White J, et al. Breaking weak 1024-bit RSA keys with cuda. In: 2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies; IEEE. p. 207–212 (2012).
[12] Russek P, Karbownik P, Wiatr K.Weak RSA key discovery on gpgpu. International Journal of Electronics and Telecommunications. 65 (2019).
[13] Janovsky A, Nemec M, Svenda P, et al. Biased RSA private keys: Origin attribution of gcdfactorable keys. In: European Symposium on Research in Computer Security; Springer. p. 505–524 (2020).
[14] Almazari MM. Universal key calculation and factorization attack [Github repository] (2022). Available from: https://github.com/lcsig/RSAWeakKeys.

Views: 278Downloads: 142Citations: 0