crypto

Lamir

Punkty: 175

Rozwiązań: 41

Got only 1 share where 3 are needed? Shamir and Lagrange say this can't be solved.

lamir.py

import binascii
import sys
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import inverse, long_to_bytes
from typing import Tuple, List
from Crypto.Util.number import getPrime

Share = Tuple[int, int]


class SSS:
    def __init__(self, threshold: int, shares: int, p: int, secret: int):
        assert shares > threshold
        self.coefficients = [random.randint(1, 2 ** 128) for _ in range(threshold - 1)] + [secret]
        self.shares = shares
        self.p = p

    def recover_secret(self, shares: List[Share]) -> int:
        assert len(shares) >= (len(self.coefficients))
        total = 0
        for j, share_j in enumerate(shares):
            xj, yj = share_j
            prod = 1
            for i, share_i in enumerate(shares):
                xi, _ = share_i
                if i != j:
                    prod *= (xi * inverse(xi - xj, self.p)) % self.p
            prod *= yj
            total += prod
        return total % self.p

    def polynomial_value(self, x: int) -> int:
        y = 0
        for index, coefficient in enumerate(self.coefficients[::-1]):
            y += x ** index * coefficient
        return y % self.p

    def generate_shares(self) -> List[Share]:
        shares = []
        for i in range(self.shares):
            x = random.randint(1, self.p)
            shares.append((x, self.polynomial_value(x)))
        return shares


def main():
    if len(sys.argv)<2:
        sys.stderr.write(f"{sys.argv[0]} flag_file\n")
        return
    flag = open(sys.argv[1], 'rb').read()
    p = getPrime(1024)
    print(p)
    secret = random.randint(0, 2 ** 128)
    aes_key = long_to_bytes(secret, 16)
    aes = AES.new(aes_key, AES.MODE_ECB)
    print(binascii.hexlify(aes.encrypt(pad(flag, 16))))
    s = 5
    t = 3
    padded_secret = secret * 2 ** 768
    sss = SSS(t, s, p, padded_secret)
    shares = sss.generate_shares()
    assert len(shares) == s
    assert sss.recover_secret(shares) == padded_secret
    assert sss.recover_secret(shares[:t]) == padded_secret
    x, y = shares[0]
    print(x)
    print(y)


if __name__ == '__main__':
    main()

out.txt

143743714667196952058900759261407323698756850133867265136150007855290420143070654830669593475191803004953810209230946510931572518918538662616021440452337240214101762994942987037198290408041514299462751377204767166967808574043704351745008991508233657591000549042018949381482851540302064230579632232840191454169
b'f4f85530dc8542de58db717a87ea0ec94614ab1089be791067b9391bcf3a1d5b032aea1cd17df2cc3cb5e5849b56337b'
104750360500342137067959022556272887374572818719019821415800094049828335325339153120299181829763181312266996468846997901272412878992535199376659696342712119307569135604623476596446008985312558455128096460793297986949635056445646044250541035798858842254071995726872072346048515376676380097608343638078089036463
81035742851364952796729284100854680488736009642765667043567806973064528210002686748133377624813373188180470748695343706175230511332491530906656121287034090730006844878275332589565422230899776681914487384215576655553023152788564010945149320033946203694906547435607625130574922215440874250943315340262024922787

Format flagi: ecsc26{litery_cyfry_i_znaki_specjalne}.
W razie wątpliwości lub pytań dotyczących konkursu zapraszamy na naszego Discorda: https://discord.gg/gAtRKa2rcn.