---
# System prepended metadata

title: recruitCTF2025 - Crypto

---

# ssmal

> When they leak the high bits of p+q, the rest is just a distributed search — rent the cloud and flex.

---

## Challenge Description
`chall.py`
```python
from Crypto.Util.number import getPrime, isPrime

p = getPrime(256)
q = getPrime(256) 
N = p*q

e = 65537

flag = b'BPCTF{redact}' 
c = pow(int.from_bytes(flag, 'big'), e, N)
gift = (p+q)>>40
print(f'N = {N}\nc = {c}\ngift = {gift}')


"""
N = 5758124415184468271370250630048687746812715972269092676700260830924771547226161680827118153372606993872590019171624226415454063566537634596851695999313069
c = 4258014490469377191207443169980969026536758269486705363402307773455639773007422079769567310663689852817179059312032143236005345809847891632360620594960862
gift = 139200565274113272217771369795858181556454302427519574149545982701
"""

```

The program leaks `N = p*q`, the ciphertext `c`, and `gift = (p+q) >> 40` — an approximation of `s = p+q` with the lower 40 bits removed. Recovering `p` and `q` (and thus `d`) reduces to finding the unknown 40 lower bits of `s`. Once `p,q` are recovered, decrypt `c` to obtain the flag.

---

## Code Review

This is a classic **partial-sum leak** RSA problem:

* If `s = p + q` were known exactly, `p` and `q` are roots of `x^2 - s x + N = 0`.
* With `gift = s >> 40`, we have `s = (gift << 40) + k` for unknown `k` in `[0, 2^40)`.
* For each candidate `k` compute `D = s^2 - 4N`. If `D` is a perfect square then `p = (s + sqrt(D)) // 2` and `q = (s - sqrt(D)) // 2`. Verify `p*q == N`.
* So the problem is an **exhaustive search over 2^40 candidates**, with plenty of ways to prune and parallelize.

This leakage is fatal but straightforward: leaking the high bits of `p+q` turns factorization into a bounded brute-force search rather than requiring subexponential factoring.

---

## Solution

1. Compute `s0 = gift << 40`.
2. For `k` in `0 .. 2^40 - 1` (parallelize!):

   * `s = s0 + k`
   * `D = s*s - 4*N`
   * If `D < 0` continue. Let `r = isqrt(D)`. If `r*r == D` then candidate found.
   * Compute `p = (s + r) // 2`, `q = (s - r) // 2`. Verify `p*q == N`.
3. Compute `d = inverse(e, (p-1)*(q-1))` and `m = pow(c, d, N)`; convert `m` to bytes to get the flag.

---

## ssmal Slayer

`solve.sage`

```python
import sys
from Crypto.Util.number import long_to_bytes
from sage.all import Integer

if len(sys.argv) != 3:
    print("Usage: sage solve.sage <start_k> <end_k>")
    sys.exit(1)

start_k = Integer(sys.argv[1])
end_k = Integer(sys.argv[2])

N = Integer("5758124415184468271370250630048687746812715972269092676700260830924771547226161680827118153372606993872590019171624226415454063566537634596851695999313069")
c = Integer("4258014415184468271370250630048687746812715972269092676700260830924771547226161680827118153372606993872590019171624226415454063566537634596851695999313069")
gift = Integer("139200565274113272217771369795858181556454302427519574149545982701")
e = 65537

print(f"Finding k from {start_k} to {end_k-1}...")

s_approx = gift << 40
Dk = (s_approx + start_k)**2 - 4*N
add_term = 2*(s_approx + start_k) + 1

for k in range(start_k, end_k):
    if Dk.is_square():
        p_minus_q = Dk.isqrt()
        s = s_approx + k
        p = (s - p_minus_q) // 2
        q = (s + p_minus_q) // 2
        
        if p * q == N:
            print(f"Found solution at k = {k}")
            phi = (p - 1) * (q - 1)
            d = pow(e, -1, phi)
            m = pow(c, d, N)
            
            m_int = int(m)
            flag_bytes = long_to_bytes(m_int)
            flag_string = flag_bytes.decode()
            print(f" {flag_string}")
    Dk += add_term
    add_term += 2
```

---

## Now it's time for money to talk🐧

When the math is done, the last stage is pure engineering muscle — brute-force `2^40` candidates.

So the simple job is to go to Google Cloud Platform (GCP) and rent the most powerful and expensive compute instances they have.

Hmm, the C4 chip series with 288 vCPUs, 144 cores, and 576 GB of memory seems good. Besides, to burn my money faster, I’ll also add some NVIDIA H100 80GB GPUs to my instance to test something funny later 🐧.

With those electricity-grid destroyers, my goal is to run many parallel workers, each searching a small shard of the `2^40` space. Each worker runs the optimized code above (with small-prime prefilters and gmpy2/C for speed) and returns immediately when it finds the correct `k`.
![htop](https://hackmd.io/_uploads/ryl3VW5pee.png)

So now enjoy watching the CPUs burn through cycles to brute-force `2^40` values.

After just over 2 hours, the master node printed:
![found](https://hackmd.io/_uploads/rkxhVb9Txe.png)

Then decode the found value to get the flag.
> The flag was harvested. Sometimes, throwing money at math really *does* work.
---

## FLAG

```
BPCTF{l4w_priv4ate_key_attack_easy_right?}
```
---

## Takeaway

* Leaking high bits of `p+q` reduces factorization to a bounded brute-force problem.
* Engineering and parallelism win: small-prime prefilters + GMP + massive parallelism make 2^40 feasible.
# Baby Pad

> Padding oracles: one-bit leaks that spill the whole secret.

---

## Challenge Description
`chall.py`
```python
from Crypto.Cipher import AES 
import os 

with open('./FLAG.txt', 'rb') as f:
    flag = f.readline()

def pad(message):
    l = -len(message) % 16 
    if l == 0: 
        l = 16 
    return message + bytes([l]) * l 

def check_pad(message):
    l = message[-1]
    if not (l >= 1 and l <= 16):
        return False
    return message[-l:] == bytes([l] * l)

key = os.urandom(16)
iv = os.urandom(16)

def encrypt(message, iv):
    cipher = AES.new(key = key, iv = iv, mode = AES.MODE_CBC)
    return cipher.encrypt(message)

def decrypt(message, iv):
    cipher = AES.new(key = key, iv = iv, mode = AES.MODE_CBC)
    return cipher.decrypt(message)

ct = iv + encrypt(pad(flag), iv)

print(f"enc = {ct.hex()}")

while True: 
    print('1. Send me a message!')
    print('2. 1 is your only choice actually')

    choice = input("Your choice: ") 

    if choice == '1':
        ciphertext = bytes.fromhex(input())
        iv = bytes.fromhex(input())
        message = decrypt(ciphertext, iv)
        if not check_pad(message):
            print("Can't read that")
        else:
            print("Message received!")
    else:
        print("Good bye")
        exit()    
```

The service prints `enc = <IV||CT hex>`, then exposes a **padding oracle**: we can submit an arbitrary ciphertext block and IV; it replies “Message received!” iff PKCS#7 padding is valid after decryption. That single bit lets us decrypt, block by block, without the key. 

---

## Code Review

CBC decryption satisfies:

```
P_i = Dec_k(C_i) ⊕ C_{i-1}
```

If we control `C_{i-1}` (or the IV for the first block), we can flip bytes so that the last `t` bytes of `P_i` equal `t` — valid PKCS#7. The oracle’s two responses (“Message received!” vs “Can't read that”) leak exactly whether our guess produced correct padding. Repeating for each byte from the end to the start recovers the full plaintext. The challenge pads the flag, prepends the random IV to the output, and never authenticates — classic oracle. 

---

## Solution

1. **Grab ciphertext**: read the printed `enc` once; split into 16-byte blocks: `C_0=IV, C_1, …, C_n`.
2. **Per-block attack**: for each target `C_i` (i≥1), craft a fake previous block `C'_{i-1}` byte-by-byte so that the oracle confirms padding `0x01`, then `0x02 0x02`, …, up to `0x10…0x10`.
3. **Recover plaintext**: each successful guess yields the intermediate state `I_i = C'_{i-1} ⊕ pad_val`; then `P_i = I_i ⊕ C_{i-1}`.
4. **Unpad** the concatenated plaintext to reveal the flag.

---

## Baby Pad Slayer

```python=
from pwn import *

HOST = "vm.daotao.antoanso.org"
PORT = XXXXX

def get_ciphertext(p):
    p.recvuntil(b'enc = ')
    return bytes.fromhex(p.recvline().strip().decode())

def oracle_query(p, cblock, iv):
    p.recvuntil(b"Your choice: ")
    p.sendline(b'1')
    p.sendline(cblock.hex().encode())
    p.sendline(iv.hex().encode())
    return b"Message received!" in p.recvline()

def decrypt_block(p, target_block, prev_block):
    I = bytearray(16)
    for i in range(15, -1, -1):
        pad = 16 - i
        iv = bytearray(16)
        for j in range(i+1, 16):
            iv[j] = I[j] ^ pad
        for g in range(256):
            iv[i] = g
            if oracle_query(p, target_block, bytes(iv)):
                I[i] = g ^ pad
                break
    return bytes(I[k] ^ prev_block[k] for k in range(16))

def main():
    p = remote(HOST, PORT)
    full_ct = get_ciphertext(p)
    blocks = [full_ct[i:i+16] for i in range(0, len(full_ct), 16)]
    pt = b""
    for i in range(1, len(blocks)):
        pt += decrypt_block(p, blocks[i], blocks[i-1])
    pad_len = pt[-1]
    print(pt[:-pad_len].decode())
    p.close()

if __name__ == "__main__":
    main()
```

---

## FLAG

```
BPCTF{Just_a_simple_padding_oracle_attack_to_warm_up_49fab148518a}
``` 

---

## Takeaway

* A single padding-validity bit breaks unauthenticated CBC.
* Always authenticate ciphertexts (use AEAD modes like GCM/EAX or MAC-then-encrypt with careful, uniform errors).
* Never expose decryption oracles that branch on padding — unify error paths and timings. 


# Baby RSA 1

> A tiny mistake in CRT stitching and the whole key unravels.

---

## Challenge Description
`chall.py`
```python
from Crypto.Util.number import *
from Crypto.PublicKey import RSA 

with open('./FLAG.txt', 'rb') as f:
    flag = f.read()

def gen_key():
    key = RSA.generate(2024)
    public_key = (key.n, key.e)
    private_key = (key.p, key.q, key.d)
    return public_key, private_key

def decrypt_data(c, private_key, q_inv):
    """
    https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm
    """
    p, q, d = private_key[0], private_key[1], private_key[2] 
    dp, dq = d % (p - 1), d % (q - 1) 
    m1 =  pow(c, dp, p)
    m2 = pow(c, dq, q)
    h = q_inv * (m1 - m2) % p
    m = m2 + h * q % (p * q) 
    return long_to_bytes(m)

def get_encrypted_flag(flag, public_key):
    n, e = public_key[0], public_key[1]
    flag = bytes_to_long(flag)
    flag_enc = pow(flag, e, n)
    return long_to_bytes(flag_enc)

border = '-' * 69
public_key, private_key = gen_key() 

flag_enc = get_encrypted_flag(flag, public_key).hex()

c = ''

while True:
    print(border)
    print('1. Decrypt data')
    print('2. Get public key')
    print('3. Get encrypted flag')
    print(border)
    
    choice = input('Enter your choice: ')

    if choice == '1':
        if c == '':
            c = input('Enter your ciphertext in hex string: ')
            c = int(c, 16)
            if c == int(flag_enc, 16):
                print("No cheating")
                exit()

        num = int(input('Enter your magic number: ')) 
        msg = decrypt_data(c, private_key, num).hex()
        print(msg)

    elif choice == '2':
        print(f'n = {public_key[0]}')
        print(f'e = {public_key[1]}')

    elif choice == '3':
        print(flag_enc)

    else:
        print('Bye')
        exit()
```

The service generates a fresh 2024-bit RSA keypair, prints `n` and `e` on request, prints the encrypted flag, and offers a decryption oracle that expects:

* a ciphertext `c` (hex), and
* a "magic number" supplied as `q_inv` which the server blindly uses as the CRT coefficient in the recombination step.

The CRT recombination is implemented exactly as in wikipedia, but the server **lets you provide the `q_inv` value** instead of computing the true `q^{-1} mod p`. That is the core flaw. 

---

## Code Review

The CRT recombination used is:

```
m1 = c^{d_p} mod p
m2 = c^{d_q} mod q
h = q_inv * (m1 - m2) mod p
m = m2 + h * q mod (p*q)
```

If `q_inv` equals the correct modular inverse `q^{-1} mod p`, this yields the correct plaintext. But the server accepts any `q_inv` you provide. A faulty `q_inv` will cause the recombination to return an incorrect value `m'` which may nevertheless leak information. By carefully choosing `c` and `q_inv` we can force a relationship between the (faulty) output and small parts of the secret (p or q), enabling factorization of `n`. The provided exploit demonstrates this attack and recovers `p` by computing a gcd — effectively turning a single faulty-oracle response into a factor of `n`. 

---

## Solution

1. Request public key `(n, e)` and encrypted flag `flag_enc`.
2. Send a chosen small ciphertext `c` (e.g., `c = 2`) and pass a deliberately chosen `q_inv` (the "magic number"), for example `1`. The server performs the CRT recombination with this wrong `q_inv` and returns `m' = decrypt_data(c, private_key, 1)`.
3. Now compute `c' = (m')^e mod n`. If the CRT recombination step produced `m'` that differs from the true modular plaintext `m` in a way linked to one of the prime factors, then `gcd(c' - c, n)` will reveal a nontrivial factor of `n` (this is a classical Bellcore-style fault attack / RSA CRT fault).
4. Once `p` is recovered, compute `q = n // p`, derive φ(n), compute `d = e^{-1} mod φ(n)`, and decrypt the encrypted flag.

The provided remote exploit script carries out these exact steps: it sends `c=2` and `magic_number=1`, receives the faulty decryption, computes `c' = (faulty_msg)^e mod n`, and finds `p = gcd(c' - c, n)`. With `p` and `q` in hand it recovers `d` and decrypts `flag_enc`. 

---

## Baby RSA 1 Slayer
`solve.py`
```python
from pwn import *
from Crypto.Util.number import GCD, inverse, long_to_bytes

HOST = 'vm.daotao.antoanso.org'
PORT = XXXXX

p = remote(HOST, PORT)
log.info(f"Connected to {HOST}:{PORT}")

p.sendlineafter(b'Enter your choice: ', b'2')
n = int(p.recvline().decode().strip().split(' = ')[1])
e = int(p.recvline().decode().strip().split(' = ')[1])
log.info(f"Received N")
log.info(f"Received e")

p.sendlineafter(b'Enter your choice: ', b'3')
flag_enc_hex = p.recvline().decode().strip()
flag_enc = int(flag_enc_hex, 16)
log.info(f"Received encrypted flag")

c = 2           
magic_number = 1

log.info(f"Using ciphertext c = {c} and magic_number = {magic_number}")

p.sendlineafter(b'Enter your choice: ', b'1')
p.sendlineafter(b'Enter your ciphertext in hex string: ', hex(c)[2:].encode())
p.sendlineafter(b'Enter your magic number: ', str(magic_number).encode())

faulty_msg_hex = p.recvline().decode().strip()
faulty_msg = int(faulty_msg_hex, 16)
log.info(f"Received faulty decrypted message.")

c_prime = pow(faulty_msg, e, n)
leaked_factor = GCD(c_prime - c, n)
p_factor = leaked_factor
q_factor = n // p_factor

if p_factor * q_factor != n or p_factor == 1 or q_factor == 1:
    log.error("Factorization failed!")
    p.close()
    exit()

log.success(f"Successfully factored N!")

phi = (p_factor - 1) * (q_factor - 1)
d = inverse(e, phi)
log.info(f"Calculated private key d.")

decrypted_flag_long = pow(flag_enc, d, n)
flag = long_to_bytes(decrypted_flag_long)

log.success(f"{flag.decode()}")
p.close()
```
---

## FLAG

```
BPCTF{Thank_you_naul_for_finding_this_not_so_intended_solution_901832123ab}
```

---

## Takeaway

* Never let users supply internal CRT recombination parameters. `q^{-1} mod p` must be computed server-side and checked.
* Faulty CRT recombination is a known fault model: incorrect partial results leak factors via gcd operations (fault attack / Bellcore vulnerability).
* For RSA implementations that use CRT for speed, protect recombination with consistency checks (e.g., verify `m^e ≡ c (mod n)` before returning) or compute a final check that the recombination matches a slower but correct decryption path.
* APIs that expose decryption or low-level internals must validate inputs and avoid letting callers control critical internal constants.


# Baby RSA 2

> If you can get one correct oracle answer, you can unblind the rest.

---

## Challenge Description
`chall.py`
```python
from Crypto.Util.number import *
from Crypto.PublicKey import RSA 

with open('./FLAG.txt', 'rb') as f:
    flag = f.read()

def gen_key():
    key = RSA.generate(2024)
    public_key = (key.n, key.e)
    private_key = (key.p, key.q, key.d)
    return public_key, private_key

def decrypt_data(c, private_key, q_inv):
    """
    https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm
    """
    p, q, d = private_key[0], private_key[1], private_key[2] 
    dp, dq = d % (p - 1), d % (q - 1) 
    m1 =  pow(c, dp, p)
    m2 = pow(c, dq, q)
    h = q_inv * (m1 - m2) % p 
    m = m2 + h * q % (p * q) 
    return long_to_bytes(m)

def get_encrypted_flag(flag, public_key):
    n, e = public_key[0], public_key[1]
    flag = bytes_to_long(flag)
    flag_enc = pow(flag, e, n)
    return long_to_bytes(flag_enc)

border = '-' * 69
public_key, private_key = gen_key() 

flag_enc = get_encrypted_flag(flag, public_key).hex()

num = ''

while True:
    print(border)
    print('1. Decrypt data')
    print('2. Get public key')
    print('3. Get encrypted flag')
    print(border)
    
    choice = input('Enter your choice: ')

    if choice == '1':
        c = input('Enter your ciphertext in hex string: ')
        c = int(c, 16)
        if c == int(flag_enc, 16):
            print("No cheating")
            exit()

        if num == '':
            num = int(input('Enter your magic number: '))
            try: assert num.bit_length() > 69 and num.bit_length() < 690
            except AssertionError: print("Bye"); exit()  

        msg = decrypt_data(c, private_key, num).hex()
        print(msg)

    elif choice == '2':
        print(f'n = {public_key[0]}')
        print(f'e = {public_key[1]}')

    elif choice == '3':
        print(flag_enc)

    else:
        print('Bye')
        exit()
```

Notes:

* The server generates a fresh 2024-bit RSA keypair and exposes `n` and `e`.
* Option 3 prints the encrypted flag (ciphertext).
* Option 1 accepts any ciphertext `c` (hex) and — the **first time you call it** — asks you for a "magic number" `num`. That `num` is used as `q_inv` in CRT recombination for all later decrypt attempts. The server enforces `69 < num.bit_length() < 690` for this supplied number. 

---

## Code Review

The decryption routine performs CRT-based recombination:

```
m1 = c^{dp} mod p
m2 = c^{dq} mod q
h = q_inv * (m1 - m2) mod p
m = m2 + h * q mod n
```

Crucially, the server **lets the caller choose `q_inv`** (the "magic number") once, subject only to a bit-length check. That is dangerous: it allows an attacker to control the recombination stage.

However, unlike the previous Baby RSA where a faulty `q_inv` was used to induce a single faulty decryption to factor `n`, here the server design lets an attacker supply a reusable `num` and then make decrypt calls repeatedly. This enables a *blinding* approach: if you can make the oracle decrypt a blinded ciphertext `c' = c * r^e (mod n)` for some chosen `r`, you can unblind the decrypted value to recover the true plaintext of `c`, because RSA is multiplicative. The provided exploit uses exactly that trick.

---

## Solution

1. **Fetch public data**: obtain `n` and `e` (menu option 2) and the encrypted flag `c_flag` (menu option 3). 
2. **Choose a blinding factor `r`** (small integer, e.g., `2`) and compute:

   ```
   c_blinded = c_flag * r^e mod n
   ```

   This is a valid ciphertext whose decryption is `m_blinded = m_flag * r mod n`.
3. **Use the decryption oracle** to decrypt `c_blinded`. Because you're allowed to submit any ciphertext and you have already set the `num` value once, the server will return `m_blinded` (in hex). The `num` only needs to pass the bit-length check; its exact value is irrelevant for this multiplicative unblinding attack. 
4. **Unblind**: compute `m_flag = m_blinded * r^{-1} mod n`. Convert `m_flag` to bytes — that's the plaintext flag.
5. Print the flag.

This attack is a standard *RSA blinding/unblinding* trick used here to *abuse a decryption oracle*: the oracle will decrypt any ciphertext once you set the magic number, so blinding lets you delegate decryption of the secret ciphertext to the oracle without ever learning or altering the RSA internals. 

---

## Baby RSA 2 Slayer
`solve.py`
```python
from pwn import *
from Crypto.Util.number import *
import math

HOST = 'vm.daotao.antoanso.org'
PORT = XXXXX

r = remote(HOST, PORT)

def get_public_key():
    r.sendlineafter(b'Enter your choice: ', b'2')
    n_line = r.recvline().decode().strip()
    e_line = r.recvline().decode().strip()
    n = int(n_line.split(' = ')[1])
    e = int(e_line.split(' = ')[1])
    return n, e

def get_encrypted_flag():
    r.sendlineafter(b'Enter your choice: ', b'3')
    flag_enc_hex = r.recvline().decode().strip()
    return int(flag_enc_hex, 16)

def decrypt(c_hex, magic_num=None):
    r.sendlineafter(b'Enter your choice: ', b'1')
    r.sendlineafter(b'Enter your ciphertext in hex string: ', c_hex.encode())
    if magic_num:
        r.sendlineafter(b'Enter your magic number: ', str(magic_num).encode())

    decrypted_hex = r.recvline().decode().strip()
    return int(decrypted_hex, 16)

log.info("Fetching public key and encrypted flag...")
n, e = get_public_key()
c_flag = get_encrypted_flag()
log.success(f"n = {n}")
log.success(f"e = {e}")
log.success(f"Encrypted flag (c_flag) = {c_flag}")

log.info("Blinding the flag's ciphertext...")
blinding_r = 2 
c_blinded = (c_flag * pow(blinding_r, e, n)) % n
log.success(f"Blinded ciphertext = {c_blinded}")

magic_num = 10**30 
log.info("Sending blinded ciphertext to the decryption oracle...")
m_blinded = decrypt(hex(c_blinded)[2:], magic_num)
log.success(f"Received decrypted blinded message (m_blinded) = {m_blinded}")

log.info("Unblinding the message to recover the flag...")
r_inv = pow(blinding_r, -1, n)
m_flag = (m_blinded * r_inv) % n

flag = long_to_bytes(m_flag)
log.success(f"FLAG: {flag.decode()}")

r.close()
```

---

## FLAG

```
BPCTF{How_many_queries_did_you_use?_af434b1f1aec}
```
---

## Takeaway

* Allowing callers to control low-level CRT parameters (`q_inv`) or to reuse a single oracle parameter for many decryptions opens powerful attacks.
* Even when you restrict the magic number by bit-length, that is not enough: a valid `num` only needs to pass the check; its value need not be correct.
* If an oracle will decrypt arbitrary ciphertexts, blinding turns it into a universal decryption oracle for any target ciphertext (no factorization or CRT fault needed).
* Defenses: never expose a decryption oracle; if decryption must be provided, authenticate and restrict inputs, compute internal invariants server-side (do not accept `q_inv`), and limit or monitor usages. In general, avoid providing a raw decryption API.

# Circle

> The circle isn't elliptic — but it’s close enough.

---

## Challenge Description
`chall.py`
```python
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad  
import hashlib 
import random 

flag = b'BPCTF{??????????????????????????????????}'
               
p = 307119639745751469235752346635781766287891925576026383455555022557456022240440834093
s = random.randint(2, p - 1)

class Point:
    def __init__(self, x, y):
        self.x = x % p 
        self.y = y % p 
    def __add__(self, other):
        x = (self.x * other.y + self.y * other.x) % p 
        y = (self.y * other.y - self.x * other.x) % p 
        return Point(x, y)
    def __mul__(self, n):
        R = Point(0, 1)
        P = Point(self.x, self.y)
        while n > 0:
            if n % 2:
                R += P 
            P += P
            n >>= 1
        return R


G = Point(269706932193805755534663280853021102698237187960981530911954571811593219484562877686, 64681749570942311062995683097786979736444359061659263379460834230175114182600310869)

P = G * s

k = hashlib.sha256(long_to_bytes(s)).digest()[:16]
iv = random.randbytes(16)

cipher = AES.new(key = k, iv = iv, mode = AES.MODE_CBC)

ct = cipher.encrypt(pad(flag, 16))

print(f"P = {P.x, P.y}")
print(f"iv = {iv}")
print(f"ct = {ct}")

P = (66458087392047205569134518238677614962987250315628901489579974197182257590937156372,
     60031618721128621274849877211225119325796011838618857532417555895902612101315597171)
iv = b'\x84G\xd8\x9c\x8f-\xdb \r\x0c3\x07\xc2\xde\xa7\xfa'
ct = b'0\x8a\x8c><p^\x9d+\xa5\xcb%\xc2\x8c78\xd3\xe1w\xc8\xd12~SL\xe1\x1c\xadw\xdc\x9b\xd3\xfe\xba\xa5\xb04\x1b\x12D\x9fC\x9b\xcd\xf3V|\x9b'
```



---

## Code Review

The structure looks familiar, but this isn’t a standard elliptic curve.
The group law defined by:

```
(x₃, y₃) = (x₁y₂ + y₁x₂,  y₁y₂ − x₁x₂) mod p
```

is not elliptic — it’s **the multiplicative group of complex numbers modulo p** represented as `(x, y)` with the rule:

```
(x, y) ≡ (r cos θ, r sin θ)
```

so addition mimics multiplication in the complex plane.

If you rewrite:

```
z = y + i·x
```

then the addition law becomes simple multiplication of `z` values.
In other words:

```
G = (x, y)  →  g = y + i·x
```

and

```
G * s  →  g^s
```

So `P = G * s` actually means modular exponentiation in a disguised field:
`p` is prime, and the field can be represented as 𝔽ₚ[i] where `i² = −1`.

We know `G`, `P`, and `p` — the task reduces to solving for `s` in:

```
(y_P + i·x_P) = (y_G + i·x_G)^s mod p
```

That’s a **discrete logarithm** over a quadratic extension of 𝔽ₚ.


Besides, The algebraic group is isomorphic to the multiplicative group of the quadratic field 𝔽ₚ[i].
So we can work with `z_G = y_G + i·x_G` and `z_P = y_P + i·x_P` directly.

Then:

```
s = log_{z_G}(z_P) mod (p² − 1)
```

since the multiplicative order of 𝔽ₚ[i] is `p² − 1`.

This can be attacked with standard **discrete logarithm algorithms** implemented in SageMath, using `GF(p^2)`.

---

## Solution

1. Embed in `GF(p²)`:

   ```python
   F.<i> = GF(p^2, modulus=x^2 + 1)
   ```
2. Construct the generator and result:

   ```python
   Gc = F(y_G) + F(i)*F(x_G)
   Pc = F(y_P) + F(i)*F(x_P)
   ```
3. Compute discrete log:

   ```python
   s = discrete_log(Pc, Gc)
   ```
4. Derive AES key:

   ```python
   k = hashlib.sha256(long_to_bytes(s)).digest()[:16]
   ```
5. Decrypt ciphertext with given IV:

   ```python
   AES.new(k, AES.MODE_CBC, iv).decrypt(ct)
   ```

That’s all — no elliptic curve math required, just number theory on the circle group.

---

## Circle Slayer
`solve.sage`    
```python
from sage.all import *
from Crypto.Cipher import AES
import hashlib

p = 307119639745751469235752346635781766287891925576026383455555022557456022240440834093
xG = 269706932193805755534663280853021102698237187960981530911954571811593219484562877686
yG = 64681749570942311062995683097786979736444359061659263379460834230175114182600310869
xP = 66458087392047205569134518238677614962987250315628901489579974197182257590937156372
yP = 60031618721128621274849877211225119325796011838618857532417555895902612101315597171

iv = b'\x84G\xd8\x9c\x8f-\xdb \r\x0c3\x07\xc2\xde\xa7\xfa'
ct = b'0\x8a\x8c><p^\x9d+\xa5\xcb%\xc2\x8c78\xd3\xe1w\xc8\xd12~SL\xe1\x1c\xadw\xdc\x9b\xd3\xfe\xba\xa5\xb04\x1b\x12D\x9fC\x9b\xcd\xf3V|\x9b'

F.<i> = GF(p^2, modulus=x^2 + 1)
G = F(yG) + i*F(xG)
P = F(yP) + i*F(xP)

s = discrete_log(P, G)
k = hashlib.sha256(int(s).to_bytes((s.nbits()+7)//8, 'big')).digest()[:16]
cipher = AES.new(k, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)
```

---

## FLAG

```
BPCTF{Group_isomorphism_and_smooth_order}
```

---

## Takeaway

* This "Circle" group mimics elliptic curve scalar multiplication but is actually modular complex multiplication — easy to linearize.
* Recasting `(x, y)` → `y + i·x` collapses the custom group law to a single multiplicative relation.
* SageMath’s `GF(p^2)` tools handle it elegantly via `discrete_log`.
* Always check if an “ECC-like” operation is actually hiding a much simpler algebraic structure.

> The circle isn’t elliptic — it’s just complex.
# Hash Collision

> Make the hash equal, and the flag becomes yours.

---

## Challenge Description
`chall.py`
```python
import string 
import random 

with open('./FLAG.txt', 'rb') as f:
    flag = f.read().decode()

s = string.ascii_letters
l = 20

def check(a):
    if len(a) != 20:
        return True 
    for x in a:
        if x not in s:
            return True 
    return False 

def h(msg, c, m):
    res = 0 
    for x, y in zip(msg, c):
        res += x * y 
        res %= m 
    return res 

m = random.randint(2 ** 127, 2 ** 128)
c = [random.randint(2 ** 69, 2 ** 75) for i in range(l)]

print(f"m = {m}")
print(f"c = {c}")

while True:
    print("Give me two strings a and b of length such that a != b and h(a, c, m) = h(b, c, m): ")
    a = input() 
    b = input()

    if check(a) or check(b):
        print("Can't read that")
        exit()

    if a == b:
        print("No")
        exit()
    
    a = a.encode()
    b = b.encode()

    if h(a, c, m) == h(b, c, m):
        print(f"Congrats! Here's your flag: {flag}")
        exit()

    else:
        print("Unlucky")
        exit()
```

The challenge prints a modulus `m` and a coefficient vector `c` and asks you to supply two different 20-character alphabetic strings `a` and `b` such that the modular linear form `h(a,c,m) == h(b,c,m)`. In short: **find a nontrivial collision for the keyed linear hash**. 

---

## Code Review

The hash is simple and linear:

```
h(msg, c, m) = (Σ msg[i] * c[i]) mod m
```

where `msg[i]` are the byte values of the characters. Because the hash is linear in the vector `msg`, a collision `a != b` is equivalent to finding a nonzero integer vector `d = (d0..d19)` (not all zeros) with small entries such that:

```
Σ d[i] * c[i] ≡ 0  (mod m),   where d = a - b
```

and `a` and `b` must both lie in the allowed alphabet (ASCII letters), so the components of `d` must be achievable as differences of letters (i.e., in the range ~[-122, 122] but further constrained to differences between letters). This is a standard lattice / shortest vector problem: find a short integer relation among the `c[i]` with modulus `m`.

Because `m` is about 128 bits and `c[i]` are large (~70–75 bits), a lattice-based approach (LLL) on a tailored lattice will find a small integer relation `d` whose last coordinate is 0 mod m — i.e., a collision. The author’s exploit does exactly that using `fpylll`. 

---

## Solution

1. Observe collision condition is linear: find nonzero integer vector `d` with

   ```
   Σ d[i] * c[i] = k * m
   ```

   for some integer `k`. If we can find `d` with small coefficients (differences between letters), we can set `a` and `b` such that `a - b = d`.
2. Build a lattice whose short vectors correspond to such `d`. A standard basis is the (l+1)×(l+1) matrix:

   ```
   B = [ I_l   c^T ]
       [ 0     m   ]
   ```

   Any integer vector `v = (d, -k)` in the lattice satisfies `B * v = 0 mod ...` and the last coordinate encodes the multiple of `m`. Short vectors with last coordinate 0 give relations Σ d[i]*c[i] = 0 (i.e., k = 0) or small multiples of m depending on construction. 
3. Apply LLL reduction to B to find short vectors. Inspect reduced basis rows for one whose last element is 0 (or small), then extract the first `l` components as `d`.
4. Convert each `d[i]` into printable characters by expressing it as `ord(a_i) - ord(b_i)` and selecting letters `a_i`, `b_i` from `string.ascii_letters` that satisfy the difference. If any component is outside achievable differences, try alternative short vectors from the reduced basis.
5. Submit `a` and `b`. If the constructed `d` is valid, `h(a,c,m) == h(b,c,m)` holds and the server returns the flag.

This approach is implemented in the provided solver script which uses `fpylll`'s LLL reduction and then maps vector differences to ASCII letters. 

---

## Hash Collision Slayer

`solve.py`
```python=
from pwn import *
from fpylll import *
import string

HOST = "vm.daotao.antoanso.org"
PORT = XXXXX

def find_chars_for_diff(diff):
    for c1 in string.ascii_letters:
        c2_ord = ord(c1) - diff
        if chr(c2_ord) in string.ascii_letters:
            return c1, chr(c2_ord)
    return None, None 

p = remote(HOST, PORT)
m_line = p.recvline().decode().strip()
m = int(m_line.split('=')[1].strip())
log.info(f"Received m = {m}")

c_line = p.recvline().decode().strip()
c = eval(c_line.split('=')[1].strip())
log.info(f"Received c = {c}")

l = 20

# Construct the lattice basis matrix B of size (l+1) x (l+1) B = [[I_l, c^T], [0, m]]
B = [[0] * (l + 1) for _ in range(l + 1)]
for i in range(l):
    B[i][i] = 1 
    B[i][l] = c[i] 
B[l][l] = m

M = IntegerMatrix.from_matrix(B)
log.info("Constructed the lattice basis matrix.")

log.info("Running LLL algorithm...")
M_lll = LLL.reduction(M)
log.info("LLL reduction complete.")

solution_d = None
for i in range(l + 1):
    vector = M_lll[i]
    if vector[l] == 0 and any(vector):
        solution_d = list(vector)[:l]
        log.success(f"Found a solution vector: {solution_d}")
        break

if not solution_d:
    log.error("Could not find a suitable solution vector from the LLL basis.")
    exit()

a = ""
b = ""
possible = True
for diff in solution_d:
    char_a, char_b = find_chars_for_diff(diff)
    if char_a is None:
        log.error(f"Failed to find characters for difference: {diff}")
        possible = False
        break
    a += char_a
    b += char_b

if not possible:
    log.error("Failed to construct collision strings from this vector. Try running again.")
    exit()

log.success(f"Constructed string a: {a}")
log.success(f"Constructed string b: {b}")

p.recvuntil(b"h(a, c, m) = h(b, c, m): \n")
p.sendline(a.encode())
p.sendline(b.encode())

response = p.recvall().decode()
print(response)
```


---

## FLAG

```
BPCTF{Yet_another_lattice_basis_reduction_algorithm_challenge_021ad1e3f365}
```

---

## Takeaway

* Linear hashes are fragile: collisions reduce to integer relations, and lattices find them efficiently.
* When the domain of message components is small (letters), a short relation gives a valid, printable collision.
* LLL (or BKZ) on a contrived basis is the canonical weapon for these problems — build the lattice so that a short vector corresponds to your needed relation.
* Always design hashes to resist structured algebraic attacks — add nonlinear mixing or use cryptographic hash functions with proven collision resistance.

# sin

> not tan?

---

## Challenge Description
`chall.py`
```python
from sage.all import *
print(sin(int.from_bytes(b'BPCTF{redact}', "big")).n(1024))

# -0.8796972610321827563892090184824431008849260677490432314800583299448516158025013449932132939406906383183958298737064924365086071175560501988906753789730930083786567693599492134797230852234912883707809575810061997560245813817036699876221799005582540720450489560203640716799332256956137334545111300264623648046
```

---

## Code Review

We’re given only `v = sin(N)` at very high precision and the knowledge that `N` itself is an **integer** encoding the ASCII flag via big-endian bytes.

Two facts unlock the challenge:

1. Periodicity and symmetry of `sin`:

   ```
   sin(N) = v  ⟺  N =  asin(v) + 2πk  or  N =  π − asin(v) + 2πk,  for some k ∈ ℤ.
   ```
2. Structure of `N`:
   `N = int.from_bytes(flag, "big")` means that converting a correct candidate `N` back to bytes should yield readable ASCII with the usual CTF pattern (e.g., `BPCTF{...}`).

The precision is the lever: with ~300+ decimal digits (from `.n(1024)`), the residual error in `sin` is so small that only an extremely tiny set of integers near the two principal branches can possibly satisfy `sin(N)=v`. That narrows the search over `k` dramatically.

---

## Solution

1. Parse the printed decimal into a high-precision real `v`.
2. Compute

   ```
   a = asin(v)       # principal solution in [-π/2, π/2]
   b = π − a         # the other solution in [π/2, 3π/2]
   ```
3. For each branch, enumerate a small window of integers

   ```
   N_k = round(a + 2πk)     and     N'_k = round(b + 2πk)
   ```

   where `k` is chosen so that `N`’s byte-length is plausible for a flag (say 8–80 bytes; tune as you like).
4. For each integer candidate, verify numerically that `|sin(Ncand) − v|` is below a strict threshold consistent with the provided precision.
5. Convert `Ncand` to bytes (big-endian) and check for printable ASCII and the flag pattern `BPCTF{...}`.

Because the sine value is given at extremely high precision, false positives are practically eliminated.

---

## sin Slayer
`solve.sage`
```python
from sage.all import *

y_str = "-0.8796972610321827563892090184824431008849260677490432314800583299448516158025013449932132939406906383183958298737064924365086071175560501988906753789730930083786567693599492134797230852234912883707809575810061997560245813817036699876221799005582540720450489560203640716799332256956137334545111300264623648046"

prec = 1024
R = RealField(prec)
y = R(y_str)
pi_prec = pi.n(prec=prec) 

x0 = asin(y)
x1 = pi_prec - x0

prefix_bytes = b'BPCTF{'
suffix_int = 125

for i, x_base in enumerate([x0, x1]):
    print(f"Case {i+1}: Trying base solution x{i}")
    
    # We want to solve for k, J: 2*k*pi + x_base ≈ 256*J + 125
    A = (2 * pi_prec) / 256
    B = (suffix_int - x_base) / 256
    C = 2**prec

    # Construct the lattice basis for the CVP -> SVP embedding
    M_cvp = Matrix(ZZ, [
        [1, round(C * A), 0],
        [0, C, 0],
        [0, round(C * B), 1]
    ])

    # Run LLL
    L = M_cvp.LLL()
    
    for row in L:
        if abs(row[2]) == 1:
            k_candidate = -row[0] * row[2]
            print(f"Found a candidate k = {k_candidate}")

            x_candidate = round(2 * k_candidate * pi_prec + x_base)
            
            try:
                num_bytes = (x_candidate.bit_length() + 7) // 8
                flag_bytes = x_candidate.to_bytes(num_bytes, 'big')

                if flag_bytes.startswith(prefix_bytes) and flag_bytes.endswith(b'}'):
                    print(flag_bytes.decode())
                    exit()
            except Exception as e:
                print(f"Failed: {e}")

```

---

## FLAG

```
BPCTF{c4n_LLL_be_used_too?!?}
```

---

## Takeaway

* High precision plus structure beats ambiguity: `sin`’s `2πk` family collapses to a tiny set of integer candidates at 300+ digits.
* Validating with a re-sine check and ASCII/format filters is enough to isolate the true `N`.
* If a challenge maps secrets into an integer and then through a periodic transcendental with massive precision, a targeted inverse search is usually feasible.

# Super Computer

> You don’t need a supercomputer. You just need Euclid.

---

## Challenge Description
`chall.py`
```python
from Crypto.Util.number import GCD
from Crypto.Cipher import AES
import random 

k1 = 721919140332708275664160621428853988653441049264644517303176376909
k2 = 762740838008948738628397951381835990843814483667554565638672490531

k = GCD((2024 ** k1 - 1) * (2024 ** k1 + 1), (2024 ** k2 - 1) * (2024 ** k2 + 1)) 

random.seed(k)
key = random.randbytes(16)

iv = b"S\x0f\xac'\xd0\x18\xfb\xe3\x92\xfdoc\x93\x7fJ\xfc"
ciphertext = b"8\x9a>&=Q\xc14\xcf\xab\xac\xbaa@\xa0s..."
cipher = AES.new(key = key, iv = iv, mode = AES.MODE_CBC)
flag = cipher.decrypt(ciphertext)
print(flag)
```
The statement said:

> "This challenge is free flag! If you have super computer :)"

That’s suspiciously ironic. No one gives away free flags.  
Let’s look closer.

---

## Code Review

At first glance, it looks brutal — exponentiating `2024 ** huge_number` twice and taking a GCD of monstrous values.
That’s where the “Super Computer” joke comes in.
But cryptography is all about patterns.

Let’s factor this down.
We see:

```
k = GCD((2024^k1 - 1)(2024^k1 + 1), (2024^k2 - 1)(2024^k2 + 1))
```

This looks scary, but algebra helps.

Because
`(a^x - 1)(a^x + 1) = a^(2x) - 1`,
we have:

```
k = GCD(2024^(2k1) - 1, 2024^(2k2) - 1)
```
Now comes the trick:
```
GCD(a^m - 1, a^n - 1) = a^gcd(m, n) - 1
```
Therefore:
```
k = 2024^(2 * gcd(k1, k2)) - 1
```

No need for exponentiation at all — just **Euclid’s algorithm**.

---

## Solution

1. Apply the GCD identity:
   `gcd(a^x - 1, a^y - 1) = a^gcd(x, y) - 1`
2. Simplify exponents with factor of 2.
3. So, we can compute:

   ```python
   gcd_val = GCD(k1, k2)
   seed = 2024 ** (2 * gcd_val) - 1
   random.seed(seed)
   ```
4. Generate the AES key and decrypt.

---

## Super Computer Slayer
`solve.py`

```
from Crypto.Util.number import GCD
from Crypto.Cipher import AES
import random

k1 = 721919140332708275664160621428853988653441049264644517303176376909
k2 = 762740838008948738628397951381835990843814483667554565638672490531
iv = b"S\x0f\xac'\xd0\x18\xfb\xe3\x92\xfdoc\x93\x7fJ\xfc"
ciphertext = b"8\x9a>&=Q\xc14\xcf\xab\xac\xbaa@\xa0s\xd4T\x18\x1f\x82\x04F\xdb\xa2\xc2\xb9V\x04\xcbG6\xe54U\x1d2\xe2q\x0b\xe6\x9b\x1e\x8d\xc6\x8c7/"

gcd_val = GCD(k1, k2)
seed = pow(2024, 2 * gcd_val) - 1
random.seed(seed)
aes_key = random.randbytes(16)

cipher = AES.new(key=aes_key, iv=iv, mode=AES.MODE_CBC)
decrypted_padded = cipher.decrypt(ciphertext)
flag = decrypted_padded[:-decrypted_padded[-1]].decode()

print(f"[*] AES key: {aes_key.hex()}")
print(f"[*] Decrypted flag: {flag}")
```

---

## FLAG

```
BPCTF{All_we_need_is_Euclid_algorithm}
```

---

## Takeaway

* Never trust a “supercomputer” claim — mathematics usually has a shortcut.
* The GCD identity `gcd(a^m - 1, a^n - 1) = a^gcd(m, n) - 1` is a **life-saver**.
* “Super Computer” wasn’t about computation power — it was about recognizing structure.

> Sometimes, the fastest computer is a clever brain with Euclid’s algorithm.

# Super Computer V2

> If v1 made you reach for Euclid, v2 makes you reach for algebra and number-theory patience.

---

## Challenge Description

`chall.py`
```python
p = 105063592580446545974028951012743983897531876308535061339451568776273476140417
a = [...10 big ints...]
b = [...10 big ints...]
y = b

# This challenge is free flag! If you have super computer v2 :) 
n = 2 ** 2976579765

for i in range(n):
    x = sum(aa * yy for aa, yy in zip(a, y)) % p
    y = [x] + y[:0:-1]

random.seed(x)

k = random.randbytes(16)

iv = b"..."
ct = b"..."

cipher = AES.new(key = k, iv = iv, mode = AES.MODE_CBC)

print(cipher.decrypt(ct))
```

This is the intimidating part: an enormous loop `for i in range(2**2976579765)` that computes a linear recurrence over the field `GF(p)` and then seeds Python's PRNG with the final `x`, which becomes the AES key used to decrypt the ciphertext. The naive interpretation suggests you need a "supercomputer" to run the loop. 

---

## Code Review

The real challenge is recognizing **structure** inside the recurrence and using modular arithmetic identities to jump to the final state without simulating the loop.

The solution performs algebraic simplifications and uses fast exponentiation and geometric series formulas to compute the final seed `x` directly (so you never run the huge loop). The `chall.py` precomputes a few derived values (`c0 = a0^2 mod p`, an exponent reduction via Fermat/Euler style modular exponent reduction, a geometric series sum modulo `p`, and several dot products) and finally composes `x_seed` from these terms. Then `random.seed(x_seed)` and AES key generation follow to decrypt the ciphertext. 

Concretely, the solver:

1. Reduces the monstrous iteration count by expressing the linear recurrence as a matrix/exponentiation-like process and extracting the closed form for the state after `2^m` steps (using properties of geometric series in modulus `p`).
2. Computes `c0_m = c0^(2^m mod (p-1)) mod p` to avoid enormous exponents by reducing modulo `p-1` (Fermat/Euler exponent reduction).
3. Uses the geometric series formula `sum_{t=0}^{M-1} r^t = (r^M - 1) / (r - 1)` modulo `p` (with modular inverse for denominator).
4. Reconstructs the final `x` as a linear combination of precomputed terms (the `term1 + term2` pattern), then seeds the PRNG with that `x`. 

No brute force, no iteration to `2**2976579765` — just algebra, modular arithmetic, and exponent reduction.

---

## Solution

1. Identify the recurrence and observe it is linear over `GF(p)`. Representing the state evolution in closed form is possible because coefficients are fixed and the iteration count is a power of two.
2. Reduce giant exponents using exponentiation modulo `p-1` (by Fermat/Euler), i.e. compute `2^m mod (p-1)` rather than `2^m` itself.
3. Compute the geometric sum modulo `p` with a modular inverse for `(c0 - 1)`.
4. Compute the dot-product terms and final `x_seed` algebraically (no loop).
5. `random.seed(x_seed)`, generate the AES key via `random.randbytes(16)` (or equivalent fallback), decrypt the provided ciphertext with the known IV and AES-CBC, then remove PKCS#7 padding to obtain the flag. 

---

## Super Computer V2 Slayer

```python
from Crypto.Cipher import AES
import random

p = 105063592580446545974028951012743983897531876308535061339451568776273476140417
a = [83976481011811924301399130599504493293806898813567214331578547737846462043958, 49020426275786164529115108197272670769137595551571093637487791519433419519672, 24128105217328007401966909205085981217503713864081435807557452995781759742691, 54164402277699203441372828355514660347224703731247371001251599709472819892728, 5692038086237571692337343150891799220298365811757620367764289696380335050730, 9194117858273293290441837426276641586104842710061165598417982956745859622444, 27514892046750325649899981908633136074585793442699873185550644927834059630396, 66943725126331355485802310409645040036783514684318190205044041417883671830813, 36611954202140140239054776427180396851470554264500586218901125625358436893646, 93863495610885066386571402764570126016623604962463646403287688220849161122613]
b = [97461761096716147515500249810325859398244538389518130625167636466504806053237, 16186849429230042905493135221645960782811658483413984147534270789857649397900, 71342178650803093723481761619050183147490358888778566439516835390010233583079, 42978771428288111481549054267767962257445180314707234054048040896605726288851, 29120967694716870074542540604659996320145561630287811543954439503459626728291, 42698044025699644061005796009375197205179997240105171525488864698040253468486, 7809495582561305433394495659190738835412543684981410733357553129731203148539, 32385280315917393807024145684356627341683296786146343663491116566930261796667, 13004050673282999217589086204520195844228711320714522230534397332477244173876, 71584418374288378249025460600779108813126354610745231566224182660591294310622]
iv = b"S\x0f\xac'\xd0\x18\xfb\xe3\x92\xfdoc\x93\x7fJ\xfc"
ct = b"9\x18~C<3\xba\x04\xfb\x04t\x94\x7f\x86t\xb7\x9b\x9b\xc0N8\x0c\x8er]\x14\xfd\x033\xac;PVa\xd0m\xfdH\xf4pI\xf7s\xd5\xc2\x03\t\x9a\x1d\x96<?k\x16\xc0GVp\xcdj#\xde\xe8\x991\xb7k\xc7\xe2^\xd5h\xa7\xf8\x07\x02\xf9\xcee\xbej \x86y\xf6\xf3T\x8c8\x85\x11Ps\xb1E\xe5WK\xb3\xcbE}\xbb\xc7\x10\xea\xb92FJ\xf6\xde&I\x99\xd8\xa9\xae\x94\x0675\xcelc\x1a\xe4\x9c"

a0 = a[0]
b0 = b[0]
c0 = pow(a0, 2, p)
m_exponent = 2976579764

USE_FAST_EXPONENT = True
if USE_FAST_EXPONENT:
    exp_mod = pow(2, m_exponent, p - 1)
    c0_m = pow(c0, exp_mod, p)
else:
    big_exp = pow(2, m_exponent)
    c0_m = pow(c0, big_exp, p)

numerator = (c0_m - 1 + p) % p
denominator_inv = pow((c0 - 1) % p, -1, p)
geo_sum = (numerator * denominator_inv) % p
c_vec = [(a0 * a[i] + a[10 - i]) % p for i in range(1, 10)]
c_dot_b_term = sum((c_vec[j] * b[j + 1]) % p for j in range(9)) % p
term1 = (c0_m * b0) % p
term2 = (geo_sum * c_dot_b_term) % p
x_seed = (term1 + term2) % p

print(f"[*] Calculated seed: {x_seed}")

random.seed(x_seed)
try:
    key = random.randbytes(16)
except AttributeError:
    key = random.getrandbits(16 * 8).to_bytes(16, "big")

cipher = AES.new(key=key, iv=iv, mode=AES.MODE_CBC)
plaintext = cipher.decrypt(ct)

try:
    pad_len = plaintext[-1]
    if pad_len < 1 or pad_len > AES.block_size:
        raise ValueError("Padding length out of range")
    unpadded_plaintext = plaintext[:-pad_len]
    flag = unpadded_plaintext.decode('utf-8', errors='replace')

    print(f"{flag}")
except Exception as e:
    print(f"[!] ERROR {e}")
```
---

## FLAG
```
BPCTF{Man1pula7in6_M4tr1X_l1k3_M4gic}
```
---

## Takeaway

* A huge loop or astronomical exponent often masks algebraic shortcuts. Look for linear recurrences, matrix/polynomial closed forms, and geometric sums.
* Reduce exponents modulo `p-1` where appropriate (Fermat/Euler) to avoid impossible computations.
* When a PRNG seed is derived from a structured arithmetic process, recovering the seed algebraically breaks the scheme — no brute force required.
* The "supercomputer" in the challenge title is rhetorical; the real power is careful math.