A new attack on RSA and Demytko's elliptic curve cryptosystem. (3rd April 2019)

• Record Type: Journal Article
• Authors: Nitaj, Abderrahmane; Fouotsa, Emmanuel
• Is Part Of: Journal of discrete mathematical sciences & cryptography. Volume 22:Number 3(2019)
• Page Start: 391
• Page End: 409
• Publication Date: 2019-04-03
• Subjects: (2010) 11K60 -- 14H52; RSA -- Cryptanalysis -- Coppersmith's method -- Elliptic curve method -- Demytko's scheme; Computer science -- Mathematics -- Periodicals; Cryptography -- Periodicals; Computer science -- Mathematics; Cryptography; Periodicals; 004.0151
• DOI: 10.1080/09720529.2019.1587827
• Languages: English
• ISSNs: 0972-0529

Abstract

Abstract: Let N = p q be an RSA modulus and e be a public exponent. Numerous attacks on RSA exploit the arithmetical properties of the key equation ed – k ( p – 1)( q – 1) = 1. In this paper, we study the more general equation eu – ( p – s )( p - r ) v = w . We show that when the unknown integers u, v, w, r and s are suitably small and p - s or p - s is factorable using the Elliptic Curve Method for factorization ECM, then one can break the RSA system. As an application, we propose an attack on Demytko's elliptic curve cryptosystem. Our method is based on Coppersmith's technique for solving multivariate polynomial modular equations.