Try   HackMD

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
C1=(pad(m))emodn,C2=(⌊pad(m)2⌋)emodn
.

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

2eC2≡(2∗⌊pad(m)2⌋)emodn. This is from RSA's multiplicative homomorphism. If
pad(m)
is even,
2eC2≡(pad(m))e≡C1modn
. This looks unsolvable. However, if
pad(m)
is odd value,
2eC2≡(2∗⌊pad(m)2⌋)e≡(pad(m)−1)emodn
since
⌊pad(m)2⌋=pad(m)−12
.

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.

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)))

  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. ↩︎