# siege

| Info     | Details |
| -------- | ------- |
| Category | Crypto  |

## Challenge Overview

> We're given `output.txt` and `main.py`.\
> Using the following Python script I recovered the flag:

```python
from Crypto.Util.number import isPrime, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import random, math
from collections import Counter

N_hex = "5de30d6f229594805cf5bd3bcf921561b1b18883f02a36f1b85be47d646c527a945e4137ef06897d546f27759e2129efc0ba462ec06fdb28f664d489bff91aaf6e688d0d9c66698821fd43ac615f2133b0fe322c3737354eef149568d925c9568fb17f7e555d14d766846815a2a1a9a0055b26923f8096b961174429edc4b7e72e73a25ee9641e1b9f6e6deb5ed2b1b5a7e1c3c4414c1ec009d8b8b24547bf7"
C_hex = "1a727061128645f52013b40c282ee3c1a64f238bb94280b684138187e1d7d7b8ba28e3816b14501862e27c2c2a324774f5d65ba1abe4ad364788afa5744109e64b89e336844d34d68d566d4943634fa0a297bed74fdc06e951312aa2d98d3f550bf4d110822ca88b1f3369c895497b009bcd9084e32c4444e24bf3c7b65a96f104d6658d6cdce1d0023acf6ec086baa4ccdcddebec2258f3a7631cc3866cb19"
iv_hex= "00fe4c7eeecf24dc1e4883585c0da618"
ct_hex= "8b15e8c2d547b79ba50552d4cecce7e26efd84d8e3f605805f6a2a406e01a2fd8962154db8663fa080802a1f48c400ca34b179ddf66495055e680a05c10c7b4b8e13a4e2da952d88cc06c91622f10277"

# These are the values from output.txt

Integer = int
N      = Integer(int(N_hex, 16))
C_key  = Integer(int(C_hex, 16))
iv     = bytes.fromhex(iv_hex)
ct     = bytes.fromhex(ct_hex)

def prime_from_seed(seed):
    rng = random.Random(seed)
    while True:
        p = rng._randbelow(1 << 256) | 1
        if isPrime(p):
            return p

factors, N_left = [], N
for i in range(3, 8):
    for seed in range(1 << i):
        p = prime_from_seed(seed)
        if N_left % p == 0:
            factors.append(p)
            N_left //= p
            break
    else:
        raise RuntimeError(f"nimic găsit la i = {i}")

assert math.prod(factors) == N, "factorizare greșită!"

phi = 1
for p, k in Counter(factors).items():
    phi *= p**(k-1) * (p-1)

e, d = 65537, inverse(65537, phi)

aes_int = pow(C_key, d, N)
aes_key = aes_int.to_bytes(16, 'big')

cipher = AES.new(aes_key, AES.MODE_CBC, iv)
flag   = unpad(cipher.decrypt(ct), AES.block_size).decode()

print("Flag:", flag)
```

## Final Flag

`OSC{5efca16a840359db72cae08a12d2784422f95d8afd12a64346e6ce4ea2431fb8}`

*made by k0d*
