> For the complete documentation index, see [llms.txt](https://elijahchia.gitbook.io/ctf-blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://elijahchia.gitbook.io/ctf-blog/akasec-ctf-24/lost-crypto.md).

# Lost (crypto)

The encryption code is given below.

```python
from random import getrandbits
from Crypto.Util.number import getPrime, bytes_to_long
from SECRET import FLAG

e = 2
p = getPrime(256)
q = getPrime(256)
n = p * q

m = bytes_to_long(FLAG)
cor_m = m - getrandbits(160)

if __name__ == "__main__":
    c = pow(m, e, n)
    print("n = {}\nc = {}\ncor_m = {}".format(n, c, cor_m))
    
# n = 5113166966960118603250666870544315753374750136060769465485822149528706374700934720443689630473991177661169179462100732951725871457633686010946951736764639
# c = 329402637167950119278220170950190680807120980712143610290182242567212843996710001488280098771626903975534140478814872389359418514658167263670496584963653
# cor_m = 724154397787031699242933363312913323086319394176220093419616667612889538090840511507392245976984201647543870740055095781645802588721
```

This challenge involves the Coppersmith attack. The flag is converted into a number `m`, and encrypted using `pow(m, e, n)` (which is RSA). We then generate 160 random bits, and subtract this from `m` to obtain `cor_m`. 

Next, we observe that `cor_m` is 441 bits long. Expressing `m` as $$m = b\_nb\_{n-1}...b\_1b\_0$$, if we have a $$b\_i$$ where $$i >= 160$$ that is 1, then for the smallest $$i$$ that fulfils this criteria, $$b\_nb\_{n-1}b\_{n-2}...b\_{i + 1}$$would be the same in `m` and `cor_m`.

Hence `cor_m` should give us the unchanged leftmost 200+ bits of `m`. Indeed, when we rightshift `cor_m` by 176 bits, we get the first half of the message:

```python
from Crypto.Util.number import long_to_bytes

# cor_m is 441 bits long
n = 5113166966960118603250666870544315753374750136060769465485822149528706374700934720443689630473991177661169179462100732951725871457633686010946951736764639
c = 329402637167950119278220170950190680807120980712143610290182242567212843996710001488280098771626903975534140478814872389359418514658167263670496584963653
cor_m = 724154397787031699242933363312913323086319394176220093419616667612889538090840511507392245976984201647543870740055095781645802588721

print(long_to_bytes(cor_m >> 176)) # AKASEC{c0pp3r5m17h_4774ck_1n_1ov3
print(len(long_to_bytes(cor_m >> 176))) # 33
```

We now know the first half of the code, and we can successfully use the Coppersmith attack to retrieve the entire flag. Since I didn't know the length of the flag, I tried a range of lengths. Below is the full solve script (in sage):

```python
from Crypto.Util.number import long_to_bytes, bytes_to_long
from sage.all import *
from tqdm import tqdm

e,N = (2, 5113166966960118603250666870544315753374750136060769465485822149528706374700934720443689630473991177661169179462100732951725871457633686010946951736764639)

c = 329402637167950119278220170950190680807120980712143610290182242567212843996710001488280098771626903975534140478814872389359418514658167263670496584963653

for flag_length in tqdm(range(20, 30)):
    m = bytes_to_long(b'AKASEC{c0pp3r5m17h_4774ck_1n_1ov3' + (flag_length) * b'\x00')
    P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
    pol = (m + x)^e - c
    roots = pol.small_roots(epsilon=1/20)
    print("Potential solutions:")
    for root in roots:
        print(long_to_bytes(int(m+root))) 
# AKASEC{c0pp3r5m17h_4774ck_1n_1ov3_w17h_5m4ll_3xp0n3nts}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://elijahchia.gitbook.io/ctf-blog/akasec-ctf-24/lost-crypto.md?ask=<question>
```

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.