Отголоски волшебства на страже точных наук
Близится вечер пятницы, трудовыебудни очередной учебно-рабочей недели агрессивно подкрадываются к своему логическому завершению, а это значит, что можно самую малость ослабить мертвую хватку должностных обязанностей и немного побездельничать. А что может быть более умиротворяющим, чем предаться софистическим фантазиям на тему закономерностей, по которым существует сей бренный мир? Решительно, ничего…
Этим текстом предлагаю разбавить высокий градус серьезности большинства хабропубликаций и, откинувшись в кресле / по пути с работы / учебы, проследить за логикой одной бредовой интересной аналогии, раскрывающей все тайны мироздания (серьезно).
Дисклеймер. Автор ни в коем случае не призывает рассматривать этот пост, как истину в последней инстанции, а просто делится собственной точкой зрения (которая, кстати, может меняться в зависимости от расположения звезд). Ну камон, дайте помечтать, в конце концов!
Предыстория
Для того, чтобы донести сравнение, рожденное моим воспаленным разумом, придется начать издалека.
Как-то раз, около года назад решал я такую криптографическую задачу. Гвоздем программы была особая подстановка на множестве чисел 
, используемая в квазиреализации алгоритма шифрования 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
В десятичном виде:
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
Как следовало начинать решение:
- Построить таблицу дифференциальных характеристик.
- Исходя из особенностей полученной таблицы (она окажется вырожденной) придти к выводу о том, что «прародителем» странной подстановки является аффинная функция вида
.
Прежде чем придти к верному умозаключению, описанному выше, я обратил внимание и на другие закономерности, которыми «живет» эта подстановка.
К примеру, вот лишь некоторые из них (
— подстановка, заданная одномерным массивом; 
— операция сложения по модулю 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
Теперь, собственно, вернемся к пятничным мечтаниям: представьте, а что если вся существующая на данный момент математика является лишь «побочным эффектом» некоторых явлений, которые нам не дано пока постичь; что моя история с аффинной подстановкой есть «современный расклад науки в миниатюре», где все открытия, стоившие человечеству таких усилий — всего лишь отголосок тех явлений, которые правят бал на самом деле.
Действительно, человечество научилось виртуозно использовать даже самые абстрактные разделы математики на благо своих нужд: общая алгебра, мат. логика, теория конечных полей и теория чисел подарили нам стойкую криптографию, без которой не представимо существование современных Интернет-технологий. Великие ученые наплодили неисчислимое количество теорем, ввели мириады различных нотаций с причудливыми значками, пытаясь хоть немного систематизировать и классифицировать те самые «отголоски» настоящего «волшебства», лежащего в основе (не?)материального мира. Люди научились во благо применять следствия из фундаментальных законов, истинную природу которых мы не понимаем ни на йоту: успехи из различных разделов физики элементарных частиц — отличное тому доказательство.
Итак, к чему я это все: если закрыть глаза и представить, какие бы изменения принесло понимания самих основ функционирования нашего мира (если только жалкое эхо настоящей науки принесло нам все то, что можно наблюдать вокруг), то можно погрузиться в транс приятных размышлений в преддверии наступающих выходных.
Попробуйте, вы не останетесь разочарованными, и удачного уикенда ╮(︶▽︶)╭
