Leaked d

Platform: uoftctf2026 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-10 | Status: Solved Techniques: factor_from_d, miller_rabin_factorization, modular_arithmetic

Summary

Given: - n1 - RSA modulus - e1 = 65537 - old public exponent - d1 - leaked private exponent for e1 - e2 = 6767671 - new public exponent - c - ciphertext encrypted with e2

Leaked d - uoftctf2026

Description

"Someone leaked my d, surely generating a new key pair is safe enough."

Given:

• n1 - RSA modulus
• e1 = 65537 - old public exponent
• d1 - leaked private exponent for e1
• e2 = 6767671 - new public exponent
• c - ciphertext encrypted with e2

Analysis

Classic RSA vulnerability when the private exponent d is leaked.

Critical mistake: After d1 was leaked, a new key (e2, d2) was generated, but the modulus n remained the same.

Why this is fatal:

• Knowing the pair (e1, d1), we know that e1 * d1 ≡ 1 (mod φ(n))
• Therefore e1 * d1 - 1 is a multiple of φ(n) = (p-1)(q-1)
• Using a Miller-Rabin based algorithm, we can find p and q in polynomial time ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Factorization algorithm:

1. Compute k = e*d - 1 (multiple of φ(n))
2. Represent k = 2^t * r, where r is odd
3. For a random base g, compute x = g^r mod n
4. Repeatedly square, looking for a non-trivial square root of 1
5. If x^2 ≡ 1 (mod n) and x ≢ ±1 (mod n), then gcd(x-1, n) gives a factor

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
uoftctf2026 - Leaked d
Crypto challenge: Factor n using leaked private exponent d1, then decrypt with new e2
"""

import random
from math import gcd
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Given data
n1 = 144193923737869044259998596038292537217126517072587407189785154961344425600188709243733103713567903690926695626210849582322575275021963176688615503362430255878068025864333805901831356111202249176714839010151878345993886718863579928588098080351940561045688931786378656665718140998014299097023143181095121810219

e1 = 65537

d1 = 12574092103116126584156918631595005114605155027996964036950457918490065036621732354668884564796078087090438462300608898225025828108557296714458055780952572974382089675780912070693778415852291145766476219909978391880801604060224785419022793121117332853938170749724540897211958251465747669952580590146500249193
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

e2 = 6767671

c = 31703515320997441500407462163885912085193988887521686491271883832485018463764003313655377418478488372329742364292629844576532415828605994734718987367062694340608380583593689052813716395874850039382743513756381017287371000882358341440383454299152364807346068866304481227367259672607408256375720022838698292966


def factor_from_d(n, e, d):
    """
    Factor n given (e, d) where e*d ≡ 1 (mod φ(n))
    Based on the fact that e*d - 1 is a multiple of φ(n)
    """
    k = e * d - 1  # k = e*d - 1 is a multiple of φ(n) = (p-1)(q-1)
    
    # k = 2^t * r where r is odd
    t = 0
    r = k
    while r % 2 == 0:
        t += 1
        r //= 2
    
    # Try random bases
    for _ in range(100):
        g = random.randint(2, n - 2)
        x = pow(g, r, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(t - 1):
            y = pow(x, 2, n)
            if y == 1:
                p = gcd(x - 1, n)
                if 1 < p < n:
                    return p, n // p
            if y == n - 1:
                break
            x = y
    
    return None, None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍


def long_to_bytes(n):
    """Convert integer to bytes"""
    return n.to_bytes((n.bit_length() + 7) // 8, 'big')


# Step 1: Factor n using (e1, d1)
print("[*] Factoring n using leaked d1...")
p, q = factor_from_d(n1, e1, d1)

if p is None:
    print("[-] Factorization failed!")
    exit(1)

print(f"[+] p = {p}")
print(f"[+] q = {q}")
print(f"[+] Verification: p * q == n1: {p * q == n1}")

# Step 2: Compute new private exponent d2 for e2
phi = (p - 1) * (q - 1)
d2 = pow(e2, -1, phi)
print(f"[+] d2 = {d2}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Step 3: Decrypt the ciphertext
m = pow(c, d2, n1)
flag = long_to_bytes(m)
print(f"[+] Decrypted message: {flag}")
print(f"[+] Flag: {flag.decode()}")

Theory

Why it works:

• e * d ≡ 1 (mod φ(n)) means e * d - 1 = k * φ(n) for some k
• φ(n) = (p-1)(q-1) is even (for p, q > 2)
• The algorithm searches for an element of order 2 in the group (Z/nZ)*
• A non-trivial square root of 1 mod n exists only for composite n
• gcd(x-1, n) gives a non-trivial divisor

Proper fix: After d is leaked, you need to generate a completely new key with new p, q, n - as the flag says: "I should've just changed the whole thing instead" ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

References

• Boneh, D. "Twenty Years of Attacks on the RSA Cryptosystem"
• Factoring with High Bits Known ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍