Secrets

Platform: spbctf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-09 | Status: Solved Techniques: chinese_remainder_theorem, hastad_broadcast_attack, nth_root

Summary

Task: RSA with small e=17, same message encrypted for multiple recipients. Solution: Hastad's Broadcast Attack using Chinese Remainder Theorem to recover m^e, then extract e-th root.

Secrets — cryptokids20

Description

A task on Hastad's Broadcast Attack on RSA. The same message is encrypted with a small public exponent e=17 for different recipients (different moduli n).

Analysis

RSA Broadcast Attack (Hastad's Attack)

When the same message m is encrypted with the same small e for different moduli n1, n2, ..., ne:

c1 = m^e mod n1
c2 = m^e mod n2
...
ce = m^e mod ne

Using the Chinese Remainder Theorem (CRT), we can find m^e mod (n1 * n2 * ... * ne).

If m < min(n1, n2, ..., ne), then m^e < n1 * n2 * ... * ne, and CRT gives the exact value of m^e (without modulo). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Then m = e-th root of m^e.

Attack Conditions

1. Same small e (usually e=3, e=5, e=17)
2. At least e different ciphertexts
3. Different moduli n (pairwise coprime)
4. Same message m

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from pwn import *
import gmpy2
from functools import reduce

def chinese_remainder_theorem(remainders, moduli):
    """
    Chinese Remainder Theorem.
    Finds x such that x ≡ r_i (mod m_i) for all i.
    """
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y
    
    def modinv(a, m):
        g, x, _ = extended_gcd(a % m, m)
        return x % m
    
    # Total modulus
    M = reduce(lambda x, y: x * y, moduli)
    
    result = 0
    for r_i, m_i in zip(remainders, moduli):
        M_i = M // m_i
        y_i = modinv(M_i, m_i)
        result += r_i * M_i * y_i
    
    return result % M
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def nth_root(x, n):
    """Compute integer n-th root"""
    return int(gmpy2.iroot(x, n)[0])

def hastad_attack(ciphertexts, moduli, e):
    """
    Hastad's attack on RSA broadcast.
    
    Args:
        ciphertexts: list of ciphertexts c_i
        moduli: list of moduli n_i
        e: public exponent
    
    Returns:
        Decrypted message m
    """
    assert len(ciphertexts) >= e, f"Need at least {e} ciphertexts"
    assert len(ciphertexts) == len(moduli)
    
    # Use first e ciphertexts
    c_list = ciphertexts[:e]
    n_list = moduli[:e]
    
    # CRT: find m^e mod (n1 * n2 * ... * ne)
    m_e = chinese_remainder_theorem(c_list, n_list)
    
    # Extract e-th root
    m = nth_root(m_e, e)
    
    # Verification
    assert m ** e == m_e, "Root extraction failed"
    
    return m
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Connect to server
r = remote('crypto-kids20.forkbomb.ru', PORT)

e = 17  # Public exponent

# Collect 17 pairs (n, c)
ciphertexts = []
moduli = []

for i in range(e):
    # Get next pair
    n = int(r.recvline().decode().split('=')[1].strip())
    c = int(r.recvline().decode().split('=')[1].strip())
    
    moduli.append(n)
    ciphertexts.append(c)
    print(f"[+] Collected {i+1}/{e} ciphertexts")

# Hastad's attack
m = hastad_attack(ciphertexts, moduli, e)
print(f"[+] Recovered m = {m}")

# Convert to bytes
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
print(f"[+] Flag: {flag}")

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

Alternative implementation with gmpy2

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import gmpy2
from functools import reduce

def crt(remainders, moduli):
    """CRT via gmpy2"""
    M = reduce(lambda x, y: x * y, moduli)
    result = 0
    for r, m in zip(remainders, moduli):
        Mi = M // m
        yi = gmpy2.invert(Mi, m)
        result += r * Mi * yi
    return result % M

def hastad(ciphertexts, moduli, e):
    """Hastad's broadcast attack"""
    m_e = crt(ciphertexts[:e], moduli[:e])
    m, exact = gmpy2.iroot(m_e, e)
    assert exact, "Not a perfect root"
    return int(m)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Usage
m = hastad(ciphertexts, moduli, 17)
flag = bytes.fromhex(hex(m)[2:]).decode()

Concepts

Chinese Remainder Theorem (CRT)

If m1, m2, ..., mk are pairwise coprime, then the system:

x ≡ r1 (mod m1)
x ≡ r2 (mod m2)
...
x ≡ rk (mod mk)

has a unique solution modulo M = m1 * m2 * ... * mk.

Why the Attack Works

1. c_i = m^e mod n_i for each i
2. CRT gives m^e mod (n1 * n2 * ... * ne)
3. If m < min(n_i), then m^e < n1 * n2 * ... * ne
4. So CRT gives the exact m^e (not modulo)
5. Extract e-th root and get m ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Defense Against the Attack

1. Padding: OAEP adds randomness, making m different for each recipient
2. Large e: e=65537 requires too many ciphertexts
3. Unique messages: Add recipient ID to the message

Attack Variations

• Coppersmith's short pad attack: When padding is short
• Franklin-Reiter related message attack: When messages are linearly related
• Hastad with linear padding: m_i = a_i * m + b_i ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍