Schema de criptare a algoritmului DES. Algoritmi de criptare DES și AES

Pe care ANSI îl numește algoritmul de criptare a datelor DEA (Algoritmul de criptare a datelor), iar ISO îl numește DEA-1, a devenit un standard mondial în 20 de ani. De-a lungul anilor de existență, a rezistat atacurilor diferitelor atacuri și, cu anumite restricții, este considerat încă criptorezistent.

DES este un cifru bloc care criptează datele în blocuri de 64 de biți. Un bloc de text simplu de 64 de biți este introdus la un capăt al algoritmului, iar un bloc de text cifrat de 64 de biți este scos la celălalt capăt. DES este un algoritm simetric: același algoritm și cheie sunt utilizate pentru criptare și decriptare (cu excepția diferențelor minore în utilizarea cheii). Lungimea cheii este de 56 de biți. (O cheie este de obicei reprezentată ca un număr de 64 de biți, dar fiecare al optulea bit este folosit pentru paritate și este ignorat. Biții de paritate sunt cei mai puțin semnificativi biți ai octeților de cheie.) Cheia, care poate fi orice număr de 56 de biți , poate fi schimbat în orice moment.

Puterea criptografică este complet determinată de cheie. Elementul fundamental al DES este combinația de substituții și permutări. DES este format din 16 cicluri.

Vedere generală a ciclului de conversie:

Dacă L i și R i sunt jumătățile stânga și dreapta rezultate din a-a iterație, Ki este cheia de 48 de biți pentru bucla i și f este o funcție care efectuează toate substituțiile, permutările și XOR-urile pe cheie, atunci unul bucla de conversie poate fi reprezentată ca:

Luând în considerare substituția Fi (*) și permutarea T (*), ciclul de transformare poate fi reprezentat așa cum se arată în Fig.

Se poate observa că fiecare ciclu DES este un cifr de compoziție cu două transformări secvențiale - substituția F i (*) și permutarea T (*) (cu excepția ultimului, al șaisprezecelea ciclu, unde permutarea este omisă).

Substituţie:

(L i , R i) = (R i −1 , L i −1) ⊕ f (R i −1 , K)

este o involuţie, din moment ce

F i (F i (L i −1 , R i −1)) = Fi i (R i −1 , L i −1) ⊕ (f (R i −1 , K i))) = (R i − 1 , L i −1 ⊕(f (R i −1 , K i)) ⊕ (f (R i −1 , K i))) = (L i −1 , R i −1)

O înlocuire

T (L i ′, R i ′) = (R i ′, L i ′),

este şi o involuţie, din moment ce

T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′

Dacă notăm permutările inițiale și finale ca (IP) și (IP) − 1, atunci transformarea DES directă (criptare) implementează funcția:

DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1 ,

iar transformarea DES inversă (decriptare) implementează funcția:

DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).

Astfel, DES este un cifr Feistel și este conceput pentru a îndeplini proprietatea utilă că același algoritm este utilizat pentru criptare și decriptare. Singura diferență este că cheile trebuie folosite în ordine inversă.

Adică, dacă cheile K 1, K 2, K 3, ..., K 16 au fost folosite în timpul criptării, atunci cheile de decriptare vor fi K 16, K 15, K 14, ..., K 1. Algoritmul folosește numai operații aritmetice și logice standard pe 64 de biți, astfel încât poate fi implementat cu ușurință în hardware.

DES operează pe un bloc de text simplu pe 64 de biți. După amestecarea inițială, blocul este împărțit în jumătăți drepte și stângi a câte 32 de biți fiecare. Apoi sunt efectuate 16 transformări (funcția f) în care datele sunt combinate cu cheia. După al șaisprezecelea ciclu, jumătățile din dreapta și din stânga sunt combinate, iar algoritmul se termină cu o permutare finală (reversul originalului). La fiecare ciclu (vezi figura), biții cheie sunt deplasați, apoi 48 de biți sunt selectați din cei 56 de biți cheie. Jumătatea dreaptă a datelor este extinsă la 48 de biți folosind permutarea de expansiune, XOR cu cei 48 de biți ai tastei deplasate și permutate, trecuți prin 8 casete S pentru a forma 32 de biți noi și permuți din nou. Aceste patru operații sunt efectuate de funcția f.

Rezultatul lui f este apoi combinat cu jumătatea stângă folosind un alt XOR. Ca urmare a acestor acțiuni, apare o nouă jumătate dreaptă, iar vechea jumătate din dreapta devine o nouă jumătate stângă. Acești pași se repetă de 16 ori, rezultând 16 cicluri DES.

Standard rusesc - GOST 28147-89

GOST 28147-89 este un cifr de bloc cu o cheie de 256 de biți și 32 de cicluri de conversie, care funcționează pe blocuri de 64 de biți. Algoritmul cripto folosește și o cheie suplimentară, care este discutată mai jos. Pentru criptare, textul simplu este mai întâi împărțit în jumătățile stânga și dreaptă L și R. În ciclul i, se utilizează subcheia Ki:

L i = R i −1 ,
R i = L i −1 ⊕ (f (R i −1 , K i)).

Funcția f este implementată după cum urmează. Mai întâi, jumătatea dreaptă și subcheia i-a sunt adăugate modulo 2 32. Rezultatul este împărțit în opt subsecvențe de 4 biți, fiecare dintre acestea fiind introdusă în propria sa S-box. GOST folosește opt casete S diferite, primii 4 biți merg în prima casetă S, ceilalți 4 biți în a doua casetă S etc. Fiecare casetă S este o permutare a numerelor de la 0 la 15. De exemplu, S-box ar putea arăta astfel: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. În acest caz, dacă intrarea casetei S este 0, atunci ieșirea este 7. Dacă intrarea este 1, ieșirea este 10 etc. Toate cele opt casete S sunt diferite, de fapt sunt materiale cheie suplimentare. Ieșirile tuturor celor opt casete S sunt combinate într-un cuvânt de 32 de biți, apoi întregul cuvânt este rotit la stânga cu 11 biți. În cele din urmă, rezultatul este XOR cu jumătatea stângă pentru a crea o nouă jumătate dreaptă, iar jumătatea dreaptă devine noua jumătate stângă. Pentru a genera subchei, cheia originală de 256 de biți este împărțită în opt blocuri de 32 de biți: k 1, k 2, ..., k 8. Fiecare ciclu folosește propria sa subcheie. Decriptarea se realizează în același mod ca și criptarea, dar ordinea subcheilor k i este inversată. Standardul nu specifică modul în care sunt generate S-box-urile.

Principalele diferențe între DES și GOST

Principalele diferențe dintre DES și GOST sunt următoarele:

• DES folosește o procedură complexă pentru a genera subchei din chei. În GOST această procedură este foarte simplă;
• în DES există o cheie de 56 de biți, iar în GOST este de 256 de biți. Dacă adăugăm permutări secrete ale casetelor S, atunci volumul total de informații secrete GOST va fi de aproximativ 610 biți;
• Cutiile DES S au intrări pe 6 biți și ieșiri pe 4 biți, în timp ce casetele S GOST au intrări și ieșiri pe 4 biți. Ambii algoritmi folosesc opt S-box, dar dimensiunea S-box GOST este egală cu un sfert din dimensiunea S-box DES;
• DES folosește permutări neregulate numite P-block, în timp ce GOST folosește o schimbare ciclică la stânga pe 11 biți;
• în DES există 16 cicluri, iar în GOST - 32.

Un atac în forță asupra GOST este absolut inutil. GOST folosește o cheie de 256 de biți, iar dacă luați în considerare casetele S secrete, lungimea cheii va fi și mai mare. GOST pare a fi mai rezistent la criptoanaliza diferențială și liniară decât DES. Deși cutiile S GOST aleatorii, având posibilitatea de a alege, nu garantează o rezistență criptografică ridicată în comparație cu cutiile S fixe DES, secretul lor crește rezistența GOST la criptoanaliza diferențială și liniară. În plus, eficacitatea acestor metode criptoanalitice depinde de numărul de cicluri de conversie - cu cât mai multe cicluri, cu atât criptoanaliza este mai dificilă. GOST utilizează de două ori mai multe cicluri decât DES, ceea ce poate duce la eșecul criptoanalizei diferențiale și liniare.

GOST nu folosește permutarea extensiei existentă în DES. Eliminarea acestei permutări din DES o slăbește prin reducerea efectului de avalanșă; Este rezonabil să presupunem că absența unei astfel de operațiuni în GOST are un impact negativ asupra puterii sale criptografice. Din punct de vedere al puterii criptografice, operația de adăugare aritmetică utilizată în GOST nu este mai rea decât operația XOR din DES.

Principala diferență pare să fie utilizarea deplasării ciclice în loc de permutare în GOST. Rearanjarea DES crește efectul de avalanșă. În GOST, schimbarea unui bit de intrare afectează o casetă S dintr-un ciclu de conversie, care afectează apoi două casete S din ciclul următor, apoi trei blocuri din ciclul următor etc. Este nevoie de opt cicluri înainte ca schimbarea unui bit de intrare să afecteze fiecare bit al ieșirii; în DES acest lucru necesită doar cinci cicluri. Cu toate acestea, GOST este format din 32 de cicluri, iar DES doar din 16.

Dezvoltatorii GOST au încercat să atingă un echilibru între puterea criptografică și eficiență. Folosind designul lui Feistel ca bază, au dezvoltat un algoritm criptografic care este mai potrivit pentru implementarea software-ului decât DES. Pentru a crește puterea criptografică, a fost introdusă o cheie extra-lungă și numărul de cicluri a fost dublat. Cu toate acestea, întrebarea dacă eforturile dezvoltatorilor au fost încununate cu crearea unui algoritm mai criptografic decât DES rămâne deschisă.

Vorobyova E., Lukyanova A.

Adnotare: Unul dintre cele mai cunoscute sisteme criptografice cu cheie privată este DES – Standardul de criptare a datelor. Acest sistem a fost primul care a primit statutul de standard de stat în domeniul criptării datelor. Și, deși vechiul standard american DES și-a pierdut acum statutul oficial, acest algoritm merită totuși atenție atunci când studiem criptografia. Această prelegere explică, de asemenea, ce este DES dublu, un atac de întâlnire la mijloc și cum să-l atenuăm. Această prelegere discută, de asemenea, pe scurt noul standard american pentru cifrurile bloc, algoritmul Rijndael.

Scopul prelegerii: introduceți studentul în informațiile de bază despre algoritmul de criptare DES.

Informatii de baza

Unul dintre cele mai cunoscute sisteme criptografice cu chei private este DES – Standard de criptare a datelor. Acest sistem a fost primul care a primit statutul de standard de stat în domeniul criptării datelor. A fost dezvoltat de specialiști IBM și a intrat în vigoare în SUA în 1977. Algoritm DES utilizat pe scară largă pentru stocarea și transmiterea datelor între diverse sisteme informatice; în sisteme poștale, sisteme electronice de desen și schimb electronic informatii comerciale. Standard DES a fost implementat atât în ​​software cât și în hardware. Întreprinderi din diferite țări au lansat producția în masă de dispozitive digitale folosind DES pentru criptarea datelor. Toate dispozitivele au fost supuse certificării obligatorii pentru conformitatea cu standardul.

În ciuda faptului că acest sistem nu a avut de ceva timp statutul de standard guvernamental, este încă utilizat pe scară largă și merită atenție atunci când se studiază cifrurile bloc cu o cheie privată.

Lungimea cheii în algoritm DES este de 56 de biți. Tocmai cu acest fapt, principala controversă privind capacitatea de a DES rezista diferitelor atacuri. După cum știți, orice cifru bloc cu o cheie privată poate fi spart încercând toate combinațiile de taste posibile. Cu o lungime a cheii de 56 de biți, sunt posibile 2 56 de chei diferite. Dacă un computer caută prin 1.000.000 de chei într-o secundă (care este aproximativ egal cu 2 20), atunci va dura 2 36 de secunde sau puțin peste două mii de ani pentru a căuta prin toate cele 2 56 de chei, ceea ce, desigur, este inacceptabil pentru atacatori.

Cu toate acestea, sunt posibile sisteme de calcul mai scumpe și mai rapide decât Calculator personal. De exemplu, dacă este posibil să combinați un milion de procesoare pentru calcule paralele, atunci timpul maxim de selectare a tastei este redus la aproximativ 18 ore. Acest timp nu este prea lung, iar un criptoanalist echipat cu echipamente atât de scumpe poate sparge cu ușurință datele criptate DES într-un timp rezonabil.

În același timp, se poate observa că sistemul DES Poate fi folosit în aplicații de dimensiuni mici și mijlocii pentru a cripta date de valoare mică. Pentru criptarea datelor de importanță națională sau cu valoare comercială semnificativă, sistemul DES bineînțeles, nu ar trebui să fie folosit în prezent. În 2001, după o competiție special anunțată, în Statele Unite a fost adoptat un nou standard de criptare bloc, numit AES (Standard avansat de criptare), care s-a bazat pe cifru Rijndael, dezvoltat de specialiști belgieni. Acest cifru este discutat la sfârșitul prelegerii.

Setări principale DES: dimensiunea blocului 64 de biți, lungimea cheii 56 de biți, numărul de runde – 16. DES este o rețea Feishtel clasică cu două ramuri. Algoritmul convertește un bloc de date de intrare pe 64 de biți într-un bloc de ieșire de 64 de biți în mai multe runde. Standard DES construit pe utilizarea combinată a permutării, substituției și gamma. Datele criptate trebuie să fie în formă binară.

Criptare

Structura generală DES prezentată în fig. 4.1. Procesul de criptare a fiecărui bloc de date brute pe 64 de biți poate fi împărțit în trei etape:

1. pregătirea inițială a unui bloc de date;
2. 16 runde ale „ciclului principal”;
3. prelucrarea finală a unui bloc de date.

În prima etapă se realizează permutarea initiala Bloc sursă de text pe 64 de biți, în timpul căruia biții sunt rearanjați într-un mod specific.

La următoarea etapă (principală), blocul este împărțit în două părți (ramuri) a câte 32 de biți fiecare. Ramura dreaptă este transformată folosind o funcție F și cea corespunzătoare cheie parțială, obținut din cheia principală de criptare folosind un algoritm special de conversie a cheii. Apoi datele sunt schimbate între ramurile stânga și dreapta ale blocului. Acest lucru se repetă într-un ciclu de 16 ori.

În cele din urmă, a treia etapă rearanjează rezultatul obținut după șaisprezece pași ai buclei principale. Această permutare este inversul permutației inițiale.

Orez. 4.1.

Să aruncăm o privire mai atentă la toate etapele conversiei criptografice conform standardului DES.

În prima etapă, blocul de date sursă pe 64 de biți suferă o permutare inițială. În literatură, această operație este uneori numită „albire”. În timpul permutării inițiale, biții blocului de date sunt rearanjați într-un anumit mod. Această operațiune adaugă ceva „haos” mesajului original, reducând posibilitatea utilizării criptoanalizei folosind metode statistice.

Simultan cu permutarea inițială a blocului de date, se realizează o permutare inițială a celor 56 de biți ai cheii. Din fig. 4.1. Se poate observa că în fiecare dintre runde se folosește cheia parțială de 48 de biți corespunzătoare Ki. Cheile Ki sunt obținute folosind un algoritm specific, folosind de mai multe ori fiecare dintre biții cheii inițiale. În fiecare rundă, cheia de 56 de biți este împărțită în două jumătăți de 28 de biți. Jumătățile sunt apoi deplasate la stânga cu unul sau doi biți, în funcție de numărul rotunjii. După schimbare, 48 din cei 56 de biți sunt selectați într-un anumit mod. Deoarece aceasta nu numai că selectează un subset de biți, dar le schimbă și ordinea, această operație se numește „permutare de compresie”. Rezultatul său este un set de 48 de biți. În medie, fiecare bit al cheii inițiale de 56 de biți este utilizat în 14 din cele 16 subchei, deși nu toți biții sunt utilizați de același număr de ori.

În continuare, se realizează ciclul principal de transformare, organizat folosind rețeaua Feishtel și format din 16 runde identice. În acest caz, în fiecare rundă (Fig. 4.2) se obține o valoare intermediară de 64 de biți, care este apoi procesată în runda următoare.

Orez. 4.2.

Ramurile stânga și dreapta ale fiecărei valori intermediare sunt tratate ca valori separate de 32 de biți, notate L și R .

În primul rând, partea dreaptă a blocului R i este extinsă la 48 de biți folosind un tabel care specifică permutarea plus extinderea cu 16 biți. Această operație potrivește dimensiunea jumătății drepte cu dimensiunea cheii pentru a efectua o operație XOR. În plus, prin efectuarea acestei operații, dependența tuturor biților de rezultat de biții de date sursă și cheie crește mai repede (acesta se numește „efectul de avalanșă”). Cu cât efectul de avalanșă este mai puternic atunci când utilizați unul sau altul algoritm de criptare, cu atât mai bine.

După efectuarea permutației de expansiune, valoarea rezultată de 48 de biți este XORed cu subcheia de 48 de biți Ki. Apoi valoarea rezultată de 48 de biți este transmisă la intrarea blocului de substituție S (din engleză. Substituţie - substituție), rezultat care este o valoare de 32 de biți. Înlocuirea se realizează în opt blocuri de înlocuire sau opt casete S. Când este executat, DES pare destul de complicat pe hârtie, darămite implementarea software-ului! Elaborați un program de funcționare corect și optim, în conformitate cu DES, probabil, doar programatorii experimentați o pot face. Unele dificultăți apar la implementarea software-ului, de exemplu, permutarea inițială sau permutarea cu extindere. Aceste dificultăți sunt legate de ceea ce a fost inițial planificat să fie implementat DES numai hardware. Toate operațiunile utilizate în standard sunt realizate cu ușurință de către unitățile hardware și nu apar dificultăți de implementare. Cu toate acestea, la ceva timp după publicarea standardului, dezvoltatorii de software au decis să nu stea pe loc și să se apuce, de asemenea, de crearea sistemelor de criptare. Mai departe DES a fost implementat atât în ​​hardware cât și în software.

• Tutorial

Bună ziua %username%!
Mulți oameni știu că algoritmul DES a fost mult timp considerat standardul implicit în domeniul criptării simetrice. 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 text simplu/cifrat, permite deschiderea cheii secrete a cifrului DES în 2 43 de operații.
Sub tăietură voi încerca să subliniez pe scurt punctele principale ale acestui atac.

Criptanaliza liniară

Criptanaliza liniară este un tip special de atac asupra cifrurilor simetrice, care vizează recuperarea unei chei de criptare necunoscute din mesajele simple cunoscute și textele lor cifrate corespunzătoare.

În general, un atac bazat pe criptoanaliza liniară se rezumă la următoarele condiții. Atacatorul are un număr mare de perechi text simplu/cifrat obținute folosind aceeași cheie de criptare K. Scopul atacatorului este să recupereze parțial sau total cheia K.

În primul rând, atacatorul examinează cifrul și găsește așa-numitul analog statistic, adică o ecuație de următoarea formă, care este valabilă cu probabilitatea 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.
Odată ce o astfel de ecuație este găsită, 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ă a ecuației (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).
In caz contrar
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 deschise 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.

Să luăm în considerare soluția acestor probleme folosind cifrul DES ca exemplu.

Descrierea DES

Dar mai întâi, să descriem pe scurt cum funcționează algoritmul. S-a spus deja destule despre DES. O descriere completă a cifrului poate fi găsită pe Wikipedia. Cu toate acestea, pentru a explica în continuare atacul, vom avea nevoie de o serie de definiții care sunt cel mai bine introduse în prealabil.

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 casetele S, apoi le vom extinde la întregul cifr.

Analiza blocului S

Fiecare S-box ia o secvență de 6 biți ca intrare și pentru fiecare astfel de secvență este returnată o valoare fixă ​​de 4 biți. Acestea. există un total de 64 de opțiuni de intrare și ieșire. Sarcina noastră este să arătăm relația dintre datele de intrare și de ieșire ale blocurilor S. De exemplu, pentru a treia casetă S a cifrului DES, al treilea bit al secvenței de intrare este egal cu al treilea bit al secvenței de ieșire în 38 din 64 de cazuri. Prin urmare, am găsit următorul analog statistic pentru al treilea S -cutie:
S 3 (x) = x, care se îndeplinește cu probabilitatea P=38/64.
Ambele părți ale ecuației reprezintă 1 bit de informații. Prin urmare, dacă părțile stânga și dreaptă ar fi independente una de cealaltă, ecuația ar trebui să fie satisfăcută cu o probabilitate de 1/2. Astfel, tocmai am demonstrat relația dintre intrarea și ieșirea celei de-a treia casete S a algoritmului DES.

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ă arătăm acum cum putem combina analogii statistici a mai multor runde de DES și în cele din urmă să obținem un analog statistic pentru întregul cifr.
Pentru a face acest lucru, luați în considerare o versiune cu trei runde a algoritmului:

Să folosim un analog statistic eficient al celei de-a 5-a casete s pentru a calcula anumiți biți ai valorii X(2).
Știm că cu probabilitatea 12/64 egalitatea este valabilă în funcția f X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, unde X este al doilea bit de intrare al celei de-a 5-a casete S, este în esență al 26-lea bit al secvenței obținute după extinderea biților de intrare. Analizând funcția de expansiune, putem stabili că al 26-lea bit este înlocuit cu al 17-lea bit al secvenței X(1).
În mod similar, Y,..., Y sunt în esență cei 17, 18, 19 și 20 din secvența obținută înainte de permutarea P. Examinând permutarea P, aflăm că biții Y,..., Y sunt de fapt biți Y (1), Y(1), Y(1), Y(1).
Bitul cheie K implicat în ecuații este al 26-lea bit al subcheii K1 din prima rundă și apoi analogul statistic ia următoarea formă:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Prin urmare, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) cu probabilitate P=12/64.
Cunoscând 3, 8, 14, 25 de biți ai secvenței Y(1), puteți găsi 3, 8, 14, 25 de biți ai secvenței X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) sau luând în considerare ecuația (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) cu o probabilitate de 12/64.

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 atacatorului, 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.

Atac cunoscut în text simplu asupra DES

Să vă prezentăm o metodă prin care puteți extinde atacul și puteți obține imediat 6 biți din prima rundă de conectare.
La alcătuirea ecuației (5), am ținut cont de faptul că nu cunoaștem valoarea lui F1(PR, K1). Prin urmare, am folosit analogul său statistic K1 ⊕ PR.
Să returnăm valoarea F1(PR, K1) în loc de expresia K1 ⊕ PR și să obținem următoarea ecuație:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , care se va executa cu probabilitate 12/64. Probabilitatea s-a schimbat de când am lăsat doar analogul statistic din runda a treia, toate celelalte valori sunt fixe.

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. Acestea. 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ă.

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;

· după ce ai criptat un mesaj folosind un pachet, poț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ă a biților 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 în așa fel încât procesul de decriptare să fie cât mai dificil posibil prin selectarea unei chei. Structura algoritmului DES este prezentată în Fig. 2.

Orez. 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 de decriptat 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). Acesta este:

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

Prin urmare,

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

Număr de iterație	Shift (biți)

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). Prin urmare:

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!

chei simetrice.

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ă. Al doilea motiv: criticii erau îngrijorați de un design ascuns al structurii interne a DES.

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.

Dispoziții 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ă.

Orez. 8.2.

Orez. 8.3.

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.

Tabelul 8.1. Tabelul permutărilor inițiale și finale

Permutările inițiale								Permutări finite
58	50	42	34	26	18	10	02	40	08	48	16	56	24	64	32
60	52	44	36	28	20	12	04	39	07	47	15	55	23	63	31
62	54	46	38	30	22	14	06	38	06	46	14	54	22	62	30
64	56	48	40	32	24	16	08	37	05	45	13	53	21	61	29
57	49	41	33	25	17	09	01	36	04	44	12	52	20	60	28
59	51	43	35	27	19	11	03	35	03	43	11	51	19	59	27
61	53	45	37	29	21	13	05	34	02	42	10	50	18	58	26
63	55	47	39	31	23	15	07	33	01	41	09	49	17	57	25

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