## 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:```pythondef 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
```pyimport osos.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 - 1enc_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 - encrts = 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}`