# Naptime (crypto)

{% file src="<https://243380073-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FBIa0PcXGYuP6chd3J1Ry%2Fuploads%2FozpBiuYYdXcwGKm7OhJ4%2Fpub.txt?alt=media&token=64e46d68-b2d8-42f3-aea8-dc201cad8b8a>" %}

{% file src="<https://243380073-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FBIa0PcXGYuP6chd3J1Ry%2Fuploads%2FZd5Mk23AI0xwnSQBjCOh%2Fenc_dist.sage?alt=media&token=997a4d74-f6b7-4b59-b4f7-ba1c471ac8df>" %}

The given sage file implements the encryption scheme:

```python
from random import randint
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import numpy as np

def get_b(n):
    b = []
    b.append(randint(2**(n-1), 2**n))
    for i in range(n - 1):
        lb = sum(b)
        found = False
        while not found:
            num = randint(max(2**(n + i), lb + 1), 2**(n + i + 1))
            if num > lb:
                found = True
                b.append(num)

    return b

def get_MW(b):
    lb = sum(b)
    M = randint(lb + 1, 2*lb)
    W = getPrime(int(1.5*len(b)))

    return M, W

def get_a(b, M, W):
    a_ = []
    for num in b:
        a_.append(num * W % M)
    pi = np.random.permutation(list(i for i in range(len(b)))).tolist()
    a = [a_[pi[i]] for i in range(len(b))]
    return a, pi


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

def dec(ct, a, b, pi, M, W, n):
    # construct inverse permuation to pi
    pii = np.argsort(pi).tolist()
    m = ""
    U = pow(W, -1, M)
    ct = [c * U % M for c in ct]
    for c in ct:
        # find b_pi(j)
        diff = 0
        bits = ["0" for _ in range(n)]
        for i in reversed(range(n)):
            if c - diff > sum(b[:i]):
                diff += b[i]
                bits[pii[i]] = "1"
        # convert bits to character
        m += chr(int("".join(bits), base=2))

    return m


def main():
    flag = 'uiuctf{I_DID_NOT_LEAVE_THE_FLAG_THIS_TIME}'

    # generate cryptosystem
    n = 8
    b = get_b(n)
    M, W = get_MW(b)
    a, pi = get_a(b, M, W)

    # encrypt
    ct = enc(flag, a, n)

    # public information
    print(f"{a =  }")
    print(f"{ct = }")

    # decrypt
    res = dec(ct, a, b, pi, M, W, n)

if __name__ == "__main__":
    main()
```

Let's look at the `main()` function first. It generates the cryptosystem starting from `n = 8`. Using `n`, we generate `b` using `get_b(n)`. Looking at the function, it just seems to be generating an array of 8 random integers. Then we generate `M` and `W` using `get_MW()`. `M` is a random integer, whereas `W` is a random 12-bit prime. Then, `a` and `pi` are generated using `get_a(b, M, W)`.&#x20;

```python
def get_a(b, M, W):
    a_ = []
    for num in b:
        a_.append(num * W % M)
    pi = np.random.permutation(list(i for i in range(len(b)))).tolist()
    a = [a_[pi[i]] for i in range(len(b))]
    return a, pi
```

`get_a` makes `a_`, which is an array containing each element in `b` multiplied by `W` and modulo `M`. `pi` is a random permutation of `[0,1,2,...,7]`. Then, `a` is `a_` but shuffled according to the indexes given by `pi`.

Once the cryptosystem generation is done, the ciphertext `ct` is obtained using `enc(flag, a, n)`.&#x20;

```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
```

The encryption algorithm iterates through each character `c` in the flag. Each character is converted into an 8-bit bitstring and added to the array `bitstrings`. Then, it iterates through each bitstring `bits` in the array. For each bitstring, we maintain a sum `curr`. When the bit at an index `i` is `1`, we add `a[i]` to `curr`. So for example if we had a bitstring `01011101`, we would have `curr = a[1] + a[3] + a[4] + a[5] + a[7]`. After the 8 bits have been iterated through, the sum `curr` is appended to the array `ct`.&#x20;

We are given the array `a` and the ciphertext `ct`.&#x20;

Thinking about this problem, every 8-bit character is represented as a sum of the elements in `a`. This is essentially a 0/1 knapsack problem, where we want to find out which elements of `a` to add to the sum for each ciphertext integer in `ct`.&#x20;

To solve this problem, we can iterate through all `2^8=256` possible characters, and calculate the sum which each character would give us. Then, for each integer in `ct`, we just need to match its sum with the character that produces that sum. This allows us to work backwards from integers in `ct` to characters in the plaintext!

The script below uses a dictionary whose keys are the sum each character gives, and its values are the respective character. After the dictionary is filled with all 256 key-value pairs, I iterate through each integer in `ct`, obtain the corresponding plaintext character using the dictionary, and append it to `flag`.&#x20;

```python
a =  [66128, 61158, 36912, 65196, 15611, 45292, 84119, 65338]
ct = [273896, 179019, 273896, 247527, 208558, 227481, 328334, 179019, 336714, 292819, 102108, 208558, 336714, 312723, 158973, 208700, 208700, 163266, 244215, 336714, 312723, 102108, 336714, 142107, 336714, 167446, 251565, 227481, 296857, 336714, 208558, 113681, 251565, 336714, 227481, 158973, 147400, 292819, 289507]

# generate all 2^8 permutations; for each element in a we either take it or we don't
mapping = dict()
for i in range(0, 256):
    bitstring = bin(i)[2:].zfill(8)
    curr = 0
    for j, b in enumerate(bitstring):
        if b == "1":
            curr += a[j]
    mapping[curr] = chr(i)
# print(mapping)
flag = ""

for i in ct:
    flag += mapping[i]

print(flag) # uiuctf{i_g0t_sleepy_s0_I_13f7_th3_fl4g}
```