SECCON CTF 2022 Quals | BBB

#SECCON_CTF_2022_Quals

#xornet

from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from math import gcd
from secret import FLAG
from os import urandom


assert len(FLAG) < 100


def generate_key(rng, seed):
    e = rng(seed)
    while True:
        for _ in range(randint(10,100)):
            e = rng(e)
        p = getPrime(1024)
        q = getPrime(1024)
        phi = (p-1)*(q-1)
        if gcd(e, phi) == 1:
            break

    n = p*q
    return (n, e)


def generate_params():
    p = getPrime(1024)
    a = randint(0, p-1)

    return (p,a)


def main():
    p,a = generate_params()
    print("[+] The parameters of RNG:")
    print(f"{a=}")
    print(f"{p=}")
    b = int(input("[+] Inject [b]ackdoor!!: "))
    rng = lambda x: (x**2 + a*x + b) % p

    keys = []
    seeds = []
    for i in range(5):
        seed = int(input("[+] Please input seed: "))
        seed %= p
        if seed in seeds:
            print("[!] Same seeds are not allowed!!")
            exit()
        seeds.append(seed)
        n, e = generate_key(rng, seed)
        if e <= 10:
            print("[!] `e` is so small!!")
            exit()

        keys.append((n,e))

    flag = bytes_to_long(FLAG + urandom(16))
    for n,e in keys:
        c = pow(flag, e, n)
        print("[+] Public Key:")
        print(f"{n=}")
        print(f"{e=}")
        print("[+] Cipher Text:", c)


if __name__ == "__main__":
    main()

RSAだが、が可変でという式を用いてと計算される。この式のうちが教えてもらえて、はこちらで事前に決められる

5回、それぞれ異なるを渡すと、それを用いてが計算され、そのを用いてフラグが暗号化される

平文の長さとの関係からがすべて11になるようにを決められればHastad Broadcast Attackができる。したがって、とその回が11に収束する異なる5つの不動点を探すことがこの問題の本質

• まず を決める。 は となるように定めたいので、 を解けば決まる

• 続いて の5つの不動点を求める。 は確実なので、seedの一つは でよい

• 適当に となる を求めたら、次は となるような を求める……として次々にseedを求められる

• そしてこれは を解けば全部求まるんじゃないか…？

• なんかうまくイカなかったと思う

from ptrlib import Socket

sock = Socket("bbb.seccon.games", 8080)
a = int(sock.recvlineafter("a="))
p = int(sock.recvlineafter("p="))

PR.<b> = GF(p)[]
f = 11**2 + 11*a + b - 11
b = f.roots()[0][0]

PR.<x> = GF(p)[]
f = x**2 + x*a + int(b)
assert f(11) == 11

roots = [11]
unused = {11}
while True:
    rs = (f - unused.pop()).roots(multiplicities=False)
    for r in rs:
        if r not in roots:
            roots.append(r)
            unused.add(r)
    if len(roots) >= 5:
        break

print(roots)

sock.sendlineafter("[b]ackdoor!!: ", str(b))
for r in roots[:5]:
    sock.sendlineafter("seed: ", str(r))

ns = []
cs = []
for _ in range(5):
    ns.append(int(sock.recvlineafter("n=")))
    cs.append(int(sock.recvlineafter("Cipher Text: ")))

m11 = CRT(cs, ns)
m = m11.nth_root(11)

print(bytes.fromhex(hex(m)[2:]))