Adnotare: Una dintre cele mai cunoscute sisteme criptografice Cu cheie privată este DES – Standard de criptare a datelor. Acest sistem a fost primul care a primit statutul 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ă pe scurt nou standard SUA pentru cifru bloc – algoritmul Rijndael.
Scopul prelegerii: introduceți elevul în informații de bază despre algoritm 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; V sisteme poştale, V sisteme electronice desene și schimb electronic informatii comerciale. Standard DES a fost implementat atât în software cât și în hardware. Întreprinderi tari diferite a fost lansată producția de masă dispozitive digitale folosind DES pentru criptarea datelor. Toate dispozitivele au trecut certificare obligatorie pentru conformitatea cu standardul.
În ciuda faptului că acest sistem nu a mai avut statutul de standard guvernamental de ceva timp, 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 posibili 2 56 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 altele mai scumpe și mai rapide sisteme de calcul, Cum Calculator personal . De exemplu, dacă este posibil să combinați un milion de procesoare pentru calcule paralele, atunci timp maxim selecția cheii 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 desigur, nu ar trebui să fie utilizate î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 de criptare avansat), 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 rețea clasică Feishtel 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 utilizare combinată permutări, substituții și gamificări. 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:
- pregătirea inițială a unui bloc de date;
- 16 runde ale „ciclului principal”;
- prelucrarea finală a unui bloc de date.
În prima etapă se realizează permutarea inițială pe 64 de biți bloc sursă text, în timpul căruia biții sunt rearanjați într-un anumit mod.
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 inversa 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 fiecare bit al cheii inițiale de mai multe ori. Î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 rapid (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 posibil programatori experimentati. Unele dificultăți apar atunci când implementare software, de exemplu, permutarea inițială sau permutarea cu expansiune. 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 rămână pe loc și, de asemenea, să se apuce de crearea sistemelor de criptare. Mai departe DES a fost implementat atât în hardware cât și în software.
Standard DES conceput pentru a proteja împotriva accesului neautorizat la importante, dar nu informatie clasificataîn organizațiile guvernamentale și comerciale ale 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. Apărea softwareși microcalculatoare specializate concepute pentru a cripta și decripta informațiile din rețelele de date.
Până în prezent, DES este cel mai comun algoritm utilizat în sistemele de securitate informatii comerciale. 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ă de mare viteză procesarea informatiei;
· 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țiunilor 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 î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 iterația 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. Toate acțiunile trebuie efectuate î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). 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.
Recuperare text sursă se efectuează conform acestui 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!
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 algoritm simetric: Criptarea și decriptarea folosesc același algoritm și cheie (cu excepția micilor diferențe î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 mici biți semnificativi octeți ai cheii.) 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)
Și înlocuirea
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 performa proprietate utilă: 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 doar aritmetică standard pe 64 de biți și operatii logice, astfel încât să poată fi implementat cu ușurință în hardware.
DES operează pe un bloc text simplu de 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 cheie suplimentară, despre care se discută mai jos. Pentru criptare text simplu 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 dintre 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 de 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.
Cel mai comun și mai cunoscut algoritm de criptare simetrică este DES (Standard de criptare a datelor). Algoritmul a fost dezvoltat în 1977 și a fost adoptat de NIST (Institutul Național de Standarde și Tehnologie, SUA) ca standard în 1980.
DES este o rețea Feishtel clasică cu două ramuri. Datele sunt criptate în blocuri de 64 de biți folosind o cheie de 56 de biți. Algoritmul convertește o intrare de 64 de biți într-o ieșire de 64 de biți în mai multe runde. Lungimea cheii este de 56 de biți. Procesul de criptare constă din patru etape. Prima etapă realizează o permutare inițială (IP) a textului sursă de 64 de biți (albire), în timpul căreia biții sunt reordonați în funcție de masa standard. Următoarea etapă constă din 16 runde cu aceeași funcție, care utilizează operațiunile de schimbare și înlocuire. La a treia etapă, jumătățile stânga și dreapta ale rezultatului ultimei (a 16-a) iterație sunt schimbate. În cele din urmă, a patra etapă realizează o permutare IP-1 a rezultatului obținut în a treia etapă. Permutația IP-1 este inversa permutației inițiale.
Fig.4. algoritmul DES
Figura prezintă o metodă care utilizează o cheie de 56 de biți. Inițial, cheia este furnizată la intrarea funcției de permutare. Apoi, pentru fiecare dintre cele 16 runde, subcheia Ki este o combinație de deplasare circulară la stânga și permutare. Funcția de permutare este aceeași pentru fiecare rundă, dar subcheile Ki pentru fiecare rundă sunt diferite din cauza deplasării repetate a biților cheie.
Permutarea inițială și inversarea acesteia sunt determinate de un tabel standard. Dacă M este arbitrar de 64 de biți, atunci X = IP(M) este cei 64 de biți rearanjați. Dacă aplicăm funcția de permutare inversă Y = IP-1 (X) = IP-1 (IP(M)), obținem secvența de biți originală.
Descrierea rundei des
Să ne uităm la succesiunea transformărilor utilizate în fiecare rundă.
Fig.5. Ilustrație a unei runde a algoritmului DES
Un bloc de intrare pe 64 de biți trece prin 16 runde, cu fiecare iterație producând o valoare intermediară de 64 de biți. Laturile stânga și dreapta ale fiecărei valori intermediare sunt tratate ca valori separate de 32 de biți, notate L și R. Fiecare iterație poate fi descrisă după cum urmează:
R i = L i -1 F(R i -1 , Ki i)
Astfel, ieșirea jumătății stângi L i este egală cu intrarea jumătății drepte R i-1. Ieșirea jumătății drepte a lui R i este rezultatul aplicării unei operații XOR la L i-1 și a unei funcții F în funcție de R i-1 și Ki .
Să ne uităm la funcția F mai detaliat. Ri, care este furnizat la intrarea funcției F, are o lungime de 32 de biți. În primul rând, R i este extins la 48 de biți folosind un tabel care specifică permutarea plus extinderea pe 16 biți. Expansiunea are loc după cum urmează. Cei 32 de biți sunt împărțiți în grupuri de 4 biți și apoi extinși la 6 biți prin adăugarea celor mai exteriori biți din două grupuri adiacente. De exemplu, dacă face parte din mesajul de intrare
Efgh ijkl mnop . . .
atunci rezultatul extinderii este mesajul
Defghi hijklm lmnopq. . .
Valoarea rezultată de 48 de biți este apoi XOR cu subcheia de 48 de biți Ki. Valoarea rezultată de 48 de biți este apoi introdusă în funcția de substituție, care are ca rezultat o valoare de 32 de biți.
Substituția constă din opt casete S, fiecare dintre ele primește 6 biți ca intrare și produce 4 biți ca ieșire. Aceste transformări sunt definite de tabele speciale. Primii și ultimii biți ai valorii de intrare S-box determină numărul rândului din tabel, cei 4 biți din mijloc determină numărul coloanei. Intersecția unui rând și a unei coloane determină ieșirea pe 4 biți. De exemplu, dacă intrarea este 011011, atunci numărul rândului este 01 (rândul 1) și numărul coloanei este 1101 (coloana 13). Valoarea din rândul 1 și coloana 13 este 5, adică. ieșirea este 0101.
Valoarea rezultată pe 32 de biți este apoi procesată utilizând permutarea P, al cărei scop este de a reordona biții cât mai mult posibil, astfel încât în următoarea rundă de criptare, fiecare bit este probabil să fie procesat de o cutie S diferită.
Cheia pentru o rundă individuală K i constă din 48 de biți. Cheile Ki sunt obținute folosind următorul algoritm. Pentru cheia de 56 de biți utilizată ca intrare în algoritm, o permutare este mai întâi efectuată în conformitate cu tabelul Permuted Choice 1 (PC-1). Cheia de 56 de biți rezultată este împărțită în două părți de 28 de biți, notate ca C0 și, respectiv, D0. La fiecare rundă, C i și D i sunt deplasate ciclic independent la stânga cu 1 sau 2 biți, în funcție de numărul rundei. Valorile rezultate sunt intrarea pentru runda următoare. Ele sunt, de asemenea, intrarea la Permuted Choice 2 (PC-2), care produce o valoare de ieșire de 48 de biți care este intrarea pentru funcția F(R i-1, Ki).
Procesul de decriptare este similar cu procesul de criptare. Intrarea în algoritm este text cifrat, dar cheile K i sunt folosite în ordine inversă. K 16 este folosită în prima rundă, K 1 este folosită în ultima rundă. Fie rezultatul rundei i-a de criptare L i ||R i . Atunci intrarea corespunzătoare a rundei de decriptare (16-i) va fi R i ||L i .
După ultima rundă a procesului de decriptare, cele două jumătăți ale ieșirii sunt schimbate astfel încât intrarea permutării finale IP-1 să fie R 16 ||L 16 . Rezultatul acestei etape este text simplu.
Algoritm DES
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țiunilor 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 unui bloc de 64 de biți, șaisprezece cicluri de criptare și, în final, o permutare inversă a biților (Fig. 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.
Fig.2. Structura algoritmului de criptare DES
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. Rezultat 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 luați în considerare funcția de criptare f(R(i-1),K(i)). Este prezentat schematic în Fig. 3.
Fig.3. Calculul funcției f(R(i-1), K(i))
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 definită în Tabelul 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 Tabelul 4.
Tabelul 4
La tabelul 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 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 fiecăruia dintre blocurile de 6 biți B(1), B(2), ..., B(8), obținem secvența 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 pe cei rămași, se utilizează 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 consta din biții 63, 55, ..., 12, 4 ai cheii K. După definirea 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 Tabelul 7.
Tabelul 7
Tabel Shift pentru calculul cheii
| Număr de iterație | Shift (biți) |
| 01 | 1 |
| 02 | 1 |
| 03 | 2 |
| 04 | 2 |
| 05 | 2 |
| 06 | 2 |
| 07 | 2 |
| 08 | 2 |
| 09 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
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.
Fig.4. Diagrama bloc a algoritmului de calcul al cheii K(i)
Restaurarea textului original se realizează folosind acest algoritm, dar mai întâi utilizaț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!
Moduri de operare ale algoritmului DES
Pentru a satisface pe deplin toate cerințele pentru sisteme comerciale criptare, sunt implementate mai multe moduri de operare ale algoritmului DES. Cele mai utilizate moduri sunt:
· electronic codebook (Electronic Codebook) - BCE;
· lanț de blocuri digitale (Cipher Block Chaining) - CBC;
· feedback digital (Cipher Feedback) - CFB;
· feedback extern (Output Feedback) - OFB.
În acest mod dosarul original M este împărțit în blocuri de 64 de biți (8 octeți fiecare): M = M(1)M(2)...M(n). Fiecare dintre aceste blocuri este criptat independent folosind aceeași cheie de criptare (Fig. 5). Principalul avantaj al acestui algoritm este ușurința sa de implementare. Dezavantajul este că este relativ slab împotriva criptoanalistilor calificați.
