DES algoritam i njegove varijante. Algoritmi šifriranja DES i AES

• Tutorial

Pozdrav %username%!
Mnogi ljudi znaju da je zadani standard na terenu simetrična enkripcija dugo vremena smatralo se DES algoritam. Prvi uspješan napad na ovaj algoritam koji se ne može uništiti objavljen je 1993. godine, 16 godina nakon što je usvojen kao standard. Metoda, koju je autor nazvao linearna kriptoanaliza, u prisutnosti 2 47 parova čistih/šifriranih tekstova, omogućuje probijanje tajni ključ DES šifra u 2 43 operacije.
Ispod presjeka pokušat ću ukratko ocrtati glavne točke ovog napada.

Linearna kriptoanaliza

Općenito, napad temeljen na linearnoj kriptoanalizi svodi se na sljedeće uvjete. Napadač ima velik broj parovi otvoreni tekst/šifrirani tekst dobiveni korištenjem istog ključa za šifriranje K. Cilj napadača je vratiti dio ili cijeli ključ K.

Prije svega, napadač ispituje šifru i pronalazi tzv statistički analog, tj. jednadžba sljedećeg oblika, koja vrijedi s vjerojatnošću P ≠ 1/2 za proizvoljan par javnog/privatnog teksta i fiksni ključ:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
gdje su P n, C n, K n n-ti bitovi teksta, šifrirani tekst i ključ.
Nakon što se pronađe takva jednadžba, napadač može oporaviti 1 bit ključne informacije pomoću sljedećeg algoritma

Algoritam 1
Neka je T broj tekstova za koje lijeva strana jednadžba (1) jednaka 0, tada
Ako je T>N/2, gdje je N broj poznatih otvorenih tekstova.
Pretpostavimo da je K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (kada je P>1/2) ili 1 (kada je P<1/2).
Inače
Pretpostavimo da je K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (kada je P>1/2) ili 0 (kada je P<1/2).
Očito je da uspjeh algoritma izravno ovisi o vrijednosti |P-1/2| i na broj dostupnih parova otvorenog/zatvorenog teksta N. Što se vjerojatnost P jednakosti (1) više razlikuje od 1/2, to je manji broj čistih tekstova N potreban za napad.

Postoje dva problema koja je potrebno riješiti da bi napad bio uspješan:

• Kako pronaći efektivnu jednadžbu oblika (1).
• Kako koristiti ovu jednadžbu da dobijete više od jednog bita informacija o ključu.

Opis DES-a

Dakle, DES je blok šifra temeljena na Feistelovoj mreži. Šifra ima veličinu bloka od 64 bita i veličinu ključa od 56 bita. Razmotrimo shemu šifriranja DES algoritma.

Kao što se može vidjeti sa slike, prilikom šifriranja teksta izvode se sljedeće operacije:

1. Početna permutacija bita. U ovoj fazi, bitovi ulaznog bloka se miješaju određenim redoslijedom.
2. Nakon toga, izmiješani bitovi se dijele na dvije polovice, koje se šalju na ulaz Feistelove funkcije. Za standardni DES, Feistelova mreža uključuje 16 rundi, ali postoje i druge varijante algoritma.
3. Dva bloka dobivena u zadnjem krugu transformacije se kombiniraju i još jedna permutacija se izvodi na rezultirajućem bloku.

U svakom krugu Feistelove mreže, najmanje značajna 32 bita poruke prolaze kroz funkciju f:

Pogledajmo operacije koje se izvode u ovoj fazi:

1. Ulazni blok prolazi kroz funkciju proširenja E, koja pretvara 32-bitni blok u 48-bitni blok.
2. Rezultirajući blok dodaje se okruglom ključu K i .
3. Rezultat prethodnog koraka podijeljen je u 8 blokova od po 6 bitova.
4. Svaki od primljenih blokova B i prolazi kroz supstitucijsku funkciju S-Box i, koja zamjenjuje 6-bitni niz s 4-bitnim blokom.
5. Rezultirajući 32-bitni blok prolazi kroz permutaciju P i vraća se kao rezultat funkcije f.

S gledišta kriptoanalize za nas su od najvećeg interesa S blokovi, dizajnirani da sakriju vezu između ulaznih i izlaznih podataka funkcije f. Da bismo uspješno napali DES, prvo ćemo konstruirati statističke analogije za svaki od S-kutija, a zatim ih proširiti na cijelu šifru.

S blok analiza

Razmotrimo kako možemo pronaći statistički analog S-kutije u općem slučaju.

Za S-kutiju S a, 1 ≤ α ≤ 63 i 1 ≤ β ≤ 15, vrijednost NS a (α, β) opisuje koliko je puta od 64 moguća XOR ulazna bita S a superponiranih na α bitove jednako izlazni bitovi XOR superponirani na α bitove β, tj.:
gdje je simbol logično I.
Vrijednosti α i β za koje se NS a (α, β) najviše razlikuje od 32 opisuju najučinkovitiji statistički analog S-kutije S a .

Najučinkovitiji analog je pronađen u 5. S-kutiji DES šifre za α = 16 i β = 15 NS 5 (16, 15) = 12. To znači da vrijedi sljedeća jednadžba: Z=Y ⊕ Y ⊕ Y ⊕ Y, gdje je Z ulazni niz S-kutije, a Y izlazni niz.
Ili uzimajući u obzir činjenicu da se u DES algoritmu prije ulaska u S-box podaci zbrajaju modulo 2 okruglim ključem, tj. Z = X ⊕ K dobivamo
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, gdje su X i Y ulazni i izlazni podaci funkcije f bez uzimanja u obzir permutacija.
Rezultirajuća jednadžba se izvodi u svim rundama DES algoritma s istom vjerojatnošću P=12/64.
Sljedeća tablica prikazuje popis učinkovitih, tj. koji imaju najveće odstupanje od P=1/2, statistički analozi za svaki s-blok DES algoritma.

Konstruiranje statističkih analoga za više rundi DES-a

Pronađimo sličan izraz koristeći posljednju rundu. Ovaj put imamo jednadžbu
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Jer
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
shvaćamo to
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4) s vjerojatnošću 12/64.

Izjednačavanjem desnih strana jednadžbi (3) i (4) dobivamo
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 s vjerojatnošću (12/64) 2 +(1-12/64) 2.
Uzimajući u obzir činjenicu da je X(1) = PR i X(3) = CR, dobivamo statistički analog
SL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
koji se izvršava s vjerojatnošću (12/64) 2 + (1-12/64) 2 =0,7.
Gore opisani statistički analog može se grafički prikazati na sljedeći način (bitovi na slici su numerirani s desna na lijevo i počevši od nule):

Svi bitovi na lijevoj strani jednadžbe poznati su napadaču, tako da može primijeniti Algoritam 1 i saznati vrijednost K1 ⊕ K3. Pokažimo kako, koristeći ovaj statistički analog, možete otvoriti ne 1, već 12 bitova ključa za šifriranje K.

Napad na DES s poznatim otvorenim tekstom

Gore smo već utvrdili da na vrijednost F1(PR, K1) utječu ulazni bitovi 5. S-kutije, naime ključni bitovi K1 i bitovi PR bloka. Pokažimo kako, imajući samo skup otvorenih/zatvorenih tekstova, možete vratiti vrijednost K1. Da bismo to učinili, koristit ćemo algoritam 2.

Algoritam 2
Neka N bude broj otvorenih/zatvorenih tekstualnih parova poznatih prije napada. Zatim da biste otvorili ključ morate poduzeti sljedeće korake.
Za (i=0; i<64; i++) do
{
Za (j=0; j {
if(SL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) tada
T i = T i +1
}
}
Kao vjerojatni niz K1 uzima se vrijednost i tako da je izraz |T i -N/2| ima najveću vrijednost.

S obzirom na dovoljan broj poznatih otvorenih tekstova, algoritam će imati veliku vjerojatnost vraćanja točne vrijednosti šest bitova prvog kruga podključa K1. To se objašnjava činjenicom da ako varijabla i nije jednaka K1, tada će vrijednost funkcije F1(PR j, K) biti slučajna i broj jednadžbi za takvu vrijednost i za koju je lijeva strana jednaka nuli će težiti N/2. Ako je podključ točno pogoden, lijeva će strana biti jednaka fiksnom bitu K3 s vjerojatnošću 12/64. one. doći će do značajnog odstupanja od N/2.

Nakon što ste primili 6 bitova potključa K1, na sličan način možete otvoriti 6 bitova potključa K3. Sve što trebate učiniti je zamijeniti C s P i K1 s K3 u jednadžbi (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algoritam 2 će vratiti ispravnu K3 vrijednost jer je proces dešifriranja DES algoritma identičan procesu šifriranja, samo je slijed ključeva obrnut. Tako se u prvom krugu dešifriranja koristi ključ K3, au zadnjem krugu ključ K1.

Primivši 6 bitova potključeva K1 i K3, napadač vraća 12 bitova zajedničkog ključa šifre K, jer okrugli ključevi su uobičajena permutacija ključa K. ​​Broj otvorenih tekstova potrebnih za uspješan napad ovisi o vjerojatnosti statističkog analoga. Za probijanje 12-bitnog 3-kružnog DES ključa dovoljno je 100 parova javnog/privatnog teksta. Za otvaranje 12 bita DES ključa od 16 krugova bit će potrebno oko 244 para tekstova. Preostala 44 bita ključa otvaraju se normalnom grubom silom.

Napomena: Jedan od najpoznatijih kriptografskih sustava s privatnim ključem je DES – Data Encryption Standard. Ovaj sustav je prvi dobio status državnog standarda u području šifriranja podataka. Iako je stari američki standard DES sada izgubio svoj službeni status, ovaj algoritam i dalje zaslužuje pozornost pri proučavanju kriptografije. Ovo predavanje također objašnjava što je dvostruki DES, napad susreta u sredini, i kako ga ublažiti. Ovo predavanje također ukratko govori o novom američkom standardu za blokovne šifre, Rijndaelov algoritam.

Svrha predavanja: upoznati studenta s osnovnim informacijama o DES algoritmu šifriranja.

Osnove

Jedan od najpoznatijih kriptografskih sustava s privatnim ključem je DES – Standard šifriranja podataka. Ovaj sustav je prvi dobio status državnog standarda u području šifriranja podataka. Razvili su ga IBM-ovi stručnjaci i stupio je na snagu u SAD-u 1977. Algoritam DESširoko se koristi za pohranu i prijenos podataka između različitih računalnih sustava; u poštanskim sustavima, sustavima elektroničkog crtanja i elektroničkoj razmjeni komercijalne informacije. Standard DES je implementiran iu softveru iu hardveru. Poduzeća iz različitih zemalja pokrenula su masovnu proizvodnju digitalnih uređaja DES za šifriranje podataka. Svi uređaji prošli su obveznu certifikaciju za usklađenost sa standardom.

Unatoč činjenici da ovaj sustav već neko vrijeme nema status državnog standarda, još uvijek se široko koristi i zaslužuje pozornost pri proučavanju blok šifara s privatnim ključem.

Duljina ključa u algoritmu DES je 56 bita. Upravo s ovom činjenicom glavna je polemika u vezi s sposobnošću da DES oduprijeti se raznim napadima. Kao što znate, bilo koja blok šifra s privatnim ključem može se probiti isprobavanjem svih mogućih kombinacija ključeva. Uz duljinu ključa od 56 bita, moguće je 2 56 različitih ključeva. Ako računalo pretražuje 1.000.000 ključeva u jednoj sekundi (što je otprilike jednako 2 20), tada će mu trebati 2 36 sekundi ili nešto više od dvije tisuće godina da pretraži svih 2 56 ključeva, što je, naravno, neprihvatljivo za napadači.

Međutim, mogući su skuplji i brži računalni sustavi od osobno računalo. Na primjer, ako je moguće kombinirati milijun procesora za paralelne izračune, tada se maksimalno vrijeme odabira ključa smanjuje na približno 18 sati. Ovo vrijeme nije predugo, a kriptoanalitičar opremljen tako skupom opremom može lako razbiti DES-kriptirane podatke u razumnom vremenskom roku.

Pritom se može primijetiti da sustav DES Može se koristiti u malim do srednje velikim aplikacijama za šifriranje podataka male vrijednosti. Za šifriranje podataka od nacionalne važnosti ili značajne komercijalne vrijednosti, sustav DES trenutno se naravno ne bi trebao koristiti. Godine 2001., nakon posebno raspisanog natječaja, u SAD-u je usvojen novi standard blok šifriranja tzv. AES (napredni standard šifriranja), koji se temeljio na šifri Rijndael, koji su razvili belgijski stručnjaci. O ovoj šifri raspravlja se na kraju predavanja.

Osnovni parametri DES: veličina bloka 64 bita, duljina ključa 56 bita, broj krugova – 16. DES je klasična Feishtelova mreža s dvije grane. Algoritam pretvara 64-bitni ulazni blok podataka u 64-bitni izlazni blok tijekom nekoliko krugova. Standard DES izgrađen na kombiniranoj uporabi permutacije, supstitucije i gama. Šifrirani podaci moraju biti u binarnom obliku.

Šifriranje

Opća struktura DES prikazano na sl.

1. 4.1. Proces šifriranja svakog 64-bitnog bloka neobrađenih podataka može se podijeliti u tri faze:
2. početna priprema bloka podataka;
3. 16 krugova "glavnog ciklusa";

završna obrada bloka podataka. U prvoj fazi se provodi početna permutacija

64-bitni izvorni blok teksta, tijekom 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 pretvorbu ključa. Zatim se podaci razmjenjuju između lijeve i desne grane bloka. Ovo se ponavlja u ciklusu 16 puta.

Konačno, treća faza preuređuje rezultat dobiven nakon šesnaest koraka glavne petlje. Ova permutacija je inverzna početnoj permutaciji.

Riža. 4.1. DES.

Pogledajmo pobliže sve faze kriptografske pretvorbe prema standardu

Istovremeno s početnom permutacijom podatkovnog bloka, izvodi se početna permutacija 56 bita ključa. Od sl.

4.1. Može se vidjeti da se u svakoj od rundi koristi odgovarajući 48-bitni djelomični ključ K i. Ključevi K i se dobivaju pomoću specifičnog algoritma, koristeći svaki bit početnog ključa nekoliko puta. U svakom krugu, 56-bitni ključ se dijeli na dvije 28-bitne polovice. Polovice se zatim pomiču ulijevo za jedan ili dva bita, ovisno o okruglom broju. Nakon pomaka, 48 od 56 bita se odabire na određeni način. Budući da ovo ne samo da odabire podskup bitova, već i mijenja njihov redoslijed, ova se operacija naziva "kompresijska permutacija". Njegov rezultat je skup od 48 bita. U prosjeku, svaki bit izvornog 56-bitnog ključa koristi se u 14 od 16 podključeva, iako se svi bitovi ne koriste isti broj puta.

Riža. 4.2.

Lijeva i desna grana svake srednje vrijednosti tretiraju se kao zasebne 32-bitne vrijednosti, označene L i R .

Prvo, desna strana bloka Ri je proširena na 48 bita pomoću tablice koja specificira permutaciju plus proširenje za 16 bita. Ova operacija usklađuje veličinu desne polovice s veličinom ključa za izvođenje operacije XOR. Osim toga, izvođenjem ove operacije brže se povećava ovisnost svih bitova rezultata o bitovima izvornih podataka i ključu (ovo se naziva "efekt lavine"). Što je jači učinak lavine pri korištenju jednog ili drugog algoritma za šifriranje, to bolje. Nakon izvođenja permutacije proširenja, rezultirajuća 48-bitna vrijednost je XOR s 48-bitnim podključem K i . Zatim se dobivena 48-bitna vrijednost dovodi na ulaz supstitucijskog bloka S (od engleskog. - Zamjena zamjena), rezultat DES, vjerojatno, samo iskusni programeri to mogu učiniti. Neke poteškoće nastaju prilikom implementacije softvera, na primjer, početna permutacija ili permutacija s proširenjem. Te su poteškoće povezane s onim što je prvotno planirano da se provede DES samo hardver. Sve operacije korištene u standardu lako izvode hardverske jedinice i nema poteškoća u implementaciji. Međutim, neko vrijeme nakon objavljivanja standarda, programeri softvera odlučili su ne stajati po strani i također preuzeti stvaranje sustava šifriranja. U budućnosti DES implementiran je i hardverski i softverski.

Algoritam DES

Glavne prednosti DES algoritma:

· koristi se samo jedan ključ duljine 56 bita;

· nakon što ste šifrirali poruku koristeći jedan paket, možete koristiti bilo koji drugi za dešifriranje;

· relativna jednostavnost algoritma osigurava veliku brzinu obrade informacija;

· dovoljno visoka stabilnost algoritma.

DES šifrira 64-bitne blokove podataka pomoću 56-bitnog ključa. Dešifriranje u DES-u obrnuta je operacija od enkripcije i izvodi se ponavljanjem operacija šifriranja obrnutim redoslijedom (unatoč prividnoj očitosti, to se ne radi uvijek. Kasnije ćemo pogledati šifre u kojima se enkripcija i dešifriranje izvode pomoću različitih algoritama) .

Proces enkripcije sastoji se od početne permutacije bitova 64-bitnog bloka, šesnaest ciklusa enkripcije i, konačno, obrnute permutacije bitova (slika 1).

Treba odmah napomenuti da su SVE tablice dane u ovom članku STANDARDNE, i stoga ih treba uključiti u vašu implementaciju algoritma nepromijenjene. Sve permutacije i kodove u tablicama programeri su odabrali na takav način da odabirom ključa maksimalno otežaju proces dešifriranja. Struktura DES algoritma prikazana je na slici 2.

sl.2. Struktura DES algoritma za šifriranje

Neka se sljedeći 8-bajtni blok T pročita iz datoteke, koja se transformira korištenjem početne permutacijske matrice IP (tablica 1) na sljedeći način: bit 58 bloka T postaje bit 1, bit 50 postaje bit 2, itd., što će dati rezultat: T(0) = IP(T).

Rezultirajuća sekvenca bitova T(0) podijeljena je u dvije sekvence od po 32 bita: L(0) - lijevi ili viši bitovi, R(0) - desni ili niži bitovi.

Tablica 1: Matrica početne permutacije IP-a

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 provodi enkripcija koja se sastoji od 16 ponavljanja. Rezultat i-te iteracije opisuje se sljedećim formulama:

R(i) = L(i-1) xili 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), dobiven u (i-1) iteraciji, i 48-bitni ključ K(i), koji je rezultat pretvorbe 64-bitnog ključa K. U nastavku je detaljno opisana funkcija šifriranja i algoritam za dobivanje ključeva K(i).

U 16. iteraciji dobivaju se sekvence R(16) i L(16) (bez permutacije) koje se spajaju u 64-bitnu sekvencu R(16)L(16).

Tada se položaji bitova ovog niza preuređuju u skladu s matricom IP -1 (tablica 2).

Tablica 2: Inverzna permutacijska matrica 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

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 IP -1 matrice je 8, a vrijednost 8. elementa IP matrice jednaka je 2, itd.

Proces dešifriranja podataka inverzan je procesu enkripcije. Svi koraci se moraju izvesti obrnutim redoslijedom. To znači da se dešifrirani podaci najprije preuređuju prema IP-1 matrici, a zatim se na nizu bitova R(16)L(16) izvode iste radnje kao u procesu enkripcije, 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 dobivaju 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 takve permutacije je originalni 64-bitni niz.

Sada razmotrite funkciju šifriranja f(R(i-1),K(i)). Shematski je prikazano na sl. 3.

sl.3. Izračun funkcije f(R(i-1), K(i))

Za izračun vrijednosti funkcije f koriste se sljedeće matrične funkcije:

E - proširenje 32-bitne sekvence u 48-bitnu,

S1, S2, ..., S8 - pretvaranje 6-bitnog bloka u 4-bitni,

P - permutacija bitova u nizu od 32 bita.

Funkcija ekspanzije E definirana je u tablici 3. Prema ovoj tablici, prva 3 bita od E(R(i-1)) su bitovi 32, 1 i 2, a posljednji su 31, 32 i 1.

Tablica 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 modulo 2 (xor operacija) s 48-bitnim ključem K(i). Rezultirajuća 48-bitna sekvenca podijeljena je 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 tablici 4.

Tablica 4

Na tablicu 4. potrebno je dodatno pojašnjenje. Neka je ulaz matrične funkcije Sj 6-bitni blok B(j) = b1b2b3b4b5b6, tada dvobitni broj b1b6 označava broj retka matrice, a b2b3b4b5 broj stupca. Rezultat Sj(B(j)) bit će 4-bitni element smješten na sjecištu navedenog retka i stupca.

Na primjer, B(1)=011011. Tada se S1(B(1)) nalazi na sjecištu retka 1 i stupca 13. U stupcu 13 retka 1 vrijednost je 5. To znači S1(011011)=0101.

Primjenom operacije odabira na svaki od 6-bitnih blokova B(1), B(2), ..., B(8), dobivamo 32-bitni niz S1(B(1))S2(B(2) ))S3( B(3))...S8(B(8)).

Konačno, da bi se dobio rezultat funkcije šifriranja, bitovi ovog niza moraju se preurediti. U tu svrhu koristi se permutacijska funkcija P (tablica 5). U ulaznoj sekvenci, bitovi se preuređuju tako da bit 16 postaje bit 1, bit 7 postaje bit 2, i tako dalje.

Tablica 5: Funkcija permutacije P

dakle,

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

Za potpuni opis algoritma za šifriranje podataka ostaje još prikazati algoritam za dobivanje 48-bitnih ključeva K(i), i=1...16. U 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 s osam bitova parnosti koji se nalaze na pozicijama 8,16,24,32,40,48, 56. 64.

Za uklanjanje kontrolnih bitova i preuređivanje ostalih koristi se funkcija G početne pripreme ključa (tablica 6).

Tablica 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) podijeljen je u dva 28-bitna bloka C(0) i D(0), a C(0) će se 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 definiranja C(0) i D(0), C(i) i D(i), i= 1...16, određuju se rekurzivno. Da biste to učinili, primijenite ciklički pomak ulijevo za jedan ili dva bita, ovisno o broju iteracije, kao što je prikazano u tablici 7.

Tablica 7

Tablica pomaka za izračun ključa

Rezultirajuća vrijednost ponovno se "miješa" u skladu s matricom H (tablica 8).

Tablica 8: Ključna matrica završetka 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 niza C(i)D(i). Stoga:

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

Blok dijagram algoritma za izračun ključa prikazan je na slici 4.

sl.4. Blok dijagram algoritma za izračunavanje ključa K(i)

Vraćanje izvornog teksta provodi se pomoću ovog algoritma, ali prvo koristite ključ

K(15), zatim K(14) i tako dalje. Sada biste trebali shvatiti zašto autor ustrajno preporučuje korištenje danih matrica. Ako krenete lutati, mogli biste završiti s vrlo tajnim kodom, ali ga nećete moći sami razbiti!

Načini rada DES algoritma

Kako bi se u najvećoj mjeri zadovoljili svi zahtjevi za komercijalne sustave šifriranja, implementirano je nekoliko načina rada DES algoritma. Načini koji se najčešće koriste su:

· elektronički šifrarnik (Electronic Codebook) - ECB;

· lanac digitalnih blokova (Cipher Block Chaining) - CBC;

· digitalna povratna veza (Cipher Feedback) - CFB;

· vanjska povratna sprega (Output Feedback) - OFB.

U ovom načinu, izvorna datoteka M podijeljena je u 64-bitne blokove (svaki po 8 bajtova): M = M(1)M(2)...M(n). Svaki od ovih blokova je neovisno šifriran korištenjem istog ključa za šifriranje (slika 5). Glavna prednost ovog algoritma je njegova jednostavnost implementacije. Nedostatak je što je relativno slab protiv vještih kriptoanalitičara.

Standard DES dizajniran je za zaštitu od neovlaštenog pristupa osjetljivim, ali neklasificiranim informacijama u vladinim i komercijalnim organizacijama SAD-a. Algoritam na kojem se temelji standard brzo se proširio, a već 1980. odobrio ga je američki Nacionalni institut za standarde i tehnologiju. Od ovog trenutka, DES postaje standard ne samo u imenu, već iu stvari. Pojavljuju se softver i specijalizirana mikroračunala koji su dizajnirani za šifriranje i dekriptiranje informacija u podatkovnim mrežama.

Do danas je DES najčešći algoritam koji se koristi u komercijalnim informacijskim sigurnosnim sustavima. Štoviše, implementacija DES algoritma u takvim sustavima postaje znak dobre forme.

Glavne prednosti DES algoritma:

· koristi se samo jedan ključ duljine 56 bita;

· nakon što ste šifrirali poruku koristeći jedan paket, možete koristiti bilo koji drugi za dešifriranje;

· relativna jednostavnost algoritma osigurava veliku brzinu obrade informacija;

· dovoljno visoka stabilnost algoritma.

DES šifrira 64-bitne blokove podataka pomoću 56-bitnog ključa. Dešifriranje u DES-u obrnuta je operacija od enkripcije i izvodi se ponavljanjem operacija šifriranja obrnutim redoslijedom (unatoč prividnoj očitosti, to se ne radi uvijek. Kasnije ćemo pogledati šifre u kojima se enkripcija i dešifriranje izvode pomoću različitih algoritama) .

Proces enkripcije sastoji se od početne permutacije bitova 64-bitnog bloka, šesnaest ciklusa enkripcije i na kraju obrnute permutacije bitova (Slika 1).

Treba odmah napomenuti da su SVE tablice dane u ovom članku STANDARDNE, i stoga ih treba uključiti u vašu implementaciju algoritma nepromijenjene. Sve permutacije i kodove u tablicama programeri su odabrali na takav način da odabirom ključa maksimalno otežaju proces dešifriranja. Struktura DES algoritma prikazana je na slici. 2.

Riža. 2.

Neka se sljedeći 8-bajtni blok T pročita iz datoteke, koja se transformira korištenjem početne permutacijske matrice IP (tablica 1) na sljedeći način: bit 58 bloka T postaje bit 1, bit 50 postaje bit 2, itd., što će rezultat je: T(0) = IP(T).

Rezultirajuća sekvenca bitova T(0) podijeljena je u dvije sekvence od po 32 bita: L(0) - lijevi ili viši bitovi, R(0) - desni ili niži bitovi.

Tablica 1: Matrica početne permutacije IP-a

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 provodi enkripcija koja se sastoji od 16 ponavljanja. Rezultat i-te iteracije opisuje se sljedećim formulama:

R(i) = L (i-1) xili 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), dobiven u (i-1) iteraciji, i 48-bitni ključ K(i), koji je rezultat pretvorbe 64-bitnog ključa K. U nastavku je detaljno opisana funkcija šifriranja i algoritam za dobivanje ključeva K(i).

U 16. iteraciji dobivaju se sekvence R(16) i L(16) (bez permutacije) koje se spajaju u 64-bitnu sekvencu R(16) L(16).

Zatim se položaji bitova ovog niza preuređuju u skladu s matricom IP -1 (Tablica 2).

Tablica 2: Inverzna permutacijska matrica 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

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 IP -1 matrice je 8, a vrijednost 8. elementa IP matrice jednaka je 2, itd.

Proces dešifriranja podataka inverzan je procesu enkripcije. Svi koraci se moraju izvesti obrnutim redoslijedom. To znači da se dešifrirani podaci najprije preuređuju prema IP-1 matrici, a zatim se na nizu bitova R(16) L(16) izvode iste radnje kao u procesu enkripcije, 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 dobivaju 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 takve permutacije je originalni 64-bitni niz.

Sada razmotrite funkciju šifriranja f (R(i-1), K(i)). Shematski je prikazano na sl. 3.

Riža. 3.

Za izračun vrijednosti funkcije f koriste se sljedeće matrične funkcije:

E - proširenje 32-bitne sekvence u 48-bitnu,

S1, S2,…, S8 - pretvaranje 6-bitnog bloka u 4-bitni,

P - permutacija bitova u nizu od 32 bita.

Funkcija proširenja E određena je tablicom. 3. Prema ovoj tablici, prva 3 bita od E (R(i-1)) su bitovi 32, 1 i 2, a posljednji su 31, 32 i 1.

Tablica 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 modulo 2 (xor operacija) s 48-bitnim ključem K(i). Rezultirajuća 48-bitna sekvenca podijeljena je 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 tablici. 4.

Tablica 4

Za stol 4. Potrebno je dodatno pojašnjenje. Neka je ulaz matrične funkcije Sj 6-bitni blok B(j) = b1b2b3b4b5b6, tada dvobitni broj b1b6 označava broj retka matrice, a b2b3b4b5 broj stupca. Rezultat Sj (B(j)) bit će 4-bitni element smješten na sjecištu navedenog retka i stupca.

Na primjer, B(1)=011011. Tada se S1 (B(1)) nalazi na sjecištu reda 1 i stupca 13. U stupcu 13 reda 1 vrijednost je 5. To znači S1 (011011)=0101.

Primjenom operacije odabira na svaki od 6-bitnih blokova B(1), B(2),…, B(8), dobivamo 32-bitnu sekvencu S1 (B(1)) S2 (B(2)) S3 (B(3))... S8 (B(8)).

Konačno, da bi se dobio rezultat funkcije šifriranja, bitovi ovog niza moraju se preurediti. U tu svrhu koristi se permutacijska funkcija P (tablica 5). U ulaznoj sekvenci, bitovi se preuređuju tako da bit 16 postaje bit 1, bit 7 postaje bit 2 itd.

Tablica 5: Permutacijska funkcija P

dakle,

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

Za potpuni opis algoritma za šifriranje podataka ostaje još prikazati algoritam za dobivanje 48-bitnih ključeva K(i), i=1...16. U 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 s osam bitova parnosti koji se nalaze na pozicijama 8,16,24,32,40,48, 56. 64.

Za uklanjanje kontrolnih bitova i preuređivanje ostalih koristi se funkcija G početne pripreme ključa (Tablica 6).

Tablica 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) podijeljen je u dva 28-bitna bloka C(0) i D(0), a C(0) će se 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 određivanja C(0) i D(0), C(i) i D(i), i=1… 16, određuju se rekurzivno. Da biste to učinili, primijenite ciklički pomak ulijevo za jedan ili dva bita, ovisno o broju iteracije, kao što je prikazano u tablici. 7.

Tablica 7. Tablica pomaka za izračun ključa

Rezultirajuća vrijednost ponovno se "miješa" u skladu s matricom H (tablica 8).

Tablica 8: Ključna matrica završetka 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) sastojat će se od bitova 14, 17,…, 29, 32 niza C(i) D(i). Stoga:

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

Blok dijagram algoritma za izračun ključa prikazan je na sl. 4.

Riža. 4.

Vraćanje izvornog teksta se provodi pomoću ovog algoritma, ali prvo koristite ključ K(15), zatim K(14) i tako dalje. Sada biste trebali shvatiti zašto autor ustrajno preporučuje korištenje danih matrica. Ako krenete lutati, mogli biste završiti s vrlo tajnim kodom, ali ga nećete moći sami razbiti!

Jednostavna konverzija između dijelova bloka. Budući da se konverzija izvodi blok po blok, poseban korak zahtijeva dijeljenje izvornih podataka u blokove potrebne veličine. Štoviše, bez obzira na format izvornih podataka, bili to tekstualni dokumenti, slike ili druge datoteke, oni se moraju interpretirati u binarni oblik i tek onda podijeliti u blokove. Sve navedeno može se obaviti softverski ili hardverski.

Transformacije Feistel mreže

Ovo je transformacija preko vektora (blokova) koji predstavljaju lijevu i desnu polovicu posmačnog registra. DES algoritam koristi prednju Feistelovu mrežnu transformaciju u enkripciji (vidi sliku 1) i obrnutu Feistelovu mrežnu transformaciju u dešifriranju (vidi sliku 2).

Shema šifriranja DES algoritma

Izvorni tekst je 64-bitni blok.
Šifrirani tekst je 64-bitni blok.

Proces šifriranja sastoji se od početne permutacije, 16 ciklusa šifriranja i konačne permutacije.
Pogledajmo detaljan dijagram DES algoritma:
L i R i =1,2\ldots.lijeva i desna polovica 64-bitnog bloka L i R i
k i - 48 bitni ključevi
f - funkcija šifriranja
IP - početna permutacija
IP -1 - konačna permutacija. Prema tablici, prva 3 bita rezultirajućeg bloka IP(T) nakon početne permutacije IP-a su bitovi 58, 50, 42 ulaznog bloka T, a njegova zadnja 3 bita su bitovi 23, 15, 7 bloka T. ulazni blok. Zatim, 64-bitni IP(T) blok sudjeluje u 16 ciklusa Feistelove transformacije.

16 ciklusa Feistelove transformacije:

Podijelite IP(T) na dva dijela L 0 ,R 0 , gdje su L 0 ,R 0 32 bita najveće važnosti i 32 bita najmanje važnosti bloka T0 IP(T)= L 0 R 0 .

Neka je T i -1 = L i -1 R i -1 rezultat (i-1) iteracije, tada se određuje rezultat i-te iteracije T i = L i R i:

L i = R i - 1 Lijeva polovica od L i jednaka je desnoj polovici prethodnog vektora L i - 1 R i - 1 . A desna polovica od R i je zbrajanje bita od L i - 1 i f(R i - 1, k i) modulo 2.

U Feistelovoj transformaciji od 16 ciklusa, funkcija f igra ulogu enkripcije. Pogledajmo detaljnije funkciju f.

Argumenti funkcije f su 32-bitni vektor R i - 1 , 48-bitni ključ k i , koji su rezultat pretvorbe 56-bitnog izvornog ključa šifre k.

Za izračun funkcije f koristi se funkcija ekspanzije E, transformacija S koja se sastoji od 8 S-box transformacija i permutacija P.

Funkcija E proširuje 32-bitni vektor R i - 1 na 48-bitni vektor E(R i - 1) dupliciranjem nekih bitova iz R i - 1, dok redoslijed bitova vektora E(R i - 1 ) prikazan je u tablici 2. Prva tri bita vektora E(R i - 1) su bitovi 32, 1, 2 vektora R i -1. Tablica 2 pokazuje da su bitovi 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 duplicirani. Posljednja 3 bita vektora E(Ri - 1) su bitovi 31, 32, 1 vektora Ri - 1. Blok E(R i -1) dobiven nakon preuređenja dodaje se modulo 2 s ključevima k i i zatim prikazuje u obliku osam uzastopnih blokova B 1 , B 2 ,...B 8 .
E(R i - 1) = B 1 B 2 ...B 8
Svaki B j je 6-bitni blok. Zatim se svaki od blokova B j transformira u 4-bitni blok B" j pomoću transformacija S j. Transformacije S j su određene tablicom 3. Pretpostavimo da je B 3 = 101111 i želimo pronaći B" 3. Prvi i zadnji bit B 3 su binarna reprezentacija broja a, 0. Vrijednost funkcije f(R i - 1,k i) (32 bita) dobiva se permutacijom P primijenjenom na 32-bitni blok B " 1 B" 2 ...B" 8. Permutacija P je dana u tablici 4.
f(R i - 1 ,k i) = P(B" 1 B" 2 ...B" 8)
Prema tablici 4, prva četiri bita rezultirajućeg vektora nakon djelovanja funkcije f su bitovi 16, 7, 20, 21 vektora B" 1 B" 2 ...B" 8

Generiranje ključeva k i .
Ključevi k i se na ovaj način dobivaju iz početnog ključa k (56 bita = 7 bajtova ili 7 ASCII znakova). Osam bitova, koji se nalaze na pozicijama 8, 16, 24, 32, 40, 48, 56, 64, dodaje se ključu k tako da svaki bajt sadrži neparan broj jedinica. Ovo se koristi za otkrivanje grešaka u razmjeni ključeva i pohrani. Zatim se vrši permutacija za prošireni ključ (osim za dodane bitove 8, 16, 24, 32, 40, 48, 56, 64). Ova je permutacija definirana kao u tablici 5.

Ova permutacija definirana je s dva bloka C 0 i D 0 od po 28 bita. Prva 3 bita od C0 su bitovi 57, 49, 41 proširenog ključa. A prva tri bita od D 0 su bitovi 63, 55, 47 proširenog ključa. C i ,D i i=1,2,3…dobivaju se iz C i - 1 ,D i - 1 pomoću jednog ili dva ciklička pomaka ulijevo prema tablici 6.

Ključ k i , i=1,…16 sastoji se od 48 bitova odabranih između bitova vektora C i D i (56 bitova) prema tablici 7. Prvi i drugi bit k i su bitovi 14, 17 vektora C i D i

Konačna permutacija IP - 1 djeluje na T 16 i koristi se za vraćanje položaja. To je inverzna IP permutacija. Konačna permutacija određena je tablicom 8.
Načini korištenja DES-a DES se može koristiti u četiri načina.

Način elektroničke kodne knjige (ECB): normalna uporaba DES-a kao blok šifre (vidi sliku 7).

Način ulančavanja blokova (CBC - Cipher Block Chaining) (vidi sl. 8). Svaki sljedeći blok C i i>=1, prije enkripcije, dodaje se modulo 2 sa sljedećim blokom otvorenog teksta M i + 1. Vektor C 0 je početni vektor, mijenja se svakodnevno i čuva se u tajnosti.

Cipher Feedback mod (CFB - Cipher Feedback) (vidi sl. 9). U CFB modu, generira se blok “gama” Z 0 ,Z 1 ,...Z i = DESk(C i - 1) . Početni vektor C 0 se drži u tajnosti.

Način izlazne povratne veze (OFB - Output Feed Back) (vidi sl. 10). U OFB modu, generira se blok “gama” Z 0 ,Z 1 ,... , i>=1