RSA  and a higher degree diophantine equation

Abderrahmane Nitaj

Paper 2006/093

RSA and a higher degree diophantine equation

Abderrahmane Nitaj

Abstract

Let $N = p q$ be an RSA modulus where $p$ , $q$ are large primes of the same bitsize. We study the class of the public exponents $e$ for which there exist an integer $m$ with $1 \leq m \leq \frac{\log N}{\log 32}$ and small integers $u$ , $X$ , $Y$ and $Z$ satisfying $(e + u) Y^{m} - ψ (N) X^{m} = Z,$ where $ψ (N) = (p + 1) (q - 1)$ . First we show that these exponents are of improper use in RSA cryptosystems. Next we show that their number is at least $O (m N^{\frac{1}{2} + \frac{\a}{m} - \a - \e})$ where $\a$ is defined by $N^{1 - \a} = ψ (N)$ .

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: RSA cryptosystem Continued fractions Coppersmith's algorithm
Contact author(s): nitaj @ math unicaen fr
History: 2006-03-09: received
Short URL: https://ia.cr/2006/093
License: CC BY

BibTeX

@misc{cryptoeprint:2006/093,
      author = {Abderrahmane Nitaj},
      title = {{RSA}  and a higher degree diophantine equation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/093},
      year = {2006},
      url = {https://eprint.iacr.org/2006/093}
}