Dachshund Attacks

Description

Solution

1. Step 1Collect e, n, and c
   Connect to the server. It prints the public exponent e, modulus n, and ciphertext c. Copy these values for use in the attack script.
   Learn more

   In RSA encryption, the public key consists of two numbers: the modulus n (a product of two large primes) and the public exponent e. The ciphertext c is produced by computing c = m^e mod n, where m is the plaintext message as an integer.

   These three values -- e, n, and c -- are all that's needed to attempt an attack. The server gives them to you openly because e and n are part of the public key; only d (the private exponent) is supposed to be secret. The challenge is recovering d without factoring n.

2. Step 2Apply Wiener's Attack
   Wiener's attack recovers the private exponent d when d < n^0.25. The owiener Python library implements this attack. Install it with pip, then run the script to recover d and decrypt the ciphertext.
   pip install owienerCopied!

   python3 << 'EOF' import owiener from Crypto.Util.number import long_to_bytes e = <e> n = <n> c = <c> d = owiener.attack(e, n) if d is None: print("Wiener's attack failed -- d may not be small enough.") else: m = pow(c, d, n) print(long_to_bytes(m).decode()) EOFCopied!
   Learn more

   Wiener's attack (1990) exploits a mathematical weakness in RSA when the private exponent d is too small relative to the modulus -- specifically when d < n^0.25 / 3. In that case, a property of continued fraction approximations allows an attacker to recover d efficiently from the public values e and n alone.

   The attack works because RSA's key relationship e*d ≡ 1 (mod φ(n)) means the fraction e/n is very close to k/d for some small integer k. When d is small enough, the convergents of the continued fraction expansion of e/n include k/d as one of its early terms -- making it directly recoverable.

   Real-world significance: Developers sometimes choose small values of d to speed up RSA decryption (since modular exponentiation with a smaller exponent is faster). Wiener's attack demonstrates why this is catastrophic. Modern RSA implementations always use random, full-size private exponents. The long_to_bytes function from pycryptodome converts the recovered plaintext integer back into a readable string.

Flag

picoCTF{...}

Wiener's attack exploits RSA when d < n^0.25 -- always use d larger than the cube root of n.