HITCON CTF 2022 | babySSS

#HITCON_CTF_2022

from random import SystemRandom
from Crypto.Cipher import AES
from hashlib import sha256
from secret import flag

rand = SystemRandom()


def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])


DEGREE = 128
SHARES_FOR_YOU = 8  # I am really stingy :)

poly = [rand.getrandbits(64) for _ in range(DEGREE + 1)]
shares = []
for _ in range(SHARES_FOR_YOU):
    x = rand.getrandbits(16)
    y = polyeval(poly, x)
    shares.append((x, y))
print(shares)

secret = polyeval(poly, 0x48763)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR)
print(cipher.encrypt(flag))
print(cipher.nonce)

Shamir's Secret Sharingだが、剰余が取られていない。でのあまりを取って係数を復元し、CRTで正確な値を求めるとよい

import ast
from hashlib import sha256
from Crypto.Cipher import AES

with open("output.txt") as f:
    shares = ast.literal_eval(f.readline())
    ciphertext = ast.literal_eval(f.readline())
    nonce = ast.literal_eval(f.readline())


def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])


DEGREE = 128
SHARES_FOR_YOU = 8  # I am really stingy :)


coeffs = []
for d in range(DEGREE + 1):
    pairs = []
    values = []
    mods = []
    for i in range(len(shares)):
        x, y = shares[i]
        s = y - polyeval(coeffs, x)
        values.append(s // x**d)
        mods.append(x)

    c = CRT(values, mods)
    coeffs.append(c)


secret = polyeval(coeffs, int(0x48763))
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(ciphertext))