International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

RSA and a higher degree diophantine equation

Authors:
Abderrahmane Nitaj
Download:
URL: http://eprint.iacr.org/2006/093
Search ePrint
Search Google
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)$.
BibTeX
@misc{eprint-2006-21586,
  title={RSA  and a higher degree diophantine equation},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / RSA cryptosystem, Continued fractions,  Coppersmith's algorithm},
  url={http://eprint.iacr.org/2006/093},
  note={ nitaj@math.unicaen.fr 13216 received 9 Mar 2006},
  author={Abderrahmane Nitaj},
  year=2006
}