09.11.2018 13:05
snovvcrash 6 3900 Источник
image

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

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

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

Предыстория


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

Как-то раз, около года назад решал я такую криптографическую задачу. Гвоздем программы была особая подстановка на множестве чисел $\overline{0, 255}$, используемая в квазиреализации алгоритма шифрования 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

В десятичном виде:
Sbox-M Decimal
43 196 77 162 118 153 16 255
86 185 48 223 11 228 109 130
219 52 189 82 134 105 224 15
166 73 192 47 251 20 157 114
149 122 243 28 200 39 174 65
232 7 142 97 181 90 211 60
101 138 3 236 56 215 94 177
24 247 126 145 69 170 35 204
203 36 173 66 150 121 240 31
182 89 208 63 235 4 141 98
59 212 93 178 102 137 0 239
70 169 32 207 27 244 125 146
117 154 19 252 40 199 78 161
8 231 110 129 85 186 51 220
133 106 227 12 216 55 190 81
248 23 158 113 165 74 195 44
111 128 9 230 50 221 84 187
18 253 116 155 79 160 41 198
159 112 249 22 194 45 164 75
226 13 132 107 191 80 217 54
209 62 183 88 140 99 234 5
172 67 202 37 241 30 151 120
33 206 71 168 124 147 26 245
92 179 58 213 1 238 103 136
143 96 233 6 210 61 180 91
242 29 148 123 175 64 201 38
127 144 25 246 34 205 68 171
2 237 100 139 95 176 57 214
49 222 87 184 108 131 10 229
76 163 42 197 17 254 119 152
193 46 167 72 156 115 250 21
188 83 218 53 225 14 135 104


Как следовало начинать решение:
  1. Построить таблицу дифференциальных характеристик.
  2. Исходя из особенностей полученной таблицы (она окажется вырожденной) придти к выводу о том, что «прародителем» странной подстановки является аффинная функция вида $f(x) = Mx \oplus v$.

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

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

  • $\forall i\in \{0, 1, 2, 4, 8, 16, 32, 64, 128\}: sbox[i]=random\_unique$ — произвольные, не совпадающие с другими элементы подстановки.
  • $\forall i\in \{3, 5, 7, 9, 11, 13, 15\}: sbox[i]=sbox[i-3]\oplus sbox[i-2]\oplus sbox[i-1]$
  • $\forall i\in \{6, 10, 14\}: sbox[i]=sbox[i-6]\oplus sbox[i-4]\oplus sbox[i-2]$
  • $i=12: sbox[i]=sbox[i-12]\oplus sbox[i-8]\oplus sbox[i-4]$
  • $\forall i\in \overline{17, 32}\cup \overline{33, 48}\cup \overline{65, 80}\cup \overline{129, 144}: sbox[i]=sbox[i-17]\oplus sbox[i-16]\oplus sbox[i-1]$
  • $\forall i\in \overline{80, 96}\cup \overline{144, 160}\cup \overline{208, 224}: sbox[i]=sbox[i-16]\oplus sbox[16]\oplus sbox[0]$
  • $\forall i\in \overline{96, 112}\cup \overline{160, 176}\cup \overline{224, 240}: sbox[i]=sbox[i-32]\oplus sbox[32]\oplus sbox[0]$
  • $\forall i\in \overline{192, 208}: sbox[i]=sbox[i-64]\oplus sbox[64]\oplus sbox[0]$
  • $\forall i\in \overline{48, 64}\cup \overline{112, 128}\cup \overline{176, 192}\cup \overline{240, 256}: sbox[i]=sbox[i-48]\oplus sbox[i-32]\oplus sbox[i-16]$
  • $\ldots$

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

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

Несложный алгоритм под спойлером ниже.
emulate_affine_sbox.py
#!/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


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

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

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

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

Комментарии (6)


  1. Softer
    09.11.2018 16:22
    #19345318

    А папаша Торк на КДПВ определенно ПВ :)
    image


    1. snovvcrash Автор
      09.11.2018 16:44
      #19345474

      И правда похож, но я взял любительский арт с SCP-343. Почему-то это было первое, что пришло в голову =)


  1. slonpts
    09.11.2018 18:57
    #19346108

    Собственно, наука как раз занимается поиском таких общих законов, из которых следуют частные.

    Например, сейчас студентам в курсе общей физики дают сравнительно простой закон всемирного тяготения, и из него выводят более сложные законы Кеплера.

    Однако исторически же сначала Тихо Браге наблюдал за планетами, потом Кеплер из этих наблюдений вывел 3 закона (планеты двигаются по эллипсу, радиус-вектора заметают постоянную площадь в единицу времени, и соотношение радиусов орбит с периодами обращения), а потом Ньютон догадался, что это всего лишь следствия гравитационного притяжения между телами.


  1. CoreTeamTech
    09.11.2018 20:11
    #19346374
    +1

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

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

    Такое «пирамидное» изучение иногда дает приближенное и наивное представление о том, что законы природы, на самом деле, работают снизу вверх, от микровзаимодействий к макровзаимодействиям. Но это лишь от того, что мы ограничены в нашем восприятии, которое порождает бесконечный аналитический вопрос «а что внтутри?». Это позволяет истинным законам постоянно от нас «ускользать», оставляя в наших «руках» клочки материи, за которую мы успели «ухватиться». Это делает наши модели дискретными. Урвали знание тут, зацепили там, а потом договорились как лучше это «склеить». То есть на основании этих «кусочков» стали строить гипотезы о том, как может выглядеть Целое. А Целое очевидно устойчиво, какая-то часть его свойств проецируется в поле нашей досягаемости. И подобно проекциям из пространства большой размерности в меньшее, мы воспринимаем отдельные явления, которые нам кажутся целыми сами по себе.

    Поэтому, да, мы ищем закономерности, пытаемся о них договориться сначала с собой, потом с другими. Математика — это лишь общий язык для того, чтобы приходить к согласию более эффективно. И да, она не совершенна. Потому, что «пространство» истинных явлений мы проецируем сначала на «пространство» нашего восприятия, а потом еще и на «пространство» языка для согласования этого восприятия. Причем, забавен тот факт, что «пространство» математики больше «пространства» нашего восприятия! Математика, все-таки, — самая крутая штука порожденная человечеством!

    Уфф, сорри за лонгрид =)


    1. vassabi
      10.11.2018 08:54
      #19347664
      +1

      Самое обидное в этом всем процессе, что каждый индивидуум начинает его с очень низкого старта (скажи «ма-ма», скажи «ба-ба» и т.д.), и единственный способ, чтобы этот процесс радикально сократить — это эксплуатация доверия (дети, откройте учебник на странице 123, запомните)…


      1. scifinder
        10.11.2018 09:38
        #19347720
        +2

        … а на стр. 123 цитата: «И видел Бог, что это хорошо, и отдыхал он на седьмой день»