Cryptology ePrint Archive: Report 2019/1050

A New Attack on RSA and Demytko's Elliptic Curve Cryptosystem

Abderrahmane Nitaj and Emmanuel Fouotsa

Abstract: Let $N=pq$ 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)(q-r)v=w$. We show that when the unknown integers $u$, $v$, $w$, $r$ and $s$ are suitably small and $p-s$ or $q-r$ 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.

Category / Keywords: public-key cryptography / RSA, Cryptanalysis, Coppersmith's method, Elliptic Curve Method, Demytko's scheme.

Original Publication (with minor differences): Journal of Discrete Mathematical Sciences and Cryptography

Date: received 16 Sep 2019

Contact author: abderrahmane nitaj at unicaen fr

Available format(s): PDF | BibTeX Citation

Version: 20190918:123745 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]