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

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

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

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

$$ \begin{aligned} f_1 &= (2x+1)^e - c_1 \\ f_2 &= x^e - c_2 \end{aligned} $$ 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)$.

 1from Crypto.Util.number import long_to_bytes
 2
 3def gcd(a, b):
 4  while b != 0:
 5    a, b = b, a%b
 6  return a
 7
 8n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
 9e = 1337
10c1 = 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
11c2 = 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762
12
13PR.<x> = PolynomialRing(Zmod(n))
14f1 = (2*x+1)^e - c1
15f2 = x^e - c2
16r = gcd(f1, f2)
17x0 = int(-r.monic()[0])
18flag = long_to_bytes(2*x0 + 1)
19print(flag)

Flag: zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}

OT or NOT OT [crypto, 69solves]

Unknown:

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

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

$$ \begin{aligned} vz^{-1} &\equiv (b^r c^s)(d^{-r} t^{-s}) \pmod p \\ &\equiv (bd^{-1})^r \\ &\equiv 2^r. \end{aligned} $$ 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.)

 1import ast
 2import base64
 3
 4from Crypto.Cipher import AES
 5from Crypto.Util.number import long_to_bytes
 6from pwn import remote
 7
 8s = remote("crypto.ctf.zer0pts.com", 10130)
 9
10enc = s.recvline().removeprefix(b"Encrypted flag: ")
11p = ast.literal_eval(s.recvline().decode().removeprefix("p = "))
12key_bitlength = ast.literal_eval(s.recvline().decode().removeprefix("key.bit_length() = "))
13key = 0
14
15for i in range(key_bitlength + 1 >> 1):
16    print(f"{i+1}/{key_bitlength+1>>1}")
17    t = ast.literal_eval(s.recvline().decode().removeprefix("t = "))
18    a, b, c, d = 8, 4, t, 2
19    s.recvuntil("a = ")
20    s.sendline(str(a))
21    s.recvuntil("b = ")
22    s.sendline(str(b))
23    s.recvuntil("c = ")
24    s.sendline(str(c))
25    s.recvuntil("d = ")
26    s.sendline(str(d))
27    x = ast.literal_eval(s.recvline().decode().removeprefix("x = "))
28    y = ast.literal_eval(s.recvline().decode().removeprefix("y = "))
29    z = ast.literal_eval(s.recvline().decode().removeprefix("z = "))
30
31    for k in range(0b100):
32        u = x ^ (k & 1)
33        v = y ^ ((k >> 1) & 1)
34        if u * pow(v, -1, p) % p == v * pow(z, -1, p) % p:
35            key |= k << 2 * i
36            break
37
38key = long_to_bytes(key)
39enc = base64.b64decode(enc)
40iv, ciphertext = enc[:16], enc[16:]
41cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
42flag = cipher.decrypt(ciphertext)
43print(flag)

Flag: zer0pts{H41131uj4h_H41131uj4h}