def enc(flag, a, n):
bitstrings = []
for c in flag:
# c -> int -> 8-bit binary string
bitstrings.append(bin(ord(c))[2:].zfill(8))
ct = []
for bits in bitstrings:
curr = 0
for i, b in enumerate(bits):
if b == "1":
curr += a[i]
ct.append(curr)
return ct
Despite there being an alternative method of decryption in the challenge by bruteforce, we can see that this is a knapsack question.
We use the CJLOSS algorithm given below and the code from
from sage.crypto.util import bin_to_ascii
def improved_basis(arr,s):
M = identity_matrix(QQ, len(arr))
M = M.augment(vector(arr))
M = M.stack(vector([-1/2 for _ in range(len(arr))] + [-s])
for row in M.LLL():
for row in (row, -row):
if row[-1] == 0:
subset = [arr[i] for i, x in enumerate(row[:-1]) if x+1/2==1]
if sum(subset) == s:
return row
return None
flag=''
for i in ct:
r1=improved_basis(a,i)
flag+=bin_to_ascii(''.join(str(i+1/2) for i in r1[:-1]))
print(flag)
'uiuctf{i_g0t_sleepy_s0_I_13f7_th3_fl4g}'