Crypto-Naptime

I'm pretty tired. Don't leak my flag while I'm asleep. - Anakin

Full Implementation

Challenge

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 here

752KB

cjloss.pdf

PDF

Open

Pg 18, A Gentle Tutorial for Lattice-Based Cryptanalysis

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}'