Overview
Flag: MetaCTF{sh4r3d_f4ct0rs_s1nk_b0th_k3ys}
We get four files: n1.txt, n2.txt, e.txt, and flag.enc. Two RSA public keys (same exponent e=65537, different moduli) and a ciphertext. The challenge implies that both keys were generated on the servers. Could it be that they were generated at similar times?
RSA security depends on n being the product of two large primes that nobody else knows. If two different keys share one of those primes, they’re both broken. The attack is super simple: compute gcd(n1, n2).
from math import gcd
p = gcd(n1, n2)
If the RNG reused state across both key generations, both n values share p. The gcd gives it to us, and from there it’s standard RSA decryption: factor n1 into p and q1, compute phi, invert e, decrypt.
q1 = n1 // p
phi1 = (p - 1) * (q1 - 1)
d1 = pow(e, -1, phi1)
m = pow(c, d1, n1)
print(m.to_bytes((m.bit_length() + 7) // 8, "big").decode())
This isn’t just a theoretical attack! In 2012, Nadia Heninger and colleagues ran this computation against RSA public keys scraped from the public internet and factored roughly 0.2% of them, mostly from embedded devices with bad entropy at boot time. https://eprint.iacr.org/2012/064
The fix, if you’re curious, is ensuring the RNG is seeded with actual entropy before generating keys, not from a deterministic source like system uptime.
Solve Script
#!/usr/bin/env python3
from math import gcd
n1 = int(open("n1.txt").read().strip())
n2 = int(open("n2.txt").read().strip())
e = int(open("e.txt").read().strip())
c = int(open("flag.enc").read().strip(), 16)
p = gcd(n1, n2)
assert p > 1, "no shared factor found -- check the input files"
q1 = n1 // p
phi1 = (p - 1) * (q1 - 1)
d1 = pow(e, -1, phi1)
m = pow(c, d1, n1)
print(m.to_bytes((m.bit_length() + 7) // 8, "big").decode())