Tags: polynomials 

Rating:

## Gambler

### Challenge

In this challenge, we have access to a server with the following options

```
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Hi, there is a strong relation between philosophy and the gambling! +
+ Gamble as an ancient philosopher and find the flag :) +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
```

Where the encrypttion function is given by:
```python
def encrypt(m, p, a, b):
assert m < p and isPrime(p)
return (m ** 3 + a * m + b) % p
```

### Solution

The goal is to decrypt the flag by recovering the hidden parameters $a,b,p$ and then solving the polynomial used in `encrypt`.

We can recover all parameters quite easily with the function to encrypt our own message.

We can obtain from the server the value of

$$
y(x) = x^3 + ax + b \mod p
$$

for any input $x$.

We can recover $b$ by encrypting 0 as

$$
y(0) = 0^3 + a*0 + b = b \mod p
$$

Where we are assuming that $a,b < p$.

With the value of $b$, we can calculate

$$
y(1) = 1 + a + b \mod p, \quad \Rightarrow \quad a = y(1) - 1 - b
$$

Finally, with both $a,b$ recovered, we need to find the modulus $p$. If we encrypt a fairly small message, such that $y(x) > p$ we can use that

$$
x^3 + ax + b = y(x) + kp, \quad \Rightarrow \quad kp = x^3 + ax + b - y(x)
$$

Since we know a and b, we can compute all the terms on the right hand side of this equation and recover $k p$. All that remains is solving for $k$, which is pretty fast as $k$ is so small.

With all parameters known, we can request the encrypted flag from the server and solve the cubic equation with Sage:
$$
x^3 + ax + b = c \mod p
$$

### Implementation

```py
import os
os.environ["PWNLIB_NOTERM"] = "True"
from pwn import *
from Crypto.Util.number import long_to_bytes

debug = False

r.recvuntil(b'|\t[Q]uit\n')

r.sendline('C')
data = r.recvuntil(b'|\t[Q]uit\n')
enc = int(data.split()[3].decode().strip())

def encrypt_int(n):
r.sendline('T')
r.recvuntil(' your message to encrypt:\n')
r.sendline(str(n))
data = r.recvuntil(b'|\t[Q]uit\n')
b = int(data.split()[3].decode().strip())
return b

b = encrypt_int(0)
c = encrypt_int(1)
a = c - b - 1
enc_kp = encrypt_int(100)
kp = (100**3 + a*100 + b) - enc_kp

if debug:
print(a)
print(b)
print(kp)

p = max(f[0] for f in factor(kp))
PR.<x> = PolynomialRing(GF(p))
f = x^3 + a * x + b - enc
rts = f.roots()
print(rts)

for root in rts:
flag = root[0]
print(long_to_bytes(flag))

r.interactive()
```

### Flag

`CCTF{__Gerolamo__Cardano_4N_itaLi4N_p0lYma7H}`

Original writeup (https://blog.cryptohack.org/cryptoctf2020#gambler).