# war(sa)mup - zer0pts CTF 2021
###### tags: `zer0pts CTF 2021` `crypto`

## overview

This is the very simple warmup-level RSA challenge. We're given public key $N, e$ and ciphertext $C_1 = (pad(m))^e \mod n, C_2 = (\lfloor \frac{pad(m) }{2} \rfloor)^e \mod n$.

from Crypto.Util.number import getStrongPrime, GCD
from random import randint
from flag import flag
import os

def pad(m: int, n: int):
  # PKCS#1 v1.5 maybe
  ms = m.to_bytes((m.bit_length() + 7) // 8, "big")
  ns = n.to_bytes((n.bit_length() + 7) // 8, "big")
  assert len(ms) <= len(ns) - 11

  ps = b""
  while len(ps) < len(ns) - len(ms) - 3:
    p = os.urandom(1)
    if p != b"\x00":
      ps += p
  return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")


while True:
  p = getStrongPrime(512)
  q = getStrongPrime(512)
  n = p * q
  phi = (p-1)*(q-1)
  e = 1337
  if GCD(phi, e) == 1:
    break

m = pad(int.from_bytes(flag, "big"), n)
c1 = pow(m, e, n)
c2 = pow(m // 2, e, n)

print("n =", n)
print("e =", e)
print("c1=", c1)
print("c2=", c2)

## solution

Considering $2^eC_2 \equiv (2 * \lfloor \frac{pad(m)}{2} \rfloor)^e \mod n$. This is from RSA's multiplicative homomorphism. If $pad(m)$ is even, $2^eC_2 \equiv (pad(m))^e \equiv C_1 \mod n$. This looks unsolvable. However, if $pad(m)$ is odd value, $2^eC_2 \equiv (2 * \lfloor \frac{pad(m)}{2} \rfloor)^e \equiv (pad(m) - 1)^e \mod n$ since $\lfloor \frac{pad(m)}{2} \rfloor = \frac{pad(m)-1}{2}$.

Then we get two cipheretexts and a difference of their plantexts. As $e$ is small[^1], we can apply the **Franklin-Reiter's Related Message Attack**.

[^1]: The plagiarism challenge in diceCTF 2021 introduces us the Half-GCD method which solves polynomial GCD faster than euclidean method. So we can solve this challenge if even $e$ is not so small. I didn't know such a great way when I've created this challenge.

Only the problem is $pad(m)$ is even or odd. We have 1/2 chance of win. Additionally, as $m$ is the flag, we can guess it ends with `}`. It is odd value, then $m$ and $pad(m)$ is odd value highly probability.

## exploit

def pgcd(a, b):
  while b:
    a, b = b, a % b
  return a.monic()

def unpad(m: int):
  m = int(m).to_bytes((m.bit_length() + 7) // 8, "big")
  return m.split(b"\x00", 2)[-1]

exec(open("output.txt").read())

PR.<x> = PolynomialRing(Zmod(n))

c2_ = c2 * pow(2,e,n)%n
f1 = (x)^e - c1
f2 = (x - 1)^e - c2_

m = -pgcd(f1, f2)[0]
print(unpad(int(m)))