Uncover Weak Keys of RSADemo2 Software Using Batch Greatest Common Divisor Algorithm

  • Luqman Hakeem Zainul Hisham Department of Mathematics and Statistics, Universiti Putra Malaysia, 43400 UPM Serdang, Malaysia
  • Muhammad Asyraf Asbullah Institute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Malaysia
  • Saidu Isah Abubakar Department of Mathematics, Sokoto State University, Airport Road Sokoto, PMB 2134, Nigeria

Abstract

RSA encryption is crucial for protecting our privacy and allowing us to transfer information over the internet without being concerned that unauthorised people will see it. RSA encryption can be deemed insecure in a variety of ways. This project focuses on factoring RSA moduli to detect weak RSA keys generated by an RSA simulator software called RSADemo2 (v2.1) (Darby, 2016). The approach used to factor RSA moduli is collecting samples from RSADemo2 and then using the batch-greatest common divisor (gcd) method. In addition, we will be using Maple software to simulate the batch-gcd algorithm on the collected samples.

References

Bernstein, D. J., CDAhang, Y. A., Cheng, C. M., Chou, L. P., Heninger, N., Lange, T., & Van Someren, N. (2013). Factoring RSA keys from certified smart cards: Coppersmith in the wild. In Advances in Cryptology-ASIACRYPT 2013: 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part II 19 (pp. 341-360). Springer Berlin Heidelberg.
Cloostermans, B. (2012). Quasi-linear GCD computation and factoring RSA moduli (Doctoral dissertation, Thesis (Eindhoven University of Technology, Department of Mathematics and Computer Science, 2012)).
Darby, G. (2016). RSA Public Key Demo Program, http://delphiforfun.org/programs/math topics/RSA KeyDemo.htm.
Diffie, W., & Hellman, M. E. (2022). New directions in cryptography. In Democratizing Cryptography: The Work of Whitfield Diffie and Martin Hellman (pp. 365-390).
Diffie, W., & Hellman, M. E. (1976). New directions in cryptography. IEEE transactions on Information Theory, 22(6), 644-654.
Heninger, N., Durumeric, Z., Wustrow, E., & Halderman, J. A. (2012). Mining your Ps and Qs: Detection of widespread weak keys in network devices. In 21st USENIX Security Symposium (USENIX Security 12) (pp. 205-220).
Heninger, N., & Shacham, H. (2009). Reconstructing RSA private keys from random key bits. In Annual International Cryptology Conference (pp. 1-17). Berlin, Heidelberg: Springer Berlin Heidelberg.
Kraft, J., & Washington, L. (2018). An introduction to number theory with cryptography. CRC press.
Lenstra, A. K., Hughes, J. P., Augier, M., Bos, J. W., Kleinjung, T., & Wachter, C. (2012). Public keys. In Annual Cryptology Conference (pp. 626-642). Berlin, Heidelberg: Springer Berlin Heidelberg.
Milanov, E. (2009). The RSA algorithm. RSA laboratories, 1-11.
Mironov, I. 2012, Factoring RSA Moduli. Part I., https://windowsontheory.org/2012/05/15/979/.
Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126
Published
2023-11-19
How to Cite
ZAINUL HISHAM, Luqman Hakeem; ASBULLAH, Muhammad Asyraf; ABUBAKAR, Saidu Isah. Uncover Weak Keys of RSADemo2 Software Using Batch Greatest Common Divisor Algorithm. Menemui Matematik (Discovering Mathematics), [S.l.], v. 45, n. 2, p. 177-184, nov. 2023. ISSN 0126-9003. Available at: <https://myjms.mohe.gov.my/index.php/dismath/article/view/24755>. Date accessed: 26 july 2024.

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.