SECCON Beginners 2021 | Field Trip

#secconbeginners2021

from Crypto.Util.number import *
from random import getrandbits
from flag import flag


flag = bytes_to_long(flag.encode("utf-8"))
flag = bin(flag)[2:]
length = len(flag)

A = []
a, b = 0, 0
for _ in range(length):
    a += getrandbits(32) + b
    b += a
    A.append(a)

p = getStrongPrime(512)
q = getStrongPrime(512)

assert q > sum(A)

pub_key = [a * p % q for a in A]
cipher = sum([int(flag[i]) * pub_key[i] for i in range(length)])

f = open("output.txt", "w")
f.write("pub_key = " + str(pub_key) + "\n")
f.write("cipher = " + str(cipher) + "\n")
f.close()

どこからどうみてもナップザック暗号なのでやるだけ

import ast
with open("output.txt") as f:
    pubkey = ast.literal_eval(f.readline().strip().split(" = ")[1])
    cipher = ast.literal_eval(f.readline().strip().split(" = ")[1])


b = pubkey
c = cipher

# check the density
n = len(b)
d = float(n / log(max(b), 2))
print(d)
# assert(d < 0.9048)

# low-density attack, CLOS method
# prepare a basis
MULTIPLIER = 100
B = matrix(ZZ, n + 1, n + 1)
B.set_block(0, 0, MULTIPLIER * matrix(n, 1, b))
B.set_block(n, 0, MULTIPLIER * matrix([-c]))
B.set_block(0, 1, 2 * identity_matrix(n))
B.set_block(n, 1, matrix([-1] * n))

# LLL algorithm
for x in B.LLL():
    # print(x)
    if x[0] == 0 and all((x_i in [-1, +1]) for x_i in x[1:]):
        print('x={}'.format(x))

        # decode x
        m = 0
        for x_i in x:
            m *= 2
            m += int(x_i == +1)
        print(bytes.fromhex(hex(m)[2:]))