MAGENTA

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 27 octombrie 2021; verificarea necesită 1 editare .

MAGENTA  este un cifru bloc dezvoltat de Michael Jacobson și Klaus Huber pentru compania germană de telecomunicații Deutsche Telekom AG . MAGENTA este prescurtarea de la Algoritm multifuncțional pentru aplicații de criptare de uz general și telecomunicații în rețea.

Istorie

Dezvoltarea MAGENTA a început în 1990 cu principiile de bază descrise într-o carte inedită [1] .Ideea principală a fost aplicarea unei tehnici simple, fără tabele magice și constante, care se putea realiza atât în ​​hardware cât și în software. Planurile erau de a dezvolta un cip care să poată transfera date la viteze de până la 1 Gb/s și să fie folosit pentru criptarea ATM . Din păcate, implementarea hardware nu a ieșit la lumină așa cum era planificat din cauza aplicației înguste, dar, în ciuda acestui fapt, cercetările au arătat că un astfel de cip poate fi dezvoltat [2] . MAGENTA a intrat în competiția AES în 1998, dar a fost eliminată după primul tur. Cifrul a devenit disponibil pentru participanții la conferință doar în ziua prezentării, spre deosebire de alte cifruri care au participat. MAGENTA a fost folosit pentru criptarea datelor în interior de către Deutsche Telekom . Trebuie remarcat faptul că înainte de MAGENTA, transformarea Fourier rapidă în scopuri criptografice a fost folosită în 2 cifruri. Numele specific al primului nu a fost găsit [3] , a fost inventat de Jean-Pierre Wasser și înregistrat la 2 iunie 1959. Al doilea cifr este una dintre implementările algoritmului A3  - Comp-128.

Criptare

MAGENTA are o structură de rețea Feistel . Funcția rotundă se bazează pe transformarea rapidă Hadamard[4] , cu excepția faptului că, în loc de adunare și scădere la fiecare etapă, caseta S dată de funcția f(x) este aplicată unuia dintre termenii , și apoi se adaugă modulo 2 .

Fie setul . Dimensiunea blocului  textului sursă este de 128 de biți. Mărimea cheii poate lua 3 valori:

Fie F o funcție rotundă. Cifrul bloc M se calculează după cum urmează:

Rundă unu 2 3 patru 5 6

Cheie aplicată		 K 1 K 1 K 2 K 2 K 1 K 1
Rundă unu 2 3 patru 5 6

Cheie aplicată		 K 1 K 2 K 3 K 3 K 2 K 1
Rundă unu 2 3 patru 5 6 7 opt

Cheie aplicată		 K 1 K 2 K 3 K 4 K 4 K 3 K 2 K 1

Decriptare

Trebuie remarcat faptul că secvența părților cheie utilizate este un palindrom. Lasă . Apoi

[5] [6]

Deci decriptarea

Funcția rotunjită F

Blocul de intrare X cu dimensiunea de 128 de biți ai rotundei n cu cheia rotundă K n este împărțit în 2 părți X 1 și X 2 cu dimensiunea de 64 de biți fiecare.

X = X 1 X 2

După trecerea rundei, obținem X ' = X 2 F(X 2 K n )

Din dependența divizării în părți ale cheii originale de numărul de runde: lungimea părții cheie utilizată în fiecare rundă este întotdeauna de 64 de biți.

Prin urmare, funcția F primește un argument de 128 de biți și trebuie să returneze un rezultat de 64 de biți sau 8 octeți.

Introducem funcții auxiliare în termenii cărora apoi exprimăm F:

Funcţie Dimensiunea argumentelor acceptate Mărimea valorii returnate Descriere
f(x) 1 octet 1 octet Returnează elementul cu numărul x din caseta S
A(x, y) 1 octet 1 octet f(x ⊕ f(y))
PE(x, y) 1 octet 2 octeți (A(x, y)A(y, x)) - concatenează rezultatele lui A(x, y) și A(y, x)
P(X) 16 octeți 16 octeți X=X 0 X 1 ...X 14 X 15

(PE(X 0 ,X 8 )PE(X 1 ,X 9 )...PE(X 6 ,X 14 )PE(X 7 ,X 15 )) - concatenează rezultatele lui PE(X i ,X i+ 8 ) i=0...7, X i are o dimensiune de 1 octet.

T(X) 16 octeți 16 octeți P(P(P(P(X)))) - aplică funcția P la X de 4 ori.
S X) 16 octeți 16 octeți (X 0 X 2 X 4 ... X 14 X 1 X 3 X 5 ... X 15 ) - efectuează o permutare a X octeți: mai întâi se scriu octeți cu un număr de ordine par, apoi cu unul impar.
С(k, X) k∈Ν
X — 16 octeți		 16 octeți Functie recursiva:
С(1,X) = T(X))
С(k,X) = T(X ⊕ S(C(k-1,X)))

Schema functiei P(X):

F se presupune că este egal cu primii 8 octeți din S(C(n, ( X2Kn ) ) ), adică octeții C(n, ( X2Kn ) ) cu un număr de secvență par. Inițial, n a fost setat egal cu 7, dar testele au arătat că în acest caz cifrul poate fi spart. Prin urmare, punem apoi n = 3. După cum au arătat testele, aceasta este cea mai bună alegere, care nu permite slăbiciuni criptografice care afectează întregul cifr. În acest fel,

F se presupune că este egal cu primii 8 octeți din S(C(3,(X 2 K n )))

S-bloc

Blocul S este format după cum urmează:

Primul element este 1, cele ulterioare sunt formate printr-o deplasare de biți la stânga celui precedent, până când 1 depășește limita octetului din stânga. În consecință, începutul blocului este 1 2 4 8 16 32 64 128

256 10 =1 0000 0000 2 , 1 din limita octetului. În acest caz, trebuie să adăugați modulo 2 numărul deplasat rezultat 0000 0000 2 cu numărul 101 10 \u003d 0110 0101 2 :

0000 0000 2 ⊕ 0110 0101 2 \u003d 0110 0101 2 \u003d 101 10 , adică după 128 va fi 101.

101 10 =0110 0101 2 << 1 = 1100 1010 2 =202 10 , 1 nu este în afara limitelor, deci următorul element este 202.
202 10 << 1= 1100 1010 2 << 1 = 1001 0, 10 este 1001 0 , 1 de legat:

1001 0100 2 ⊕ 0110 0101 2 = 1111 0001 2 = 241 10 .

Ultimul element 256 se presupune a fi 0. Rezultatul este următoarea S-box:

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

Intrând mai adânc în teorie, putem rezuma: Fie un câmp Galois GF(2 8 ) și un polinom care specifică acest câmp  — p(x)=x 8 +x 6 +x 5 +x 2 +1 și fie α un element primitiv al câmpului, p( α)=0. Apoi elementul f(x) din caseta S cu indicele x poate fi reprezentat ca

Proprietăți ale funcțiilor utilizate

f(x)

În timpul unei execuții a MAGENTA, funcția f(x) este evaluată de 2304 ori pentru chei de 128 și 192 de biți și de 3072 de ori pentru o cheie de 256 de biți. Deoarece funcția reprezintă partea neliniară a algoritmului, este de o importanță deosebită pentru analiza întregului algoritm. Sunt cunoscute următoarele proprietăți ale lui f(x):

  1. f(x) este o funcție unu-la-unu, adică o permutare peste mulțimea B={0,1} 8  — a tuturor vectorilor binari de opt biți.
  2. Această permutare poate fi reprezentată ca rezultatul a 6 cicluri neînrudite cu lungimea 198 38 9 5 5 și 1. Conform analizei combinatorii, aceste valori sunt „normale” și nu diferă semnificativ de ciclurile similare pentru permutările aleatoare. Singurul număr rămas pe loc este 161.
  3. ∀x ∈ B și astfel încât f(x) ∈ {1,2,…127}:

f(x+1) = 2∙f(x), unde ∙ este produsul numerelor zecimale. ∀(x, y)∈B 2 și astfel încât f(x)∙f(y)∈{1,2,…255} avem f((x+y) mod 255) = f(x)∙f ( y)

  1. Dacă considerăm f(x) ca o funcție vectorială, adică f(x) = (f 7 (x), f 6 (x),…f 0 (x)), atunci fiecare dintre cele 8 funcții booleene este ne -liniar și de gradul 7. De asemenea, toate combinațiile XOR netriviale posibile ale acestor funcții sunt neliniare. O reprezentare explicită a acestor funcții poate fi găsită aici. [7] O altă proprietate interesantă este că fiecare astfel de funcție are 128 de termeni.

PE(x, y)

Criptanaliză

Criptanaliza diferențială

Se pare că cel puțin o parte din MAGENTA poate fi spartă prin metodele acestei criptoanalize. Adunarea modulo 2 dintre aceste elemente este luată ca diferență între două elemente (texte clare sau cifruri). Această definiție a diferenței se datorează utilizării frecvente a operației xor în acest cifr. Indicii de rând ai tabelului XOR reprezintă diferitele diferențe dintre textele clare, iar indicii de coloană reprezintă diferitele diferențe dintre textele cifrate. La intersecția unei anumite diferențe de text simplu, adică un indice de șir, și o diferență specifică de criptare, adică un index de coloană, se află numărul de perechi de texte clare care satisfac această diferență, ale căror cifruri diferă printr-un index de coloană. Tabelul XOR pentru funcția f are dimensiunile 256*256. Suma fiecărui rând și coloană este 256. Primul element al primului rând (cu indicele 0), corespunzător diferenței zero dintre texte clare și cifruri, este 256. Toate celelalte elemente ale primului rând sunt 0. În mod similar, toate elementele a coloanei 1, cu excepția primei, egale cu 256, sunt 0. Un interes deosebit pentru analiza diferențială sunt valorile mari - cea mai mare valoare din acest tabel este 8. Apare cu astfel de diferențe

Diferența dintre
textele simple		 Diferența dintre
cifruri
51 35, 66, 154, 155, 250
102 111, 114, 232, 233, 244
153 96, 97, 115, 229, 247
204 18, 19, 38, 207, 251

Celulele rămase ale tabelului conțin numerele 0, 2, 4, 6. Probabilitatea maximă de tranziție pentru diferențele diferite de zero este . Pentru funcția PE - au fost definite și valorile maxime - este egal cu 36 pentru o diferență în text clar (234, 234) și o diferență zero în cifruri. Probabilitatea maximă de tranziție este ≈ . Probabilitatea maximă de tranziție pentru funcția T este , pentru C(3,X) este . Deoarece numărul de perechi de cifr necesare este mai mare decât inversul probabilității de tranziție, acest tip de analiză diferențială bazată pe tabele xor nu este aplicabilă pentru MAGENTA. Cu toate acestea, întrebarea altor tipuri rămâne deschisă.

Criptanaliza liniară

A fost calculat un tabel de aproximare liniară pentru S-box. [8] . Pentru funcții și pentru fiecare sumă xor , ca și pentru toate funcțiile liniare, s-a determinat câte cifre ale valorilor din tabel sunt în concordanță cu cifrele corespunzătoare ale funcțiilor liniare considerate. Ca urmare, s-au obținut 255 de valori între 0 și 256. Normalizarea a constat în scăderea a 128. Toate valorile din tabel se află pe intervalul [-24;26]. Aceste valori corespund celor așteptate pentru alese în mod arbitrar . Valoarea 26 se obține cu următoarele combinații liniare:

Aplicarea lemei privind incursiunea semnelor la funcția rotundă F( , l=12)

Valoarea rezultată este o limită superioară a celei mai bune transformări afine pentru F. Aproximativ perechile text clar-cifr sunt necesare pentru a utiliza aproximarea liniară afină cu probabilitate [8] . Având în vedere rezultatele anterioare, pentru a ataca F aveți nevoie de . Prin urmare, din cauza neliniarității lui f(x), MAGENTA nu poate fi spart de atacuri bazate pe criptoanaliza liniară.

Note

  1. ↑ K. Huber. Neue Kryptographische Verfahren durch Combination von Operationen in endlichen Körpern mit der schnellen Walshtransformation. Manuscris nepublicat, 1990.
  2. ↑ K. Huber și S. Wolter. Algoritmul MAGENTA de la Telekom pentru en-/decriptare în intervalul gigabit/sec. În ICASSP 1996 Conference Proceedings, volumul 6, paginile 3233-3235, 1996.
  3. ↑ JP Vaseur. Verschluesselungsanordnung mit Mischverdrahtung. Deutsches Patentamt Auslegeschrift 1148397, Anmeldetag: 2 iunie 1959, Auslegeschrift: 9 mai 1963, Anmelder: Compagnie Generale de Telegraphie sans Fil, Paris.
  4. ↑ S.Y. Kung. procesoare matrice VLSI. Prentice Hall, 1988.
  5. ↑ M. Luby și C. Rackoff. Cum se construiesc permutări pseudoaleatoare din funcții pseudoaleatoare. SIAM J. Computing, 17(2):373-386, aprilie 1988.
  6. ↑ J. Pieprzyk și B. Sadeghiyan. Design of Hashing Algorithms, volumul 756 din Lecture Notes in Computer Science. Springer, 1993.
  7. ↑ SIT GmbH. Abschlussbericht - Untersuchung eines universellen Kryptoalgorithmus. Raport tehnic, SIT GmbH, 1994.
  8. ↑ 1 2 E. Biham. Pe criptoanaliza liniară a lui Matsui. În Proc. EUROCRYPT '94, volumul 658 din Note de curs în informatică, paginile 81-91, 1995.

Link -uri