Worsehelp - RSA Wiener Attack

This challenge exposes a custom RSA key generation flow where the client supplies two large integers a and b that “harden” the private exponent via an exponentiation step. By crafting a and b carefully, we force the private exponent to be small and then recover it using Wiener’s attack.

• Service: nc challenge.secso.cc 7008
• Attachment: chall.py
• Flag format: K17{...}
• Solution Files: GitHub - worsehelp

Challenge Code Summary

The server does:

1
from Crypto.Util.number import isPrime, getStrongPrime
2
from os import urandom
3
from math import gcd
4
from secrets import FLAG
5

6
a, b = map(int, input("Enter your secure parameters a, b …").split(","))
7

8
if a.bit_length() < 1024 or b.bit_length() < 1024 or not isPrime(a) or isPrime(b):
9
    print("Your parameters are not secure"); quit()
10

11
p, q = getStrongPrime(1024), getStrongPrime(1024)
12
phi = (p - 1) * (q - 1)
13

14
# to harden d
15
r = ((a**2 + b**2 + 3*a + 3*b + a*b) * pow(2 * a * b + 7, -1, phi)) % phi
16
while gcd(k := int.from_bytes(urandom(32), "big"), phi) != 1:
17
    continue
18

19
d = pow(k, r, phi); d |= 1
20

21
e = pow(d, -1, phi)
22

23
m = int.from_bytes(FLAG, "big")
24
c = pow(m, e, n)
25
print(f"{c = }")
26
print(f"{e = }")
27
print(f"{n = }")

You choose a and b (with constraints: a is a 1024+ bit prime, b is a 1024+ bit composite). The server then computes:

• r ≡ (a² + b² + ab + 3a + 3b) · (2ab + 7)⁻¹ (mod φ)
• d = k^r (mod φ) for a random 256-bit k, and e = d⁻¹ (mod φ)

Core Idea — Force r = 2

We would like to make r a small known integer. If we can enforce:

1
a² + b² + ab + 3a + 3b = S · (2ab + 7)

then r ≡ S (mod φ). Choosing S = 2 yields r = 2, hence d = k² (mod φ). Since k is 256-bit, k² is ≈512-bit — a small private exponent for a 2048-bit RSA modulus, which is vulnerable to Wiener’s attack in many instances.

Rewriting the identity with S=2 gives a quadratic Diophantine equation:

1
a² + b² - 3ab + 3a + 3b - 14 = 0

Let u = a - 3 and v = b - 3. Then the equation becomes:

1
u² + v² - 3uv = 5

Setting x = u - v and y = u + v transforms it to a Pell-type equation:

1
y² - 5x² = -20

One particular solution is (y₀, x₀) = (5, 3). The fundamental unit of x² - 5y² = 1 is (9, 4), so all solutions to our negative Pell can be generated by:

1
(y + x√5) = (y₀ + x₀√5) · (9 + 4√5)^k,  for k ≥ 0

Mapping back via u = (y + x)/2, v = (y - x)/2, then a = u + 3, b = v + 3, we obtain infinitely many integer pairs (a, b) that satisfy the required identity with S = 2.

In particular, for any integer k ≥ 0:

• (a, b) satisfies a² + b² + ab + 3a + 3b = 2(2ab + 7) ⇒ r = 2
• We then get d = k² (mod φ) which is small enough to often trigger Wiener’s attack

Practical Considerations

• Constraints: ensure a is prime and b is composite, both ≥1024 bits. Use Miller–Rabin for primality checks.
• Invertibility hiccup: the server sometimes aborts with “base is not invertible” when gcd(2ab+7, φ) ≠ 1 for the freshly generated p,q. This depends on random p,q. Just reconnect/retry; with fixed (a,b) it will usually work within a few attempts.
• Wiener’s attack succeeds probabilistically depending on how small d is relative to n. With r = 2, d ≈ k² is typically ~512 bits for a 2048-bit modulus, which is at the cusp of the classic Wiener bound (d < n^(1/4)/3). In practice, it works frequently; if not, retry to get a more favorable instance.

Exploit Script

The file solve.py in this repository implements:

• Pell parametrization to generate (a,b) with r=2
• Selection of a 1024+ bit prime a and composite b
• Remote interaction to fetch c, e, n
• Wiener’s attack to recover d and decrypt c

Usage:

python3 solve.py --host challenge.secso.cc --port 7008 --attempts 12

If one attempt fails (either invertibility or Wiener), it retries automatically.

Example Outcome

On a successful run, decryption yields the flag:

1
K17{v137a_83A75_5MAlL_ds_aNy_daY}

Takeaways

• A “hardened” exponent mechanism can be subverted if the user controls parameters that algebraically fix the exponent to a small value modulo φ.
• For RSA, small private exponents remain dangerous due to continued fraction attacks (Wiener).
• Pell equations appear in unexpected places in cryptography.
• Mathematical elegance can bypass security measures.

Credits: Derived the Pell parametrization, implemented a param search for a and b, handled remote edge-cases, and used Wiener’s attack to recover the key and decrypt the flag.

Full Solution: GitHub - worsehelp