Alpaca CTF 2026: reused-n

#ctf #cryptography #rsa #common-modulus-attack #number-theory #python

Challenge Information

AttributeDetails
EventAlpaca CTF 2026
CategoryCryptography
Challengereused-n

Summary

The challenge encrypts a single plaintext flag with the same RSA modulus n under two different public exponents, e1 = 1234 and e2 = 5678. The name reused-n is a direct hint toward the Common Modulus Attack. The twist: gcd(e1, e2) = 2, not 1, so the classic attack only yields m² mod n rather than m directly. However, the constraint len(flag) < 100 guarantees m² < n, meaning no modular reduction occurs and a plain integer square root recovers m exactly.

Analysis

Challenge Setup

flag = os.getenv("FLAG", "Alpaca{DUMMY}").encode()
assert len(flag) < 100
m = bytes_to_long(flag)


p = getPrime(1024)
q = getPrime(1024)
n = p * q          # 2048-bit modulus


e1 = 1234
e2 = 5678


c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

The output file (chall.txt) gives us n, e1, c1, e2, c2.

Identifying the Attack

Two ciphertexts, same n, same plaintext, different exponents — this is the textbook setup for the Common Modulus Attack. The attack relies on Bézout’s identity: if we can find integers a, b such that:

a·e1 + b·e2 = gcd(e1, e2)

then:

c1^a · c2^b ≡ m^(a·e1 + b·e2) ≡ m^gcd(e1,e2)  (mod n)

The gcd Twist

Computing gcd(e1, e2) = gcd(1234, 5678):

1234 = 2 · 617
5678 = 2 · 17 · 167
gcd  = 2

The classic attack assumes gcd = 1 and recovers m directly. Here, gcd = 2, so we only recover m² mod n, not m.

Breaking Out of the Dead-End

Normally, computing a square root modulo an unknown RSA composite is as hard as factoring n. But there is a saving constraint:

  • len(flag) < 100 → m < 2^800 (at most 100 bytes)
  • m² < 2^1600
  • n is ~2048 bits → n > 2^2047

Therefore m² < 2^1600 < 2^2047 < n, which means m² mod n == m² (no reduction ever happens). The modular square root is simply an integer square root over the integers — a deterministic, efficient operation.

Solution

Step 1: Extended GCD (Bézout Coefficients)

Find a, b such that a · 1234 + b · 5678 = 2:

def xgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = xgcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

Step 2: Handle Negative Exponents

One of a or b will be negative (since e1 · e2 > 0). A negative exponent in modular arithmetic becomes a modular inverse:

g, a, b = xgcd(e1, e2)   # g = 2


if a < 0:
    c1 = pow(c1, -1, n)   # modular inverse of c1
    a = -a
if b < 0:
    c2 = pow(c2, -1, n)
    b = -b

Step 3: Recover m²

m_squared = (pow(c1, a, n) * pow(c2, b, n)) % n

This equals m^(a·e1 + b·e2) mod n = m² mod n = m².

Step 4: Integer Square Root

from math import isqrt


m = isqrt(m_squared)
assert m * m == m_squared, "Square root was not exact — something went wrong"

Step 5: Recover the Flag

flag = m.to_bytes((m.bit_length() + 7) // 8, "big")
print(flag.decode())

Full Solver

import sys
from math import isqrt
from pathlib import Path


def xgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = xgcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def solve(chall_path: str = "chall.txt"):
    data = {}
    for line in Path(chall_path).read_text().splitlines():
        line = line.strip()
        if "=" in line:
            k, v = line.split("=", 1)
            data[k.strip()] = int(v.strip())


    n, e1, c1, e2, c2 = data["n"], data["e1"], data["c1"], data["e2"], data["c2"]


    print(f"[+] n bit-length: {n.bit_length()}")
    print(f"[+] e1 = {e1}, e2 = {e2}")


    g, a, b = xgcd(e1, e2)
    print(f"[+] gcd(e1, e2) = {g}")


    if a < 0:
        c1 = pow(c1, -1, n)
        a = -a
    if b < 0:
        c2 = pow(c2, -1, n)
        b = -b


    m_squared = (pow(c1, a, n) * pow(c2, b, n)) % n
    print(f"[+] m^{g} mod n bit-length: {m_squared.bit_length()}")


    m = isqrt(m_squared)
    assert m * m == m_squared, "isqrt was not exact — m^2 >= n or attack failed"


    flag = m.to_bytes((m.bit_length() + 7) // 8, "big")
    print(f"[+] flag: {flag.decode()}")


if __name__ == "__main__":
    path = sys.argv[1] if len(sys.argv) > 1 else "chall.txt"
    solve(path)

Expected output:

[+] n bit-length: 2047
[+] e1 = 1234, e2 = 5678
[+] gcd(e1, e2) = 2
[+] m^2 mod n bit-length: 445
[+] flag: Alpaca{e1_e2_share_a_secr3t}

Flag

Alpaca{e1_e2_share_a_secr3t}

Key Takeaways

  • Common Modulus Attack: Encrypting the same message under the same n but two different exponents leaks m^gcd(e1,e2). When gcd = 1 this gives m directly.
  • gcd > 1 is not always a dead-end: If the plaintext is small enough that m^g < n, the modular g-th root collapses to an integer g-th root, which is straightforward to compute.
  • Small-message guarantees matter: The len(flag) < 100 constraint is load-bearing — it’s what makes the integer square root tractable. Without it, recovering m from m² mod n would require factoring n.
  • Exponent choice is not cosmetic: Choosing non-coprime exponents for the same modulus introduces structural weaknesses that an attacker can exploit without ever touching the private key.
  • pow(x, -1, n) in Python: Python 3.8+ natively computes modular inverses, making negative Bézout coefficients trivial to handle.

Tools Used

  • Python 3.8+: math.isqrt for exact integer square roots; pow(x, -1, n) for modular inverses
  • Extended Euclidean Algorithm: Hand-rolled xgcd for Bézout coefficients
  • No third-party packages required

References