Cryptanalysis of RSA with constrained keys

Abderrahmane Nitaj

Paper 2006/092

Cryptanalysis of RSA with constrained keys

Abderrahmane Nitaj

Abstract

Let $n = p q$ be an RSA modulus with unknown prime factors and $F$ any function for which there exists an integer $u \neq 0$ satisfying $F (u) \approx n$ and $p u$ or $q u$ is computable from $F (u)$ and $n$ . We show that choosing a public key exponent $e$ for which there exist positive integers $X$ , $Y$ such that $| e Y - X F (u) |$ and $Y$ are suitably small, then the system is insecure.

Metadata

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

BibTeX

@misc{cryptoeprint:2006/092,
      author = {Abderrahmane Nitaj},
      title = {Cryptanalysis of {RSA} with constrained keys},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/092},
      year = {2006},
      url = {https://eprint.iacr.org/2006/092}
}