sqRSA

Cryptography · BearcatCTF 2025 · Sean

Problem

Description

473B

sqRSA.py

Open

1KB

output.txt

Open

Solution

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.

Flag: BCCTF{Don7_b3_4_squArE_ac6c54f792c90a69b8}::::::::::::::::::::::::::::::::::::::::::::::::::::::::::