Ki ga ANSI imenuje algoritem za šifriranje podatkov DEA (Data Encryption Algorithm), ISO pa DEA-1, je v 20 letih postal svetovni standard. V letih svojega obstoja je kljuboval naletom različnih napadov in z določenimi omejitvami še vedno velja za kripto odpornega.
DES je bločna šifra, ki šifrira podatke v 64-bitnih blokih. 64-bitni blok odprtega besedila je vnesen na enem koncu algoritma, 64-bitni blok šifriranega besedila pa je izhoden na drugem koncu. DES je simetričen algoritem: isti algoritem in ključ se uporabljata za šifriranje in dešifriranje (razen manjših razlik v uporabi ključa). Dolžina ključa je 56 bitov. (Ključ je običajno predstavljen kot 64-bitno število, vendar se vsak osmi bit uporablja za pariteto in se prezre. Paritetni biti so najmanjši pomembni deli bajtov ključa.) Ključ, ki je lahko katera koli 56-bitna številka, lahko kadar koli spremenite.
Kriptografsko moč v celoti določa ključ. Temeljni gradnik DES je kombinacija substitucij in permutacij. DES je sestavljen iz 16 ciklov.
Splošni pogled na cikel pretvorbe:
Če sta L i in R i leva in desna polovica, ki izhajata iz i-te ponovitve, je K i 48-bitni ključ za zanko i in je f funkcija, ki izvaja vse zamenjave, permutacije in XOR-je na ključu, potem ena pretvorbeno zanko lahko predstavimo kot:
Ob upoštevanju zamenjave F i (*) in permutacije T (*) lahko transformacijski cikel predstavimo, kot je prikazano na sl.
Vidimo, da je vsak cikel DES kompozicijska šifra z dvema zaporednima transformacijama - substitucijo F i (*) in permutacijo T (*) (z izjemo zadnjega, šestnajstega cikla, kjer je permutacija izpuščena).
Zamenjava:
(L i, R i) = (R i −1, L i −1) ⊕ f (R i −1, K)
je involucija, saj
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)
In zamenjava
T (L i ′, R i ′) = (R i ′, L i ′),
je tudi involucija, saj
T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′
Če začetno in končno permutacijo označimo kot (IP) in (IP) − 1, potem neposredna transformacija DES (šifriranje) izvaja funkcijo:
DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1 ,
in povratna transformacija DES (dešifriranje) izvaja funkcijo:
DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).
Tako je DES Feistelova šifra in je zasnovana tako, da deluje uporabna lastnina: Isti algoritem se uporablja za šifriranje in dešifriranje. Edina razlika je v tem, da je treba ključe uporabiti v obratnem vrstnem redu.
To pomeni, da če so bili med šifriranjem uporabljeni ključi K 1, K 2, K 3, ..., K 16, bodo ključi za dešifriranje K 16, K 15, K 14, ..., K 1. Algoritem uporablja samo standardno 64-bitno aritmetiko in logične operacije, tako da ga je mogoče preprosto implementirati v strojno opremo.
DES deluje na 64-bitnem bloku golega besedila. Po začetnem mešanju se blok razdeli na desno in levo polovico po 32 bitov. Nato se izvede 16 transformacij (funkcija f), v katerih se podatki združijo s ključem. Po šestnajstem ciklu se združita desna in leva polovica, algoritem pa se konča s končno permutacijo (obratno od izvirnika). Pri vsakem ciklu (glej sliko) se ključni biti premaknejo, nato pa se izmed 56 ključnih bitov izbere 48 bitov. Desna polovica podatkov je razširjena na 48 bitov z uporabo razširitvene permutacije, izvedena XOR z 48 biti premaknjenega in permutiranega ključa, prenesena skozi 8 S-polj, da se tvori 32 novih bitov, in ponovno permutirana. Te štiri operacije izvaja funkcija f.
Rezultat f se nato združi z levo polovico z uporabo drugega XOR. Kot rezultat teh dejanj se pojavi nova desna polovica, stara desna pa postane nova leva polovica. Ti koraki se ponovijo 16-krat, rezultat pa je 16 ciklov DES.
Ruski standard - GOST 28147-89
GOST 28147-89 je blokovna šifra z 256-bitnim ključem in 32 pretvorbenimi cikli, ki deluje na 64-bitnih blokih. Uporablja tudi kripto algoritem dodatni ključ, ki je obravnavan spodaj. Za šifriranje golo besedilo najprej razdeljen na levo in desno polovico L in R. V i-tem ciklu se uporabi podključ K i:
L i = R i −1,
R i = L i −1 ⊕ (f (R i −1 , K i)).
Funkcija f je implementirana na naslednji način. Najprej se doda desna polovica in i-ti podključ modulo 2 32. Rezultat je razdeljen na osem 4-bitnih podzaporedij, od katerih je vsako vneseno v svoj S-box. GOST uporablja osem različnih S-polj, prvi 4 biti gredo v prvo S-polje, drugi 4 biti v drugo S-polje itd. Vsako S-polje je permutacija števil od 0 do 15. Na primer, S-box bi lahko izgledal takole: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. V tem primeru, če je vhod S-boxa 0, potem je izhod 7. Če je vhod 1, je izhod 10 itd. Vseh osem S-boxov je različnih, so pravzaprav dodaten ključni material. Izhodi vseh osmih S-polj so združeni v 32-bitno besedo, nato pa se celotna beseda zasuka levo za 11 bitov. Na koncu se rezultat izvede XOR z levo polovico, da se ustvari nova desna polovica, desna polovica pa postane nova leva polovica. Za generiranje podključev je izvirni 256-bitni ključ razdeljen na osem 32-bitnih blokov: k 1, k 2, ..., k 8. Vsak cikel uporablja svoj podključ. Dešifriranje se izvede na enak način kot šifriranje, le da je vrstni red podključev k i obrnjen. Standard ne določa, kako se generirajo S-boxi.
Glavne razlike med DES in GOST
Glavne razlike med DES in GOST so naslednje:
- DES uporablja zapleten postopek za ustvarjanje podključev iz ključev. V GOST je ta postopek zelo preprost;
- v DES je 56-bitni ključ, v GOST pa 256-bitni. Če dodamo tajne permutacije S-polj, bo skupna količina tajnih informacij GOST približno 610 bitov;
- DES S-boxi imajo 6-bitne vhode in 4-bitne izhode, GOST S-boxi pa 4-bitne vhode in izhode. Oba algoritma uporabljata osem S-boxov, vendar je velikost GOST S-boxa enaka četrtini velikosti DES S-boxa;
- DES uporablja nepravilne permutacije, imenovane P-blok, medtem ko GOST uporablja 11-bitni ciklični levi premik;
- v DES je 16 ciklov, v GOST pa 32.
Silovit napad na GOST je popolnoma zaman. GOST uporablja 256-bitni ključ, in če upoštevate tajne S-boxe, bo dolžina ključa še večja. Zdi se, da je GOST bolj odporen na diferencialno in linearno kriptoanalizo kot DES. Čeprav naključni GOST S-boxi, pod določeno izbiro, ne zagotavljajo visoke kriptografske trdnosti v primerjavi s fiksnimi DES S-boxi, njihova tajnost poveča odpornost GOST-a na diferencialno in linearno kriptoanalizo. Poleg tega je učinkovitost teh kriptoanalitičnih metod odvisna od števila ciklov pretvorbe – več kot je ciklov, težja je kriptoanaliza. GOST uporablja dvakrat več ciklov kot DES, kar lahko povzroči neuspeh diferencialne in linearne kriptoanalize.
GOST ne uporablja permutacije razširitve, ki obstaja v DES. Odstranitev te permutacije iz DES ga oslabi z zmanjšanjem učinka plazu; Smiselno je domnevati, da odsotnost takšne operacije v GOST negativno vpliva na njegovo kriptografsko moč. Z vidika kriptografske trdnosti aritmetična operacija seštevanja, uporabljena v GOST, ni nič slabša od operacije XOR v DES.
Zdi se, da je glavna razlika uporaba cikličnega premika namesto permutacije v GOST. Preureditev DES poveča učinek plazu. V GOST sprememba enega vhodnega bita vpliva na eno polje S v enem ciklu pretvorbe, ki nato vpliva na dva polja S naslednjega cikla, nato na tri bloke naslednjega cikla itd. Traja osem ciklov, preden sprememba enega vhodnega bita vpliva na vsak bit izhoda; v DES to zahteva samo pet ciklov. Vendar GOST sestavlja 32 ciklov, DES pa samo 16.
Razvijalci GOST-a so poskušali doseči ravnovesje med kriptografsko močjo in učinkovitostjo. Na osnovi Feistelove zasnove so razvili kriptografski algoritem, ki je bolj primeren za implementacijo programske opreme kot DES. Za povečanje kriptografske moči je bil uveden zelo dolg ključ in število ciklov je bilo podvojeno. Vendar ostaja odprto vprašanje, ali so bila prizadevanja razvijalcev okronana z ustvarjanjem bolj kriptografskega algoritma kot DES.
Vorobyova E., Lukyanova A.
Algoritem DES
Glavne prednosti algoritma DES:
· uporablja se samo en ključ dolžine 56 bitov;
· ko ste sporočilo šifrirali z enim paketom, lahko za dešifriranje uporabite katerega koli drugega;
· zagotavlja relativno preprostost algoritma visoka hitrost obdelava informacij;
· dovolj visoka stabilnost algoritma.
DES šifrira 64-bitne bloke podatkov s 56-bitnim ključem. Dešifriranje v DES je obratna operacija šifriranja in se izvaja s ponavljanjem operacij šifriranja v obratnem vrstnem redu (kljub navidezni očitnosti se to ne naredi vedno. Kasneje si bomo ogledali šifre, pri katerih se šifriranje in dešifriranje izvajata z različnimi algoritmi) .
Postopek šifriranja je sestavljen iz začetne permutacije bitov 64-bitnega bloka, šestnajstih ciklov šifriranja in na koncu obratne permutacije bitov (slika 1).
Takoj je treba opozoriti, da so VSE tabele, navedene v tem članku, STANDARDNE in jih je zato treba vključiti v vašo implementacijo algoritma nespremenjene. Vse permutacije in kode v tabelah razvijalci izberejo tako, da čim bolj otežijo postopek dešifriranja z izbiro ključa. Struktura algoritma DES je prikazana na sliki 2.
Slika 2. Struktura šifrirnega algoritma DES
Naj se iz datoteke prebere naslednji 8-bajtni blok T, ki se transformira z uporabo začetne permutacijske matrike IP (tabela 1), kot sledi: bit 58 bloka T postane bit 1, bit 50 postane bit 2 itd., kar bo rezultat: T(0) = IP(T).
Nastalo bitno zaporedje T(0) je razdeljeno na dve zaporedji po 32 bitov: L(0) - levi ali višji bit, R(0) - desni ali nižji bit.
Tabela 1: Začetna permutacijska matrika 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
Nato se izvede šifriranje, sestavljeno iz 16 ponovitev. Rezultat i ponovitev je opisana z naslednjimi formulami:
R(i) = L(i-1) xali f(R(i-1), K(i)) ,
kjer je xor operacija IZKLJUČNO ALI.
Funkcija f se imenuje šifrirna funkcija. Njegova argumenta sta 32-bitno zaporedje R(i-1), pridobljeno pri (i-1) ponovitvi, in 48-bitni ključ K(i), ki je rezultat pretvorbe 64-bitnega ključa K. Spodaj je podrobno opisana funkcija šifriranja in algoritem za pridobivanje ključev K(i).
Pri 16. iteraciji dobimo zaporedji R(16) in L(16) (brez permutacije), ki ju povežemo v 64-bitno zaporedje R(16)L(16).
Nato se položaji bitov tega zaporedja prerazporedijo v skladu z matriko IP -1 (tabela 2).
Tabela 2: Inverzna permutacijska matrika 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
Matriki IP -1 in IP sta povezani na naslednji način: vrednost 1. elementa matrike IP -1 je 40, vrednost 40. elementa matrike IP pa je 1, vrednost 2. element matrike IP -1 je 8, vrednost 8. elementa matrike IP pa je enaka 2 itd.
Postopek dešifriranja podatkov je obraten procesu šifriranja. Vse korake je treba izvesti v obratnem vrstnem redu. To pomeni, da se dešifrirani podatki najprej preuredijo po matriki IP-1, nato pa se izvedejo enaka dejanja nad zaporedjem bitov R(16)L(16) kot pri procesu šifriranja, vendar v obratnem vrstnem redu.
Iterativni proces dešifriranja je mogoče opisati z naslednjimi formulami:
R(i-1) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) x ali f(L(i), K(i)), i = 1, 2, ..., 16.
Pri 16. iteraciji dobimo zaporedji L(0) in R(0), ki ju povežemo v 64-bitno zaporedje L(0)R(0).
Položaji bitov tega zaporedja se nato prerazporedijo v skladu z matriko IP. Rezultat takšne permutacije je izvirno 64-bitno zaporedje.
Zdaj razmislite o šifrirni funkciji f(R(i-1),K(i)). Shematično je prikazano na sl. 3.
Slika 3. Izračun funkcije f(R(i-1), K(i))
Za izračun vrednosti funkcije f se uporabljajo naslednje matrične funkcije:
E - razširitev 32-bitnega zaporedja na 48-bitno,
S1, S2, ..., S8 - pretvorba 6-bitnega bloka v 4-bitni blok,
P - permutacija bitov v 32-bitnem zaporedju.
Razširitvena funkcija E je definirana v tabeli 3. Glede na to tabelo so prvi 3 biti E(R(i-1)) biti 32, 1 in 2, zadnji pa 31, 32 in 1.
Tabela 3: Funkcija razširitve 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-bitno zaporedje, ki se doda modulo 2 (operacija xor) z 48-bitnim ključem K(i). Nastalo 48-bitno zaporedje je razdeljeno na osem 6-bitnih blokov B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). To je:
E(R(i-1)) xali K(i) = B(1)B(2)...B(8) .
Funkcije S1, S2, ..., S8 so definirane v tabeli 4.
Tabela 4
Na tabelo 4. potrebna so dodatna pojasnila. Naj bo vhod matrične funkcije Sj 6-bitni blok B(j) = b1b2b3b4b5b6, potem dvobitno število b1b6 označuje številko vrstice matrike, b2b3b4b5 pa številko stolpca. Rezultat Sj(B(j)) bo 4-bitni element, ki se nahaja na presečišču podane vrstice in stolpca.
Na primer B(1)=011011. Potem se S1(B(1)) nahaja na presečišču vrstice 1 in stolpca 13. V stolpcu 13 vrstice 1 je vrednost 5. To pomeni S1(011011)=0101.
Z uporabo izbirne operacije za vsakega od 6-bitnih blokov B(1), B(2), ..., B(8) dobimo 32-bitno zaporedje S1(B(1))S2(B(2) ))S3( B(3))...S8(B(8)).
Za pridobitev rezultata funkcije šifriranja je treba bite tega zaporedja preurediti. V ta namen uporabimo permutacijsko funkcijo P (Tabela 5). V vhodnem zaporedju so biti prerazporejeni tako, da bit 16 postane bit 1, bit 7 postane bit 2 in tako naprej.
Tabela 5: Permutacijska funkcija P
torej
f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))
Za dokončanje opisa algoritma za šifriranje podatkov ostane še predstaviti algoritem za pridobitev 48-bitnih ključev K(i), i=1...16. Pri vsaki ponovitvi se uporabi nova vrednost ključa K(i), ki se izračuna iz začetnega ključa K. K je 64-bitni blok z osmimi paritetnimi biti na mestih 8,16,24,32,40,48, 56. 64.
Za odstranitev kontrolnih bitov in prerazporeditev preostalih se uporabi funkcija G začetne priprave ključa (tabela 6).
Tabela 6
Matrika G začetne priprave 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 razdeljen na dva 28-bitna bloka C(0) in D(0), C(0) pa bo sestavljen iz bitov 57, 49, ..., 44, 36 ključa K in D(0 ) bosta sestavljena iz bitov 63, 55, ..., 12, 4 ključa K. Po definiranju C(0) in D(0), C(i) in D(i), i= 1...16, so rekurzivno določene. Če želite to narediti, uporabite ciklični premik v levo za en ali dva bita, odvisno od številke ponovitve, kot je prikazano v tabeli 7.
Tabela 7
Shift tabela za izračun ključa
| Številka ponovitve | Shift (biti) |
| 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 |
Dobljeno vrednost ponovno »zmešamo« v skladu z matriko H (tabela 8).
Tabela 8: Ključna zaključna matrika 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) bo sestavljen iz bitov 14, 17, ..., 29, 32 zaporedja C(i)D(i). Torej:
K(i) = H(C(i)D(i))
Blokovni diagram algoritma za izračun ključa je prikazan na sliki 4.
Slika 4. Blokovna shema algoritma za izračun ključa K(i)
Obnovitev izvirnega besedila se izvede s tem algoritmom, vendar najprej uporabite ključ
K(15), nato K(14) in tako naprej. Zdaj bi morali razumeti, zakaj avtor vztrajno priporoča uporabo danih matrik. Če boste lopovski, boste morda na koncu dobili zelo skrivno kodo, vendar je ne boste mogli razbiti sami!
Načini delovanja algoritma DES
Za najbolj popolno izpolnjevanje vseh zahtev za komercialne sisteme šifriranja je implementiranih več načinov delovanja algoritma DES. Najpogosteje uporabljeni načini so:
· elektronski šifrant (Electronic Codebook) - ECB;
· veriga digitalnih blokov (Cipher Block Chaining) - CBC;
· digitalno Povratne informacije(Cipher Feedback) - CFB;
· zunanja povratna informacija (Output Feedback) - OFB.
V tem načinu originalna datoteka M je razdeljen na 64-bitne bloke (po 8 bajtov): M = M(1)M(2)...M(n). Vsak od teh blokov je šifriran neodvisno z istim šifrirnim ključem (slika 5). Glavna prednost tega algoritma je njegova enostavna implementacija. Slabost - relativno šibka stabilnost proti kvalificiranim kriptoanalitikom.
- Vadnica
Pozdravljeni %username%!
Marsikdo ve, da je algoritem DES dolgo veljal za privzeti standard na področju simetričnega šifriranja. Prvi uspešen napad na ta neuničljiv algoritem je bil objavljen leta 1993, 16 let po tem, ko je bil sprejet kot standard. Metoda, ki jo je avtor poimenoval linearna kriptoanaliza, ob prisotnosti 247 parov golo/šifrirano besedilo omogoča odpiranje skrivnega ključa šifre DES v 243 operacijah.
Pod rezom bom poskušal na kratko orisati glavne točke tega napada.
Linearna kriptoanaliza
Linearna kriptoanaliza je posebna vrsta napada na simetrične šifre, namenjena obnovitvi neznanega šifrirnega ključa z uporabo znanih odprta sporočila in njihova ustrezna šifrirana besedila.IN splošni primer Napad, ki temelji na linearni kriptoanalizi, se skrči na naslednje pogoje. Napadalec ima velik znesek pari golo besedilo/šifrirano besedilo, pridobljeni z uporabo istega šifrirnega ključa K. Napadalčev cilj je povrniti del ali celoten ključ K.
Najprej napadalec pregleda šifro in najde t.i statistični analog, tj. enačba naslednje oblike, ki velja z verjetnostjo P ≠ 1/2 za poljuben par javno/zasebno besedilo in fiksni ključ:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
kjer so P n, C n, K n n-ti biti besedila, šifriranega besedila in ključa.
Ko je taka enačba najdena, lahko napadalec obnovi 1 bit ključne informacije z uporabo naslednjega algoritma
Algoritem 1
Naj bo T število besedil, za katera je leva stran enačbe (1) enaka 0, potem
Če je T>N/2, kjer je N število znanih odprtih besedil.
Predpostavimo, da je K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (ko je P>1/2) ali 1 (ko je P<1/2).
V nasprotnem primeru
Predpostavimo, da je K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (ko je P>1/2) ali 0 (ko je P<1/2).
Očitno je, da je uspeh algoritma neposredno odvisen od vrednosti |P-1/2| in na število razpoložljivih parov odprto/zaprto besedilo N. Bolj kot se verjetnost P enakosti (1) razlikuje od 1/2, manjše število odprtih besedil N je potrebnih za napad.
Da bo napad uspešen, je treba rešiti dve težavi:
- Kako najti učinkovito enačbo oblike (1).
- Kako uporabiti to enačbo, da dobimo več kot en bit informacij o ključu.
Opis DES
Najprej pa na kratko opišemo, kako deluje algoritem. O DES je bilo že dovolj povedanega. Celoten opis šifre je na voljo na Wikipediji. Vendar pa bomo za nadaljnjo razlago napada potrebovali številne definicije, ki jih je najbolje predstaviti vnaprej.DES je torej blokovna šifra, ki temelji na omrežju Feistel. Šifra ima velikost bloka 64 bitov in velikost ključa 56 bitov. Oglejmo si shemo šifriranja algoritma DES. 
Kot je razvidno iz slike, se pri šifriranju besedila izvajajo naslednje operacije:
- Začetna bitna permutacija. Na tej stopnji se biti vhodnega bloka premešajo v določenem vrstnem redu.
- Po tem se mešani biti razdelijo na dve polovici, ki se podajo na vhod Feistelove funkcije. Za standardni DES Feistelovo omrežje vključuje 16 krogov, vendar obstajajo tudi druge različice algoritma.
- Dva bloka, dobljena v zadnjem krogu transformacije, se združita in na dobljenem bloku se izvede druga permutacija.
V vsakem krogu Feistelovega omrežja se najmanj pomembnih 32 bitov sporočila prenese skozi funkcijo f: 
Oglejmo si operacije, ki se izvajajo na tej stopnji:
- Vhodni blok se prenese skozi razširitveno funkcijo E, ki pretvori 32-bitni blok v 48-bitni blok.
- Nastali blok se doda okroglemu ključu K i .
- Rezultat prejšnjega koraka je razdeljen na 8 blokov po 6 bitov.
- Vsak od prejetih blokov B i se prenese skozi substitucijsko funkcijo S-Box i , ki nadomesti 6-bitno zaporedje s 4-bitnim blokom.
- Nastali 32-bitni blok se prenese skozi permutacijo P in vrne kot rezultat funkcije f.
Z vidika kriptoanalize so za nas najbolj zanimivi bloki S, ki so namenjeni skrivanju povezave med vhodnimi in izhodnimi podatki funkcije f. Za uspešen napad na DES bomo najprej izdelali statistične analoge za vsako od S-polj in jih nato razširili na celotno šifro.
Analiza bloka S
Vsak S-box kot vhod sprejme 6-bitno zaporedje in za vsako tako zaporedje se vrne fiksna 4-bitna vrednost. Tisti. skupno je na voljo 64 vhodnih in izhodnih možnosti. Naša naloga je prikazati razmerje med vhodnimi in izhodnimi podatki blokov S. Na primer, za tretje polje S šifre DES je 3. bit vhodnega zaporedja enak 3. bitu izhodnega zaporedja v 38 od 64 primerov. Zato smo našli naslednji statistični analog za tretji S -škatla:S 3 (x) = x, kar je izpolnjeno z verjetnostjo P=38/64.
Obe strani enačbe predstavljata 1 bit informacije. Torej, če bi bili leva in desna stran neodvisni druga od druge, bi morala biti enačba izpolnjena z verjetnostjo 1/2. Tako smo pravkar prikazali razmerje med vhodom in izhodom 3. S-boxa algoritma DES.
Razmislimo, kako lahko najdemo statistični analog S-boxa v splošnem primeru.
Za S-polje S a, 1 ≤ α ≤ 63 in 1 ≤ β ≤ 15, vrednost NS a (α, β) opisuje, kolikokrat od 64 možnih vhodnih bitov XOR S a, prekritih z biti α, je enakih izhodni biti XOR, prekriti z bitji α β, tj.:
kjer je simbol logični IN.
Vrednosti α in β, za katere se NS a (α, β) najbolj razlikuje od 32, opisujejo najučinkovitejši statistični analog S-boxa Sa.
Najučinkovitejši analog je bil najden v 5. S-polju šifre DES za α = 16 in β = 15 NS 5 (16, 15) = 12. To pomeni, da velja naslednja enačba: Z=Y ⊕ Y ⊕ Y ⊕ Y, kjer je Z vhodno zaporedje polja S, Y pa izhodno zaporedje.
Oziroma ob upoštevanju dejstva, da se v algoritmu DES pred vnosom v S-box podatki seštevajo po modulu 2 z okroglim ključem, tj. Z = X ⊕ K dobimo
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, kjer sta X in Y vhodni in izhodni podatek funkcije f brez upoštevanja permutacij.
Nastala enačba se izvede v vseh krogih algoritma DES z enako verjetnostjo P=12/64.
Naslednja tabela prikazuje seznam učinkovitih, tj. z največjim odstopanjem od P=1/2, statistični analogi za vsak s-blok algoritma DES. 
Konstruiranje statističnih analogov za več krogov DES
Pokažimo zdaj, kako lahko združimo statistične analoge več krogov DES in na koncu dobimo statistični analog za celotno šifro.Če želite to narediti, razmislite o trikrožni različici algoritma:
Uporabimo učinkovit statistični analog 5. s-boxa za izračun določenih bitov vrednosti X(2).
Vemo, da z verjetnostjo 12/64 velja enakost v f-funkciji X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, kjer je X drugi vhodni bit 5. polja S, je v bistvu 26. bit zaporedja, dobljenega po razširitvi vhodnih bitov. Z analizo ekspanzijske funkcije lahko ugotovimo, da je 26. bit nadomeščen s 17. bitom zaporedja X(1).
Podobno so Y,..., Y v bistvu 17., 18., 19. in 20. bit zaporedja, dobljenega pred permutacijo P. Ob pregledu permutacije P ugotovimo, da so biti Y,..., Y pravzaprav biti Y (1), Y(1), Y(1), Y(1).
Ključni bit K, vključen v enačbe, je 26. bit prvega kroga podključa K1, nato pa ima statistični analog naslednjo obliko:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
torej X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) z verjetnostjo P=12/64.
Če poznate 3, 8, 14, 25 bitov zaporedja Y(1), lahko najdete 3, 8, 14, 25 bitov zaporedja X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ali ob upoštevanju enačbe (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) z verjetnostjo 12/64.
Poiščimo podoben izraz z uporabo zadnjega kroga. Tokrat imamo enačbo
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Ker
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
to razumemo
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4)
z verjetnostjo 12/64.
Z enačenjem desnih strani enačb (3) in (4) dobimo
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 z verjetnostjo (12/64) 2 +(1-12/64) 2.
Ob upoštevanju dejstva, da je X(1) = PR in X(3) = CR, dobimo statistični analog
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5)
,
ki se izvede z verjetnostjo (12/64) 2 + (1-12/64) 2 =0,7.
Zgoraj opisani statistični analog je mogoče grafično predstaviti na naslednji način (biti na sliki so oštevilčeni od desne proti levi in se začnejo z ničlo): 
Napadalec pozna vse bite na levi strani enačbe, zato lahko uporabi algoritem 1 in ugotovi vrednost K1 ⊕ K3. Pokažimo, kako lahko s tem statističnim analogom odprete ne 1, ampak 12 bitov šifrirnega ključa K.
Napad na DES z znanim golim besedilom
Naj predstavimo metodo, s katero lahko razširite napad in takoj pridobite 6 bitov prve runde povezave.Pri sestavi enačbe (5) smo upoštevali dejstvo, da ne poznamo vrednosti F1(PR, K1). Zato smo uporabili njegov statistični analog K1 ⊕ PR.
Namesto izraza K1 ⊕ PR vrnimo vrednost F1(PR, K1) in dobimo naslednjo enačbo:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , ki bo izvedena z verjetnostjo 12/64. Verjetnost se je spremenila, saj smo pustili samo statistični analog iz tretjega kroga, vse druge vrednosti so fiksne.
Zgoraj smo že ugotovili, da na vrednost F1(PR, K1) vplivajo vhodni biti 5. S-polja, in sicer ključni biti K1 in biti PR bloka. Pokažimo, kako lahko obnovite vrednost K1, če imate le nabor odprtih/zaprtih besedil. Za to bomo uporabili algoritem 2.
Algoritem 2
Naj bo N število odprtih/zaprtih besedilnih parov, znanih pred napadom. Če želite odpreti ključ, morate narediti naslednje korake.
Za (i=0; i<64; i++) do
{
Za (j=0; j
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) potem
T i =T i +1
}
}
Kot verjetno zaporedje K1 se vzame vrednost i, tako da je izraz |T i -N/2| ima največjo vrednost.
Glede na zadostno število znanih odprtih besedil bo imel algoritem veliko verjetnost, da vrne pravilno vrednost šestih bitov prvega kroga podključa K1. To je razloženo z dejstvom, da če spremenljivka i ni enaka K1, bo vrednost funkcije F1(PR j, K) naključna in število enačb za takšno vrednost i, za katero je leva stran enako nič, se bo nagibalo k N/2. Če je podključ pravilno uganjen, bo leva stran enaka fiksnemu bitu K3 z verjetnostjo 12/64. Tisti. prišlo bo do znatnega odstopanja od N/2.
Ko prejmete 6 bitov podključa K1, lahko podobno odprete 6 bitov podključa K3. Vse kar morate storiti je, da zamenjate C s P in K1 s K3 v enačbi (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algoritem 2 bo vrnil pravilno vrednost K3, ker je postopek dešifriranja algoritma DES enak procesu šifriranja, le zaporedje ključev je obrnjeno. Tako se v prvem krogu dešifriranja uporabi ključ K3, v zadnjem krogu pa ključ K1.
Ko prejme 6 bitov podključev K1 in K3, napadalec pridobi 12 bitov skupnega ključa šifre K, ker okrogli ključi so običajna permutacija ključa K. Število odprtih besedil, potrebnih za uspešen napad, je odvisno od verjetnosti statističnega analoga. Za razbijanje 12-bitnega 3-krožnega ključa DES zadostuje 100 parov besedila javno/zasebno. Za odpiranje 12 bitov 16-krožnega ključa DES bo potrebnih približno 244 parov besedil. Preostalih 44 bitov ključa se odpre z običajno surovo silo.
Najpogostejši in najbolj znan algoritem simetričnega šifriranja je DES (Standard šifriranja podatkov). Algoritem je bil razvit leta 1977 in ga je leta 1980 kot standard sprejel NIST (Nacionalni inštitut za standarde in tehnologijo, ZDA).
DES je klasično Feishtelovo omrežje z dvema vejama. Podatki so šifrirani v 64-bitnih blokih s 56-bitnim ključem. Algoritem v več krogih pretvori 64-bitni vhod v 64-bitni izhod. Dolžina ključa je 56 bitov. Postopek šifriranja je sestavljen iz štirih stopenj. Prvi korak je začetna permutacija (IP) 64-bitnega izvornega besedila (beljenje), med katero so biti prerazporejeni v skladu s standardno tabelo. Naslednja stopnja je sestavljena iz 16 krogov iste funkcije, ki uporablja operacije premika in zamenjave. Na tretji stopnji se zamenjata leva in desna polovica izhoda zadnje (16.) ponovitve. Končno četrta stopnja izvede permutacijo IP-1 rezultata, pridobljenega v tretji stopnji. Permutacija IP-1 je obratna od začetne permutacije.
Slika 4. algoritem DES
Slika prikazuje metodo, ki uporablja 56-bitni ključ. Na začetku je ključ dobavljen vhodu permutacijske funkcije. Nato je za vsakega od 16 krogov podključ K i kombinacija levega krožnega premika in permutacije. Funkcija permutacije je enaka za vsak krog, vendar so podključi K i za vsak krog različni zaradi ponavljajočega premikanja bitov ključa.
Začetna permutacija in njena inverzija sta določeni s standardno tabelo. Če je M poljubnih 64 bitov, potem je X = IP(M) preurejenih 64 bitov. Če uporabimo inverzno permutacijsko funkcijo Y = IP-1 (X) = IP-1 (IP(M)), dobimo izvirno bitno zaporedje.
Opis okrogle des
Oglejmo si zaporedje transformacij, uporabljenih v vsakem krogu.
Slika 5. Ilustracija kroga algoritma DES
64-bitni vhodni blok gre skozi 16 krogi, pri čemer vsaka ponovitev proizvede vmesno 64-bitno vrednost. Leva in desna stran vsake vmesne vrednosti se obravnavata kot ločeni 32-bitni vrednosti, označeni z L in R. Vsako ponovitev je mogoče opisati na naslednji način:
R i = L i -1 F(R i -1 , K i)
Tako je izhod leve polovice L i enak vhodu desne polovice R i-1. Izhod desne polovice R i je rezultat uporabe operacije XOR za L i-1 in funkcije F, ki je odvisna od R i-1 in K i.
Oglejmo si funkcijo F podrobneje. R i , ki je doveden na vhod funkcije F, ima dolžino 32 bitov. Najprej se R i razširi na 48 bitov z uporabo tabele, ki določa permutacijo in 16-bitno razširitev. Razširitev poteka na naslednji način. 32 bitov je razdeljenih v skupine po 4 bitov in nato razširjenih na 6 bitov z dodajanjem najbolj oddaljenih bitov iz dveh sosednjih skupin. Na primer, če je del vhodnega sporočila
Efgh ijkl mnop . . .
potem je rezultat razširitve sporočilo
Defghi hijklm lmnopq. . .
Nastala 48-bitna vrednost se nato izvede XOR z 48-bitnim podključem K i . Nastala 48-bitna vrednost se nato vnese v substitucijsko funkcijo, ki ima za posledico 32-bitno vrednost.
Substitucija je sestavljena iz osmih S-polj, od katerih vsaka prejme 6 bitov kot vhod in proizvede 4 bite kot izhod. Te transformacije so opredeljene s posebnimi tabelami. Prvi in zadnji bit vhodne vrednosti S-boxa določata številko vrstice v tabeli, srednji 4 biti pa številko stolpca. Presečišče vrstice in stolpca določa 4-bitni izhod. Na primer, če je vnos 011011, je številka vrstice 01 (vrstica 1) in številka stolpca 1101 (stolpec 13). Vrednost v vrstici 1 in stolpcu 13 je 5, tj. rezultat je 0101.
Dobljena 32-bitna vrednost se nato obdela s permutacijo P, katere namen je čim bolj preurediti bite, tako da bo v naslednjem krogu šifriranja vsak bit verjetno obdelal drug S-box.
Ključ posameznega kroga K i je sestavljen iz 48 bitov. Ključi K i so pridobljeni z uporabo naslednjega algoritma. Za 56-bitni ključ, ki se uporablja kot vhod v algoritem, se najprej izvede permutacija v skladu s tabelo Permuted Choice 1 (PC-1). Nastali 56-bitni ključ je razdeljen na dva 28-bitna dela, označena kot C0 oziroma D0. V vsakem krogu sta C i in D i neodvisno ciklično premaknjena v levo za 1 ali 2 bita, odvisno od števila kroga. Dobljene vrednosti so vhod za naslednji krog. So tudi vhod v Permuted Choice 2 (PC-2), ki proizvede 48-bitno izhodno vrednost, ki je vhod v funkcijo F(R i-1, K i).
Postopek dešifriranja je podoben postopku šifriranja. Vhod v algoritem je šifrirano besedilo, vendar se ključi K i uporabljajo v obratnem vrstnem redu. K 16 se uporablja v prvem krogu, K 1 se uporablja v zadnjem krogu. Naj bo rezultat i-tega kroga šifriranja L i ||R i . Potem bo ustrezen vnos (16-i)-tega kroga dešifriranja R i ||L i .
Po zadnjem krogu postopka dešifriranja se dve polovici izhoda zamenjata, tako da je vhod končne permutacije IP-1 R 16 ||L 16 . Rezultat te stopnje je golo besedilo.
Več kot 30 let je minilo od sprejetja algoritma DES kot standarda šifriranja v ZDA. DES je šifrirni algoritem z najbogatejšo in najbolj zanimivo zgodovino.
Zgodovina nastanka algoritma
Eden najbolj znanih kriptologov na svetu, Bruce Schneier, je v svoji slavni knjigi “Uporabna kriptografija” opisal težave uporabnikov orodij za informacijsko varnost v zgodnjih 70. letih. XX. stoletja (seveda govorimo o uporabnikih na drugi strani železne zavese):
Ni bilo niti splošno sprejetega standarda za šifriranje podatkov niti preprosto široko uporabljenih algoritmov za varnost informacij, zato združljivost med različnimi programskimi ali strojnimi orodji za šifriranje ni prišla v poštev;
Skoraj vsako šifrirno orodje je bilo »črna skrinjica« z dokaj nejasno vsebino: kateri šifrirni algoritem je uporabljen, kako kriptografsko močan je, ali je pravilno implementiran, ali so šifrirni ključi ustvarjeni, shranjeni in uporabljeni pravilno, ali orodje vsebuje nedokumentirane zmožnosti, ki so jih vstavili razvijalci itd. - vse te zelo pomembne informacije so bile nedostopne veliki večini kupcev kriptografskih sredstev.
Nacionalni urad za standarde (NBS) ZDA je bil zaskrbljen zaradi tega problema. Posledično je bil leta 1973 objavljen prvi odprti natečaj za šifrirni standard. NBS je bila za izbiro standarda pripravljena preučiti kandidate za algoritme, ki so izpolnjevali naslednja merila:
Algoritem mora biti kriptografsko močan;
Algoritem mora biti hiter;
Struktura algoritma mora biti jasna in natančna;
Moč šifriranja naj bo odvisna le od ključa, sam algoritem ne sme biti tajen;
Algoritem mora biti enostavno uporaben za različne namene;
Algoritem je treba preprosto implementirati v strojno opremo z uporabo obstoječih komponent strojne opreme.
Predvidevalo se je, da bodo zainteresirane organizacije ali strokovnjaki NBS poslali podrobne specifikacije algoritmov, ki so zadostni za njihovo implementacijo, torej brez kakršnih koli "mrtvih točk". Predvidevalo se je tudi, da bo algoritem certificiran s strani NBS za splošno uporabo, iz njega pa bodo odpravljene vse patentne in izvozne omejitve, zaradi česar bi moral tak standard rešiti vse težave z združljivostjo šifriranja. Poleg tega je NBS prevzela naloge certificiranja šifrirnih orodij – torej naj bi “črne skrinjice” postale preteklost.
Pravzaprav je obstajal samo en kandidatni algoritem: to je bil šifrirni algoritem Lucifer, ki ga je razvil ShM (glejte poglavje 3.31). V dveh letih je bil algoritem izpopolnjen:
Prvič, NBS je skupaj z ameriško agencijo za nacionalno varnost (NSA, National Security Agency) opravila temeljito analizo algoritma, ki je privedla do njegove precejšnje revizije;
Drugič, upoštevane so bile pripombe in kritike vseh zainteresiranih organizacij in posameznikov.
Kot rezultat skupnih prizadevanj IBM, NBS in NSA je bil januarja 1977 DES objavljen kot ameriški standard (zadnja različica tega standarda je v dokumentu) za algoritem za šifriranje podatkov (razen zelo občutljivih informacij). Algoritem DES je patentiral YuM, vendar je NBS dejansko prejel brezplačno in neomejeno licenco za uporabo tega algoritma. Alternativno, vendar manj pogosto uporabljeno ime za algoritem je DEA (Data Encryption Algorithm).
Glavne značilnosti in zgradba algoritma
Algoritem DES šifrira informacije v 64-bitnih blokih z uporabo 64-bitnega šifrirnega ključa, ki uporablja samo 56 bitov (postopek razširitve ključa je podrobno opisan spodaj).
Šifriranje informacij se izvede na naslednji način (slika 3.56):
1. Začetna permutacija se izvede na 64-bitnem podatkovnem bloku v skladu s tabelo. 3.16.
Tabela 3.16
Tabela se interpretira na naslednji način: vrednost vhodnega bita 58 (v nadaljevanju so vsi biti oštevilčeni od leve proti desni, začenši z 1) se postavi v izhodni bit 1, vrednost bita 50 se postavi v bit 2 itd.
2. Rezultat prejšnje operacije je razdeljen na 2 podbloka po 32 bitov (per
riž. 3,56 označeno A 0 in B 0), nad katerim se izvede 16 krogov
naslednje transformacije:
Kot je navedeno zgoraj, od 64-bitnega šifrirnega ključa algoritem DES uporablja le 56 bitov. Vsak 8. bit je zavržen in se v algoritmu na noben način ne uporablja, uporaba preostalih bitov šifrirnega ključa v implementacijah algoritma DES pa standard nikakor ne omejuje. Postopek za ekstrahiranje 56 pomembnih bitov 64-bitnega ključa na sl. 3.59 je označen kot E. Ta postopek poleg ekstrakcije izvede tudi preureditev ključnih bitov v skladu s tabelo. 3.19 in 3.20.
Tabela 3.19
Tabela 3.20
Kot rezultat permutacije nastaneta dve 28-bitni vrednosti C in D. Tabela 3.19 določa izbiro ključnih bitov za C, tabelo. 3,20 - za D.
Nato se izvede 16 krogov transformacij, pri čemer vsaka da enega od krogov ključev K t. V vsakem krogu postopka razširitve ključa se izvedejo naslednja dejanja:
1. Trenutne vrednosti C in D ciklično premaknjena levo za spremenljivo število bitov p. Za 1., 2., 9. in 16. krog p= 1, se v preostalih krogih izvede ciklični premik za 2 bita.
2. C in D se združijo v 56-bitno vrednost, na katero se uporabi kompresijska permutacija CP, katere rezultat je 48-bitni okrogli ključ K (. Kompresijska permutacija se izvede v skladu s tabelo 3.21.
Tabela 3.21
Pri dešifriranju podatkov lahko uporabite isti postopek razširitve ključa, vendar uporabite okrogle ključe v obratnem vrstnem redu. Obstaja še ena možnost: v vsakem krogu postopka razširitve ključa namesto cikličnega premika v levo izvedemo ciklični premik v desno za n bitov, kjer je rc' = 0 za prvi krog, u' = 1 za kroge. 2, 9, 16 in n = 2 za preostale kroge. Ta postopek razširitve ključa bo takoj zagotovil okrogle ključe, potrebne za dešifriranje.
Vredno je povedati, da se možnost izvajanja razširitve ključa "na letenje" (še posebej, če ta možnost obstaja tako med šifriranjem kot med dešifriranjem) šteje za prednost šifrirnih algoritmov, saj se v tem primeru lahko razširitev ključa izvaja vzporedno s šifriranjem. in ne zapravljajte pomnilnika za shranjevanje ključev drugih krogov, razen trenutnega.
