Noob RSA Returns

Cryptography · BITSCTF 2025

Problem

Description

As this challenge only had 13 solves at the end of the CTF, I deliberately chose it and decided to explain the solution.

574B

encrypt.py

1KB

chall.txt

Analysis

One thing we need to focus on is the equation that defines K Mathematically expressed as:

$$K = (A\cdot p^{2}-C\cdot p+D)\cdot d$$

By multiplying both sides, we will get:

$$K \cdot e= (A\cdot p^{2}-C\cdot p+D)\cdot d \cdot e$$

In RSA, $\color{Red} e\cdot d \equiv 1 mod \Phi(n)$ or $\color{Red} e\cdot d =1+z\cdot\Phi(n)$, where z is some integer.

For example, $11 \equiv1mod5$ or $11=1+z\cdot5$, where z = 2.

Substitute $e \cdot d$ into the equation above.

$$K \cdot e= (A\cdot p^{2}-C\cdot p+D) \cdot (1+z\Phi(n))$$

$$\frac{K}{(A\cdot p^{2}-C\cdot p+D)} = \frac{(1+z\Phi(n))}{e}$$

Solution

Brute-forcing z until we get an integer value for p.

• Finding p:

  • The script tries to find the prime factor ppp by solving an equation for each value of z in the range [START, e]

  • The equation relates p, z, and other parameters (including n) to eventually factor nnn.

• Equation Setup:

  • The equation:

    pythonCopyEditequation = Eq(K / (A*p**2 - C*p + D), (z*((p - 1) * (n/p - 1)) + 1) / e)

    is derived to calculate ppp. It depends on the unknown prime p, and the loop iterates over possible values of z.

• Loop and Progress Bar:

  • The tqdm loop iterates over values of z, solving the equation to find valid integer solutions for p. Once a valid p is found, it exits the loop.

from sympy import Eq, symbols, solve
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm

e = 65537
n = 94391578028846794543970306963076155289398888845132329034244336898352288130614402434536624297683695128972774452047972797577299176726976054101512298009248486464357336027594075427866979990479026404794249095503495046303993475122649145761379383861274918580282133794104162177538259963029805672413580517485119968223
ct = 39104570513649572073989733086496155533723794051858605899505397827989625611665929344072330992965609070817627613891751881019486310635360263164859429539044097039969287153948226763672953863052936937079161030077852648023719781006057880499973169570114083902285555659303311508836688226455433255342509705736365222119
K = 20846957286553798859449981607534380028938425515469447720112802165918184044375264023823946177012518880630631981155207307372567493851397122661053548491580627249805353321445391571601385814438186661146844697737274273249806871709168307518276727937806212329164651501381607714573451433576078813716191884613278097774416977870414769368668977000867137595804897175325233583378535207450965916514442776136840826269286229146556626874736082105623962789881101475873449157946816513513532838149452759771630220014344325387486921028690085783785067988074331005737389865053848981113695310344572311901555735038842261745556925398852334383830822697851
C = 0xbaaaaaad
D = 0xdeadbeef
A = 0xbaadf00d        

START = 42675
END = e

p = symbols("p", integer=True)


for z in tqdm(range(START, END + 1), desc="Solving for p"):
    print(f"{z = }")
    equation = Eq(K / (A*p**2 - C*p + D), (z*((p - 1) * (n/p - 1)) + 1) / e)

    solutions = solve(equation, p)

    for sol in solutions:
        if sol.is_integer:
            p = int(sol)
            break

print(f"The value of p: {p}")
phi = (p - 1) * (n//p - 1)
d = pow(e, -1, phi)
m = pow(ct, d, n)


print(f"The value of m: {m}")
print(f"Flag: {long_to_bytes(m).decode()}")

Since the correct value of z was 42677, I set the starting value to 42675. Setting larger values, but still less than e, is suitable for capturing z as it saves both time and memory.

Flag: BITSCTF{I_H0P3_Y0UR3_H4V1NG_FUN_S0_F4R_EHEHEHEHEHO_93A5B675}