International Association
for Cryptologic Research

We analyze the security of RSA keys where the public exponent $e$ is larger than $\varphi(N)$. While nearly all real-world applications of RSA use a small set of pre-determined constant values for $e$, the literature contains a number of constructions involving large special-form exponents. Examples include proposed countermeasures against Wiener's attack on small RSA private exponents, exponent masking against side channels, a 2018 proposal by Joye and Michalevsky to extend the usefulness of hardware security modules, and a 2023 RSA blind signature construction by Amjad, Yeo, and Yung.

We give an efficient algorithm to factor an RSA modulus $N$ given an integer $a$ that is "close" to a multiple of $\varphi(N)$. That is, we can factor $N$ in polynomial time given $\varphi(N) < a \le N^{3/2}$ if there is an integer $y$ with $|y| \le a N^{-3/4}$ such that $a - y \equiv 0 \bmod \varphi(N)$. Our attack is a special case of Blömer and May's 2004 algorithm using Coppersmith's method that enables us to give stronger bounds for our application range of interest.

We instantiate our attack against several constructions and exhibit families of weak public exponents that do not appear to have been analyzed in the literature. In particular, the Joye and Michalevsky exponent transform permits full key recovery if used for small public exponents. While it is well known that RSA is vulnerable for small private exponent $d$, our work suggests that care must also be taken when generating large public exponents, or when publishing transformed exponents.