Može li se DES razbiti diferencijalnom kriptoanalizom?
Diferencijalna kriptoanaliza je oblik kriptoanalize primjenjiv primarno na blok šifre, koja uključuje analizu učinka određenih razlika u ulaznim parovima na razlike na izlazu. Ovu metodu uveli su Eli Biham i Adi Shamir kasnih 1980-ih i od tada je postala temeljni alat u alatu kriptoanalitičara. Standard za šifriranje podataka (DES), algoritam sa simetričnim ključem za šifriranje digitalnih podataka, bio je jedan od primarnih predmeta diferencijalne kriptoanalize.
DES algoritam, dizajniran od strane IBM-a u ranim 1970-ima i prihvaćen kao federalni standard 1977. od strane Nacionalnog instituta za standarde i tehnologiju (NIST), radi na 64-bitnim blokovima podataka koristeći 56-bitni ključ. DES koristi 16 krugova Feistelove mreže, gdje se svaki krug sastoji od niza zamjena i permutacija određenih rasporedom ključeva.
Da bismo razumjeli može li se DES razbiti diferencijalnom kriptoanalizom, važno je razmotriti specifičnosti i DES strukture i načela diferencijalne kriptoanalize.
Struktura DES-a i raspored ključeva
DES je izgrađen na kombinaciji operacija supstitucije i permutacije. Svaki krug DES-a uključuje sljedeće korake:
1. Proširenje (E-box): 32-bitni polublok se proširuje na 48 bita pomoću permutacije proširenja.
2. Miješanje tipki: Prošireni polublok je XOR s okruglim ključem izvedenim iz glavnog ključa pomoću rasporeda ključeva.
3. Zamjena (S-box): 48-bitni rezultat je podijeljen u osam 6-bitnih segmenata, od kojih se svaki prolazi kroz odgovarajuću S-kutiju za proizvodnju 4-bitnog izlaza. Osam 4-bitnih izlaza spojeno je u 32-bitni blok.
4. Permutacija (P-box): 32-bitni blok se permutira korištenjem fiksne permutacijske tablice.
5. XOR i Swap: Permutiranom bloku vrši se XOR s drugom polovicom bloka podataka, a polovice se zamjenjuju.
Raspored ključeva generira niz od 16 okruglih ključeva, svaki od 48 bita, iz originalnog 56-bitnog ključa. Ovaj proces uključuje operacije permutiranog izbora i kružne pomake ulijevo.
Principi diferencijalne kriptoanalize
Diferencijalna kriptoanaliza uključuje proučavanje kako se razlike u parovima otvorenog teksta šire kroz šifru da bi proizvele razlike u šifriranom tekstu. Osnovna ideja je odabrati parove otvorenih tekstova koji imaju određenu razliku, šifrirati ih i analizirati rezultirajuće razlike šifriranih tekstova. Promatrajući kako se te razlike razvijaju kroz krugove šifre, napadač može zaključiti informacije o ključu.
Ključni pojmovi u diferencijalnoj kriptoanalizi uključuju:
- Diferencijal: XOR razlika između dvije vrijednosti. Na primjer, ako 
i 
su dva otvorena teksta, njihov diferencijal je 
.
- Karakterističan: Niz razlika koji opisuje kako se ulazni diferencijal širi kroz krugove šifre.
- Vjerojatnost: Vjerojatnost da će dati ulazni diferencijal proizvesti određeni izlazni diferencijal nakon određenog broja krugova.
Prijava na DES
DES je posebno dizajniran da se odupre diferencijalnoj kriptoanalizi, koja nije bila javno poznata u vrijeme njegovog dizajna, ali su je razumjeli IBM i NSA. S-kutije u DES-u pažljivo su odabrane kako bi se smanjila vjerojatnost diferencijalnih karakteristika, što otežava diferencijalnu kriptoanalizu.
Međutim, Biham i Shamir pokazali su da DES nije imun na diferencijalnu kriptoanalizu. Pokazali su da, iako je cijeli DES od 16 krugova otporan na praktične diferencijalne napade, smanjene verzije šifre su ranjive. Točnije, razvili su napade na DES s manje od 16 rundi.
Na primjer, napad na DES od 8 krugova može se izvesti sa složenošću od oko 
izabranih otvorenih tekstova, što je znatno učinkovitije od napada grubom silom na puni prostor ključa. Za puni DES od 16 krugova, složenost diferencijalne kriptoanalize je mnogo veća, što je čini nepraktičnom s računalnim resursima dostupnim u vrijeme njihova istraživanja.
Primjer diferencijalne kriptoanalize na DES-u
Da bismo ilustrirali kako radi diferencijalna kriptoanaliza, razmotrimo pojednostavljeni primjer s DES-om smanjenog kruga:
1. Odaberite diferencijal: Odaberite određeni ulazni diferencijal 
. Radi jednostavnosti, pretpostavimo utječe samo na nekoliko bitova.
2. Generiraj parove otvorenog teksta: Generirajte veliki broj parova otvorenog teksta 
tako da 
.
3. Šifriranje parova otvorenog teksta: Šifrirajte svaki par da biste dobili šifrirane tekstove 
.
4. Analizirajte izlazne razlike: Izračunajte izlazni diferencijal 
za svaki par.
5. Prepoznajte karakteristike: Identificirajte obrasce u izlaznim razlikama koje sugeriraju specifične karakteristike unutarnje strukture šifre.
6. Zaključite ključne informacije: Upotrijebite identificirane karakteristike kako biste zaključili informacije o okruglim ključevima, i konačno o glavnom ključu.
Praktična razmatranja
Iako je diferencijalna kriptoanaliza moćan alat, njena praktična primjena na DES zahtijeva značajne računalne resurse i veliki broj odabranih otvorenih tekstova. Moderne kriptografske prakse razvile su se za korištenje složenijih i sigurnijih algoritama, kao što je Advanced Encryption Standard (AES), koji su dizajnirani da se odupru ne samo diferencijalnoj kriptoanalizi, već i širokom rasponu drugih kriptoanalitičkih napada.
Diferencijalna kriptoanaliza je dobro uspostavljena tehnika u polju kriptografije koja se može koristiti za analizu i, u nekim slučajevima, razbijanje blok šifri poput DES. Dok je DES od 16 rundi otporan na praktične diferencijalne napade, verzije DES-a sa smanjenom rundom su ranjive. Dizajn DES-a, posebno njegovih S-boxova, odražava svijest o principima diferencijalne kriptoanalize, pokazujući važnost pažljivog kriptografskog dizajna u osiguravanju sigurnosti.
Ostala nedavna pitanja i odgovori u vezi Standard šifriranja podataka (DES) - Raspored ključeva i dešifriranje:
- Između linearne i diferencijalne kriptoanalize koja je učinkovita za razbijanje DES-a?
- Kako linearna kirpanaliza može razbiti DES kriptosustav?
- Mogu li dva različita ulaza x1, x2 proizvesti isti izlaz y u standardu šifriranja podataka (DES)?
- Je li diferencijalna kriptoanaliza učinkovitija od linearne kriptoanalize u razbijanju DES kriptosustava?
- Kako je DES poslužio kao temelj za moderne algoritme šifriranja?
- Zašto se duljina ključa u DES-u smatra relativno kratkom prema današnjim standardima?
- Što je struktura Feistelove mreže i kako se ona odnosi na DES?
- Kako se proces dešifriranja u DES-u razlikuje od procesa šifriranja?
- Koja je svrha rasporeda ključeva u DES algoritmu?
- Kako razumijevanje rasporeda ključeva i procesa dešifriranja DES-a doprinosi proučavanju klasične kriptografije i evoluciji algoritama šifriranja?