A new attack to RSA with small private exponent and partial information.

Jorge Jimenez Urroz

Paper 2026/1295

A new attack to RSA with small private exponent and partial information.

Jorge Jimenez Urroz

, Universidad Politecnica de Madrid

Abstract

We give a new algorithm to attack RSA with small private exponent, when some partial information of $p + q$ is given. The algorithm is a very simple modification of original Wiener’s attack with continued fractions, and allows us to factor $n$ whenever $d<n^{(1+\delta)/2}$ if we know a $δ$-fraction of the most significant bits of $n$. The algorithm is unconditional, which is not the case in previous improvements that use Coppersmith method. As a simple example, our algorithm can be applied to break any cryptosystem with modulus $n$ of $512$ bits and $d < n^{0.3}$, given an improvement in the original. attack of Wiener.

Note: Some typos removed.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: rsa continued fractions
Contact author(s): jorge urroz @ upm es
History: 2026-06-25: last of 2 revisions; 2026-06-20: received; See all versions
Short URL: https://ia.cr/2026/1295
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2026/1295,
      author = {Jorge Jimenez Urroz},
      title = {A new attack to {RSA} with small private exponent and partial information.},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1295},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1295}
}