• Tutorial

Bună ziua %username%!
Mulți oameni știu că standardul implicit în domeniu criptare simetrică pentru o lungă perioadă de timp a fost considerat algoritmul DES. Primul atac de succes asupra acestui algoritm care nu poate fi ucis a fost publicat în 1993, la 16 ani după ce a fost adoptat ca standard. Metoda, pe care autorul a numit-o criptoanaliza liniară, în prezența a 2 47 de perechi de texte simple/cifrate, face posibilă spargerea cheie secretă Cifrul DES în 2 43 de operații.
Sub tăietură voi încerca să subliniez pe scurt punctele principale ale acestui atac.

Criptanaliza liniară

În general, un atac bazat pe criptoanaliza liniară se rezumă la următoarele condiții. Atacatorul are un număr mare Perechile text clar/ciphertext obținute folosind aceeași cheie de criptare K. Scopul atacatorului este de a recupera parțial sau integral cheia K.

În primul rând, atacatorul examinează cifrul și găsește așa-numitul analog statistic, adică ecuaţie următorul tip, care se execută cu probabilitate P ≠ 1/2 pentru o pereche arbitrară de text public/privat și o cheie fixă:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
unde P n, C n, K n sunt biții de n ai text, text cifrat și cheie.
După ce este găsită o astfel de ecuație, atacatorul poate recupera 1 bit de informații cheie folosind următorul algoritm

Algoritmul 1
Fie T numărul de texte pentru care partea stângă ecuația (1) este egală cu 0, atunci
Dacă T>N/2, unde N este numărul de texte clare cunoscute.
Să presupunem că K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (când P>1/2) sau 1 (când P<1/2).
Altfel
Să presupunem că K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (când P>1/2) sau 0 (când P<1/2).
Este evident că succesul algoritmului depinde direct de valoarea lui |P-1/2| iar pe numărul de perechi de texte deschise/închise disponibile N. Cu cât probabilitatea P de egalitate (1) diferă de 1/2, cu atât este nevoie de un număr mai mic de texte clare N pentru atac.

Există două probleme care trebuie rezolvate pentru ca atacul să aibă succes:

• Cum să găsiți o ecuație eficientă de forma (1).
• Cum să utilizați această ecuație pentru a obține mai multe informații despre cheie.

Descrierea DES

Deci, DES este un cifru bloc bazat pe rețeaua Feistel. Cifrul are o dimensiune a blocului de 64 de biți și o dimensiune a cheii de 56 de biți. Să luăm în considerare schema de criptare a algoritmului DES.

După cum se poate observa din figură, la criptarea textului, se efectuează următoarele operații:

1. Permutarea inițială a biților. În această etapă, biții blocului de intrare sunt amestecați într-o anumită ordine.
2. După aceasta, biții amestecați sunt împărțiți în două jumătăți, care sunt alimentate la intrarea funcției Feistel. Pentru DES standard, rețeaua Feistel include 16 runde, dar există și alte variante ale algoritmului.
3. Cele două blocuri obținute în ultima rundă de transformare sunt combinate și se realizează o altă permutare asupra blocului rezultat.

În fiecare rundă a rețelei Feistel, cei mai puțin semnificativi 32 de biți ai mesajului sunt trecuți prin funcția f:

Să ne uităm la operațiunile efectuate în această etapă:

1. Blocul de intrare este trecut prin funcția de extensie E, care convertește un bloc de 32 de biți într-un bloc de 48 de biți.
2. Blocul rezultat este adăugat la cheia rotundă Ki .
3. Rezultatul pasului anterior este împărțit în 8 blocuri a câte 6 biți fiecare.
4. Fiecare dintre blocurile primite B i este trecut prin funcția de substituție S-Box i, care înlocuiește secvența de 6 biți cu un bloc de 4 biți.
5. Blocul rezultat de 32 de biți este trecut prin permutarea P și returnat ca rezultat al funcției f.

De cel mai mare interes pentru noi din punctul de vedere al criptoanalizei cifrate sunt blocurile S, concepute pentru a ascunde conexiunea dintre datele de intrare și de ieșire ale funcției f. Pentru a ataca cu succes DES, vom construi mai întâi analogi statistici pentru fiecare dintre cutiile S, apoi le vom extinde la întregul cifr.

Analiza blocului S

Să luăm în considerare cum putem găsi un analog statistic al cutiei S în cazul general.

Pentru o casetă S S a , 1 ≤ α ≤ 63 și 1 ≤ β ≤ 15, valoarea NS a (α, β) descrie de câte ori din 64 de biți de intrare XOR posibili S a suprapusi pe biții α sunt egali cu biții de ieșire XOR suprapusi pe biții α β, adică:
unde simbolul este logic ŞI.
Valorile lui α și β pentru care NS a (α, β) este cel mai diferit de 32 descriu cel mai eficient analog statistic al casetei S a.

Cel mai eficient analog a fost găsit în a 5-a casetă S a cifrului DES pentru α = 16 și β = 15 NS 5 (16, 15) = 12. Aceasta înseamnă că următoarea ecuație este valabilă: Z=Y ⊕ Y ⊕ Y ⊕ Y, unde Z este secvența de intrare a casetei S și Y este secvența de ieșire.
Sau ținând cont de faptul că în algoritmul DES, înainte de a intra în S-box, datele sunt adăugate modulo 2 cu o cheie rotundă, adică. Z = X ⊕ K obținem
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, unde X și Y sunt datele de intrare și de ieșire ale funcției f fără a lua în considerare permutările.
Ecuația rezultată este executată pe toate rundele algoritmului DES cu aceeași probabilitate P=12/64.
Următorul tabel prezintă o listă a celor eficiente, de ex. având cea mai mare abatere de la P=1/2, analogi statistici pentru fiecare s-bloc al algoritmului DES.

Construirea de analogi statistici pentru mai multe runde de DES

Să găsim o expresie similară folosind ultima rundă. De data aceasta avem ecuația
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Deoarece
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
înţelegem asta
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4) cu o probabilitate de 12/64.

Echivalând laturile din dreapta ale ecuațiilor (3) și (4) obținem
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 cu probabilitate (12/64) 2 +(1-12/64) 2.
Ținând cont de faptul că X(1) = PR și X(3) = CR obținem un analog statistic
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
care se execută cu probabilitate (12/64) 2 + (1-12/64) 2 =0,7.
Analogul statistic descris mai sus poate fi reprezentat grafic după cum urmează (biții din figură sunt numerotați de la dreapta la stânga și începând de la zero):

Toți biții din partea stângă a ecuației sunt cunoscuți de atacator, astfel încât acesta poate aplica algoritmul 1 și poate afla valoarea lui K1 ⊕ K3. Să arătăm cum, folosind acest analog statistic, puteți deschide nu 1, ci 12 biți ai cheii de criptare K.

Atacul asupra DES cu Known Plaintext

Am stabilit deja mai sus că valoarea lui F1(PR, K1) este influențată de biții de intrare ai celei de-a 5-a casete S, și anume biții cheie K1 și biții blocului PR. Să arătăm cum, având doar un set de texte deschise/închise, puteți restabili valoarea lui K1. Pentru a face acest lucru, vom folosi algoritmul 2.

Algoritmul 2
Fie N numărul de perechi de texte deschise/închise cunoscute înainte de atac. Apoi, pentru a deschide cheia, trebuie să parcurgeți următorii pași.
Pentru (i=0; i<64; i++) do
{
Pentru(j=0; j {
dacă(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) atunci
Ti =T i +1
}
}
Ca succesiune probabilă K1, se ia o valoare a lui i astfel încât expresia |T i -N/2| are valoarea maximă.

Având în vedere un număr suficient de texte clare cunoscute, algoritmul va avea o probabilitate mare de a returna valoarea corectă a celor șase biți ai subcheii K1 din prima rundă. Acest lucru se explică prin faptul că, dacă variabila i nu este egală cu K1, atunci valoarea funcției F1(PR j, K) va fi aleatorie și numărul de ecuații pentru o astfel de valoare a lui i pentru care partea stângă este egal cu zero va tinde spre N/2. Dacă subcheia este ghicită corect, partea stângă va fi egală cu bitul fix K3 cu probabilitatea 12/64. Aceste. va exista o abatere semnificativă de la N/2.

După ce ați primit 6 biți de subcheie K1, puteți deschide în mod similar 6 biți de subcheie K3. Tot ce trebuie să faceți este să înlocuiți C cu P și K1 cu K3 în ecuația (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algoritmul 2 va returna valoarea K3 corectă deoarece procesul de decriptare al algoritmului DES este identic cu procesul de criptare, doar secvența de chei este inversată. Deci, în prima rundă de decriptare se folosește cheia K3, iar în ultima rundă se folosește cheia K1.

După ce a primit 6 biți de subchei K1 și K3, atacatorul recuperează 12 biți din cheia comună a cifrului K, deoarece cheile rotunde sunt permutarea obișnuită a tastei K. Numărul de texte clare necesare pentru un atac de succes depinde de probabilitatea analogului statistic. Pentru a sparge o cheie DES pe 12 biți și 3 runde, sunt suficiente 100 de perechi de text public/privat. Pentru a deschide 12 biți dintr-o cheie DES cu 16 runde, vor fi necesare aproximativ 2 44 de perechi de texte. Restul de 44 de biți ai cheii sunt deschiși folosind forța brută normală.

Modificarea propusă de IBM a proiectului, numită Lucifer, a fost adoptată ca DES. DES au fost publicate sub formă de schiță în Registrul Federalîn martie 1975 ca Standard federal de procesare a informațiilor (FIPS – Standard federal de procesare a informațiilor).

La publicare, schița a fost aspru criticată din două motive. În primul rând, au fost criticate lungimea cheii îndoielnic de mică (doar 56 de biți), care ar putea face cifrul vulnerabil la atacuri cu forță brută.

Ei au bănuit că o parte a structurii (S-boxes) ar putea avea o ușă ascunsă care ar permite decriptarea mesajelor fără cheie. Designerii IBM au raportat ulterior că structura internă a fost modificată pentru a preveni criptoanaliza.

DES a fost în cele din urmă publicat ca FIPS 46 în Federal Register în ianuarie 1977. Cu toate acestea, FIPS a declarat DES ca standard pentru utilizare în aplicații neoficiale. DES a fost cel mai utilizat cifru bloc cu chei simetrice, începând de la publicarea sa. NIST a propus ulterior un nou standard (FIPS 46-3) care recomandă utilizarea triplu-ului DES (triplu DES cipher) pentru aplicații viitoare. După cum vom vedea mai târziu în prelegerile 9-10, noul standard AES este de așteptat să înlocuiască DES.

Prevederi generale

După cum se arată în Fig. 8.1. DES - cifru bloc.

Orez. 8.1.

În ceea ce privește criptarea, DES preia text simplu pe 64 de biți și produce text cifrat pe 64 de biți; În ceea ce privește decriptarea, DES preia un text cifrat de 64 de biți și produce un text simplu de 64 de biți. Ambele părți folosesc aceeași cheie de 56 de biți pentru criptare și decriptare.

8.2. Structura DES

Să ne uităm mai întâi la criptare și apoi la decriptare. Procesul de criptare constă din două permutări (blocuri P) - numite permutări de început și de sfârșit - și șaisprezece runde Feistel. Fiecare rundă folosește o cheie diferită de 48 de biți generată. Algoritmul de generare va fi discutat mai târziu în această prelegere. Figura 8.2 prezintă elementele unui cifr DES pe partea de criptare.

Permutările de început și de sfârșit

Figura 8.3 prezintă permutările inițiale și finale (blocuri P). Fiecare dintre permutări ia o intrare pe 64 de biți și își rearanjează elementele conform unei anumite reguli. Am arătat doar un număr mic de porturi de intrare și porturi de ieșire corespunzătoare. Aceste permutări sunt permutări directe fără chei, care sunt inverse una față de cealaltă. De exemplu, în permutarea inițială, al 58-lea bit al intrării merge la primul bit al ieșirii. În mod similar, în permutarea finală, primul bit de intrare trece la al 58-lea bit de ieșire. Cu alte cuvinte, dacă nu există nicio rundă între aceste două permutări, al 58-lea bit furnizat la intrarea dispozitivului inițial de permutare va fi livrat la a 58-a ieșire prin permutarea finală.

Regulile de permutare pentru această casetă P sunt prezentate în Tabelul 8.1. Tabelul poate fi reprezentat ca o matrice de 64 de elemente. Rețineți că am discutat despre lucrul cu tabelul, valoarea fiecărui element determină numărul portului de intrare, iar numărul de serie (index) al elementului determină numărul portului de ieșire.

Permutări finite

Aceste două permutări nu au nicio semnificație pentru criptografie

Standardul DES este conceput pentru a proteja împotriva accesului neautorizat la informații sensibile, dar neclasificate în organizațiile guvernamentale și comerciale din SUA. Algoritmul care stă la baza standardului s-a răspândit destul de repede și deja în 1980 a fost aprobat de Institutul Național de Standarde și Tehnologie din SUA. Din acest moment, DES devine un standard nu numai de nume, ci și de fapt. Apar software-ul și microcalculatoarele specializate care sunt concepute pentru a cripta și decripta informațiile din rețelele de transmisie a datelor.

Până în prezent, DES este cel mai comun algoritm utilizat în sistemele comerciale de securitate a informațiilor. Mai mult, implementarea algoritmului DES în astfel de sisteme devine un semn de bună formă.

Principalele avantaje ale algoritmului DES:

· este folosită o singură cheie cu lungimea de 56 de biți;

· având criptat un mesaj folosind un pachet, puteți folosi oricare altul pentru a-l decripta;

· simplitatea relativă a algoritmului asigură viteză mare de procesare a informaţiei;

· stabilitate suficient de mare a algoritmului.

DES criptează blocuri de date pe 64 de biți folosind o cheie de 56 de biți. Decriptarea în DES este operația inversă a criptării și se realizează prin repetarea operațiilor de criptare în ordine inversă (în ciuda evidentei evidente, acest lucru nu se face întotdeauna. Mai târziu ne vom uita la cifrurile în care criptarea și decriptarea sunt efectuate folosind diferiți algoritmi).

Procesul de criptare constă dintr-o permutare inițială de biți a unui bloc de 64 de biți, șaisprezece cicluri de criptare și, în final, o permutare inversă a biților (Figura 1).

Trebuie remarcat imediat că TOATE tabelele prezentate în acest articol sunt STANDARD și, prin urmare, ar trebui incluse în implementarea algoritmului neschimbate. Toate permutările și codurile din tabele sunt selectate de dezvoltatori astfel încât să facă procesul de decriptare cât mai dificil posibil prin selectarea unei chei. Structura algoritmului DES este prezentată în Fig. 2.

Lăsați următorul bloc T de 8 octeți să fie citit din fișier, care este transformat folosind matricea inițială de permutare IP (Tabelul 1) după cum urmează: bitul 58 al blocului T devine bitul 1, bitul 50 devine bitul 2 etc., care va rezultă: T(0) = IP(T).

Secvența de biți rezultată T(0) este împărțită în două secvențe a câte 32 de biți fiecare: L(0) - biți stânga sau de ordin superior, R(0) - biți de ordin drept sau de ordin inferior.

Tabelul 1: Matricea de permutare inițială IP

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07

Apoi se realizează criptarea, constând din 16 iterații. Rezultatul i-a iterație este descris prin următoarele formule:

R(i) = L (i-1) xor f (R(i-1), K(i)),

unde xor este operația EXCLUSIVĂ SAU.

Funcția f se numește funcție de criptare. Argumentele sale sunt secvența de 32 de biți R(i-1), obținută la (i-1)-a iterație și cheia de 48 de biți K(i), care este rezultatul conversiei cheii K de 64 de biți. În detaliu, funcția de criptare și algoritmul pentru obținerea cheilor K(i) sunt descrise mai jos.

La a 16-a iterație se obțin secvențele R(16) și L(16) (fără permutare), care sunt concatenate într-o secvență de 64 de biți R(16) L(16).

Apoi pozițiile biților din această secvență sunt rearanjate în conformitate cu matricea IP -1 (Tabelul 2).

Tabelul 2: Matricea de permutare inversă IP -1

40 08 48 16 56 24 64 32

39 07 47 15 55 23 63 31

38 06 46 14 54 22 62 30

37 05 45 13 53 21 61 29

36 04 44 12 52 20 60 28

35 03 43 11 51 19 59 27

34 02 42 10 50 18 58 26

33 01 41 09 49 17 57 25

Matricele IP -1 și IP sunt legate după cum urmează: valoarea primului element al matricei IP -1 este 40, iar valoarea celui de-al 40-lea element al matricei IP este 1, valoarea celui de-al doilea elementul matricei IP -1 este 8, iar valoarea celui de-al 8-lea element al matricei IP este egală cu 2 etc.

Procesul de decriptare a datelor este invers procesului de criptare. Toți pașii trebuie efectuati în ordine inversă. Aceasta înseamnă că datele decriptate sunt mai întâi rearanjate conform matricei IP-1, iar apoi se execută aceleași acțiuni pe secvența de biți R(16) L(16) ca în procesul de criptare, dar în ordine inversă.

Procesul de decriptare iterativă poate fi descris prin următoarele formule:

R (i-1) = L(i), i = 1, 2,..., 16;

L (i-1) = R(i) xor f (L(i), K(i)), i = 1, 2,…, 16.

La a 16-a iterație, se obțin secvențele L(0) și R(0), care sunt concatenate într-o secvență de 64 de biți L(0) R(0).

Pozițiile de biți ale acestei secvențe sunt apoi rearanjate conform matricei IP. Rezultatul unei astfel de permutări este secvența originală de 64 de biți.

Acum considerăm funcția de criptare f (R(i-1), K(i)). Este prezentat schematic în Fig. 3.

Orez. 3.

Pentru a calcula valoarea funcției f, se folosesc următoarele funcții matriceale:

E - extinderea unei secvențe de 32 de biți la 48 de biți,

S1, S2,…, S8 - conversia unui bloc de 6 biți într-unul de 4 biți,

P - permutarea biților într-o secvență de 32 de biți.

Funcția de expansiune E este determinată de tabel. 3. Conform acestui tabel, primii 3 biți ai lui E (R(i-1)) sunt biții 32, 1 și 2, iar ultimii sunt 31, 32 și 1.

Tabelul 3: Funcția de extensie E

32 01 02 03 04 05

04 05 06 07 08 09

08 09 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 01

Rezultatul funcției E (R(i-1)) este o secvență de 48 de biți care este adăugată modulo 2 (operație xor) cu cheia de 48 de biți K(i). Secvența de 48 de biți rezultată este împărțită în opt blocuri de 6 biți B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). Adică:

E (R(i-1)) xor K(i) = B(1) B(2)… B(8).

Funcțiile S1, S2,…, S8 sunt definite în tabel. 4.

Tabelul 4

La masă 4. Sunt necesare clarificări suplimentare. Fie intrarea funcției matrice Sj un bloc de 6 biți B(j) = b1b2b3b4b5b6, apoi numărul de doi biți b1b6 indică numărul rândului matricei, iar b2b3b4b5 numărul coloanei. Rezultatul lui Sj (B(j)) va fi un element de 4 biți situat la intersecția rândului și coloanei specificate.

De exemplu, B(1)=011011. Atunci S1 (B(1)) este situat la intersecția rândului 1 și coloanei 13. În coloana 13 a rândului 1 valoarea este 5. Aceasta înseamnă S1 (011011)=0101.

Aplicând operația de selecție la fiecare dintre blocurile de 6 biți B(1), B(2),…, B(8), obținem o secvență de 32 de biți S1 (B(1)) S2 (B(2)) S3 (B(3))... S8 (B(8)).

În cele din urmă, pentru a obține rezultatul funcției de criptare, biții acestei secvențe trebuie rearanjați. În acest scop, se utilizează funcția de permutare P (Tabelul 5). În secvența de intrare, biții sunt rearanjați astfel încât bitul 16 să devină bitul 1, bitul 7 să devină bitul 2 și așa mai departe.

Tabelul 5: Funcția de permutare P

Astfel,

f (R(i-1), K(i)) = P (S1 (B(1)),... S8 (B(8)))

Pentru a completa descrierea algoritmului de criptare a datelor, rămâne de prezentat algoritmul de obținere a cheilor de 48 de biți K(i), i=1...16. La fiecare iterație, este utilizată o nouă valoare a cheii K(i), care este calculată din cheia inițială K. K este un bloc de 64 de biți cu opt biți de paritate localizați la pozițiile 8,16,24,32,40,48, 56. 64.

Pentru a elimina biții de control și a rearanja restul, este utilizată funcția G a pregătirii inițiale a cheii (Tabelul 6).

Tabelul 6

Matricea G de pregătire inițială a cheii

57 49 41 33 25 17 09

01 58 50 42 34 26 18

10 02 59 51 43 35 27

19 11 03 60 52 44 36

63 55 47 39 31 23 15

07 62 54 46 38 30 22

14 06 61 53 45 37 29

21 13 05 28 20 12 04

Rezultatul transformării G(K) este împărțit în două blocuri de 28 de biți C(0) și D(0), iar C(0) va consta din biții 57, 49, ..., 44, 36 ai cheii. K și D(0) vor fi formate din biții 63, 55,..., 12, 4 taste K. După determinarea C(0) și D(0), C(i) și D(i), i=1... 16, sunt determinate recursiv. Pentru a face acest lucru, aplicați o deplasare ciclică la stânga cu unul sau doi biți, în funcție de numărul de iterație, așa cum se arată în tabel. 7.

Tabelul 7. Tabelul Shift pentru calculul cheii

Valoarea rezultată este din nou „amestecată” în conformitate cu matricea H (Tabelul 8).

Tabelul 8: Matricea de completare a cheilor H

14 17 11 24 01 05

03 28 15 06 21 10

23 19 12 04 26 08

16 07 27 20 13 02

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

Cheia K(i) va consta din biții 14, 17,..., 29, 32 ai secvenței C(i) D(i). Astfel:

K(i) = H (C(i) D(i))

Diagrama bloc a algoritmului de calcul cheie este prezentată în Fig. 4.

Orez. 4.

Restaurarea textului original se realizează folosind acest algoritm, dar mai întâi folosiți cheia K(15), apoi K(14) și așa mai departe. Acum ar trebui să înțelegeți de ce autorul recomandă insistent utilizarea matricelor date. Dacă devii necinstiți, s-ar putea să ajungi cu un cod foarte secret, dar nu vei putea să-l spargi singur!

Conversie ușoară între părțile blocului. Deoarece conversia se realizează bloc cu bloc, un pas separat necesită împărțirea datelor sursă în blocuri de dimensiunea necesară. Mai mult, indiferent de formatul datelor sursă, fie că este vorba de documente text, imagini sau alte fișiere, acestea trebuie interpretate în formă binară și abia apoi împărțite în blocuri. Toate cele de mai sus pot fi realizate prin software sau hardware.

Transformări ale rețelei Feistel

Aceasta este o transformare peste vectori (blocuri) reprezentând jumătățile stânga și dreapta ale registrului de deplasare. Algoritmul DES folosește o transformare înainte de rețea Feistel în criptare (vezi Fig. 1) și o transformare inversă a rețelei Feistel în decriptare (vezi Fig. 2).

Schema de criptare a algoritmului DES

Textul sursă este un bloc de 64 de biți.
Textul cifrat este un bloc de 64 de biți.

Procesul de criptare constă dintr-o permutare inițială, 16 cicluri de criptare și o permutare finală.
Să ne uităm la diagrama detaliată a algoritmului DES:
L i R i =1,2\ldots.jumătățile stânga și dreapta ale blocului de 64 de biți L i R i
k i - taste pe 48 de biți
f - functie de criptare
IP - permutare inițială
IP -1 - permutarea finală. Conform tabelului, primii 3 biți ai blocului rezultat IP(T) după permutarea inițială a IP sunt biții 58, 50, 42 ai blocului de intrare T, iar ultimii 3 biți ai acestuia sunt biții 23, 15, 7 din bloc de intrare. Apoi, blocul IP(T) pe 64 de biți participă la 16 cicluri ale transformării Feistel.

16 cicluri de transformare Feistel:

Împărțiți IP(T) în două părți L0,R0, unde L0,R0 sunt cei 32 de biți cei mai semnificativi și respectiv 32 de biți cei mai puțin semnificativi ai blocului TO IP(T)= L0R0, respectiv.

Fie T i -1 = L i -1 R i -1 rezultatul iterației (i-1), apoi se determină rezultatul i-a iterației T i = L i R i:

L i = R i - 1 Jumătatea stângă a lui L i este egală cu jumătatea dreaptă a vectorului anterior L i - 1 R i - 1 . Și jumătatea dreaptă a lui R i este adăugarea de biți a lui L i - 1 și f(R i - 1, k i) modulo 2.

În transformarea Feistel cu 16 cicluri, funcția f joacă rolul de criptare. Să ne uităm la funcția f în detaliu.

Argumentele funcției f sunt vectorul de 32 de biți R i - 1 , cheia de 48 de biți k i , care sunt rezultatul conversiei cheii de cifră originale de 56 de biți k.

Pentru a calcula funcția f se utilizează funcția de expansiune E, transformarea S, constând din 8 transformări S-box și permutarea P.

Funcția E extinde vectorul de 32 de biți R i - 1 la vectorul de 48 de biți E(R i - 1) prin duplicarea unor biți din R i - 1, în timp ce ordinea biților din vectorul E(R i - 1) ) este indicată în tabelul 2. Primii trei biți ai vectorului E(R i - 1) sunt biții 32, 1, 2 ai vectorului R i -1. Tabelul 2 arată că biții 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 sunt duplicați. Ultimii 3 biți ai vectorului E(Ri - 1) sunt biții 31, 32, 1 ai vectorului Ri - 1. Blocul E(R i -1) obținut după rearanjare este adăugat modulo 2 cu tastele k i și apoi prezentat sub forma a opt blocuri consecutive B 1 , B 2 ,...B 8 .
E(R i - 1) = B 1 B 2 ...B 8
Fiecare B j este un bloc de 6 biți. În continuare, fiecare dintre blocurile B j este transformată într-un bloc de 4 biți B" j folosind transformările S j. Transformările S j sunt determinate de Tabelul 3. Să presupunem că B 3 = 101111 și dorim să găsim B" 3. Primii și ultimii biți ai lui B 3 sunt reprezentarea binară a numărului a, 0. Valoarea funcției f(R i - 1,k i) (32 de biți) se obține prin permutarea P aplicată blocului B de 32 de biți. "1 B" 2 ...B" 8. Permutația P este dată de Tabelul 4.
f(R i - 1 ,k i) = P(B" 1 B" 2 ...B" 8)
Conform tabelului 4, primii patru biți ai vectorului rezultat după acțiunea funcției f sunt biții 16, 7, 20, 21 ai vectorului B" 1 B" 2 ...B" 8

Generarea cheilor k i .
Cheile k i se obțin din cheia inițială k (56 biți = 7 octeți sau 7 caractere ASCII) în acest fel. Opt biți, localizați la pozițiile 8, 16, 24, 32, 40, 48, 56, 64, sunt adăugați la cheia k, astfel încât fiecare octet să conțină un număr impar de uni. Acesta este folosit pentru a detecta erori în schimbul și stocarea cheilor. Apoi se face o permutare pentru cheia extinsă (cu excepția biților adăugați 8, 16, 24, 32, 40, 48, 56, 64). Această permutare este definită ca în Tabelul 5.

Această permutare este definită de două blocuri C 0 și D 0 de 28 de biți fiecare. Primii 3 biți ai C0 sunt biții 57, 49, 41 ai cheii extinse. Iar primii trei biți ai lui D 0 sunt biții 63, 55, 47 ai cheii extinse. C i ,D i i=1,2,3...se obțin din C i - 1 ,D i - 1 prin una sau două deplasări ciclice la stânga conform Tabelului 6.

Cheia k i , i=1,...16 constă din 48 de biți selectați dintre biții vectorului C i D i (56 de biți) conform Tabelului 7. Primul și al doilea biți k i sunt biții 14, 17 ai vectorului C i D i

Permutarea finală IP - 1 acționează asupra T 16 și este folosită pentru a restabili poziția. Este inversul permutației IP. Permutarea finală este determinată de Tabelul 8.
Moduri de utilizare DES DES poate fi utilizat în patru moduri.

Modul Electronic Code Book (ECB): utilizarea obișnuită a DES ca cifru bloc (vezi Fig. 7).

Modul de blocare în lanț (CBC - Cipher Block Chaining) (vezi Fig. 8). Fiecare bloc următor C i>=1, înainte de criptare, este adăugat modulo 2 cu următorul bloc de text simplu M i + 1. Vectorul C 0 este vectorul inițial, se schimbă zilnic și este ținut secret.

Modul Cipher Feedback (CFB - Cipher Feed Back) (vezi Fig. 9). În modul CFB, se generează un bloc „gamma” Z 0 ,Z 1 ,...Z i = DESk(C i - 1) . Vectorul inițial C 0 este ținut secret.

Modul feedback de ieșire (OFB - Output Feed Back) (vezi Fig. 10). În modul OFB, se generează un bloc „gamma” Z 0 ,Z 1 ,... , i>=1

Standardul de criptare a datelor (DES) este un standard de criptare a datelor inventat în Statele Unite în anii 1980. Printre cifruri, este considerat pe bună dreptate un „pensionar”, rămânând în același timp calul de bătaie al criptografiei. DES nu mai este potrivit în medii cu tehnologie ultra-rapidă și volume mari de date din cauza limitărilor de 56 de biți per cheie și 64 de biți per date. Cu toate acestea, este încă în uz.

Ce sunt cifrurile bloc?

DES este un algoritm de criptare bloc. Multe cifruri bloc au fost create în ultimii 20-30 de ani, dar crearea unui cifr bun care este sigur este o sarcină dificilă. Este important ca cifrul să aibă caracteristici care îi vor permite să funcționeze în multe domenii și industrii.

Cifrurile bloc constau din mai multe iterații de utilizare a unui cifr pe rând. Fiecare iterație se numește rundă. După cum arată practica, chiar și unii algoritmi primitivi, atunci când sunt utilizați în mod consecvent, sunt capabili să creeze cifruri de încredere. Algoritmul DES este un exemplu care a rămas fiabil și indestructibil timp de 20 de ani.

Această abordare a dezvoltării cifrului simplifică foarte mult procesul și simplifică analiza securității. De exemplu, un atac de testare asupra unui cifru bloc începe cu un număr minim de runde și continuă metodic cu o creștere a numărului de runde.

Folosind DES

Deși DES este considerat învechit și nu îndeplinește cerințele moderne, poate fi folosit, de exemplu, sub formă de 3DES, atunci când cifrul este folosit de trei ori la rând. Această abordare elimină limitarea dimensiunii cheii, dar blocul de date criptate rămâne același. La un moment dat, DES era un cifr destul de rapid și sigur. Acum nu este cazul, iar 3DES funcționează de trei ori mai lent. În ciuda acestui fapt, DES este încă folosit într-un număr de sisteme, dar utilizarea sa în proiecte noi este interzisă.

Oficial, algoritmul de cifrare DES a fost un standard în Statele Unite până în 1998. În 1997, a început crearea unui nou standard, care se numea System) și, deși criptoanaliza arată că o încercare de a sparge DES duce la multe sisteme de ecuații neliniare, metodele analitice nu pot ajuta la rezolvarea problemei - punctul său slab este setul mic de chei posibile. Numărul lor este 2 56 și toate opțiunile pot fi rezolvate folosind tehnologii moderne într-un timp relativ scurt.

O rundă în algoritm

Pentru claritatea prezentării și descrierii algoritmului DES, folosim Figura 4.1, care arată structura unei runde.

Fiecare dreptunghi din diagrama de linii reprezintă un fel de calcul, iar săgeata care emană din acesta indică locul unde vor fi transferate rezultatele blocului. Semnul plus încercuit denotă o operațiune „exclusivă sau”, numită XOR în programare. Operația se mai numește „adăugare pe biți” sau „adăugare fără transport”. Puteți găsi algoritmul DES în C online și îl puteți studia pentru o mai bună înțelegere.

DES acceptă un bloc de text cu dimensiunea de 64 de biți. Trece prin permutarea inițială după un anumit principiu. La analiza algoritmului, s-a dovedit că această permutare are puțin sens, deoarece nu dă niciun efect criptografic. Blocul de text este împărțit în 2 părți egale: dreapta (R) și stânga (L). Părțile criptate sunt apoi schimbate și combinate, iar la sfârșitul rundei se obține un bloc de date pe 64 de biți, doar criptat.

Algoritm general

Algoritmul DES include 16 runde, efectuate conform schemei descrise mai sus. Toate rundele sunt numerotate prin i, unde i = (1; 16). Fiecare i-a rundă din pereche (Li-1, Ri-1) primește o nouă pereche (Li, Ri), folosind cheia Ki. Principalele transformări au loc în interiorul funcției F.

Algoritmul de funcționare al funcției F

După cum puteți vedea din Figura 4.1, R trece prin operația Expand. Acest bloc dublează un număr de biți din R și îl completează cu aceștia, rezultând o valoare de 48 de biți. Rezultatul rezultat este trecut prin adăugare pe biți cu cheia de 48 de biți Ki. Iar rezultatul acestei operații este transferat în blocul S. Blocul S conține 8 matrice de substituție mici, care sunt selectate într-un mod special.

Fiecare matrice primește 6 biți de informații ca intrare și produce o valoare de 4 biți. Ca rezultat, blocul S primește date de 48 de biți la intrare și prezintă rezultatul ca o valoare de 32 de biți la ieșire.

Această valoare de 32 de biți este trecută printr-o altă operație de permutare și apoi xored cu L. În cele din urmă, părțile din dreapta și din stânga sunt schimbate și runda este finalizată. După cum am menționat mai devreme, algoritmul efectuează 16 astfel de runde.

Aici nu vom supraîncărca articolul cu exemple care ocupă mult spațiu. Lucrările DES și exemplele pot fi vizualizate online.

Cifrul Feistel

Algoritmul DES se bazează pe cifrul Feistel. Ideea lui este destul de elegantă. La fiecare rundă, partea L este adăugată la valoarea F(R, Ki) și L este schimbată cu R. Caracteristica cheie a algoritmului lui Feistel este că decriptarea și criptarea constau în aceiași pași: părțile L și R sunt schimbate, apoi se realizează operaţia de adunare a lui L şi F (R, Ki). Acest lucru face ca procedurile de criptare și decriptare să fie simple și directe.

O schimbare interesantă care este adesea introdusă în cifrurile Feistel este eliminarea permutației L și R în ultima iterație. Acest lucru face ca algoritmii de criptare și decriptare să fie complet simetrici. Singura diferență este ordinea în care sunt folosite tastele Ki. Acest principiu s-a dovedit a fi extrem de convenabil pentru utilizare la nivel de software, deoarece criptarea și decriptarea au loc folosind o singură funcție. De exemplu, o implementare concisă a algoritmului de criptare DES în C.

Chei de criptare

DES folosește șaisprezece chei pe 48 de biți pentru a cripta datele. O cheie pe rundă. Fiecare cheie este creată prin eșantionarea a 48 de biți dintr-o cheie principală de 56 de biți. Generarea cheilor pentru o anumită rundă este determinată de un mecanism descris în detaliu în documentația DES.

Pe scurt, algoritmul pentru selectarea tastei i este următorul. Biții sunt adăugați la cheia principală la pozițiile 8, 16, 24, 32, 40, 48, 56, 64. Acest lucru se face în așa fel încât fiecare octet să conțină un număr impar de uni. Respectarea regulii ajută la detectarea erorilor în schimburile de chei. După aceasta, folosind tabele speciale, cheia augmentată suferă permutări și deplasări, excluzând biții care au fost adăugați. În acest fel se obține cheia necesară.

Componentele DES

Fiecare componentă a algoritmului DES rezolvă o problemă specifică:

1. Algoritmul lui Feistel simplifică criptarea și decriptarea, asigurând în același timp că ambele jumătăți ale textului sunt amestecate.
2. Însumarea pe biți a părților de text cu chei amestecă textul simplu cu cheia și îl criptează.
3. S-box și tabelele de corespondență fac algoritmul neliniar, crescându-i rezistența la diferite atacuri.
4. Expansiunea, S-box și permutările asigură difuzarea algoritmului - un efect de avalanșă. Cu alte cuvinte, dacă se modifică cel puțin 1 bit în datele de intrare ale funcției F, aceasta va provoca o schimbare în mai mulți biți simultan. Dacă nu există niciun efect de avalanșă în cifru, atunci modificările datelor deschise vor duce la modificări echivalente în forma criptată, care poate fi urmărită și utilizată pentru cracare. În criptografie există un criteriu pentru efectul de avalanșă. Algoritmul îl satisface dacă schimbarea a 1 bit de date simple modifică cel puțin jumătate din datele criptate. Algoritmul DES îl satisface începând cu runda 4. Rezultatul este că dacă modificați 1 bit de date simple în cifrul DES, 29 de biți se vor schimba.

Probleme de securitate în DES

O problemă evidentă cu DES este selectarea cheilor de criptare dintr-o cheie partajată. Ce se întâmplă dacă alegeți o valoare zero ca cheie (toți biții cheii sunt 0)? Acest lucru va duce la faptul că selecția tuturor cheilor de criptare din fiecare rundă va fi aceeași și toate cheile vor fi egale cu zero. Nu numai că 16 criptări vor funcționa cu o singură cheie, dar deoarece algoritmii de criptare și decriptare DES diferă doar în ordinea în care sunt utilizate cheile, acestea vor fi exact aceleași. Întregul punct de criptare va fi pierdut.

DES are 4 chei, care sunt numite slabe, ducând la efectul descris. DES are 12 chei semi-slabe și 48 pseudo-slabe, ceea ce are ca rezultat o variație limitată a cheilor generate de-a lungul rundelor. Cu alte cuvinte, există posibilitatea ca în timpul a 16 runde de criptare să nu fie folosite 16 chei diferite, ci 8, 4 sau chiar 2.

Un dezavantaj mai puțin evident al DES este proprietatea sa de complementaritate. Înseamnă că dacă utilizați complementul textului simplu și complementul cheii pentru a cripta, veți ajunge cu o valoare care este complementul textului cifrat. Această proprietate ciudată poate duce la atacuri de succes împotriva proiectelor care folosesc DES pentru securitate.

Problemă cu cheia de criptare

Este fundamental pentru DES și este considerat principalul motiv pentru care acest algoritm ar trebui abandonat. Deoarece dimensiunea cheii în DES este de 56 de biți, pentru a enumera toate cheile va trebui să căutați prin 2 56 de opțiuni. Este atât de mult?

Dacă efectuați 10 milioane de verificări ale cheilor pe secundă, atunci verificarea va dura aproximativ 2000 de ani. Algoritmul pare a fi destul de robust. Așa a fost în secolul trecut, când crearea unui computer de o asemenea putere era o sarcină aproape imposibilă atât din punct de vedere tehnic, cât și financiar.

Dacă construiți un computer cu un milion de cipuri, căutarea în întregul set de chei DES va dura 20 de ore. Primul astfel de computer pentru decriptare folosind algoritmul DES a apărut în 1998, care a finalizat sarcina în 56 de ore. Tehnologiile moderne de rețea și procesele paralele pot reduce acest timp și mai mult.

Criptanaliză și DES

Se poate spune fără exagerare că DES a devenit motivul apariției unei științe aplicate numită „Analiză criptografică”. Încă de la începutul apariției DES, s-au făcut încercări de a-l sparge și au fost efectuate lucrări științifice pentru a-l studia. Toate acestea au dus la apariția unor domenii ale matematicii precum:

• criptoanaliza liniară - studiul și identificarea dependențelor dintre text simplu și text cifrat;
• criptoanaliza diferențială - studiul și analiza dependențelor dintre mai multe texte clare și versiunile lor criptate;
• criptoanaliza pe chei înrudite - studiul dependențelor dintre textele cifrate obținute pe cheia primară și cheile legate de primar într-un fel sau altul.

DES a rezistat la 20 de ani de criptoanalize și atacuri la nivel mondial, dar rămâne un cifr puternic. Dar cine caută va găsi întotdeauna...

1. Biham și Shamir, oameni de știință din Israel, au arătat în 1991, folosind criptoanaliza diferențială, că ar putea fi făcut un atac asupra DES în care cheia să fie calculată cu condiția ca atacatorul să aibă 247 de perechi special selectate de text simplu și text cifrat.
2. Omul de știință japonez Mitsuru Matsui a arătat în 1993 că o cheie poate fi calculată folosind criptoanaliza liniară. Pentru a face acest lucru, trebuie doar să cunoașteți 2 47 de perechi de text simplu și versiunea criptată corespunzătoare.

Ulterior, aceste metode de hacking au fost ușor rafinate, îmbunătățite și simplificate și au apărut și o serie de noi metode de hacking. Dar rămân prea complexe pe fondul lor, o căutare completă a tuturor opțiunilor cheie arată ca cel mai adecvat atac asupra DES.