Challenge Description#

Two interns implemented RSA for encrypting secrets in our secure server. We intercepted both ciphertexts. Can you recover the flag?

Analysis#

The provided archive contained a generator script and an output file, so the first thing I did was inspect what exactly had been produced.

unzip -l ~/Downloads/chall.zip

Archive:  /home/rei/Downloads/chall.zip
  Length      Date    Time    Name
---------  ---------- -----   ----
        0  03-05-2026 15:34   chall/
      286  03-05-2026 15:34   chall/chall.py
     1888  03-05-2026 15:34   chall/output.txt
---------                     -------
     2174                     3 files

After extracting it, I opened the Python source and saw the whole weakness immediately: both ciphertexts were generated from the same plaintext m and the same modulus n, but with two different public exponents e1=65537 and e2=65539.

python - <<'PY'
from pathlib import Path
print(Path('/home/rei/Downloads/chall/chall.py').read_text())
PY

from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = 65537
e2 = 65539
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)

print(f'n = {n}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

That structure is textbook common-modulus RSA. If gcd(e1, e2) = 1, we can find integers a, b such that a*e1 + b*e2 = 1, then recover the message with m = c1^a * c2^b mod n (using modular inverses for negative exponents). Seeing that in a challenge titled Shared Secrets felt like a very clean setup.

I also checked FactorDB for the modulus because that is a fast sanity check in RSA problems, but factoring was not needed here.

curl -s "http://factordb.com/api?query=15613484457778220039654980022958049872188444253536664521878299346186299690596318997570659826434425721731355370867138953213026989976743377142765504571260215527294553654271781118212391204159518990968596261295168948440228041082301965364441584458294798204816467467908512566839304154861242122515409061246841994536031227773267237489476565872647263855436518839434244445147544831375630611604780739609297263212880689033429083233944328446260315066792177513234981491811498730902716481483964992285351131375028474577146777612691751569767048371788903417264587467014081622284179248112287589493777512320561114613569144195800437234229"

{"id":1100000008667485363,"status":"C","factors":[["15613484457778220039654980022958049872188444253536664521878299346186299690596318997570659826434425721731355370867138953213026989976743377142765504571260215527294553654271781118212391204159518990968596261295168948440228041082301965364441584458294798204816467467908512566839304154861242122515409061246841994536031227773267237489476565872647263855436518839434244445147544831375630611604780739609297263212880689033429083233944328446260315066792177513234981491811498730902716481483964992285351131375028474577146777612691751569767048371788903417264587467014081622284179248112287589493777512320561114613569144195800437234229",1]]}

From there, I solved it directly by computing Bézout coefficients and combining the two ciphertexts. The script output showed gcd(e1,e2)=1, the coefficients, and then the plaintext bytes containing the flag.

Solution#

# solve.py
from Crypto.Util.number import long_to_bytes, inverse, GCD
import gmpy2

n = 15613484457778220039654980022958049872188444253536664521878299346186299690596318997570659826434425721731355370867138953213026989976743377142765504571260215527294553654271781118212391204159518990968596261295168948440228041082301965364441584458294798204816467467908512566839304154861242122515409061246841994536031227773267237489476565872647263855436518839434244445147544831375630611604780739609297263212880689033429083233944328446260315066792177513234981491811498730902716481483964992285351131375028474577146777612691751569767048371788903417264587467014081622284179248112287589493777512320561114613569144195800437234229
e1 = 65537
e2 = 65539
c1 = 9993101309645876502949976287351370837087212167463601135659111788912319726915093674009462120594008269989008925333217460421430203800047071767579752710054483432224346596053896659465738808575198886663715562845557687700402715816367297769270518664187091496291749035092716942598505777700905531276887268308717281893126466300494901891672682998412050742915841266547122291660915410868923631123588939260269452921830387151231234789601092989858662523545385249240016725050116847916335240805667958853225966905850197851020285337377665991491289079417071778155413318565685381549602247790265946594726923972917864945191029562424733812524
c2 = 1459990896005860319581605016387430715096561756375928594932709277269470162996773374417666359991498904474234027848805093551270183052672717877677016566803102633601483736045973272091574131607667228774747601427437246567833005924484611585275742766787330814784819766302018961967282308860312651304011031214767071494208834399731910492783951824755536020781340507015496313124672307894535740061398743388902728605193621115124288349678071989303084136247288974179307747576149265328334715814354203355283998097003259121570840175049215292066138969738944431506461055176325857467753743848408609930624101141775509515316985830281107115623

g = GCD(e1, e2)
print(f"gcd(e1,e2) = {g}")

_, a, b = gmpy2.gcdext(e1, e2)
a = int(a)
b = int(b)
print(f"Bezout coefficients: a={a}, b={b}")

if a < 0:
    c1_part = pow(inverse(c1, n), -a, n)
else:
    c1_part = pow(c1, a, n)

if b < 0:
    c2_part = pow(inverse(c2, n), -b, n)
else:
    c2_part = pow(c2, b, n)

m = (c1_part * c2_part) % n
print(long_to_bytes(m))

python solve.py

gcd(e1,e2) = 1
Bezout coefficients: a=32769, b=-32768
b'TACHYON{c0mm0n_m0dulu5_att4ck!}'