Echoes of magic on guard of exact sciences

Friday evening is approaching, the labor wages of the next workweek week are aggressively sneaking up to their logical conclusion, which means that it is possible to weaken the stranglehold of official duties a little and laze a little. And what could be more pacifying than indulging in sophistic fantasies about the laws by which this mortal world exists? Definitely nothing ...

With this text, I propose to dilute the high degree of seriousness of the majority of habro-publications and, leaning back in the chair / on the way from work / study, follow the logic of one ~~crazy~~ interesting analogy, revealing all the secrets of the universe (seriously).

Disclaimer The author does not in any way call to treat this post as the ultimate truth, but simply shares his own point of view (which, by the way, may vary depending on the location of the stars). Well Kamon, let me dream in the end!

Prehistory

In order to bring the comparison, born of my inflamed mind, will have to start from afar.

Once, about a year ago, I solved such a cryptographic problem. The highlight of the program was a special substitution on the set of numbers

o v e r l i n e 0, 255

$\ overline {0, 255}$ used in the quasi-implementation of the AES-256 encryption algorithm, which turned an unbreakable cipher into a pile of useless algebraic transformations.
')
This substitution had the following form:

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

In decimal form:

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

How to start the solution:

Build a table of differential characteristics.
Based on the features of the resulting table (it turns out to be degenerate) to conclude that the “ancestor” of a strange substitution is an affine function of the form $f (x) = Mx \ oplus v$ .

Before arriving at the correct conclusion described above, I drew attention to other patterns by which this substitution “lives”.

For example, here are just some of them (

s b o x

$sbox$ - the substitution defined by a one-dimensional array;

o p l u s

$\ oplus$ - addition operation modulo 2 (aka XOR)):

$\ forall i \ in \ {0, 1, 2, 4, 8, 16, 32, 64, 128 \}: sbox [i] = random \ _unique$ - arbitrary, not coinciding with other substitution elements.
$\ 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$

Now it is obvious that all this is just a “side effect”, “consequence” of applying the true method (using a mathematical transformation) of generating such substitutions.

Before getting the right algorithm for building affine Sboxes , I was so interested in this “magic dependency of three XORs”, that I tried to deduce an artificial method to get them (fake Sboxes ) to get them. And I did it: I found a sufficient number of patterns that do not contradict each other (which, I recall, are only a consequence of the matte operation used) in order to be able to generate substitutions (256 elements long), which, in turn, have the same degenerate table diff. characteristics, as well as substitutions constructed in the "correct" way.

Simple algorithm under the spoiler below.

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

Now, actually, let us return to the Friday dreams: imagine, and what if all the mathematics existing at the moment is only a “side effect” of certain phenomena that we are not yet given to comprehend; that my story with affine substitution is “the modern layout of science in miniature”, where all the discoveries that cost humanity such an effort are only an echo of those phenomena that really rule the ball.

Indeed, humanity has learned to masterly use even the most abstract branches of mathematics for the benefit of its needs: general algebra, mat. logic, the theory of finite fields and the theory of numbers gave us strong cryptography, without which the existence of modern Internet technologies cannot be imagined. Great scientists spawned an incalculable number of theorems, introduced a myriad of different notations with fancy icons, trying to systematize and classify the “echoes” of the real “magic” underlying the (not?) Material world at least a little. People have learned to benefit from the consequences of the fundamental laws, the true nature of which we do not understand in the least: successes from various branches of particle physics are excellent proof of this.

So, what I am all about: if you close your eyes and imagine what changes the understanding of the very foundations of the functioning of our world would bring (if only the miserable echo of real science brought us all that can be observed around), then you can immerse yourself in a trance of pleasant reflections in the eve of the upcoming weekend.

Try it, you will not be disappointed, and have a good weekend ╮ (︶ ▽ ︶)

Source: https://habr.com/ru/post/428702/

All Articles

Echoes of magic on guard of exact sciences

Prehistory

Back to the Dreaming

More articles: