I participated in zer0pts CTF as a member of Wani Hackase, and solved 2 cryptography challenges.

## war(sa)mup [warmup, crypto, 95 solves]

We are given a public key $$(n, e)$$ and two ciphertexts $$c_1, c_2$$.

$\begin{eqnarray*} c_1 &\equiv& m^e \pmod n \\ c_2 &\equiv& \left\lfloor \frac{m}{2} \right\rfloor ^e \pmod n \end{eqnarray*}$

Let $$x := \lfloor \frac{m}{2} \rfloor$$ and $$f_1, f_2$$ be two polynomials over $$\mathbb{Z}/n\mathbb{Z}$$.

$\begin{eqnarray*} f_1 &=& (2x+1)^e - c_1 \\ f_2 &=& x^e - c_2 \end{eqnarray*}$

These polynomials should have a common factor $$(x - \left\lfloor \frac{m}{2} \right\rfloor)$$. Therefore, we can get $$\left\lfloor \frac{m}{2} \right\rfloor$$ by calculating the greatest common divisor of $$(f_1, f_2)$$.

from Crypto.Util.number import long_to_bytes

def gcd(a, b):
while b != 0:
a, b = b, a%b
return a

n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1 = 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2 = 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762

PR.<x> = PolynomialRing(Zmod(n))
f1 = (2*x+1)^e - c1
f2 = x^e - c2
r = gcd(f1, f2)
x0 = int(-r.monic()[0])
flag = long_to_bytes(2*x0 + 1)
print(flag)

Flag: zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}

## OT or NOT OT [crypto, 69solves]

The main objective is to recover AES key from other parameters. Here's a summary of parameters.
Known:

• $$p$$, 1024-bit prime
• $$t \in [2, p-1]$$
• $$a, b, c, d \in [2, p-1]$$, distinct numbers
• $$x = u \oplus ({\rm key} \verb|&| 1)$$
• $$y = v \oplus (({\rm key \verb|>>| 1}) \verb|&| 1)$$
• $$z = d^r t^s \pmod p$$

Unknown:

• $$u \equiv a^r c^s \pmod p$$
• $$v \equiv b^r c^s \pmod p$$
• $${\rm key}$$

We can get the lower 2 bits of the key in every iteration, but there's no way to know $$u$$ and $$v$$. After a little thought, I noticed the difference between $$x$$ and $$u$$ is only 1 bit. The same is true for $$y$$ and $$v$$. So we can recover $$u, v$$ by bruteforcing the bit and checking if an equation for recovered values is true or not.

Let $$(a, b, c, d) = (8, 4, t, 2)$$ and try bruteforcing $$(u, v) = (x, y), (x, y \oplus 1) ,(x \oplus 1, y), (x \oplus 1, y \oplus 1)$$.
If $$(u, v)$$ is correct, we have

$\begin{eqnarray*} uv^{-1} &\equiv& (a^r c^s)(b^{-r} c^{-s}) \pmod p \\ &\equiv& (ab^{-1})^r \\ &\equiv& 2^r \end{eqnarray*}$

$\begin{eqnarray*} vz^{-1} &\equiv& (b^r c^s)(d^{-r} t^{-s}) \pmod p \\ &\equiv& (bd^{-1})^r \\ &\equiv& 2^r. \end{eqnarray*}$

Therefore, we can decide $$u$$ and $$v$$ by checking if $$uv^{-1} \equiv vz^{-1} \pmod p$$.

(I haven't proven that this method works correctly, but it succeeds with a high probability.)

import ast
import base64

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from pwn import remote

s = remote("crypto.ctf.zer0pts.com", 10130)

enc = s.recvline().removeprefix(b"Encrypted flag: ")
p = ast.literal_eval(s.recvline().decode().removeprefix("p = "))
key_bitlength = ast.literal_eval(s.recvline().decode().removeprefix("key.bit_length() = "))
key = 0

for i in range(key_bitlength + 1 >> 1):
print(f"{i+1}/{key_bitlength+1>>1}")
t = ast.literal_eval(s.recvline().decode().removeprefix("t = "))
a, b, c, d = 8, 4, t, 2
s.recvuntil("a = ")
s.sendline(str(a))
s.recvuntil("b = ")
s.sendline(str(b))
s.recvuntil("c = ")
s.sendline(str(c))
s.recvuntil("d = ")
s.sendline(str(d))
x = ast.literal_eval(s.recvline().decode().removeprefix("x = "))
y = ast.literal_eval(s.recvline().decode().removeprefix("y = "))
z = ast.literal_eval(s.recvline().decode().removeprefix("z = "))

for k in range(0b100):
u = x ^ (k & 1)
v = y ^ ((k >> 1) & 1)
if u * pow(v, -1, p) % p == v * pow(z, -1, p) % p:
key |= k << 2 * i
break

key = long_to_bytes(key)
enc = base64.b64decode(enc)
iv, ciphertext = enc[:16], enc[16:]
cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
flag = cipher.decrypt(ciphertext)
print(flag)

Flag: zer0pts{H41131uj4h_H41131uj4h}