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