from Crypto.Util.number import long_to_bytes
from math import gcd
from sympy.ntheory.residue_ntheory import sqrt_mod
# Given values
e = 2
p = 8946541176074654913817717054410771331419218032593785296134838490312525894218240553305396599307555077734655624876704161811830296918000348456470769765921767
q = 8932929811422923151480388874853984777290071075825590049173830382535883452482114410463430296988680318519251836647527145507992221700683938654669731212502879
n = p * q
c = 17349894155329354363328734000800652637346887108866919240446747423455120556394923514564284438906649577094462846372316919957176356395706169922421515974398971844608693078173465906525109301576180786133798467234128571459625488335621909834995712400917418963473920470534646258784866422718709370743346105151573384808
# Step 1: Compute square roots modulo p
m_p = sqrt_mod(c, p, all_roots=True)
# Step 2: Compute square roots modulo q
m_q = sqrt_mod(c, q, all_roots=True)
# Step 3: Combine results using CRT
from sympy.ntheory.modular import crt
# Iterate through all combinations of m_p and m_q
for mp in m_p:
for mq in m_q:
# Solve using CRT
m, _ = crt([p, q], [mp, mq])
# Convert to bytes
flag_candidate = long_to_bytes(m)
# Check if the candidate contains the flag (e.g., starts with "CTF")
if b"CTF{" in flag_candidate:
print("Flag:", flag_candidate.decode())
break
The technique used in this code is a method for solving a cryptographic challenge where the ciphertext c is encrypted using RSA-like encryption with small exponent e = 2. The key idea is to leverage the Chinese Remainder Theorem (CRT) and square roots modulo prime numbers to recover the plaintext.
