# [crypto] Party Ticket - CakeCTF 2021
###### tags: `CakeCTF 2021`

## overview

$C_i = M(M + B_i) \mod N_i$ という式が2つある。言うまでもなくこれはRabin Cryptosystem

from Crypto.Util.number import getPrime, isPrime
import random

def getSafePrime(bits):
    while True:
        p = getPrime(bits - 1)
        q = 2*p + 1
        if isPrime(q):
            return q

def make_inivitation():
    with open("flag.txt", "rb") as f:
        m = int.from_bytes(f.read().strip(), "big")

    p = getSafePrime(512)
    q = getSafePrime(512)

    n = p * q
    b = random.randint(2, n-1)

    c = m*(m + b) % n

    return c, n, b

# print("Dear Moe:")
print(make_inivitation())

# print("Dear Lulu:")
print(make_inivitation())

## solution

Rabin Cryptosystemは$e = 2$のRSAの素朴な変形のように捉えることもできる。Padding付きの平文に対するHastad's Broadcast Attackが適用できる

$f_1(x) = x^2 + xb_1 - c_1, f_2(x) = x^2 + xb_2 - c_2$とすると、$f_1, f_2$はそれぞれ$\mod n_1, \mod n_2$で$m$を根に持つ

ここで$\mod n_1$で$1$、$\mod n_2$で$0$となるような$k_1$と$\mod n_1$では$0$、$\mod n_2$では$1$となるような$k_2$を考えて$f = k_1f_1 + k_2f_2$とする

すると$f(m) \equiv 0 \mod n_1$, $f(m) \equiv 0 \mod n_2$より、$f(m) \equiv 0 \mod n_1n_2$ であるから、$m$は$f$の$\mod n_1n_2$での根であることがわかる。$m < n_1, n_2 < n_1n_2$であるから、およそ$m < (n_1n_2)^{1/2}$であり、$f$の次数が2であることを考えると十分小さい。

したがって、$f$を定義して$\mod n_1n_2$でのsmall_rootを求めることで$m$が求まる。

import ast

with open("./distfiles/output.txt") as f:
    c1, n1, b1 = ast.literal_eval(f.readline().strip())
    c2, n2, b2 = ast.literal_eval(f.readline().strip())


N = n1 * n2
PR.<x> = PolynomialRing(Zmod(N))

k1 = crt([1, 0], [n1, n2])
k2 = crt([0, 1], [n1, n2])

f1 = x*(x + b1) - c1
f2 = x*(x + b2) - c2

f = k1*f1 + k2*f2
f = f.monic()

for root in f.small_roots():
    print(int(root).to_bytes(100, "big").strip(b"\0"))