> For the complete documentation index, see [llms.txt](https://ctf.zeyu2001.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ctf.zeyu2001.com/2021/uiuctf-2021/back_to_basics.md).

# back\_to\_basics

## Description

Shoutout to those people who think that base64 is proper encryption

**author**: epistemologist

{% file src="/files/-Mg9POGzlc1qn0QPTlMy" %}
main.py
{% endfile %}

{% file src="/files/vlFWOvWByQWNraUWxzMi" %}
flag\_enc
{% endfile %}

## Solution

We are provided with the following source code.

```python
from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import mpz, to_binary
#from secret import flag, key

ALPHABET = bytearray(b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ#")

def base_n_encode(bytes_in, base):
	  return mpz(bytes_to_long(bytes_in)).digits(base).upper().encode()

def base_n_decode(bytes_in, base):
	  bytes_out = to_binary(mpz(bytes_in, base=base))[:1:-1]
	  return bytes_out

def encrypt(bytes_in, key):
	  out = bytes_in
	  for i in key:
		    print(i)
		    out = base_n_encode(out, ALPHABET.index(i))
	  return out

def decrypt(bytes_in, key):
	  out = bytes_in
	  for i in key:
		    out = base_n_decode(out, ALPHABET.index(i))
	  return out

"""
flag_enc = encrypt(flag, key)
f = open("flag_enc", "wb")
f.write(flag_enc)
f.close()
"""
```

This is a custom encryption algorithm that repeatedly base-*n* encodes the ciphertext for each character of the key. In the encryption function, we see that the base is determined by the position of the key character `i` in the `ALPHABET`.

```python
def encrypt(bytes_in, key):
	  out = bytes_in
	  for i in key:
		    print(i)
		    out = base_n_encode(out, ALPHABET.index(i))
	  return out
```

The `base_n_encode()` simply implements the base-*n* encoding.

```python
def base_n_encode(bytes_in, base):
	  return mpz(bytes_to_long(bytes_in)).digits(base).upper().encode()
```

The flaw in this encryption scheme is that we know every input to `base_n_encode()`, other than the original plaintext, must also be a base-*n* encoded string. This allows us to bruteforce the key by ruling out invalid decoded outputs.

The following solver script implements this. Since there might be multiple valid bases, a depth-first search is performed on all possible bases. This turned out to be unnecessary, because the smallest valid base worked every time.

```python
def decrypt_flag(enc, base):

    if base:

        try:
            enc = base_n_decode(enc, base).decode()

        except:
            return False
            
        else:
            if "uiuctf" in enc:
                return enc

    for possible_base in range(2, len(ALPHABET)):

        decrypted = decrypt_flag(enc, possible_base)

        # This base works
        if decrypted:
            return decrypted
    
    return False

with open('flag_enc', 'rb') as f:
    enc = f.read()
    
print(decrypt_flag(enc, None))
```

Running this gives us the flag, `uiuctf{r4DixAL}`.

![](/files/rg043Aps1SnTzniItgXT)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://ctf.zeyu2001.com/2021/uiuctf-2021/back_to_basics.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.