Data Encryption Standard

**DES**
	; DES Fejstelova mreža
	Opšte
Projektant(i)	IBM
Datum objave	1977. (standardizovan u januaru 1979.)
Izveden od	Lucifer
Naslednici	Trostruki DES, G-DES, DES-X, LOKI89, ICE
	Detalji šifre
Veličina ključa	56 bita
Veličina bloka	64 bita
Struktura	Fejstelova mreža
Runde	16
	Najbolja javna kriptoanaliza
	DES se sada smatra nesigurnim zbog mogućeg brutalnog napada. Od 2008, najbolji analitički napad je linearna kriptoanaliza koji zahteva 243 poznata otvorena teksta i ima vreme složenosti od 239–43.

DES (engl. Data Encryption Standard) algoritam je najviše korišćen algoritam za kriptovanje na svetu. Dugo godina, DES je među ljudima bio sinonim za sigurno šifrovanje. Uprkos naporu Electronic Frontier fondacije u pravljenju mašine za razbijanje DES-šifrovanih poruka, vredne 250.000 američkih dolara.

Istorijat

Dana 15. maja 1973. god. američka nacionalna uprava za standarde (engl. NBS - National Bureau of Standards) izdala je obaveštenje u kojem traže propozicije za kriptografske algoritme radi zaštite podataka tokom prenosa i skladištenja. NBS je čekao na reakciju, i ona je stigla 6. avgusta 1974, tri dana pre Niksonove ostavke, kada je IBM podneo svog kandidata pod imenom LUCIFER. Posle procenjivanja algoritma, uz pomoć američke vladine ustanove zadužene za sigurnost (NSA), NBS je usvojio modifikaciju LUCIFER algoritma jula 1977. i nazvao ga DES. Najozbiljnija primedba se odnosila na veličinu ključa (128 za LUCIFER, 56 bita za DES). DES je brzo prihvaćen u nedigitalnim medijima, kao u javnim telefonskim linijama. Npr. međunarodna udruženja koja su se bavila patentima za mirise i parfeme su slali njihove vazne formule, kriptovane DES-om, preko telefona. U međuvremenu, bankarska industrija, koja ja najveći korisnik enkripcije izvan vlade, je prihvatila DES kao standard za njihove transakcije 1980. od ANSI X3.92. 1998. godine, pod vodjstvom Džon Gilmor, EFF tim je potrošio 250.000 dolara da napravi mašinu koja bi provalila ceo DES ključ u proseku za oko 4,5 dana. 17. jula 1998, objavili su da su odredili 56-bitni ključ za 56 sati. Ta mašina je nazvana Deep Crack, i sadržala je 27 ploča sa po 64 čipa, i bila sposobna da testira 90 biliona ključeva u sekundi.

Opis

DES predstavlja kriptovanje koje transofmiše 64 bitne blokove podataka u 64 bitne kriptovane blokove podataka. Dužina ključa kriptovanja je 64 bita, od kojih 8 otpada na proveru pariteta, tako da je efektivna dužina ključa 56 bita.

DES kriptovanje i dekriptovanje se sprovodi u nekoliko koraka, kako je to prikazano na slici. Prvo se bitovi ulaznog bloka dužine 64 bita permutuju nekom inicijalizovanom permutacijom - IP. Tada se ulazni blok podeli na dva dela po 32 bita, levi $L_{0}$ i desni deo $R_{0}$ . Nad desnim blokom se obavlja funkcija $F(R_{i},K_{i})$ , odnosno $F(R_{i},K_{16-i+1})$ kod dekriptovanja, gde je $R_{i}$ desnih 32 bita, a $K_{i}$ je 48 bitni ključ koji se generiše iz zadanog tajnog ključa kriptovanja. Vrednost dobijena operacijom XOR između vrednosti funkcije $F$ i levih 32 bita podataka, postaje $R_{i+1}$ , tj. desnih 32 bita za sledeći korak iteracije. $L_{i+1}$ za sledeći korak je $R_{i}$ . Nakon 16 takvik koraka blokovi se zamenjuju te se spajaju i obavlja se konačna permutacija koja je inverzna početnoj permutaciji, tj. $IP^{-1}$ . Dobijenih 64 bita su kriptovani blokovi. Budući da se nakon dve uzastopne operacije XOR sa istim brojem dobija početna vrednost, tj. a = (aĹ b)Ĺ b, postupak dekriptovanja može se sprovesti tako da se operacije obavljaju obrnutim redosedom. Zbog simetričnosti algoritma to se postiže tako da se kriptovani blok pusti kroz isti algoritam sa tom razlikom da se umesto ključa $K_{i}$ u i-tom koraku upotrebi ključ $K_{16-i+1}$ .

Postupak generisanja šestnaest 48 bitnih ključeva od zadanog, tajnog ključa sprovodi se u nekoliko koraka. Prvo se pomoću zadane tablice permutacije iz ključa generišu dva bloka po 28 bita. Zatim sledi 16 sledećih koraka: svaki se blok rotira u levo za određeni broj bita (u zavisnosti o kojem je koraku reč) te se iz nastalih blokova (2 × 28) pomoću tablicom zadate permutacije generiše ključ $K_{i}$ , gde je i broj koraka. Funkcija enkripcije $F$ jeste zapravo najkritičniji deo algoritma, tj. upravo zbog njene kompleksnosti ne postoji (barem koliko je za sada poznato) način provaljivanja DES-a (osim grubom računarskom silom). Vrednost funkcije dobija se u nekoliko koraka. Najpre se od ulaznih 32 bita ( $R_{i}$ ) proširenjem zadanom tablicom dobija 48 bita. Ta se vrednost zbraja logičkom operacijom XOR sa ključem $K_{i}$ paralelno nad svakim bitom. Dobijena se 48 bitna vrednost deli na osam delova od po šest bita. Prvi i zadnji bit svakog dela predstavlja adresu reda, a srednja četiri adresu kolone u tablici selekcije, odnosno, pomoću šest određena su četiri bita. Istim postupkom nad svakom šestorkom od ulaznih 48 bita selekcijom dobijamo 32 bita. Tih se 32 bita još permutuje zadatom tablicom te se dobija konačna vrednost funkcije $F$ .

Sigurnost i kriptoanaliza

Deep Crack, sadržala je 27 ploča sa po 64 čipa, i bila sposobna da testira 90 milijardi ključeva u sekundi..

DES algoritam se danas ne može smatrati sigurnim algoritmom, i zbog relativno male dužine ključa kao i zbog niza drugih nedostataka koji su omogućili kriptoanalitičarima širom sveta da objave niz algoritama za razbijanje ovog algoritma. Najpoznatiji napadi na ovaj algoritam su:

Brute force attack - ovim napado se isprobavaju svi mogući ključevi, i uz pomoć ove tehnike napada DES algoritam je razbijen 1998. godine uz pomoć Deep Crack računara, za šta je bilo neophodno svega 56 sati
Diferencijalna analiza - otkrivena kasne 1980. od strane Elija Bihama i Adija Šamira, ali je bila poznata i ranije od strane IBM-a i NSA-a, ali je bila čuvana u tajnosti.
Linearna kriptoanaliza
Unapređeni Dejvisov napad

Zamene za DES

Danas se DES sve manje koristi pre svega zbog male dužine ključa od 56 bita i sve bržim računarima i boljim algoritmima za razbijanje DES-a. Tako danas umesto ovog algoritma sve više se koriste AES (engl. Advanced Encryption Standard) algoritam. Za ovaj standard prihvaćen je algoritam RIJNDAEL, koji su kreirali belgijski matematičari Džon Demen i Vinsent Rimen. Ovaj algoritam je napredniji u odnosu na DES algoritam jer može koristiti promenljivu dužinu ključa (128, 192 ili 256 bita) kao i promenljivu dužinu bloka (128, 192 ili 256 bita) nezavisno od dužine ključa. Ostale prednosti ovog algoritma su simetrična i paralelna struktura, kao i pogodnost za realizaciju modernim procesorima, specijalizovanim hardverom ili u pametnim karticama (koje karakteriše mala memorija). Vrlo je važno je napomenuti da se kod ovog algoritma je pojava slabih ključeva nemoguća pošto algoritmi šifrovanja i dešifrovanja koriste različite komponente. Takođe AES je otporan na linearnu i diferencijalnu kriptoanalizu, kao i na druge publikovane napade na blok šifre.

Noviji blok šifarski algoritmi koji se danas najčešće koriste:

AES
Triple DES - ovaj algoritam je u stvari unapređeni DES

Vanjske veze

http://www.racunarskemreze.com/Knjiga?Module=BookOnline__Reader&Chapter=199 Arhivirano 2014-03-20 na Wayback Machine-u