Napomena: Jedan od najpoznatijih kriptografski sistemi With privatni ključ je DES - Standard šifriranja podataka. Ovaj sistem je prvi dobio status državni standard u oblasti enkripcije podataka. I iako je stari američki DES standard sada izgubio službeni status, ovaj algoritam još uvijek zaslužuje pažnju prilikom proučavanja kriptografije. Osim toga, ovo predavanje objašnjava šta je "dvostruki DES", napad "meet in the middle" i kako ga popraviti. Ovo predavanje ukratko govori novi standard Američka blok šifra - Rijndaelov algoritam.
Svrha predavanja: upoznati studenta sa osnovama algoritma DES enkripcija.
Osnovne informacije
Jedan od najpoznatijih kriptografskih sistema sa privatnim ključem je DES - Standard šifriranja podataka. Ovaj sistem je prvi dobio status državnog standarda u oblasti enkripcije podataka. Razvili su ga stručnjaci IBM-a i stupio je na snagu u SAD-u 1977. godine. Algoritam DESširoko se koristi u skladištenju i prenosu podataka između različitih računarskih sistema; v sistemi pošte, v elektronski sistemi crteži i elektronska razmjena komercijalne informacije. Standard DES implementiran i softverski i hardverski. Preduzeća različite zemlje pokrenuta je masovna proizvodnja digitalnih uređaja koristeći DES za enkripciju podataka. Svi uređaji su prošli obavezna certifikacija da ispuni standard.
Unatoč činjenici da već neko vrijeme ovaj sistem nije imao status državnog standarda, još uvijek se široko koristi i zaslužuje pažnju prilikom proučavanja blok šifri s privatnim ključem.
Dužina ključa u algoritmu DES je 56 bita. Upravo sa ovom činjenicom je glavna polemika u vezi sa sposobnošću da DES odoljeti raznim napadima. Kao što znate, svaka blok šifra s privatnim ključem može se razbiti pokušajem svih mogućih kombinacija ključeva. Sa dužinom ključa od 56 bita, 2 56 različiti ključevi. Ako kompjuter nabroji 1.000.000 ključeva u jednoj sekundi (što je otprilike jednako 220), onda će mu trebati 236 sekundi ili nešto više od dvije hiljade godina da nabroji svih 256 ključeva, što je, naravno, neprihvatljivo za napadače.
Međutim, skuplje i brže računarski sistemi, kako PC . Na primjer, ako je moguće kombinirati milion procesora za paralelno računanje, onda maksimalno vrijeme odabir ključa je smanjen na otprilike 18 sati. Ovo vrijeme nije predugo, a kriptoanalitičar opremljen tako skupom opremom može lako izvesti DES-šifrirani napad u razumnom vremenu.
Istovremeno, može se primijetiti da sistem DES može se koristiti u malim i srednjim aplikacijama za šifriranje podataka male vrijednosti. Za šifrovanje podataka od nacionalnog značaja ili značajne komercijalne vrednosti, sistem DES trenutno se, naravno, ne bi trebalo koristiti. 2001. godine, nakon posebno raspisanog konkursa u Sjedinjenim Državama, usvojen je novi standard blok šifriranja, tzv. AES (napredni standard šifriranja), koji je zasnovan na šifri Rijndael razvijen od strane belgijskih stručnjaka. O ovoj šifri se govori na kraju predavanja.
Glavna podešavanja DES: veličina bloka 64 bita, dužina ključa 56 bita, broj rundi - 16. DES je klasična mreža Feishtel sa dvije ekspoziture. Algoritam pretvara 64-bitni blok ulaznih podataka u 64-bitni izlazni blok u nekoliko rundi. Standard DES izgrađen na kombinovana upotreba permutacije, supstitucije i gamifikacije. Šifrirani podaci moraju biti u binarnom obliku.
Enkripcija
Opća struktura DES prikazano na sl. 4.1. Proces šifriranja svakog 64-bitnog bloka izvornih podataka može se podijeliti u tri faze:
- početna priprema bloka podataka;
- 16 kola "glavnog ciklusa";
- finalna obrada bloka podataka.
U prvoj fazi, početna permutacija 64-bitni izvorni blok teksta, tokom kojeg se bitovi preuređuju na određeni način.
U sljedećoj (glavnoj) fazi blok se dijeli na dva dijela (grane) od po 32 bita. Desna grana se transformira pomoću neke funkcije F i odgovarajuće djelomični ključ, dobiven iz glavnog ključa za šifriranje pomoću posebnog algoritma za konverziju ključa. Zatim se podaci razmjenjuju između lijeve i desne grane bloka. Ovo se ponavlja 16 puta u ciklusu.
Konačno, u trećoj fazi, rezultat dobijen nakon šesnaest koraka glavne petlje se permutira. Ova permutacija je suprotna originalnoj permutaciji.
Rice. 4.1.
Razmotrimo detaljnije sve faze kriptografske transformacije prema standardu DES.
U prvoj fazi, 64-bitni blok izvornih podataka prolazi kroz početnu permutaciju. U literaturi se ova operacija ponekad naziva i "whitening" - izbjeljivanje. Tokom početne permutacije, bitovi bloka podataka se preuređuju na određeni način. Ova operacija daje određenu "slučajnost" originalnoj poruci, smanjujući mogućnost korištenja kriptoanalize statističkim metodama.
Istovremeno sa početnom permutacijom bloka podataka, vrši se i početna permutacija od 56 bita ključa. Od sl. 4.1. može se vidjeti da se u svakoj rundi koristi odgovarajući 48-bitni parcijalni ključ K i. Ključevi K i se dobijaju prema određenom algoritmu, koristeći svaki od bitova početnog ključa nekoliko puta. U svakoj rundi, 56-bitni ključ je podijeljen na dvije 28-bitne polovine. Polovine se zatim pomiču ulijevo za jedan ili dva takta, ovisno o broju kruga. Nakon pomaka, 48 od 56 bita se bira na određeni način. Budući da ovo ne samo da odabire podskup bitova, već i mijenja njihov redoslijed, ova operacija se naziva operacija "swap-swap". Njegov rezultat je skup od 48 bita. U prosjeku, svaki bit originalnog 56-bitnog ključa se koristi u 14 od 16 potključeva, iako se svi bitovi ne koriste isti broj puta.
Zatim se izvodi glavni transformacijski ciklus, organiziran prema Feishtel mreži i koji se sastoji od 16 identičnih krugova. U ovom slučaju, u svakoj rundi (slika 4.2), dobije se srednja 64-bitna vrijednost, koja se zatim obrađuje u sljedećem krugu.
Rice. 4.2.
Lijeva i desna grana svake međuvrijednosti tretiraju se kao zasebne 32-bitne vrijednosti, označene kao L i R.
Prvo, desna strana R i bloka se proširuje na 48 bita koristeći tablicu koja definira permutaciju plus proširenje od 16 bita. Ova operacija prilagođava veličinu desne polovine kako bi odgovarala veličini ključa za izvođenje operacije XOR. Osim toga, zbog izvršenja ove operacije, ovisnost svih bitova rezultata o bitovima originalnih podataka i ključa raste brže (ovo se naziva "efekat lavine"). Što je jači efekat lavine kada se koristi jedan ili drugi algoritam šifriranja, to bolje.
Nakon što se izvrši permutacija proširenja, rezultirajuća 48-bitna vrijednost je XOR sa 48-bitnim potključem K i . Zatim se rezultirajuća 48-bitna vrijednost unosi na ulaz zamjenskog bloka S (sa engleskog. Zamjena - zamjena), rezultatšto je 32-bitna vrijednost . Zamjena se vrši u osam zamjenskih kutija ili osam S-kutija. Prilikom izvršavanja ovog DES-a, na papiru izgleda prilično komplikovano, a kamoli njegova softverska implementacija! Razviti program koji ispravno i optimalno funkcionira u potpunosti u skladu sa DES, vjerovatno, samo iskusni programeri. Neke poteškoće nastaju kada implementacija softvera, kao što je početna permutacija ili permutacija sa ekspanzijom. Ove poteškoće su povezane sa činjenicom da je prvobitno planirana implementacija DES samo u hardveru. Sve operacije koje se koriste u standardu lako se izvode od strane hardverskih jedinica i nema poteškoća s implementacijom. Međutim, neko vrijeme nakon objavljivanja standarda, programeri softvera odlučili su da ne stoje po strani i također se bave kreiranjem sistema šifriranja. Dalje DES implementiran kako u hardveru tako i u softveru.
DES standard dizajniran za zaštitu od neovlaštenog pristupa važnim, ali ne povjerljive informacije u američkoj vladi i komercijalnim organizacijama. Algoritam koji je u osnovi standarda proširio se prilično brzo, a već 1980. godine odobren je od strane američkog Nacionalnog instituta za standarde i tehnologiju. Od ovog trenutka DES postaje standard ne samo po imenu, već iu stvari. pojavi se softvera i specijalizovani mikroračunari dizajnirani za šifrovanje i dešifrovanje informacija u mrežama podataka.
Do danas, DES je najčešći algoritam koji se koristi u sigurnosnim sistemima. komercijalne informacije. Štaviše, implementacija DES algoritma u takvim sistemima postaje znak dobrog ukusa.
Glavne prednosti DES algoritma:
Koristi se samo jedan 56-bitni ključ;
· nakon šifriranja poruke pomoću jednog paketa, možete koristiti bilo koji drugi za dešifriranje;
Relativna jednostavnost algoritma obezbeđuje velika brzina obrada informacija;
prilično visoka stabilnost algoritma.
DES šifrira 64-bitne blokove podataka koristeći 56-bitni ključ. Dešifriranje u DES-u je obrnuta operacija šifriranja i izvodi se ponavljanjem operacija šifriranja obrnutim redoslijedom (uprkos prividnoj očiglednosti, to se ne radi uvijek. Kasnije ćemo razmotriti šifre u kojima se šifriranje i dešifriranje provode korištenjem različitih algoritama).
Proces šifriranja se sastoji od početne zamjene bitova 64-bitnog bloka, šesnaest rundi šifriranja i konačno obrnute zamjene bitova (slika 1).
Treba odmah napomenuti da su SVE tabele date u ovom članku STANDARDNE, te da ih stoga treba uključiti u vašu implementaciju algoritma nepromijenjene. Sve permutacije i kodove u tabelama su odabrani od strane programera na način da otežaju proces dešifriranja što je više moguće odabirom ključa. Struktura DES algoritma je prikazana na sl. 2.
Rice. 2.
Neka se sljedeći 8-bajtni blok T pročita iz datoteke, koja se transformira korištenjem početne permutacijske matrice IP (Tabela 1) na sljedeći način: bit 58 bloka T postaje bit 1, bit 50 postaje bit 2, itd., što će rezultirati u: T(0) = IP(T).
Rezultirajuća sekvenca bitova T(0) je podijeljena u dvije sekvence od po 32 bita: L(0) - lijevo ili visoko, R(0) - desno ili nisko.
Tabela 1: IP početna matrica permutacije
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
Zatim se izvodi enkripcija koja se sastoji od 16 iteracija. Rezultat i iteracija je opisana sljedećim formulama:
R(i) = L (i-1) xor f (R(i-1), K(i)),
gdje je xor operacija ISKLJUČIVO ILI.
Funkcija f naziva se funkcija šifriranja. Njegovi argumenti su 32-bitni niz R (i-1) dobijen na (i-1) - iteraciji i 48-bitni ključ K(i), koji je rezultat pretvaranja 64-bitnog ključa K. U nastavku je detaljno opisana funkcija šifriranja i algoritam za izvođenje ključeva K(i).
U 16. iteraciji dobijaju se sekvence R(16) i L(16) (bez permutacije), koje se spajaju u 64-bitni niz R(16) L(16).
Zatim se pozicije bitova ove sekvence preuređuju u skladu sa matricom IP -1 (tabela 2).
Tabela 2: IP-1 Inverzna matrica permutacije
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
IP -1 i IP matrice su povezane na sljedeći način: vrijednost 1. elementa IP -1 matrice je 40, a vrijednost 40. elementa IP matrice je 1, vrijednost 2. element matrice IP -1 je 8, a vrijednost 8. elementa matrice IP je 2 i tako dalje.
Proces dešifriranja podataka je inverzan od procesa šifriranja. Sve radnje se moraju izvršiti u obrnutim redosledom. To znači da se podaci koji se dešifriraju prvo preuređuju prema IP-1 matrici, a zatim se na sekvenci bita R(16) L(16) izvode iste operacije kao u procesu šifriranja, ali obrnutim redoslijedom.
Iterativni proces dešifriranja može se opisati sljedećim formulama:
R(i-1) = L(i), i = 1, 2,…, 16;
L (i-1) = R(i) xor f (L(i), K(i)), i = 1, 2,…, 16.
U 16. iteraciji dobijaju se sekvence L(0) i R(0), koje se spajaju u 64-bitnu sekvencu L(0) R(0).
Pozicije bitova ove sekvence se zatim preuređuju prema IP matrici. Rezultat ove permutacije je originalna 64-bitna sekvenca.
Sada razmotrite funkciju šifriranja f (R(i-1), K(i)). Šematski je prikazano na Sl. 3.
Rice. 3.
Za izračunavanje vrijednosti funkcije f koriste se sljedeće matrične funkcije:
E - proširenje 32-bitne sekvence na 48-bitnu,
S1, S2,…, S8 - 6-bitna u 4-bitna blok konverzija,
P je permutacija bita u 32-bitnoj sekvenci.
Funkcija proširenja E definirana je u tabeli. 3. Prema ovoj tabeli, prva 3 bita E (R(i-1)) su bitovi 32, 1 i 2, a posljednja su 31, 32 i 1.
Tabela 3: Funkcija proširenja 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
Rezultat funkcije E (R(i-1)) je 48-bitni niz koji se dodaje po modulu 2 (xor operacija) sa 48-bitnim ključem K(i). Dobija se 48-bitna sekvenca koja je podijeljena na osam 6-bitnih blokova B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). To je:
E (R(i-1)) xili K(i) = B(1) B(2)… B(8).
Funkcije S1, S2, ..., S8 definirane su u tabeli. 4.
Tabela 4
Za sto. 4. Potrebna su dodatna objašnjenja. Neka je ulaz matrične funkcije Sj 6-bitni blok B(j) = b1b2b3b4b5b6, tada dvobitni broj b1b6 označava broj reda matrice, a b2b3b4b5 broj kolone. Rezultat Sj (B(j)) će biti 4-bitni element koji se nalazi na presjeku navedenog reda i stupca.
Na primjer, B(1)=011011. Tada se S1 (B(1)) nalazi na raskrsnici reda 1 i kolone 13. Kolona 13 reda 1 je postavljena na 5. Dakle, S1 (011011)=0101.
Primjenjujući operaciju odabira na svaki od 6-bitnih blokova B(1), B(2),..., B(8), dobijamo 32-bitnu sekvencu S1 (B(1)) S2 (B(2)) S3 (B(3))… S8 (B(8)).
Konačno, da biste dobili rezultat funkcije šifriranja, trebate preurediti bitove ove sekvence. Za to se koristi funkcija permutacije P (tablica 5). U ulaznoj sekvenci, bitovi su obrnuti tako da bit 16 postaje bit 1, bit 7 postaje bit 2, itd.
Tabela 5: Funkcija permutacije P
Na ovaj način,
f (R(i-1), K(i)) = P (S1 (B(1)),… S8 (B(8)))
Da bismo završili opis algoritma za šifrovanje podataka, ostaje da navedemo algoritam za dobijanje 48-bitnih ključeva K(i), i=1…16. Pri svakoj iteraciji koristi se nova vrijednost ključa K(i), koja se izračunava iz početnog ključa K. K je 64-bitni blok sa osam paritetnih bitova smještenih na pozicijama 8,16,24,32,40,48, 56, 64.
Za uklanjanje kontrolnih bitova i preuređivanje ostataka koristi se funkcija G početne pripreme ključa (tablica 6).
Tabela 6
Matrica G početne pripreme ključa
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
Rezultat transformacije G(K) je podijeljen u dva 28-bitna bloka C(0) i D(0), gdje će se C(0) sastojati od bitova 57, 49,…, 44, 36 ključa K, i D(0) će se sastojati od bitova 63, 55,…, 12, 4 ključa K. Nakon što se odrede C(0) i D(0), C(i) i D(i), i=1 …16, određuju se rekurzivno. Za to se ciklički pomak ulijevo primjenjuje za jedan ili dva bita, ovisno o broju iteracije, kao što je prikazano u Tabeli 1. 7.
Tablica 7. Tablica pomaka za izračunavanje ključa
|
Broj iteracije |
Shift (bit) |
Rezultirajuća vrijednost se ponovo "miješa" u skladu sa matricom H (tabela 8).
Tabela 8: Ključna završna matrica 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
Ključ K(i) će se sastojati od bitova 14, 17,…, 29, 32 sekvence C(i) D(i). Na ovaj način:
K(i) = H (C(i) D(i))
Blok dijagram algoritma proračuna ključeva prikazan je na sl. 4.
Rice. 4.
Oporavak izvorni kod se izvodi po ovom algoritmu, ali prvo koristite tipku K(15), zatim - K(14) i tako dalje. Sada biste trebali razumjeti zašto autor snažno preporučuje korištenje gornjih matrica. Ako počnete da idete samovoljno, morate dobiti vrlo tajnu šifru, ali je kasnije nećete moći otvoriti!
Koji ANSI naziva DEA (Algoritam šifriranja podataka) algoritam za šifrovanje podataka, a ISO - DEA-1, postao je svjetski standard za 20 godina. Tokom godina svog postojanja izdržao je navalu raznih napada i, uz određena ograničenja, i dalje se smatra kripto otpornim.
DES je blok šifra koja šifrira podatke u 64-bitnim blokovima. 64-bitni blok otvorenog teksta se unosi sa jednog kraja algoritma, a 64-bitni blok šifrovanog teksta izlazi sa drugog kraja. DES je simetrični algoritam: Isti algoritam i ključ se koriste za šifriranje i dešifriranje (osim malih razlika u korištenju ključa). Dužina ključa je 56 bita. (Ključ je obično predstavljen kao 64-bitni broj, ali svaki osmi bit se koristi za paritet i zanemaruje se. Paritetni bitovi su najmanji značajni bitovi bajtova ključa.) Ključ, koji može biti bilo koji 56-bitni broj, može se promijeniti u bilo koje vrijeme.
Kriptografska snaga je u potpunosti određena ključem. Osnovni građevni blok DES-a je kombinacija supstitucija i permutacija. DES se sastoji od 16 ciklusa.
Opšti pogled na ciklus transformacije:
Ako su L i i R i lijeva i desna polovina rezultat i-te iteracije, K i je 48-bitni ključ za petlju i, a f je funkcija koja izvodi sve zamjene, permutacije i XOR-ove s ključem, tada jedna petlja konverzije se može zamisliti kao:
Uzimajući u obzir supstituciju F i (*) i permutaciju T (*), ciklus transformacije se može predstaviti kao što je to urađeno na Sl.
Može se vidjeti da je svaki DES ciklus složena šifra sa dvije uzastopne transformacije - supstitucijom F i (*) i permutacijom T (*) (osim posljednjeg, šesnaestog ciklusa, gdje je permutacija izostavljena).
Zamjena:
(L i , R i) = (R i −1 , L i −1) ⊕ f (R i −1 , K)
je involucija jer
F i (F i (L i −1 , R i −1)) = F 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)
Zamjena
T (L i ′, R i ′) = (R i ′, L i ′),
je takođe involucija, pošto
T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′
Ako početnu i konačnu permutaciju označimo kao (IP) i (IP) - 1, tada direktna DES transformacija (šifriranje) implementira funkciju:
DES = (IP) F 1 TF 2 T ... F 15 TF 16 (IP) − 1 ,
a inverzna DES transformacija (dešifriranje) implementira funkciju:
DES - 1 = (IP) -1 F 16 TF 15 T ... F 2 TF 1 (IP).
Dakle, DES je Feistelova šifra i dizajnirana je da radi korisno svojstvo: Isti algoritam se koristi za šifriranje i dešifriranje. Jedina razlika je u tome što se ključevi moraju koristiti obrnutim redoslijedom.
Odnosno, ako su ključevi K 1 , K 2 , K 3 , ..., K 16 korišteni za šifriranje, tada će ključevi za dešifriranje biti K 16 , K 15 , K 14 , ..., K 1 . Algoritam koristi samo standardnu aritmetiku 64-bitnih brojeva i logičke operacije, tako da je lako implementirati u hardveru.
DES radi na 64-bitnom bloku otvorenog teksta. Nakon početne permutacije, blok se dijeli na desnu i lijevu polovinu od po 32 bita. Zatim se izvodi 16 transformacija (funkcija f) u kojima se podaci kombinuju sa ključem. Nakon šesnaestog ciklusa, desna i lijeva polovina se kombinuju, a algoritam se završava konačnom permutacijom (obrnutom od originalne). U svakom ciklusu (vidi sliku), bitovi ključa se pomiču, a zatim se bira 48 bitova od 56 bitova ključa. Desna polovina podataka je povećana na 48 bita raširenom permutacijom, XOR je obrađena sa 48 bita pomaknutog i permutiranog ključa, prošla kroz 8 S-kutija da bi se formirala 32 nova bita i ponovo permutirana. Ove četiri operacije izvodi funkcija f.
Rezultat f se zatim kombinuje sa lijevom polovinom koristeći drugi XOR. Kao rezultat ovih radnji, pojavljuje se nova desna polovina, a stara desna postaje nova lijeva polovina. Ove radnje se ponavljaju 16 puta, formirajući 16 DES ciklusa.
Ruski standard - GOST 28147-89
GOST 28147-89 je blok šifra sa 256-bitnim ključem i 32 ciklusa konverzije, koja radi na 64-bitnim blokovima. Koristi se i kripto algoritam dodatni ključ, o čemu se govori u nastavku. Za enkripciju običan tekst prvo se dijeli na lijevu i desnu polovinu L i R. U i-tom ciklusu se koristi potključ K i:
L i = R i −1 ,
R i = L i −1 ⊕ (f (R i −1 , K i)).
Funkcija f se implementira na sljedeći način. Prvo, desna polovina i i-ti potključ se dodaju po modulu 2 32 . Rezultat je podijeljen na osam 4-bitnih podniza, od kojih se svaka dovodi na ulaz svog S-boxa. GOST koristi osam različitih S-kutija, prva 4 bita idu u prvu S-kutiju, druga 4 bita u drugu S-kutiju, itd. Svaki S-kutija je permutacija brojeva od 0 do 15. Za Na primjer, S-box može izgledati ovako: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. U ovom slučaju, ako je ulaz S-kutije 0, onda je izlaz 7. Ako je ulaz 1, izlaz je 10, itd. Svih osam S-kutija su različiti, oni su zapravo dodatni ključni materijal. Izlazi svih osam S-kutija se kombinuju u 32-bitnu reč, a zatim se čitava reč rotira ulevo za 11 bita. Konačno, rezultat je XOR sa lijevom polovinom, što rezultira novom desnom polovinom, a desna polovina postaje nova lijeva polovina. Za generiranje potključeva, originalni 256-bitni ključ je podijeljen u osam 32-bitnih blokova: k 1 , k 2 , …, k 8 . Svaki ciklus koristi svoj vlastiti potključ. Dešifriranje se izvodi na isti način kao i šifriranje, ali je redoslijed potključeva k i obrnut. Standard ne definiše kako se S-kutije generišu.
Glavne razlike između DES-a i GOST-a
Glavne razlike između DES-a i GOST-a su sljedeće:
- DES koristi složenu proceduru za generiranje potključeva iz ključeva. U GOST-u je ova procedura vrlo jednostavna;
- DES ima 56-bitni ključ, dok GOST ima 256-bitni ključ. Ako dodamo tajne permutacije S-kutija, onda će ukupna količina GOST tajnih informacija biti približno 610 bita;
- DES S-kutije imaju 6-bitne ulaze i 4-bitne izlaze, a GOST S-kutije imaju 4-bitne ulaze i izlaze. Oba algoritma koriste osam S-kutija, ali veličina GOST S-kutije je četvrtina veličine DES S-kutije;
- DES koristi nepravilne permutacije, nazvane P-blok, a GOST koristi 11-bitni ciklički pomak ulijevo;
- u DES-u ima 16 ciklusa, au GOST-u - 32.
Napad snage na GOST je apsolutno beznadežan. GOST koristi 256-bitni ključ, a ako uzmete u obzir tajne S-kutije, tada će dužina ključa biti još veća. Čini se da je GOST otporniji na diferencijalnu i linearnu kriptoanalizu od DES-a. Iako nasumične GOST S-kutije, uz određeni izbor, ne garantuju visoku kriptografsku snagu u poređenju sa fiksnim DES S-kutijama, njihova tajnost povećava otpornost GOST-a na diferencijalnu i linearnu kriptoanalizu. Osim toga, efikasnost ovih kriptoanalitičkih metoda ovisi o broju ciklusa konverzije – što je više ciklusa, to je kriptoanaliza teža. GOST koristi dvostruko više ciklusa nego DES, što može dovesti do neuspjeha diferencijalne i linearne kriptoanalize.
GOST ne koristi permutaciju proširenja koja postoji u DES-u. Uklanjanje ove permutacije iz DES-a slabi je smanjenjem efekta lavine; razumno je pretpostaviti da odsustvo takve operacije u GOST-u ima negativan učinak na njegovu kriptografsku snagu. Sa stanovišta kriptografske snage, operacija aritmetičkog sabiranja koja se koristi u GOST-u nije ništa lošija od operacije XOR u DES-u.
Glavna razlika je korištenje cikličkog pomaka u GOST-u umjesto permutacije. Zamjena DES-a povećava efekat lavine. U GOST-u, promjena jednog ulaznog bita utječe na jednu S-kutiju jednog ciklusa konverzije, koja zatim utječe na dva S-kutija sljedećeg ciklusa, zatim tri bloka sljedećeg ciklusa, itd. Potrebno je osam ciklusa pre nego što promena jednog ulaznog bita utiče na svaki bit rezultata; u DES-u, ovo traje samo pet ciklusa. Međutim, GOST se sastoji od 32 ciklusa, a DES samo 16.
Programeri GOST-a pokušali su postići ravnotežu između kriptografske snage i efikasnosti. Na osnovu Feistelovog dizajna, razvili su kriptalgoritam koji je prikladniji za implementaciju softvera od DES-a. Da bi se poboljšala kriptografska snaga, uveden je ekstra dug ključ, a broj ciklusa je udvostručen. Međutim, ostaje otvoreno pitanje da li su napori programera rezultirali stvaranjem više kriptografskog algoritma od DES-a.
Vorobieva E., Lukyanova A.
Najčešći i najpoznatiji algoritam simetrične enkripcije je DES (Standard šifriranja podataka). Algoritam je razvijen 1977. godine, a 1980. NIST (Nacionalni institut za standarde i tehnologiju, SAD) je usvojen kao standard.
DES je klasična Feishtel mreža sa dvije podružnice. Podaci su šifrirani u 64-bitnim blokovima pomoću 56-bitnog ključa. Algoritam pretvara 64-bitni ulaz u 64-bitni izlaz u nekoliko rundi. Dužina ključa je 56 bita. Proces šifriranja se sastoji od četiri koraka. Prvi korak je izvođenje početne permutacije (IP) 64-bitnog otvorenog teksta (izbjeljivanje), tokom kojeg se bitovi preuređuju prema standardni sto. Sljedeća faza se sastoji od 16 rundi iste funkcije, koja koristi operacije pomaka i zamjene. U trećoj fazi, lijeva i desna polovina izlaza posljednje (16.) iteracije se zamjenjuju. Konačno, u četvrtoj fazi, vrši se IP-1 permutacija rezultata dobijenog u trećoj fazi. IP-1 permutacija je inverzna od početne permutacije.
Fig.4. DES algoritam
Slika prikazuje metodu koja koristi 56-bitni ključ. U početku se ključ dovodi na ulaz funkcije permutacije. Zatim, za svaku od 16 rundi, potključ K i je kombinacija lijevog cikličkog pomaka i permutacije. Funkcija permutacije je ista za svaki krug, ali su potključevi K i za svaki krug različiti zbog ponovljenog pomjeranja bitova ključa.
Početna permutacija i njena inverzna su određena standardnom tablicom. Ako je M proizvoljna 64 bita, onda je X = IP(M) - permutirana 64 bita. Ako primijenimo funkciju inverzne permutacije Y = IP-1 (X) = IP-1 (IP(M)), dobićemo originalnu sekvencu bitova.
Opis okruglih des
Razmotrite slijed transformacija korištenih u svakoj rundi.
Sl.5. Ilustracija kruga DES algoritma
64-bitni ulazni blok prolazi kroz 16 runde, dok se pri svakoj iteraciji dobije srednja 64-bitna vrijednost. Lijevi i desni dio svake međuvrijednosti tretiraju se kao zasebne 32-bitne vrijednosti, označene L i R. Svaka iteracija se može opisati na sljedeći način:
R i = L i -1 F(R i -1 , K i)
Dakle, izlaz lijeve polovine L i jednak je ulazu desne polovine R i-1 . Izlaz desne polovice R i rezultat je XOR-a L i-1 i funkcije F ovisno o R i-1 i K i .
Razmotrimo funkciju F detaljnije. R i , koji se dovodi na ulaz funkcije F, ima dužinu od 32 bita. Prvo, R i se proširuje na 48 bita koristeći tablicu koja definira permutaciju plus proširenje od 16 bita. Ekspanzija ide ovako. 32 bita se dijele u grupe od 4 bita, a zatim se proširuju na 6 bita dodavanjem ekstremnih bitova iz dvije susjedne grupe. Na primjer, ako je dio ulazne poruke
Efgh ijkl mnop . . .
onda je rezultat proširenja poruka
Defghi hijklm lmnopq . . .
Rezultirajuća 48-bitna vrijednost se zatim pretvara u XOR sa 48-bitnim potključem K i . Rezultirajuća 48-bitna vrijednost se zatim unosi u funkciju zamjene, što rezultira 32-bitnom vrijednošću.
Zamjena se sastoji od osam S-kutija, od kojih svaki prima 6 bita kao ulaz i proizvodi 4 bita kao izlaz. Ove transformacije su definirane posebnim tabelama. Prvi i posljednji bit ulazne vrijednosti S-boxa određuju broj reda u tabeli, srednja 4 bita određuju broj kolone. Presjek reda i stupca definira 4-bitni izlaz. Na primjer, ako je unos 011011, tada je broj reda 01 (red 1), a broj stupca 1101 (kolona 13). Vrijednost u redu 1 i koloni 13 je 5, tj. izlaz je 0101.
Zatim se rezultujuća 32-bitna vrijednost obrađuje pomoću permutacije P, čija je svrha da se bitovi preurede što je više moguće tako da u sljedećem krugu enkripcije, s velikom vjerovatnoćom, svaki bit obrađuje drugačiji S. -kutija.
Ključ za jedan krug K i sastoji se od 48 bita. Ključevi K i se dobijaju sledećim algoritmom. 56-bitni ključ koji se koristi kao ulaz u algoritam se prvo permutira prema tabeli Permuted Choice 1 (PC-1). Rezultirajući 56-bitni ključ je podijeljen na dva 28-bitna dijela, označena kao C0 i D0, respektivno. U svakoj rundi, C i i D i se nezavisno rotiraju ulijevo za 1 ili 2 bita, ovisno o broju runde. Rezultirajuće vrijednosti su ulaz sljedeće runde. Oni su također ulaz za Permuted Choice 2 (PC-2), koji proizvodi 48-bitnu izlaznu vrijednost koja je ulaz funkcije F(R i-1, K i).
Proces dešifriranja je sličan procesu šifriranja. Algoritam koristi šifrirani tekst kao ulaz, ali se ključevi K i koriste obrnutim redoslijedom. K 16 se koristi u prvoj rundi, K 1 se koristi u posljednjoj rundi. Neka izlaz i-te runde šifriranja bude L i ||R i . Tada će odgovarajući ulaz (16-i) runde dešifriranja biti R i ||L i .
Nakon posljednje runde procesa dešifriranja, dvije polovice izlaza se zamjenjuju tako da je ulaz konačne permutacije IP-1 R 16 ||L 16 . Rezultat ove faze je običan tekst.
Algoritam DES
Glavne prednosti DES algoritma:
Koristi se samo jedan 56-bitni ključ;
· nakon šifriranja poruke pomoću jednog paketa, možete koristiti bilo koji drugi za dešifriranje;
Relativna jednostavnost algoritma osigurava veliku brzinu obrade informacija;
prilično visoka stabilnost algoritma.
DES šifrira 64-bitne blokove podataka koristeći 56-bitni ključ. Dešifriranje u DES-u je obrnuta operacija šifriranja i izvodi se ponavljanjem operacija šifriranja obrnutim redoslijedom (uprkos prividnoj očiglednosti, to se ne radi uvijek. Kasnije ćemo razmotriti šifre u kojima se šifriranje i dešifriranje provode korištenjem različitih algoritama).
Proces šifriranja se sastoji od početne zamjene bitova 64-bitnog bloka, šesnaest rundi šifriranja i konačno obrnute zamjene bitova (slika 1).
Treba odmah napomenuti da su SVE tabele date u ovom članku STANDARDNE, te da ih stoga treba uključiti u vašu implementaciju algoritma nepromijenjene. Sve permutacije i kodove u tabelama su odabrani od strane programera na način da otežaju proces dešifriranja što je više moguće odabirom ključa. Struktura DES algoritma je prikazana na slici 2.
Fig.2. Struktura algoritma DES enkripcije
Neka se sljedeći 8-bajtni blok T pročita iz datoteke, koja se transformira korištenjem početne permutacijske matrice IP (Tabela 1) na sljedeći način: bit 58 bloka T postaje bit 1, bit 50 postaje bit 2, itd., što će rezultirati u: T(0) = IP(T).
Rezultirajuća sekvenca bitova T(0) je podijeljena u dvije sekvence od po 32 bita: L(0) - lijevo ili visoko, R(0) - desno ili nisko.
Tabela 1: IP početna matrica permutacije
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
Zatim se izvodi enkripcija koja se sastoji od 16 iteracija. Rezultat i-ta iteracija opisuje se sljedećim formulama:
R(i) = L(i-1) xor f(R(i-1), K(i)) ,
gdje je xor operacija ISKLJUČIVO ILI.
Funkcija f naziva se funkcija šifriranja. Njegovi argumenti su 32-bitni niz R(i-1) dobijen na (i-1)-toj iteraciji i 48-bitni ključ K(i), koji je rezultat transformacije 64-bitnog ključa K. Funkcija šifriranja i algoritam za izvođenje ključeva K(i) opisani su u nastavku.
U 16. iteraciji dobijaju se sekvence R(16) i L(16) (bez permutacije), koje se spajaju u 64-bitni niz R(16)L(16).
Zatim se pozicije bitova ove sekvence preuređuju u skladu sa matricom IP -1 (tabela 2).
Tabela 2: IP-1 Inverzna matrica permutacije
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
IP -1 i IP matrice su povezane na sljedeći način: vrijednost 1. elementa IP -1 matrice je 40, a vrijednost 40. elementa IP matrice je 1, vrijednost 2. element matrice IP -1 je 8, a vrijednost 8. elementa matrice IP je 2 i tako dalje.
Proces dešifriranja podataka je inverzan od procesa šifriranja. Svi koraci se moraju izvesti obrnutim redoslijedom. To znači da se podaci koji se dešifriraju prvo preuređuju prema IP-1 matrici, a zatim se na sekvenci bita R(16)L(16) izvode iste operacije kao u procesu šifriranja, ali obrnutim redoslijedom.
Iterativni proces dešifriranja može se opisati sljedećim formulama:
R(i-1) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) x ili f(L(i), K(i)), i = 1, 2, ..., 16 .
U 16. iteraciji dobijaju se sekvence L(0) i R(0), koje se spajaju u 64-bitnu sekvencu L(0)R(0).
Pozicije bitova ove sekvence se zatim preuređuju prema IP matrici. Rezultat ove permutacije je originalna 64-bitna sekvenca.
Sada razmotrite funkciju šifriranja f(R(i-1),K(i)). Šematski je prikazano na Sl. 3.
Fig.3. Proračun funkcije f(R(i-1), K(i))
Za izračunavanje vrijednosti funkcije f koriste se sljedeće matrične funkcije:
E - proširenje 32-bitne sekvence na 48-bitnu,
S1, S2, ... , S8 - pretvaranje 6-bitnog bloka u 4-bitni blok,
P je permutacija bita u 32-bitnoj sekvenci.
Funkcija ekstenzije E definirana je u tabeli 3. Prema ovoj tabeli, prva 3 bita E(R(i-1)) su bitovi 32, 1 i 2, a posljednja su 31, 32 i 1.
Tabela 3: Funkcija proširenja 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
Rezultat funkcije E(R(i-1)) je 48-bitni niz koji se dodaje po modulu 2 (xor operacija) sa 48-bitnim ključem K(i). Rezultat je 48-bitni niz koji je podijeljen u osam 6-bitnih blokova B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). To je:
E(R(i-1)) xili K(i) = B(1)B(2)...B(8) .
Funkcije S1, S2, ..., S8 definirane su u tabeli 4.
Tabela 4
U tabelu.4. potrebna su dodatna objašnjenja. Neka je ulaz matrične funkcije Sj 6-bitni blok B(j) = b1b2b3b4b5b6, tada dvobitni broj b1b6 označava broj reda matrice, a b2b3b4b5 broj kolone. Rezultat Sj(B(j)) je 4-bitni element koji se nalazi na presjeku navedenog reda i stupca.
Na primjer, B(1)=011011. Tada se S1(V(1)) nalazi na raskrsnici reda 1 i kolone 13. Kolona 13 reda 1 je postavljena na 5. Dakle, S1(011011)=0101.
Primjenjujući operaciju odabira na svaki od 6-bitnih blokova B(1), B(2), ..., B(8), dobijamo 32-bitnu sekvencu S1(B(1))S2(B(2) ))S3( B(3))...S8(B(8)).
Konačno, da biste dobili rezultat funkcije šifriranja, trebate preurediti bitove ove sekvence. Za to se koristi funkcija permutacije P (tablica 5). U ulaznoj sekvenci, bitovi su obrnuti tako da bit 16 postaje bit 1, bit 7 postaje bit 2, itd.
Tabela 5: Funkcija permutacije P
Na ovaj način,
f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))
Da bismo završili opis algoritma za šifrovanje podataka, ostaje da navedemo algoritam za dobijanje 48-bitnih ključeva K(i), i=1...16. Pri svakoj iteraciji koristi se nova vrijednost ključa K(i), koja se izračunava iz početnog ključa K. K je 64-bitni blok sa osam paritetnih bitova smještenih na pozicijama 8,16,24,32,40,48, 56, 64.
Za uklanjanje kontrolnih bitova i preuređivanje ostataka koristi se funkcija G početne pripreme ključa (tablica 6).
Tabela 6
Matrica G početne pripreme ključa
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
Rezultat transformacije G(K) je podijeljen u dva 28-bitna bloka C(0) i D(0), a C(0) će se sastojati od bitova 57, 49, ..., 44, 36 od K ključ, a D(0) će se sastojati od bitova 63, 55, ..., 12, 4 ključa K. Nakon definiranja C(0) i D(0), C(i) i D(i), i =1...16, su rekurzivno definisane. Za to se ciklički pomak ulijevo primjenjuje za jedan ili dva bita, ovisno o broju iteracije, kao što je prikazano u Tabeli 7.
Tabela 7
Tablica pomaka za izračun ključa
| Broj iteracije | Shift (bit) |
| 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 |
Rezultirajuća vrijednost se ponovo "miješa" u skladu sa matricom H (tabela 8).
Tabela 8: Ključna završna matrica 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
Ključ K(i) će se sastojati od bitova 14, 17, ..., 29, 32 sekvence C(i)D(i). Na ovaj način:
K(i) = H(C(i)D(i))
Blok dijagram algoritma proračuna ključeva prikazan je na sl.4.
Fig.4. Blok dijagram algoritma za izračunavanje ključa K(i)
Obnavljanje originalnog teksta vrši se prema ovom algoritmu, ali prvo koristite ključ
K(15), zatim - K(14) i tako dalje. Sada biste trebali razumjeti zašto autor snažno preporučuje korištenje gornjih matrica. Ako počnete da idete samovoljno, morate dobiti vrlo tajnu šifru, ali je kasnije nećete moći otvoriti!
Načini rada DES algoritma
Kako bi u potpunosti ispunili sve zahtjeve za komercijalni sistemi enkripcijom, implementirano je nekoliko načina rada DES algoritma. Najrasprostranjeniji načini rada su:
Elektronski šifarnik (Electronic Codebook) - ECB;
lanac digitalnih blokova (Cipher Block Chaining) - CBC;
digitalna povratna informacija (Cipher Feedback) - CFB;
Eksterna povratna informacija (Output Feedback) - OFB.
U ovom modu originalni fajl M je podijeljen na 64-bitne blokove (po 8 bajtova): M = M(1)M(2)...M(n). Svaki od ovih blokova je kodiran nezavisno koristeći isti ključ za šifrovanje (slika 5). Glavna prednost ovog algoritma je jednostavnost implementacije. Nedostatak je relativno slaba otpornost na vješte kriptoanalitičare.
