Paper 2006/093

RSA and a higher degree diophantine equation

Abderrahmane Nitaj

Abstract

Let $N=pq$ 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 {\log{N}\over \log{32}}$ and small integers $u$, $X$, $Y$ and $Z$ satisfying $$(e+u)Y^m-\psi(N)X^m=Z,$$ where $\psi(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\left(mN^{{1\over 2}+{\a\over m}-\a-\e}\right)$ where $\a$ is defined by $N^{1-\a}=\psi(N)$.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
RSA cryptosystemContinued fractionsCoppersmith's algorithm
Contact author(s)
nitaj @ math unicaen fr
History
2006-03-09: received
Short URL
https://ia.cr/2006/093
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2006/093}},
      url = {https://eprint.iacr.org/2006/093}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.