Geekly articles weekly

Des échos de magie au service des sciences exactes

image

Vendredi soir approche, les semaines de travail de la prochaine semaine scolaire se rapprochant agressivement de sa conclusion logique, et cela signifie que vous pouvez desserrer l'étau des fonctions officielles juste un peu et flâner un peu. Et quoi de plus attrayant que de se livrer à des fantasmes sophistiqués sur les modèles par lesquels ce monde mortel existe? Absolument rien ...

Avec ce texte, je propose de diluer le haut degré de gravité de la plupart des publications et, en m'appuyant sur la chaise / sur le chemin du travail / des études, de suivre la logique d'une analogie intéressante délirante qui révèle tous les secrets de l'univers (sérieusement).

Clause de non-responsabilité. L'auteur n'appelle en aucun cas à considérer ce post comme la vérité ultime, mais partage simplement son propre point de vue (qui, en passant, peut varier en fonction de l'emplacement des étoiles). Et bien kamon, laisse-moi rêver, au final!

Contexte


Pour faire la comparaison, née de mon esprit enflammé, il faudra partir de loin.

Il y a un an environ, je résolvais un tel problème cryptographique. Le point culminant du programme a été une substitution spéciale sur un ensemble de chiffres  overline0,255utilisé dans la quasi-implémentation de l'algorithme de chiffrement AES-256, qui a transformé un chiffrement incassable en un tas de transformations algébriques inutiles.

Cette substitution était la suivante:

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

Sous forme décimale:
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


Comment démarrer la solution:
  1. Construisez un tableau des caractéristiques différentielles.
  2. Sur la base des caractéristiques du tableau résultant (il s'avère être dégénéré), nous concluons que «l'ancêtre» de l'étrange permutation est une fonction affine de la forme f(x)=Mx oplusv.

Avant d'en arriver à la conclusion correcte décrite ci-dessus, j'ai attiré l'attention sur d'autres schémas avec lesquels cette substitution «vit».

Par exemple, voici quelques-uns d'entre eux ( sbox- la substitution spécifiée par le tableau unidimensionnel;  oplus- opération d'addition modulo 2 (alias XOR)):

  • \ forall i \ in \ {0, 1, 2, 4, 8, 16, 32, 64, 128 \}: sbox [i] = random \ _unique - arbitraire, ne correspondant pas aux autres éléments de substitution.
  • \ 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] oplussbox[i−8] oplussbox[i−4]
  •  foralli in overline17,32 cup overline33,48 cup overline65,80 cup overline129,144:sbox[i]=sbox[i−17] oplussbox[i−16] oplussbox[i−1]
  •  foralli in overline80,96 cup overline144,160 cup overline208,224:sbox[i]=sbox[i−16] oplussbox[16] oplussbox[0]
  •  foralli in overline96,112 cup overline160,176 cup overline224,240:sbox[i]=sbox[i−32] oplussbox[32] oplussbox[0]
  •  foralli in overline192,208:sbox[i]=sbox[i−64] oplussbox[64] oplussbox[0]
  •  foralli in overline48,64 cup overline112,128 cup overline176,192 cup overline240,256:sbox[i]=sbox[i−48] oplussbox[i−32] oplussbox[i−16]
  •  ldots

Maintenant, il est évident que tout cela n'est qu'un «effet secondaire», les «conséquences» de l'application de la vraie méthode (en utilisant la transformation mathématique) pour générer de telles permutations.

Avant d'obtenir l'algorithme correct pour construire des Sbox affines, j'étais tellement intéressé par cette «addiction magique de trois XOR» que j'ai essayé de déduire une méthode artificielle pour leur (fausse Sbox ) production. Et j'ai réussi: j'ai trouvé un nombre suffisant de motifs cohérents (qui, je me souviens, ne sont qu'une conséquence du tapis. Opération utilisée) pour pouvoir générer des substitutions (256 éléments de long), qui, à leur tour, ont le même tableau dégénéré diff. caractéristiques, ainsi que des permutations construites de la «bonne» manière.

Un algorithme simple sous le spoiler ci-dessous.
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())


Retour au rêve


Maintenant, revenons aux rêves de vendredi: imaginez, si toutes les mathématiques actuellement existantes ne sont qu'un «effet secondaire» de certains phénomènes que nous n'avons pas encore pu comprendre; que mon histoire avec substitution affine est «une mise en page moderne de la science en miniature», où toutes les découvertes qui coûtent à l'humanité de tels efforts ne sont qu'un écho des phénomènes qui régissent réellement la balle.

En effet, l'humanité a appris à utiliser magistralement même les sections les plus abstraites des mathématiques au profit de ses besoins: algèbre générale, mat. la logique, la théorie des champs finis et la théorie des nombres nous ont donné une cryptographie forte, sans laquelle l'existence des technologies Internet modernes n'est pas concevable. De grands scientifiques ont produit d'innombrables théorèmes, introduit une myriade de notations différentes avec des icônes bizarres, essayant au moins de systématiser et de classer les «échos» mêmes de la vraie «magie» qui sous-tend (non?) Le monde matériel. Les gens ont appris à appliquer les conséquences des lois fondamentales pour le bien, dont nous ne comprenons pas la vraie nature: les succès de diverses branches de la physique des particules en sont une excellente preuve.

Alors, pourquoi suis-je tout cela: si vous fermez les yeux et imaginez quels types de changements permettent de comprendre les fondements mêmes du fonctionnement de notre monde (si seulement l'écho misérable de la vraie science nous apporte tout ce qui peut être observé), alors vous pouvez plonger dans une transe de pensées agréables dans à la veille du week-end à venir.

Essayez-le, vous ne serez pas déçu et passez un bon week-end ╮ (︶ ▽ ︶) ╭

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

More articles:


All Articles