xponent

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: continued_fraction_expansion, wiener_attack

Summary

Walkthrough of the CUSTOM Crypto xponent. Task: RSA encryption with unusually large public exponent e (close to n). Solution: Wiener's attack using continued fraction expansion of e/n to recover small private exponent d.

Description

RSA encryption with unusual parameters. Given n, e (very large), and ciphertext c.

Analysis

• Public exponent e is unusually large (close to n)
• Large e implies small private exponent d (since e*d ≡ 1 mod φ(n))
• Wiener's attack: when d < n^0.25 / 3, can recover d from continued fraction expansion of e/n
• Convergents of e/n contain k/d as one of the fractions

Solution

Wiener's attack exploits the relationship between large e and small d. The continued fraction expansion of e/n produces convergents, one of which is k/d. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3
# Wiener's attack on RSA with small d

def continued_fraction(n, d):
    """Generate continued fraction expansion of n/d"""
    while d:
        q = n // d
        yield q
        n, d = d, n - q * d

def convergents(cf):
    """Generate convergents from continued fraction"""
    n0, d0 = 0, 1
    n1, d1 = 1, 0
    for q in cf:
        n2 = q * n1 + n0
        d2 = q * d1 + d0
        yield n2, d2
        n0, d0 = n1, d1
        n1, d1 = n2, d2

def wiener_attack(e, n):
    """Recover d using Wiener's attack"""
    for k, d in convergents(continued_fraction(e, n)):
        if k == 0:
            continue
        # Check if d is correct
        if (e * d - 1) % k == 0:
            phi = (e * d - 1) // k
            # phi = (p-1)(q-1) = n - p - q + 1
            # p + q = n - phi + 1
            # p * q = n
            s = n - phi + 1  # p + q
            # p and q are roots of x^2 - s*x + n = 0
            discriminant = s * s - 4 * n
            if discriminant >= 0:
                sqrt_d = int(discriminant ** 0.5)
                if sqrt_d * sqrt_d == discriminant:
                    p = (s + sqrt_d) // 2
                    q = (s - sqrt_d) // 2
                    if p * q == n:
                        return d, p, q
    return None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Given parameters
n = ...  # from challenge
e = ...  # very large, close to n
c = ...  # ciphertext

# Attack
result = wiener_attack(e, n)
if result:
    d, p, q = result
    print(f"Found d = {d}")
    print(f"p = {p}")
    print(f"q = {q}")
    
    # Decrypt
    m = pow(c, d, n)
    flag = bytes.fromhex(hex(m)[2:]).decode()
    print(f"Flag: {flag}")

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering continued_fraction_expansion, wiener_attack was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-03-09 • CUSTOM • xponent • Difficulty: Medium