> For the complete documentation index, see [llms.txt](https://thr34dr1pp3r.gitbook.io/ctf/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://thr34dr1pp3r.gitbook.io/ctf/uiuctf-2024/crypto-naptime.md).

# Crypto-Naptime

## [Full Implementation](https://github.com/kinasant/THR34DR1PP3R/blob/main/2024/UIUCTF/Naptime/sol.ipynb)

## Challenge

```python
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](https://connor-mccartney.github.io/cryptography/other/BackdoorCTF-2023-writeups)

{% file src="/files/8ynOgPQaVZ8pFFn1Dcnm" %}
Pg 18, A Gentle Tutorial for Lattice-Based Cryptanalysis
{% endfile %}

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