Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Journal of Discrete Mathematical Sciences and Cryptography
Keywords
RSACryptanalysisCoppersmith's methodElliptic Curve MethodDemytko's scheme.
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
2019-09-18: received
Short URL
https://ia.cr/2019/1050
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1050,
      author = {Abderrahmane Nitaj and Emmanuel Fouotsa},
      title = {A New Attack on RSA and Demytko's Elliptic Curve Cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1050},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1050}},
      url = {https://eprint.iacr.org/2019/1050}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.