# 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="<https://2017398282-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUn3m91wNDAeWCUHREmIX%2Fuploads%2F5yVyn7NUs6BB2WTxbr01%2Fcjloss.pdf?alt=media&token=35f07565-d305-4c1f-a48d-ac72b7f266f9>" %}
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}'
```