> For the complete documentation index, see [llms.txt](https://zwique.gitbook.io/zwique_notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zwique.gitbook.io/zwique_notes/writeups/random-ctf-writeup/noob-rsa-returns.md).

# Noob RSA Returns

## Problem

<figure><img src="/files/zeAqagnktVmFMJdCIRLG" alt=""><figcaption><p>Description</p></figcaption></figure>

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}`