diploma

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}