CryptoHack Lab. base64

Для решения нужно достать ключи из hex-строки. Для этого нужно декодировать ее в байты, а затем закодировать в base64.

72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf

Немного теории

Для начала разберем, что от нас требуется.

base64 — это способ кодирования информации, в котором для кодирования используется 64 бита. Данные разбиваются на блоки по 3 октета. Далее кодируемая последовательность разбивается по 6 бит и сопоставляет символ из таблицы с заданным значением. Если доступного символа нет, то вместо него подставлеется =.

Мне нравится следующая цитата:

Чего не могу создать, того не понимаю.
— Ричард Фейнман (но это не точно)

Поэтому помучаемся и напишем свою реализацию один раз.

Пишем свой base64

Не стоит серьезно воспринимать этот код, а тем более использовать его где-то в проде. Этот код написан для того, чтобы новички могли лучше понять принцип работы base64.

Кодирование

Алгоритм кодирование у нас следующий:

1. Переводим строку в двоичный вид;
2. Разбиваем входную строку на последовательности из 24 бит. Если не хватает символов, то добавляем 8/16 нулей, а в закодированный текст добавляется 1/2 символа = соответственно;
3. Разбиваем на группы по 6 бит;
4. Кодируем по таблице и добавляем =, если дополняли нулями;

Таблица кодирования base64

Decimal	Binary	Base64 Symbol
0	000000	A
1	000001	B
2	000010	C
3	000011	D
4	000100	E
5	000101	F
6	000110	G
7	000111	H
8	001000	I
9	001001	J
10	001010	K
11	001011	L
12	001100	M
13	001101	N
14	001110	O
15	001111	P
16	010000	Q
17	010001	R
18	010010	S
19	010011	T
20	010100	U
21	010101	V
22	010110	W
23	010111	X
24	011000	Y
25	011001	Z
26	011010	a
27	011011	b
28	011100	c
29	011101	d
30	011110	e
31	011111	f
32	100000	g
33	100001	h
34	100010	i
35	100011	j
36	100100	k
37	100101	l
38	100110	m
39	100111	n
40	101000	o
41	101001	p
42	101010	q
43	101011	r
44	101100	s
45	101101	t
46	101110	u
47	101111	v
48	110000	w
49	110001	x
50	110010	y
51	110011	z
52	110100	0
53	110101	1
54	110110	2
55	110111	3
56	111000	4
57	111001	5
58	111010	6
59	111011	7
60	111100	8
61	111101	9
62	111110	+
63	111111	/

Пример

Проверим:

cu63:base64/ $ echo 'QUJDREU=' | base64 -d
ABCDE

Реализация на Python:

def base64_encode(s: bytes) -> str:
    encoded_s = []
    adjust = (3 - (len(s) % 3)) % 3

    for i in range(0, len(s), 3):
        octets = s[i:i+3]
        octets = ''.join([f'{octet:08b}' for octet in octets])

        octets = octets.ljust(24, '0')
        print(octets, len(octets))
        for j in range(0, 24, 6):
            c = octets[j:j+6]
            pos = int(c, 2)
            encoded_s.append(encode_table[pos])

    if adjust != 0:
        encoded_s[-adjust::] = '=' * adjust

    return ''.join(encoded_s)

Протестирую его с ABCDE:

cu63:base64/$ python decrypt.py
QUJDREU=

Отлично. Перейдем к декодированию)

Декодирование

Логично предположить, что у нас теперь происходит обратный процесс:

1. Разбиваем строку base64 на символы;
2. Заменяем каждый символ 6 битами из таблицы кодирования. Считаем знаки = и исключаем их из декодированного текста;
3. Полученные биты объединяем по 8, чтобы получить ascii символы;
4. Отображаем полученные символы;

Реализация на Python:

def base64_decode(s: str) -> bytes:
    adjust = s.count('=')
    bin_repr = []
    decoded_str = []

    for c in s:
        if c == '=':
            bin_repr.append('0'*6)
            continue
        pos = encode_table.index(c)
        bin_repr.append(f'{pos:06b}')
    bin_repr = ''.join(bin_repr)

    if adjust != 0:
        bin_repr = bin_repr[:-adjust * 8]

    for i in range(0, len(bin_repr), 8):
        c = bin_repr[i:i+8]
        decoded_str.append(chr(int(c, 2)))

    return ''.join(decoded_str).encode('utf-8')

Итоговый код

encode_table = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'


def base64_decode(s: str) -> bytes:
    adjust = s.count('=')
    bin_repr = []
    decoded_str = []

    for c in s:
        if c == '=':
            bin_repr.append('0'*6)
            continue
        pos = encode_table.index(c)
        bin_repr.append(f'{pos:06b}')
    bin_repr = ''.join(bin_repr)

    if adjust != 0:
        bin_repr = bin_repr[:-adjust * 8]

    for i in range(0, len(bin_repr), 8):
        c = bin_repr[i:i+8]
        decoded_str.append(chr(int(c, 2)))

    return ''.join(decoded_str).encode('utf-8')


def base64_encode(s: bytes) -> str:
    encoded_s = []Ы
    adjust = (3 - (len(s) % 3)) % 3

    for i in range(0, len(s), 3):
        octets = s[i:i+3]
        octets = ''.join([f'{octet:08b}' for octet in octets])

        octets = octets.ljust(24, '0')
        print(octets, len(octets))
        for j in range(0, 24, 6):
            c = octets[j:j+6]
            pos = int(c, 2)
            encoded_s.append(encode_table[pos])

    if adjust != 0:
        encoded_s[-adjust::] = '=' * adjust

    return ''.join(encoded_s)


if __name__ == '__main__':
    input_s = 'ABCDE'
    input_s = input_s.encode('utf-8')
    crypted_str = base64_encode(input_s)
    print(crypted_str)
    decrypted_str = base64_decode(crypted_str)
    print(decrypted_str)

Наконец решим таску

Поигрались и хватит. С алгоритмом мы разобрались (разобрались же?). Можно использовать эту реализацию, либо использовать готовые либы и тулы. Теперь уже точно можно)

Я воспользуюсь двумя способами.

1) Готовая либа:

import base64


if __name__ == '__main__':
    hex_s = '72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf'
    flag = bytes.fromhex(hex_s)
    print(base64.b64encode(flag).decode())

2) Мой шедевр (ну вы его уже видели)

Флаг:

crypto/Base+64+Encoding+is+Web+Safe/