Implications of the arithmetic ratio of prime numbers for RSA security

Ivanov, Andrey ; Stoianov, Nikolai

International Journal of Applied Mathematics and Computer Science, Tome 33 (2023) no. 1, pp. 57-70.

Résumé

The most commonly used public key cryptographic algorithms are based on the difficulty in solving mathematical problems such as the integer factorization problem (IFP), the discrete logarithm problem (DLP) and the elliptic curve discrete logarithm problem (ECDLP). In practice, one of the most often used cryptographic algorithms continues to be the RSA. The security of RSA is based on IFP and DLP. To achieve good data security for RSA-protected encryption, it is important to follow strict rules related to key generation domains. It is essential to use sufficiently large lengths of the key, reliable generation of prime numbers and others. In this paper the importance of the arithmetic ratio of the prime numbers which create the modular number of the RSA key is presented as a new point of view. The question whether all requirements for key generation rules applied up to now are enough in order to have good levels of cybersecurity for RSA based cryptographic systems is clarified.

Détail

Keywords: public key cryptography, RSA encryption, public key generation rules, kleptography, fusion of number balance
Mots-clés : kryptografia klucza publicznego, szyfrowanie RSA, kleptografia, bilans liczbowy

Bibliographie

[1] [1] Adj, G., Canales-Martínez, I., Cruz-Cortés, N., Menezes, A., Oliveira, T., Rivera-Zamarripa, L. and Rodríguez-Henríquez, F. (2018). Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields, Advances in Mathematics of Communications 12(4): 741-759.

[2] [2] Ahlswede, R. (2016). Elliptic curve cryptosystems, in A. Ahlswede et al. (Eds), Hiding Data Selected Topics: Foundations in Signal Processing, Communications and Networking, Vol. 12, Cham, pp. 225-336, DOI: 10.1007/978-3-319-31515-7_4.

[3] [3] Alwen, J., Dodis, Y. and Wichs, D. (2009). Leakage-resilient public-key cryptography in the bounded-retrieval model, in S. Halevi (Ed.), Advances in Cryptology, CRYPTO 2009, Springer, Berlin, pp. 36-54.

[4] [4] Anderson, R.J. (1993). Practical RSA trapdoor, Electronics Letters 29(11): 995.

[5] [5] Bressoud, D.M. and Wagon, S. (2000). Course in Computational Number Theory, Key College Publishing, Emeryville.

[6] [6] Devidas, S., Rao Y.V., S. and Rekha, N.R. (2021). A decentralized group signature scheme for privacy protection in a blockchain, International Journal of Applied Mathematics and Computer Science 31(2): 353-364, DOI: 10.34768/amcs-2021-0024.

[7] [7] Diffie, W. and Hellman, M. (1976). New directions in cryptography, IEEE Transactions on Information Theory 22(6): 644-654, DOI: 10.1109/TIT.1976.1055638.

[8] [8] Dodis, Y., Franklin, M., Katz, J., Miyaji, A. and Yung, M. (2004). A generic construction for intrusion-resilient public-key encryption, in T. Okamoto (Ed.), Topics in Cryptology, CT-RSA 2004, Springer, Berlin/Heidelberg, pp. 81-98.

[9] [9] Elgamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory 31(4): 469-472, DOI: 10.1109/TIT.1985.10570748.

[10] [10] Erra, R. and Grenier, C. (2009). The Fermat factorization method revisited, Cryptology ePrint Archive, Report 2009/318, https://eprint.iacr.org/2009/318.pdf.

[11] [11] ETSI (2007). Electronic signatures and infrastructures (ESI): Algorithms and parameters for secure electronic signatures. Part 1: Hash functions and asymmetric algorithms, TS 102 176-1-V2.1.1, European Telecommunications Standards Institute, Valbonne, h ttps://www.etsi.org/deliver/etsi_ts/10 2100_102199/10217601/02.01.01_60/ts_10 217601v020101p.pdf.

[12] [12] Gordon, D. (2011). Discrete logarithm problem, in H.C.A. van Tilborg and S. Jajodia (Eds), Encyclopedia of Cryptography and Security, Springer, Boston, pp. 352-353, DOI: 10.1007/978-1-4419-5906-5_445.

[13] [13] Kaliski, B. (2011). Euler’s totient function, in H.C.A. van Tilborg and S. Jajodia (Eds), Encyclopedia of Cryptography and Security, Springer, Boston, pp. 430-430.

[14] [14] Kaliski, B.S.J. (1993). Anderson’s RSA trapdoor can be broken, Electronics Letters 29(15): 1387-1388.

[15] [15] Markelova, A.V. (2021). Embedding asymmetric backdoors into the RSA key generator, Journal of Computer Virology and Hacking Techniques 17(1): 37-46, DOI: 10.1007/s11416-020-00363-x.

[16] [16] Menezes, A.J., Van Oorschot, P.C. and Vanstone, S.A. (1996). Handbook of Applied Cryptography, CRC Press, Boca Raton.

[17] [17] NIST (2019). Recommendation for pair-wise key establishment using integer factorization cryptography, NIST SP 800-56Br2, National Institute of Standards and Technology, Gaithersburg, DOI: 10.6028/NIST.SP.800-56Br2.

[18] [18] Pomerance, C. (1982). Analysis and comparison of some integer factoring algorithms, in H.W. Lenstra and R. Tijdeman (Eds), Computational Methods in Number Theory, Math Centrum, Amsterdam, pp. 89-139.

[19] [19] Rivest, R. L., Shamir, A. and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21(2): 120-126, DOI: 10.1145/359340.359342.

[20] [20] Sako, K. (2011). Digital signature schemes, in H.C.A. van Tilborg and S. Jajodia (Eds), Encyclopedia of Cryptography and Security, Springer, Boston, pp. 343-344.

[21] [21] Smart, N., Rijmen, V., Gierlichs, B., Paterson, K., Stam, M., Warinschi, B. and Watson, G. (2014). Algorithms, key size and parameters report 2014, European Union Agency for Network and Information Security (ENISA), Brussels, https://www.enisa.europa.eu/publications/algorithms-key-size-and-parametersreport-2014.

[22] [22] Svenda, P., Nemec, M., Sekan, P., Kvasnovsky, R., Formanek, D., Komarek, D. and Matyas, V. (2016). The million-key question-Investigating the origins of RSA public keys, 25th USENIX Security Symposium (USENIX Security 16), Austin, USA, pp. 893-910.

[23] [23] Yan, S.Y. (2019). Cybercryptography: Applicable Cryptography for Cyberspace Security, Springer, Cham, chapter “Elliptic curve cryptography”, pp. 343-398.

[24] [24] Yasuda, M., Shimoyama, T., Kogure, J. and Izu, T. (2012). On the strength comparison of the ECDLP and the IFP, in I. Visconti and R. De Prisco (Eds), Security and Cryptography for Networks, Springer, Berlin, pp. 302-325.

[25] [25] Young, A. and Yung, M. (1996). The dark side of “black-box” cryptography or: Should we trust capstone?, in N. Koblitz (Ed.), Advances in Cryptology, CRYPTO’96, Springer, Berlin/Heidelberg, pp. 89-103.

[26] [26] Young, A. and Yung, M. (1997). Kleptography: Using cryptography against cryptography, in W. Fumy (Ed.), Advances in Cryptology, EUROCRYPT’97, Springer, Berlin/Heidelberg, pp. 62-74.