Paper 2019/1050 Original: eprint.iacr.org/2019/1050 ↗
A New Attack on RSA and Demytko's Elliptic Curve Cryptosystem
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
- Preprint.
- History
- 2019-09-18: last updated
- 2019-09-18: published
- Short URL
- https://ia.cr/2019/1050
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2019/1050}
}