Cryptanalysis of RSA with Small Multiplicative Inverse of $\varphi(N)$ Modulo $e$ and with a Composed Prime Sum $p+q$

Abstract

In this paper, we mount an attack on RSA when $\varphi(N)$ has small multiplicative inverse $k$ modulo $e$, the public encryption exponent. For $k\leq N^\delta,$ the attack bounds for $\delta$ are described by using lattice based techniques. The bound for $\delta$ depends on the prime difference $p-q=N^\beta$ and the maximum bound for $\delta$ is $\alpha-\sqrt{\frac{\alpha}{2}}$ for $e=N^\alpha$ and for $\beta\approx0.5$. If the prime sum $p+q$ is of the form $p+q=2^nk_0+k_1$ where $n$ is a given positive integer and $k_0$ and $k_1$ are two suitably small unknown integers then the maximum bound for $\delta$ can be improved for $\beta\approx0.5$.