**Cryptanalysis of RSA with constrained keys**

*Abderrahmane Nitaj*

**Abstract: **Let $n=pq$ 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 $pu$ or $qu$ 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 $\left\vert eY-XF(u)\right\vert$ and $Y$ are suitably small, then the system is insecure.

**Category / Keywords: **RSA cryptosystem, Cryptanalysis, Continued fractions, Bl\"omer-May attack, Coppersmith's algorithm

**Date: **received 9 Mar 2006

**Contact author: **nitaj at math unicaen fr

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20060309:150750 (All versions of this report)

**Short URL: **ia.cr/2006/092

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]