Отголоски волшебства на страже точных наук

Близится вечер пятницы, трудовыебудни очередной учебно-рабочей недели агрессивно подкрадываются к своему логическому завершению, а это значит, что можно самую малость ослабить мертвую хватку должностных обязанностей и немного побездельничать. А что может быть более умиротворяющим, чем предаться софистическим фантазиям на тему закономерностей, по которым существует сей бренный мир? Решительно, ничего…

Этим текстом предлагаю разбавить высокий градус серьезности большинства хабропубликаций и, откинувшись в кресле / по пути с работы / учебы, проследить за логикой одной бредовой интересной аналогии, раскрывающей все тайны мироздания (серьезно).

Дисклеймер. Автор ни в коем случае не призывает рассматривать этот пост, как истину в последней инстанции, а просто делится собственной точкой зрения (которая, кстати, может меняться в зависимости от расположения звезд). Ну камон, дайте помечтать, в конце концов!

Предыстория

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

Как-то раз, около года назад решал я такую криптографическую задачу. Гвоздем программы была особая подстановка на множестве чисел , используемая в квазиреализации алгоритма шифрования AES-256, которая превращала невзламываемый шифр в груду бесполезных алгебраических преобразований.

Эта подстановка имела следующий вид:

2b c4 4d a2 76 99 10 ff 56 b9 30 df 0b e4 6d 82
db 34 bd 52 86 69 e0 0f a6 49 c0 2f fb 14 9d 72
95 7a f3 1c c8 27 ae 41 e8 07 8e 61 b5 5a d3 3c
65 8a 03 ec 38 d7 5e b1 18 f7 7e 91 45 aa 23 cc
cb 24 ad 42 96 79 f0 1f b6 59 d0 3f eb 04 8d 62
3b d4 5d b2 66 89 00 ef 46 a9 20 cf 1b f4 7d 92
75 9a 13 fc 28 c7 4e a1 08 e7 6e 81 55 ba 33 dc
85 6a e3 0c d8 37 be 51 f8 17 9e 71 a5 4a c3 2c
6f 80 09 e6 32 dd 54 bb 12 fd 74 9b 4f a0 29 c6
9f 70 f9 16 c2 2d a4 4b e2 0d 84 6b bf 50 d9 36
d1 3e b7 58 8c 63 ea 05 ac 43 ca 25 f1 1e 97 78
21 ce 47 a8 7c 93 1a f5 5c b3 3a d5 01 ee 67 88
8f 60 e9 06 d2 3d b4 5b f2 1d 94 7b af 40 c9 26
7f 90 19 f6 22 cd 44 ab 02 ed 64 8b 5f b0 39 d6
31 de 57 b8 6c 83 0a e5 4c a3 2a c5 11 fe 77 98
c1 2e a7 48 9c 73 fa 15 bc 53 da 35 e1 0e 87 68

В десятичном виде:

Как следовало начинать решение:

1. Построить таблицу дифференциальных характеристик.
2. Исходя из особенностей полученной таблицы (она окажется вырожденной) придти к выводу о том, что «прародителем» странной подстановки является аффинная функция вида .

Прежде чем придти к верному умозаключению, описанному выше, я обратил внимание и на другие закономерности, которыми «живет» эта подстановка.

К примеру, вот лишь некоторые из них ( — подстановка, заданная одномерным массивом; — операция сложения по модулю 2 (aka XOR) ):

• — произвольные, не совпадающие с другими элементы подстановки.
• 
• 
• 
• 
• 
• 
• 
• 
• 

Сейчас очевидно, что все это — всего лишь «побочный эффект», «последствия» применения истинного метода (с помощью математического преобразования) генерации таких подстановок.

Перед тем, как получить правильный алгоритм построения аффинных Sbox'ов, мне до того стала интересна эта «магическая зависимость трех XOR'ов», что я постарался вывести искусственный метод их (фейковых Sbox'ов) получения. И у меня получилось: я отыскал достаточное количество не противоречащих друг другу закономерностей (которые, напоминаю, являются лишь следствием использованной мат. операции), чтобы иметь возможность генерировать подстановки (длиной 256 элементов), которые, в свою очередь, имеют такую же вырожденную таблицу дифф. характеристик, как и подстановки, построенные «правильным» образом.

Несложный алгоритм под спойлером ниже.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Usage: python3 emulate_affine_sbox.py

from random import sample
from itertools import product


def xor(x, y, z):
	"""Вернуть результат трехаргументного XOR'а."""
	return x ^ y ^ z


def next_unique(rnd_sample, sbox):
	"""Вернуть значение из списка rnd_sample, которое еще не
	встречалось в подстановке sbox.
	"""
	while True:
		front = rnd_sample.pop()
		if front not in sbox:
			return front


def emulate_affine_sbox_generation():
	"""Вернуть сгенерированную аффинную подстановку sbox."""
	rnd_sample = sample(range(256), 256)
	sbox = [-1] * 256

	# 0..16
	for i in range(0, 16):
		if (i == 0
				or i == 1
				or i == 2
				or i == 4
				or i == 8):
			sbox[i] = next_unique(rnd_sample, sbox)

		elif (i == 3
				or i == 5
				or i == 7
				or i == 9
				or i == 11
				or i == 13
				or i == 15):
			sbox[i] = xor(sbox[i-3] ,sbox[i-2], sbox[i-1])

		elif (i == 6
				or i == 10
				or i == 14):
			sbox[i] = xor(sbox[i-6], sbox[i-4], sbox[i-2])

		elif (i == 12):
			sbox[i] = xor(sbox[i-12], sbox[i-8], sbox[i-4])

	# 16..256
	for i in range(16, 256):
		if (i == 16
				or i == 32
				or i == 64
				or i == 128):
			sbox[i] = next_unique(rnd_sample, sbox)

		elif (i in range(17, 32)
				or i in range(33, 48)
				or i in range(65, 80)
				or i in range(129, 144)):
			sbox[i] = xor(sbox[i-17], sbox[i-1], sbox[i-16])

		elif (i in range(80, 96)
				or i in range(144, 160)
				or i in range(208, 224)):
			sbox[i] = xor(sbox[i-16], sbox[16], sbox[0])

		elif (i in range(96, 112)
				or i in range(160, 176)
				or i in range(224, 240)):
			sbox[i] = xor(sbox[i-32], sbox[32], sbox[0])

		elif (i in range(192, 208)):
			sbox[i] = xor(sbox[i-64], sbox[64], sbox[0])

		elif (i in range(48, 64)
				or i in range(112, 128)
				or i in range(176, 192)
				or i in range(240, 256)):
			sbox[i] = xor(sbox[i-48], sbox[i-32], sbox[i-16])

	if not any_duplicates(sbox) and is_sbox_degenerate(sbox):
		return sbox

	return None


def any_duplicates(sbox):
	"""Вернуть True в случае, если sbox содежит повторяющиеся элементы,
	иначе - False.
	"""
	seen = set()
	for item in sbox:
		if item not in seen:
			seen.add(item)
		else:
			return True

	return False


def is_sbox_degenerate(sbox):
	"""Вернуть True в случае, если sbox вырожденный, иначе - False."""
	length = len(sbox)

	diff_table = [[0] * length for _ in range(length)]
	for c, d in product( *([list(range(length))]*2) ):
		diff_table[c ^ d][sbox[c] ^ sbox[d]] += 1

	count_prob = 0
	for c, d in product( *([list(range(length))]*2) ):
		if diff_table[c][d] == length:
			count_prob += 1

	return count_prob == length


if __name__ == '__main__':
	print(emulate_affine_sbox_generation())

Back to the Dreaming

Теперь, собственно, вернемся к пятничным мечтаниям: представьте, а что если вся существующая на данный момент математика является лишь «побочным эффектом» некоторых явлений, которые нам не дано пока постичь; что моя история с аффинной подстановкой есть «современный расклад науки в миниатюре», где все открытия, стоившие человечеству таких усилий — всего лишь отголосок тех явлений, которые правят бал на самом деле.

Действительно, человечество научилось виртуозно использовать даже самые абстрактные разделы математики на благо своих нужд: общая алгебра, мат. логика, теория конечных полей и теория чисел подарили нам стойкую криптографию, без которой не представимо существование современных Интернет-технологий. Великие ученые наплодили неисчислимое количество теорем, ввели мириады различных нотаций с причудливыми значками, пытаясь хоть немного систематизировать и классифицировать те самые «отголоски» настоящего «волшебства», лежащего в основе (не?)материального мира. Люди научились во благо применять следствия из фундаментальных законов, истинную природу которых мы не понимаем ни на йоту: успехи из различных разделов физики элементарных частиц — отличное тому доказательство.

Итак, к чему я это все: если закрыть глаза и представить, какие бы изменения принесло понимания самих основ функционирования нашего мира (если только жалкое эхо настоящей науки принесло нам все то, что можно наблюдать вокруг), то можно погрузиться в транс приятных размышлений в преддверии наступающих выходных.

Попробуйте, вы не останетесь разочарованными, и удачного уикенда ╮(︶▽︶)╭

Автор: snovvcrash

Источник