As this challenge only had 13 solves at the end of the CTF, I deliberately chose it and decided to explain the solution.
{% file src="/files/5ZdTne8pAmmbqVXYCDPv" %}
{% file src="/files/uZ60LZ8hyyPqqW8zhA0a" %}
## 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
$$
{% hint style="info" %}
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.
{% endhint %}
$$
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
{% hint style="info" %}
Brute-forcing `z` until we get an integer value for `p`.
{% endhint %}
* **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:
```python
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.
```python
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()}")
```
{% hint style="info" %}
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.
{% endhint %}
`Flag: BITSCTF{I_H0P3_Y0UR3_H4V1NG_FUN_S0_F4R_EHEHEHEHEHO_93A5B675}`
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://zwique.gitbook.io/zwique_notes/writeups/random-ctf-writeup/noob-rsa-returns.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.