Crypto CTF 2025 - Crypto challenges | MindCrafters CTF Team

Introduction

Crypto CTF was an online competition for hackers to test, evaluate, and expand their skills in exploiting cryptography. In this CTF, various crypto challenges focusing on modern cryptography techniques were provided. More information about this CTF can be found here. all

Vinard
ASIS Primes
Vainrat
Mancity
Interpol
Matemith
Mechanic

Vinard

Writeup author: Grzechu

Solution

from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse, isPrime
import math

# 1) Wczytanie danych
with open('output.txt') as f:
    lines = f.read().splitlines()
R = eval(lines[0].split('=',1)[1].strip())
n = int(lines[1].split('=',1)[1].strip())
c = int(lines[2].split('=',1)[1].strip())

# 2) Obliczenie wektora p_R = parinat(R[i]) dla każdego elementu R
p_bits = ''.join(str(bin(r).count('1') % 2) for r in R)
nbit = len(R)
p0 = int(p_bits, 2)
M  = (1 << nbit) - 1
p1 = M ^ p0

# 3) Wyodrębnienie p jako tego z {p0, p1}, które dzieli n
if n % p0 == 0:
    p = p0
else:
    p = p1
q = n // p
assert isPrime(p) and isPrime(q)

# 4) Obliczenie phi i sumy R
phi   = (p - 1) * (q - 1)
sum_R = sum(R)

# 5) Próbujemy obu kandydatów na e (to znów p0 lub p1)
for e in (p0, p1):
    if math.gcd(e, phi) != 1:
        continue
    d = inverse(e, phi)
    # odszyfrowanie: pow(c, d, n) == m + sum_R  (bo encrypt robi (m+sum_R)^e)
    m_plus = pow(c, d, n)
    m = (m_plus - sum_R) % n
    flag = long_to_bytes(m)
    if b'CTF' in flag:
        print(flag.decode())
        break

CCTF{s0lV1n9_4_Syst3m_0f_L1n3Ar_3qUaTi0n5_0vEr_7H3_F!3lD_F(2)!}

ASIS Primes

Writeup author: ppp45

First, we increment nbit a few times by providing invalid input that causes parsing error (because for nbit = 512 it would be extremely difficult or even impossible to solve).

Although now we know p and q, there's still some additional work to do. The exponent used during encryption is not 65537 but 65536 (65537 XOR 1). It's non-invertible, so we can't simply calculate private key d. But utilizing CRT and Tonelli–Shanks algorithm we can recover the plaintext nonetheless.

part_1

from itertools import product
import string
import pwn
from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime

pwn.context.log_level = "WARNING"


HOST = "65.109.189.98"
PORT = 13737

WHITELIST = (string.printable[:63] + "_{-}").encode("utf-8")


conn = pwn.remote(HOST, PORT)
conn.recvlines(4)


def get_ct():
    conn.recvlines(4)
    conn.sendline(b"e")
    resp = conn.recvline().strip().decode("utf8")
    return resp.split()[-1]


def increase_nbit(times=1):
    for _ in range(times):
        conn.recvlines(4)
        conn.sendline(b"s")
        conn.recvlines(3)
        conn.sendline(b"AAA")
        conn.recvline()


def get_prefix():
    resp = conn.recvline().strip()
    return resp.split()[-1][2:-1]


def find_prime(prefix, nbit):
    free_space = nbit // 8 - len(prefix) - 1
    assert free_space >= 0

    for var in product(WHITELIST, repeat=free_space):
        b = prefix + bytes(var) + b"}"
        n = bytes_to_long(b)
        if isPrime(n):
            return n

    raise Exception("NOT FOUND")


def check_prime(prime, prefix):
    prime_bytes = long_to_bytes(prime)
    failed_checks = [
        not isPrime(prime),
        not prime_bytes.startswith(prefix),
        not prime_bytes.endswith(b"}"),
        not all(e in WHITELIST for e in prime_bytes),
    ]
    if sum(failed_checks) > 0:
        print(f"{failed_checks = }")
        return False
    return True


def check_pair(p, q, p_prefix, q_prefix, nbit):
    if not check_prime(p, p_prefix):
        return False
    if not check_prime(q, q_prefix):
        return False

    real_bitsize = (9 * p * q).bit_length()
    target_bitsize = 2 * nbit

    if real_bitsize != target_bitsize:
        print(f"{real_bitsize = }")
        print(f"{target_bitsize = }")
        return False

    return True

EXTRA_NBIT = 300


original_ct = get_ct()
print(f"{original_ct = }")

increase_nbit(EXTRA_NBIT)
assert get_ct() == original_ct


conn.recvlines(4)
conn.sendline(b"s")
p_prefix = get_prefix()
q_prefix = get_prefix()

print(f"{p_prefix = }")
print(f"{q_prefix = }")


nbit = 512 + EXTRA_NBIT

nbit_p = nbit
nbit_q = nbit - 1

found = False

while not found:
    p = find_prime(p_prefix, nbit_p)
    q = find_prime(q_prefix, nbit_q)
    nbit_q += 1
    found = check_pair(p, q, p_prefix, q_prefix, nbit)


payload = f"{p},{q}".encode("utf-8")
conn.sendline(payload)
conn.recvline()

ct = get_ct()
assert ct != original_ct

print(f"{p = }")
print(f"{q = }")
print(f"{ct = }")


conn.close()

part 2

from itertools import product
from sympy.ntheory.modular import crt
from sympy.ntheory.residue_ntheory import sqrt_mod
from Crypto.Util.number import long_to_bytes

p = ...
q = ...
ct = ...


n = p * q
e = 65536


cp = ct % p
cq = ct % q


# in that case k=16 (since e = 2^16)
def all_roots(c, k, mod):
    roots = [c]
    for _ in range(k):
        new_roots = []
        for r in roots:
            try:
                sq = sqrt_mod(r, mod, all_roots=True)
                new_roots.extend(sq)
            except ValueError:
                continue  # Not a residue
        roots = new_roots
    return roots


roots_p = all_roots(cp, 16, p)
roots_q = all_roots(cq, 16, q)

print(f"{len(roots_p) = }")
print(f"{len(roots_q) = }")

candidates = []

for rp, rq in product(roots_p, roots_q):
    m, _ = crt([p, q], [rp, rq])
    candidates.append(m)

print(f"{len(candidates) = }")


for candidate in candidates:
    b = long_to_bytes(candidate)
    print(b)

CCTF{3AzY_RSA_cH4l13n9E_!n_ASIS_CTF!!}

Vainrat

Writeup author: ppp45

We have a recursive sequence. We recover y13 and y14 (two earliest y we are able to) and using them we calculate x0.

part_1

import pwn

pwn.context.log_level = "WARNING"


HOST = "91.107.161.140"
PORT = 11117


for _ in range(10):
    dct = {}
    conn = pwn.remote(HOST, PORT)

    conn.recvlines(4)
    dct["y0"] = conn.recvline().strip().decode().split()[-1]

    for i in range(1, 15):
        conn.recvlines(3)
        conn.sendline(b"c")

        resp = conn.recvline().strip().decode()
        if "rat" not in resp:
            dct[f"y{i}"] = resp.split()[-1]

    if "y13" in dct and "y14" in dct:
        print("FOUND!")
        with open("variables.txt", "w") as f:
            f.write("y0 = " + dct["y0"] + "\n")
            f.write("y13 = " + dct["y13"] + "\n")
            f.write("y14 = " + dct["y14"] + "\n")
    else:
        print("retrying...")

part_2

from Crypto.Util.number import long_to_bytes

R = RealField(440)


def simulate_sequence(x0, y0, steps=15):
    x = R(x0)
    y = R(y0)
    y_values = [y]
    for _ in range(steps):
        x = (x + y) / 2
        y = (x * y).sqrt()
        y_values.append(y)
    return y_values


# adjust tol until there's a clear result (with repeating 0s or 9s)
def find_x0(y0, target_y13, target_y14, tol=1e-130, max_iter=4000):
    y0 = R(y0)
    target_y13 = R(target_y13)
    target_y14 = R(target_y14)
    tol = R(tol)

    # initial bounds
    low = R(1e-10)
    high = max(y0, target_y13, target_y14) * 10

    for _ in range(max_iter):
        mid = (low + high) / 2
        y_vals = simulate_sequence(mid, y0, steps=14)
        y13, y14 = y_vals[13], y_vals[14]

        err13 = abs(y13 - target_y13)
        err14 = abs(y14 - target_y14)

        if err13 < tol and err14 < tol:
            return mid

        if y13 < target_y13:
            low = mid
        else:
            high = mid

    raise Exception("Failed to converge")


y0 = ...
y13 = ...
y14 = ...


x0 = find_x0(y0, y13, y14)
print(f"{x0 = }")

CCTF{h3Ur1s7!c5_anD_iNv4rIanTs_iN_CryptoCTF_2025!}

Mancity

Writeup author: Lazarus

Solution

import math
from Crypto.Util.number import long_to_bytes, inverse, isPrime

# provided function
def man(n_in):
    B = bin(n_in)[2:]
    M = ''
    for b in B:
        if b == '0':
            M += '01'
        else:
            M += '11'
    return int(M, 2)

n = 147170819334030469053514652921356515888015711942553338463409772437981228515273287953989706666936875524451626901247038180594875568558137526484665015890594045767912340169965961750130156341999306808017498374501001042628249176543370525803456692022546235595791111819909503496986338431136130272043196908119165239297
c = 77151713996168344370880352082934801122524956107256445231326053049976568087412199358725058612262271922128984783428798480191211811217854076875727477848490840660333035334309193217618178091153472265093622822195960145852562781183839474868269109313543427082414220136748700364027714272845969723750108397300867408537
e = 1234567891
nbit = 256

# search space for the 256-bit p_gen
p_gen_low = 2**(nbit - 1)
p_gen_high = 2**nbit - 1
found = False
p, q = 0, 0

# binary search for p_gen
while p_gen_low <= p_gen_high:
    p_gen_candidate = (p_gen_low + p_gen_high) // 2
    
    p_candidate = (p_gen_candidate << nbit) | (2**nbit - 1)
    q_candidate = man(p_gen_candidate)
    
    n_candidate = p_candidate * q_candidate
    
    if n_candidate == n:
        if isPrime(p_gen_candidate) and isPrime(p_candidate) and isPrime(q_candidate):
            print("Factors found!")
            p = p_candidate
            q = q_candidate
            found = True
            break
        else: 
            p_gen_high = p_gen_candidate - 1

    elif n_candidate < n:
        p_gen_low = p_gen_candidate + 1
    else:
        p_gen_high = p_gen_candidate - 1

if found:
    # standard RSA decryption
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print(f"p = {p}")
    print(f"q = {q}")
    print(f"Flag: {flag.decode()}")
else:
    print("No factors found.")

CCTF{M4nch3sReR_c0D!ng_wI7H_RSA}

Interpol

Writeup author: Lazarus

Solution

#!/usr/bin/env sage

from sage.all import *

try:
    with open('output.raw', 'rb') as f:
        poly_data = f.read()
except FileNotFoundError:
    print("Error: output.raw not found.")
    exit()

# Define the ring and deserialize
R.<x> = QQ['x']
poly = loads(poly_data)

# Iterate through possible flag lengths
for length in range(10, 100):
    
    recovered_chars = [None] * length
    is_plausible_length = True

    for n in range(length):
        x_val = -(1 + (19 * n - 14) % length)
        y_val = poly(x_val)
        
        if y_val.is_integer() and 32 <= int(y_val) <= 126:
            original_index = (63 * n - 40) % length

            if recovered_chars[original_index] is None:
                recovered_chars[original_index] = chr(int(y_val))
            else:
                is_plausible_length = False
                break
        else:
            is_plausible_length = False
            break
    
    if is_plausible_length and all(c is not None for c in recovered_chars):
        
        flag = "".join(recovered_chars)
        if flag.startswith('CCTF{') and flag.endswith('}'):
            print(f"Found the flag with length {length}:")
            print(flag)
            exit()

print("Could not find a flag.")

CCTF{7h3_!nTeRn4t10naL_Cr!Min41_pOlIc3_0r9An!Zati0n!}

Matemith

Writeup author: Lazarus

Solution (solve.sage)

# data from output.txt
p = 9892984422801315119260311427714389408772405421306235794826917610128461644036928139298330716261

# 1. Define the Finite Field
F = GF(p)

# PART 1: Solve for u, v, w
# Define a ring only for the first subsystem
R_uvw.<u,v,w> = PolynomialRing(F)

# Define the polynomials for the first subsystem directly in the correct ring
f = 8593371583346286129538282168765198524220954884352992069219549555526097253129502925759872761483*u*v + 8192555264287905175212103898575474256555217842060435386769432116145712989123062847161390929397*u + 9598573789403814092125115160545174167539204328557118715540593719644188998531033259685435430387*v + 5738603225260621554442220996093767502015758942320213371600986432070445300427944977409453429117
h = 6107224904478508858527197508483774405356161856691777460732363192128980355274418091837270668258*u*w + 3584245173493717638976874408629921683995390608944250077841702023698807664457252845973088744491*u + 5646173287331462026544218972062953582608380797148923127395811758145598594972832047259631339566*w + 1994681139685786114971936867358158466232859433926848067961874687630342141141862187589124089741
j = 1912186465211454827473018892315659311053527670028135595953520151335825509122313783795561869379*v*w + 6246883466276200389231653597272295993565421216541002743075041326054203024921176043191679609212*v + 4002308425802254921531592700910138281674785127934610897914017993007060136199147207365547047048*w + 973159800079995512996976852328990077106942094656694887771601292254542762394381629810393447820

# Create an ideal and find its variety (solutions)
I_uvw = R_uvw.ideal([f, h, j])
print("Solving for u, v, w...")
solutions_uvw = I_uvw.variety()
print(f"Found {len(solutions_uvw)} candidate solution(s) for (u,v,w).")

# PART 2: Solve for x, y, z
# Define a ring for the second subsystem
R_xyz.<x,y,z> = PolynomialRing(F)

for sol_uvw in solutions_uvw:
    u_sol, v_sol, w_sol = sol_uvw[u], sol_uvw[v], sol_uvw[w]
    
    # Construct the second set of polynomials using the solved values for u,v,w
    # All calculations are now correctly done within the finite field F.
    g = (7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*u_sol)*x*y + 6282097687310252658473848438985225466620614743750918909885172321224925965646628839166491648752*v_sol + 7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*x + 3354788147890488743832873565215769634619909759459203496980671578348799162553954862104978291860*y + 2560270290674636359252235177920929027441112715609783111306743340637878970846852799006820932563
    i = (7622670835797214156123791992548663880284352234566921286637648219243086701251627093499322050472*v_sol)*y*z + 6026769215097777844835562389865313764490318485655789123763637718591748620654875700763740623760*w_sol + 8145050175261359549200629067766090532616263522561328878195831921153188650784907223634130346224*y + 3622105614070476540808786980829452605696331317022729645355376801209444137548670550164418237117*z + 4800360746061605999597274870855047707130861888252519642520437605796496240599924899885487900040
    k = (1423338294606985951732736428034353751447528399559929388138157330118213387990891693204997290038*w_sol)*x*z + 784018806462384388182217012266169299116410899849461442885543245867941419322406775218178098109*u_sol + 7684681843989505989596042520590550892565982707534588920361260899638313817214040416765327284778*x + 4982848574842913858489870338816729222210785430242027484672099513487039514577513464674726403409*z + 7781690757622738625626304200561818137843970209349935834539461705684625161407233281360563620790

    I_xyz = R_xyz.ideal([g, i, k])
    print(f"Solving for x, y, z...")
    solutions_xyz = I_xyz.variety()

    # PART 3: Reconstruct Flag
    for sol_xyz in solutions_xyz:
        x_sol, y_sol, z_sol = sol_xyz[x], sol_xyz[y], sol_xyz[z]
        M = [u_sol, v_sol, w_sol, x_sol, y_sol, z_sol]
        
        try:
            flag_parts = [int(m).to_bytes(14, 'big') for m in M]
            flag = b'CCTF{' + b''.join(flag_parts) + b'}'
            
            if all(32 <= c < 127 for c in flag):
                print(f"\nFlag: {flag.decode()}\n")
        except Exception:
            continue

CCTF{50lv!n6_7H3_H1dD3n__num8Ers_Pr08l3m_f0r_C51dH_4nd_C5uRf_v14_4uT0m473d_C0pp3r5m17h!!?}

Mechanic

Writeup author: ppp45

To recover the original file we have to use the provided list of skeys in reversed order. Some of them are real skeys and some are random values. We don't have to check temporary file each time because when decryption fails (i.e. fake skey is used) an exception is thrown. Therefore, we simply use try and except clauses.

import shutil
from quantcrypt.kem import MLKEM_1024
from quantcrypt.cipher import KryptonKEM


KEY_SIZE = 3168
CONSTANT_BYTES = 8

ENC_FLAG_FILE = "REAL_flag_22.enc"
KEYS_FILE = "REAL_output.raw"


with open("REAL_output.raw", "rb") as f:
    keys_merged = f.read()

assert len(keys_merged) % KEY_SIZE == 0
keys = [keys_merged[i : i + KEY_SIZE] for i in range(0, len(keys_merged), KEY_SIZE)]


kry = KryptonKEM(MLKEM_1024)

TEMP_FILE = "temp.png"

shutil.copy(ENC_FLAG_FILE, TEMP_FILE)

for key in keys[::-1]:
    try:
        data = kry.decrypt_to_memory(key, TEMP_FILE)

        # ignored when decryption fails
        with open(TEMP_FILE, "wb") as f:
            print("saving...")
            f.write(data)
    except:
        pass

print("FINISHED")

CCTF{k3y_3NcAp5uL4t!0n_M3cH4n1Sms!}

Introduction

Table of contents

Vinard

Solution

ASIS Primes

part_1

part 2

Vainrat

part_1

part_2

Mancity

Solution

Interpol

Solution

Matemith

Solution (solve.sage)

Mechanic