liveBook · Manning

Wiener’s attack

As explained in Hacking Cryptography

Wiener's theorem states that an RSA private exponent can be efficiently recovered from the public key when it satisfies a specified smallness bound.

Wiener’s attack recovers an RSA private exponent from the public key when the exponent is unusually small: d < 1/3 n^(1/4). section 8.4.2

The attack treats e/n as a continued fraction. Its convergents supply candidate values for d; testing modular decryption identifies the correct private exponent. section 8.4.2

Executable attack

A vulnerable Go generator deliberately chooses d below the bound, computes e as the inverse of d modulo φ(n), and encrypts a message. The exploit computes continued-fraction convergents of e/n, tests each denominator, and successfully decrypts the ciphertext.

How Hacking Cryptography covers it

How deep it goes
Implements continued fractions, convergents, candidate testing, and decryption verification, while stopping at the stated Wiener bound.
Examples
Uses Go key-generation code, convergent calculations, RSA encryption and decryption, and a passing exploit test.
What it assumes
Assumes RSA public-key parameters and modular exponentiation, while developing continued-fraction and convergent calculations in code.
What you can do after
Diagnose/debug RSA keys by testing continued-fraction candidates against ciphertext decryption.
How it connects
Connects RSA, private exponents, Euler’s totient function, modular inverses, and continued fractions.
Cover of Hacking Cryptography
liveBookmanning.com
Read Hacking Cryptography on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.