MANUAL

Эзотерическое кодирование

В прошлый раз мы выяснили, что стойкий пароль содержит не менее 128 бит. При записи в base_16 такой пароль займет 32, а при переводе в base_10 до 39 байт. Нас окружают цифры и при желании можно “загримировать” данные под любые бытовые записи. Но как кодировать информацию не оставляя следов на бумаге?

Порядок у карт в киоске был взят

Сколько существует комбинаций у колоды из 36 карт? Для расчёта необходимо взять факториал от числа элементов. В нашем случае 36! примерно 10^41. Это 136 бит! Больше чем требуется для хранения пароля.

Но как же кодировать его картами?

Назначим каждой карте номер, тогда их можно представить как набор чисел [1,2,(…),36]. Записав номера по порядку мы получим первую комбинацию, переставив две последние карты местами - вторую. Для генерации следующих существует алгоритм Нарайаны, но он не дает информации как получить произвольную комбинацию по её номеру.

Решение было найдено в книге “Программирование в алгоритмах / С. М. Окулов”, по мотивам которой был написан следующий код.

import math

def permute_by_index(arr_len, need_index):
	
	in_arr = list(range(arr_len + 1))
	out_arr = []

	while arr_len:
		arr_len -= 1
		top_range = math.factorial(arr_len)
		first_index = (need_index // top_range) + 1
		need_index = need_index % top_range
		poped = in_arr.pop(first_index)
		out_arr.append(poped)

	return out_arr
	
def index_by_permute(arr_state):
	
	out_index = 0

	for ind, one in enumerate(arr_state):
		arr_part = arr_state[ind:]
		cur_count = 0

		for sub in arr_part:
			if sub < one: cur_count += 1

		var_count = math.factorial(len(arr_state) - ind - 1)
		out_index +=  var_count * cur_count

	return out_index

Не буду утомлять вас деталями алгоритма, давайте посмотрим как он работает:

	# Первая комбинация для массива из трёх
	assert(permute_by_index(3, 0) == [1, 2, 3])
	# Вторая, напоминаю что индекс от нуля
	assert(permute_by_index(3, 1) == [1, 3, 2])
	# Ну и наконец шестая 
	assert(permute_by_index(3, 5) == [3, 2, 1])

	# Обратная процедура, индекс из массива
	assert(index_by_permute([3, 2, 1]) == 5)
	assert(index_by_permute([1, 3, 2]) == 1)
	assert(index_by_permute([1, 2, 3]) == 0)

Всё готово чтобы добавить карты! Следующий код предложит конкретным картам номер:

def get_indexed_cards():

	indexed_cards = []
	suits_values = ['\u2660', '\u2665', '\u2663', '\u2666']
	rank_values = ['A', 'K', 'Q', 'J', '10', '9', '8', '7', '6']

	for suit in suits_values:
		for rank in rank_values:
			indexed_cards.append(suit + rank)
	return indexed_cards

def print_cards():

	indexed_cards = get_indexed_cards()
	for ind in range(0, 36):
		number = str(ind + 1).zfill(2)
		print(number, indexed_cards[ind])

print_cards() # 01 ♠A (...)

Боевое крещение

Представим пароль из прошлой части в виде набора карт:

key_int = 0x2af0f3958e106d1621658dbd7bd7653b
ind_list = permute_by_index(36, key_int)

# 1, 2, 9, 22, 34, 18, 32, 6, 14, 23, 28, 11, 36, 35, 20, 13, 24, 30,
# 19, 10, 16, 12, 8, 31, 25, 4, 27, 15, 5, 29, 33, 7, 17, 26, 21, 3

# '♠A', '♠K', '♠6', '♣J', '♦8', '♥6', '♦10', '♠9', '♥10', 
# '♣10', '♦A','♥K', '♦6', '♦7', '♣K', '♥J', '♣9', '♦Q', 
# '♣A', '♥A', '♥8', '♥Q', '♠7', '♦J', '♣8', '♠J', '♣6', 
# '♥9', '♠10', '♦K', '♦9', '♠8', '♥7', '♣7', '♣Q', '♠Q'

Осталось его правильно декодировать:

new_key = index_by_permute(ind_list)
print(hex(new_key))

# 0x2af0f3958e106d1621658dbd7bd7653b

Заработало! Разумеется, карты это абстрактный пример. В реальности это могут быть:

  • отсортированные по алфавиту книги
  • разложенные по датам письма
  • маркеры расположенные по цвету
  • ярлыки на рабочем столе, ну и т.д

Метод подходит для создания копии критических данных, вроде биткойн кошельков и ключей от FullDiskEncryption и поддерживает более чем достоверное отрицание. Такие вещи несложно сохранить на фотографии и никто в здравом уме не станет их “декодировать”