#!/usr/bin/env sage F = RealField(10**4) def recover(pk): n = len(pk) // 4 Tx, x = map(F, pk.split('\0')[:2]) a = arccos(Tx) / arccos(x) b = F(2*pi) / arccos(x) # find an integer k such that a + k * b is close to an integer B = 10**(2*n) M = matrix([[B, 0, round(a*B)], [0, 1, round(b*B)], [0, 0, B]]) for l in M.LLL().rows(): if l[0]: k = sign(l[0]) * l[1] break guess = abs(round(a + k * b)) # brute-force a small range in case we are slightly off for d in range(256): for s in (-1, +1): if abs(cos((guess + s * d) * arccos(x)) - Tx) < 1e-10: return guess + s * d kat = 0 for n in (110, 160, 210): for l in open('KAT/PQCkemKAT_{}.rsp'.format(n)): if l.startswith('pk = '): pk = l[len('pk = '):].strip().decode('hex') elif l.startswith('sk = '): # only used for verifying the recovered secret. sk = ZZ(l[len('sk = '):].strip().decode('hex').split('\0')[0]) print('attacking known-answer test #{}'.format(kat)) print('correct secret: {}'.format(sk)) secret = recover(pk) print('recovered secret: {} ({})\n'.format(secret, secret == sk)) kat += 1