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:]))