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