Šifrovací algoritmy DES a AES. Schéma šifrování algoritmu DES
- Tutorial
Dobrý den, %username%!
Mnoho lidí ví, že algoritmus DES je již dlouho považován za výchozí standard v oblasti symetrického šifrování. První úspěšný útok na tento nezničitelný algoritmus byl zveřejněn v roce 1993, 16 let poté, co byl přijat jako standard. Metoda, kterou autor nazval lineární kryptoanalýza, za přítomnosti 2 47 dvojic prostého/šifrového textu umožňuje otevřít tajný klíč šifry DES ve 2 43 operacích.
Pod střihem se pokusím stručně nastínit hlavní body tohoto útoku.
Lineární kryptoanalýza
Lineární kryptoanalýza je speciální typ útoku na symetrické šifry, jehož cílem je obnovit neznámý šifrovací klíč ze známých prostých zpráv a jejich odpovídajících šifrových textů.Obecně platí, že útok založený na lineární kryptoanalýze se scvrkává na následující podmínky. Útočník má k dispozici velké množství dvojic prostého textu/šifrovaného textu získaných pomocí stejného šifrovacího klíče K. Cílem útočníka je obnovit část nebo celý klíč K.
Útočník nejprve prozkoumá šifru a najde tzv statistická analogie, tj. rovnice následujícího tvaru, která platí s pravděpodobností P ≠ 1/2 pro libovolný pár veřejný/soukromý text a pevný klíč:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
kde P n, C n, K n jsou n-té bity textu, šifrového textu a klíče.
Jakmile je taková rovnice nalezena, útočník může obnovit 1 bit klíčových informací pomocí následujícího algoritmu
Algoritmus 1
Nechť T je počet textů, pro které je levá strana rovnice (1) rovna 0
Pokud T>N/2, kde N je počet známých otevřených textů.
Předpokládejme, že K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (když P>1/2) nebo 1 (když P<1/2).
v opačném případě
Předpokládejme, že K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (když P>1/2) nebo 0 (když P<1/2).
Je zřejmé, že úspěšnost algoritmu přímo závisí na hodnotě |P-1/2| a na počtu dostupných párů otevřených/uzavřených textů N. Čím více se pravděpodobnost P rovnosti (1) liší od 1/2, tím menší počet otevřených textů N je potřeba k útoku.
Aby byl útok úspěšný, je třeba vyřešit dva problémy:
- Jak najít efektivní rovnici tvaru (1).
- Jak použít tuto rovnici k získání více než jednoho bitu informací o klíči.
Popis DES
Nejprve si ale stručně popišme, jak algoritmus funguje. O DES už toho bylo řečeno dost. Úplný popis šifry lze nalézt na Wikipedii. K dalšímu vysvětlení útoku však budeme potřebovat řadu definic, které je nejlépe zavést předem.DES je tedy bloková šifra založená na síti Feistel. Šifra má velikost bloku 64 bitů a velikost klíče 56 bitů. Podívejme se na šifrovací schéma algoritmu DES. 
Jak je vidět z obrázku, při šifrování textu se provádějí následující operace:
- Počáteční bitová permutace. V této fázi jsou bity vstupního bloku zamíchány v určitém pořadí.
- Poté se smíšené bity rozdělí na dvě poloviny, které se přivedou na vstup funkce Feistel. Pro standardní DES síť Feistel obsahuje 16 kol, ale existují i jiné varianty algoritmu.
- Dva bloky získané v posledním kole transformace se spojí a na výsledném bloku se provede další permutace.
V každém kole Feistelovy sítě je nejméně významných 32 bitů zprávy předáno funkcí f: 
Podívejme se na operace prováděné v této fázi:
- Vstupní blok prochází rozšiřující funkcí E, která převádí 32bitový blok na 48bitový blok.
- Výsledný blok se přidá ke kulatému klíči K i.
- Výsledek předchozího kroku je rozdělen do 8 bloků po 6 bitech.
- Každý z přijatých bloků B i prochází substituční funkcí S-Box i, která nahrazuje 6bitovou sekvenci 4bitovým blokem.
- Výsledný 32bitový blok prochází permutací P a vrací se jako výsledek funkce f.
Z hlediska šifrovací kryptoanalýzy nás nejvíce zajímají S bloky, které mají skrýt spojení mezi vstupními a výstupními daty funkce f. Abychom úspěšně zaútočili na DES, nejprve zkonstruujeme statistické analogy pro každý z S-boxů a poté je rozšíříme na celou šifru.
Analýza bloku S
Každý S-box přijímá jako vstup 6bitovou sekvenci a pro každou takovou sekvenci je vrácena pevná 4bitová hodnota. Tito. k dispozici je celkem 64 možností vstupu a výstupu. Naším úkolem je ukázat vztah mezi vstupními a výstupními daty S bloků. Například pro třetí S-box šifry DES je 3. bit vstupní sekvence roven 3. bitu výstupní sekvence ve 38 ze 64 případů, a proto jsme pro třetí S našli následující statistickou analogii -box:S 3 (x) = x, což je splněno s pravděpodobností P=38/64.
Obě strany rovnice představují 1 bit informace. Pokud by tedy levá a pravá strana byly na sobě nezávislé, rovnice by musela být splněna s pravděpodobností 1/2. Tak jsme právě ukázali vztah mezi vstupem a výstupem 3. S-boxu algoritmu DES.
Uvažujme, jak můžeme najít statistickou analogii S-boxu v obecném případě.
Pro S-box S a, 1 ≤ α ≤ 63 a 1 ≤ β ≤ 15 hodnota NS a (α, β) popisuje, kolikrát ze 64 možných XOR vstupních bitů S a superponovaných na α bitech je rovno výstupní bity XOR superponované na α bitech β, tj.:
kde symbol je logické AND.
Hodnoty α a β, pro které se NS a (α, β) nejvíce liší od 32, popisují nejúčinnější statistickou analogii S-boxu Sa.
Nejúčinnější analog byl nalezen v 5. S-boxu šifry DES pro α = 16 a β = 15 NS 5 (16, 15) = 12. To znamená, že platí následující rovnice: Z=Y ⊕ Y ⊕ Y ⊕ Y, kde Z je vstupní sekvence S-boxu a Y je výstupní sekvence.
Nebo s přihlédnutím k tomu, že v algoritmu DES jsou před vstupem do S-boxu data doplněna modulo 2 s kulatým klíčem, tzn. Z = X ⊕ K dostaneme
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, kde X a Y jsou vstupní a výstupní data funkce f bez zohlednění permutací.
Výsledná rovnice je provedena ve všech kolech algoritmu DES se stejnou pravděpodobností P=12/64.
V následující tabulce je uveden seznam účinných, tzn. mající největší odchylku od P=1/2, statistické analogy pro každý s-blok algoritmu DES. 
Konstrukce statistických analogů pro více kol DES
Ukažme si nyní, jak můžeme kombinovat statistické analogy několika kol DES a nakonec získat statistickou analogii pro celou šifru.Chcete-li to provést, zvažte tříkolovou verzi algoritmu:
Použijme efektivní statistickou analogii 5. s-boxu k výpočtu určitých bitů hodnoty X(2).
Víme, že s pravděpodobností 12/64 platí rovnost ve f-funkci X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, kde X je druhý vstupní bit 5. S-boxu, je to v podstatě 26. bit sekvence získané po rozšíření vstupních bitů. Analýzou expanzní funkce můžeme stanovit, že 26. bit je nahrazen 17. bitem sekvence X(1).
Podobně Y,..., Y jsou v podstatě 17., 18., 19. a 20. bity sekvence získané před permutací P. Prozkoumáním permutace P zjistíme, že bity Y,..., Y jsou ve skutečnosti bity Y (1), Y(1), Y(1), Y(1).
Klíčový bit K zahrnutý v rovnicích je 26. bit prvního kola podklíče K1 a poté má statistická analogie následující podobu:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Proto, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) s pravděpodobností P=12/64.
Když znáte 3, 8, 14, 25 bitů sekvence Y(1), můžete najít 3, 8, 14, 25 bitů sekvence X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) nebo s přihlédnutím k rovnici (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) s pravděpodobností 12/64.
Pojďme najít podobný výraz pomocí posledního kola. Tentokrát máme rovnici
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Protože
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
dostaneme to
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4)
s pravděpodobností 12/64.
Získáme rovnítko pro pravé strany rovnic (3) a (4).
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 s pravděpodobností (12/64) 2 + (1-12/64) 2.
Vezmeme-li v úvahu skutečnost, že X(1) = PR a X(3) = CR, získáme statistickou analogii
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5)
,
který se provede s pravděpodobností (12/64) 2 + (1-12/64) 2 =0,7.
Výše popsanou statistickou analogii lze graficky znázornit následovně (bity na obrázku jsou číslovány zprava doleva a začínající od nuly): 
Všechny bity na levé straně rovnice jsou útočníkovi známy, takže může použít Algoritmus 1 a zjistit hodnotu K1 ⊕ K3. Pojďme si ukázat, jak pomocí tohoto statistického analogu můžete otevřít ne 1, ale 12 bitů šifrovacího klíče K.
Útok na DES se známým prostým textem
Dovolte nám představit metodu, pomocí které můžete rozšířit útok a okamžitě získat 6 bitů připojení prvního kola.Při sestavování rovnice (5) jsme brali v úvahu skutečnost, že neznáme hodnotu F1(PR, K1). Proto jsme použili jeho statistický analog K1 ⊕ PR.
Vraťme místo výrazu K1 ⊕ PR hodnotu F1(PR, K1) a získáme následující rovnici:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , který bude proveden s pravděpodobností 12/64. Pravděpodobnost se změnila, protože jsme nechali pouze statistickou analogii ze třetího kola, všechny ostatní hodnoty jsou pevné.
Již výše jsme určili, že hodnota F1(PR, K1) je ovlivněna vstupními bity 5. S-boxu, konkrétně bity klíče K1 a bity bloku PR. Pojďme si ukázat, jak můžete obnovit hodnotu K1 tím, že budete mít pouze sadu otevřených/zavřených textů. K tomu použijeme Algoritmus 2.
Algoritmus 2
Nechť N je počet otevřených/uzavřených textových párů známých před útokem. Poté, abyste otevřeli klíč, musíte provést následující kroky.
Pro (i=0; i<64; i++) do
{
For(j=0; j
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) pak
Ti = Ti +1
}
}
Jako pravděpodobná posloupnost K1 se bere hodnota i taková, že výraz |Ti-N/2| má maximální hodnotu.
Při dostatečném počtu známých otevřených textů bude mít algoritmus vysokou pravděpodobnost, že vrátí správnou hodnotu šesti bitů podklíče K1 prvního kola. Vysvětluje se to tím, že pokud proměnná i nebude rovna K1, pak hodnota funkce F1(PR j, K) bude náhodná a počet rovnic pro takovou hodnotu i, pro kterou je levá strana rovný nule bude mít sklon k N/2. Pokud je podklíč uhodnut správně, bude se levá strana rovnat pevnému bitu K3 s pravděpodobností 12/64. Tito. dojde k výrazné odchylce od N/2.
Po přijetí 6 bitů podklíče K1 můžete podobně otevřít 6 bitů podklíče K3. Vše, co musíte udělat, je nahradit C za P a K1 za K3 v rovnici (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algoritmus 2 vrátí správnou hodnotu K3, protože proces dešifrování algoritmu DES je identický s procesem šifrování, pouze sekvence klíčů je obrácená. Takže v prvním kole dešifrování se použije klíč K3 a v posledním kole se použije klíč K1.
Po obdržení 6 bitů podklíčů K1 a K3 útočník obnoví 12 bitů společného klíče šifry K, protože kulaté klíče jsou obvyklou permutací klíče K. Počet otevřených textů požadovaných pro úspěšný útok závisí na pravděpodobnosti statistické analogie. K prolomení 12bitového 3kolového klíče DES stačí 100 párů veřejného/soukromého textu. K otevření 12 bitů 16kolového klíče DES bude zapotřebí asi 2 44 párů textů. Zbývajících 44 bitů klíče je otevřeno normální hrubou silou.
DES(Data Encryption Standard) – symetrický šifrovací algoritmus, ve kterém se jeden klíč používá pro šifrování i dešifrování dat. DES byl vyvinut společností IBM a schválen vládou USA v roce 1977 jako oficiální standard (FTPS 46-3). DES má 64bitové bloky a 16cyklovou síťovou strukturu Feistel, používá 56bitový klíč pro šifrování. Algoritmus využívá kombinaci nelineárních (S-boxy) a lineárních (permutace E, IP, IP-1) transformací. Pro DES se doporučuje několik režimů:Bloková šifra
Vstupními daty pro blokovou šifru je blok n bitů a k-bitový klíč. Výstupem je po aplikaci šifrovací transformace n-bitový šifrovaný blok a drobné rozdíly ve vstupních datech obvykle vedou k výrazné změně výsledku. Blokové šifry jsou implementovány opakovaným aplikováním určitých základních transformací na bloky zdrojového textu.Základní transformace:
Transformations by Feistel Network
Jedná se o transformaci přes vektory (bloky) představující levou a pravou polovinu posuvného registru. Algoritmus DES využívá při šifrování dopřednou transformaci Feistelovy sítě (viz obr. 1) a reverzní transformaci sítě Feistel při dešifrování (viz obr. 2).
Schéma šifrování algoritmu DES
Zdrojový text je 64bitový blok. Šifrovaný text je 64bitový blok.
Proces šifrování se skládá z počáteční permutace, 16 šifrovacích cyklů a konečné permutace.
Podívejme se na podrobné schéma algoritmu DES:
L i R i =1,2\ldots.levá a pravá polovina 64bitového bloku L i R i
k i - 48bitové klíče
f - funkce šifrování
IP - počáteční permutace
IP -1 - konečná permutace. 
Podle tabulky jsou první 3 bity výsledného bloku IP(T) po počáteční permutaci IP bity 58, 50, 42 vstupního bloku T a jeho poslední 3 bity jsou bity 23, 15, 7 vstupní blok. Dále se 64bitový blok IP(T) účastní 16 cyklů Feistelovy transformace.
16 cyklů Feistelovy transformace:
Rozdělte IP(T) na dvě části L0,R0, kde Lo,R0 je 32 nejvýznamnějších bitů a 32 nejméně významných bitů bloku T0 IP(T)= L0R0, v tomto pořadí.
Nechť T i -1 = L i -1 R i -1 výsledek (i-1) iterace, pak se určí výsledek i-té iterace T i = L i R i:
Li = Ri-1 Levá polovina L i se rovná pravé polovině předchozího vektoru L i - 1 R i - 1 . A pravá polovina R i je bitový součet Li - 1 a f(R i - 1, k i) modulo 2.
V 16-cyklové Feistelově transformaci hraje funkce f roli šifrování. Podívejme se na funkci f podrobně.
Argumenty funkce f jsou 32bitový vektor R i-1, 48bitový klíč ki, které jsou výsledkem převodu 56bitového původního šifrového klíče k.
Pro výpočet funkce f se používá expanzní funkce E, transformace S skládající se z 8 transformací S-boxu a permutace P.
Funkce E rozšiřuje 32bitový vektor R i - 1 na 48bitový vektor E(R i - 1) duplikací některých bitů z R i - 1, přičemž pořadí bitů vektoru E(R i - 1 ) je uvedeno v tabulce 2. 
První tři bity vektoru E(R i-1) jsou bity 32, 1, 2 vektoru Rj-1. Tabulka 2 ukazuje, že bity 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 jsou duplikovány. Poslední 3 bity vektoru E(Ri - 1) jsou bity 31, 32, 1 vektoru Ri - 1. Blok E(Ri-1) získaný po přeskupení je přidán modulo 2 s klíči ki a poté prezentován ve formě osmi po sobě jdoucích bloků B1, B2,...B8.
E(Ri-1) = B1B2...B8
Každý Bj je 6bitový blok. Dále je každý z bloků B j transformován na 4bitový blok B" j pomocí transformací S j. Transformace S j jsou určeny tabulkou 3. Předpokládejme, že B 3 = 101111 a chceme najít B" 3. První a poslední bit B 3 jsou binární reprezentace čísla a, 0. Hodnotu funkce f(R i - 1,k i) (32 bitů) získáme permutací P aplikovanou na 32bitový blok B " 1 B" 2 ...B" 8. Permutace P je dána tabulkou 4. 
f(R i - 1, ki) = P(B" 1 B" 2 ...B" 8)
Podle tabulky 4 jsou první čtyři bity výsledného vektoru po působení funkce f bity 16, 7, 20, 21 vektoru B" 1 B" 2 ...B" 8
Generování klíčů k i .
Klíče ki se tímto způsobem získají z počátečního klíče k (56 bitů = 7 bajtů nebo 7 znaků ASCII). Osm bitů umístěných na pozicích 8, 16, 24, 32, 40, 48, 56, 64 je přidáno ke klíči k, takže každý bajt obsahuje lichý počet jedniček. To se používá k detekci chyb při výměně a ukládání klíčů. Poté se provede permutace pro rozšířený klíč (kromě přidaných bitů 8, 16, 24, 32, 40, 48, 56, 64). Tato permutace je definována jako v tabulce 5. 
Tato permutace je definována dvěma bloky Co a D0 po 28 bitech. První 3 bity C0 jsou bity 57, 49, 41 rozšířeného klíče. A první tři bity D0 jsou bity 63, 55, 47 rozšířeného klíče. Ci,Di=1,2,3…jsou získány z Ci-i,Di-i jedním nebo dvěma cyklickými posuny doleva podle tabulky 6. 
Klíč k i, i=1,…16 se skládá ze 48 bitů vybraných z bitů vektoru C i D i (56 bitů) podle tabulky 7. První a druhý bit k i jsou bity 14, 17 vektoru C i D i 
Konečná permutace IP - 1 působí na T 16 a slouží k obnovení polohy. Je to opak permutace IP. Konečná permutace je určena tabulkou 8. 
Režimy použití DES DES lze použít ve čtyřech režimech.
Nejběžnějším a nejznámějším symetrickým šifrovacím algoritmem je DES (Standard šifrování dat). Algoritmus byl vyvinut v roce 1977 a byl přijat NIST (National Institute of Standards and Technology, USA) jako standard v roce 1980.
DES je klasická síť Feishtel se dvěma větvemi. Data jsou šifrována v 64bitových blocích pomocí 56bitového klíče. Algoritmus během několika kol převádí 64bitový vstup na 64bitový výstup. Délka klíče je 56 bitů. Proces šifrování se skládá ze čtyř fází. Prvním krokem je počáteční permutace (IP) 64bitového zdrojového textu (bělení), během níž se bity přeskupí podle standardní tabulky. Další fáze se skládá z 16 kol stejné funkce, která využívá operace posunu a substituce. Ve třetí fázi se prohodí levá a pravá polovina výstupu poslední (16.) iterace. Nakonec čtvrtá fáze provede permutaci IP-1 výsledku získaného ve třetí fázi. Permutace IP-1 je inverzní k počáteční permutaci.
Obr.4. Algoritmus DES
Obrázek ukazuje metodu, která používá 56bitový klíč. Zpočátku je klíč přiveden na vstup permutační funkce. Potom pro každé ze 16 kol je podklíč Kj kombinací levého kruhového posunu a permutace. Permutační funkce je pro každé kolo stejná, ale podklíče Ki pro každé kolo se liší v důsledku opakovaného posunu bitů klíče.
Počáteční permutace a její inverze jsou určeny standardní tabulkou. Jestliže M je libovolných 64 bitů, pak X = IP(M) je přeskupených 64 bitů. Pokud použijeme inverzní permutační funkci Y = IP-1 (X) = IP-1 (IP(M)), dostaneme původní bitovou sekvenci.
Popis kulatého des
Podívejme se na posloupnost transformací použitých v jednotlivých kolech.
Obr.5. Ilustrace kola algoritmu DES
64bitový vstupní blok prochází 16 kola, přičemž každá iterace vytváří střední 64bitovou hodnotu. Levá a pravá strana každé mezilehlé hodnoty jsou považovány za samostatné 32bitové hodnoty, označené L a R. Každou iteraci lze popsat následovně:
Ri = Li-1 F(Ri-1, Ki)
Výstup levé poloviny L i je tedy roven vstupu pravé poloviny R i-1. Výstup pravé poloviny Ri je výsledkem aplikace operace XOR na Li-1 a funkce F v závislosti na Ri-1 a Ki.
Podívejme se na funkci F podrobněji. Ri, který je přiveden na vstup funkce F, má délku 32 bitů. Nejprve se R i rozšíří na 48 bitů pomocí tabulky, která specifikuje permutaci plus 16bitové rozšíření. Expanze probíhá následovně. 32 bitů je rozděleno do skupin po 4 bitech a poté rozšířeno na 6 bitů přidáním nejvzdálenějších bitů ze dvou sousedních skupin. Například pokud je součástí vstupní zprávy
Efgh ijkl mnop . . .
pak výsledkem expanze je zpráva
Defghi hijklm lmnopq. . .
Výsledná 48bitová hodnota je pak XORed pomocí 48bitového podklíče Ki. Výsledná 48bitová hodnota je poté přivedena do substituční funkce, jejímž výsledkem je 32bitová hodnota.
Substituce se skládá z osmi S-boxů, z nichž každý přijímá 6 bitů jako vstup a produkuje 4 bity jako výstup. Tyto transformace jsou definovány speciálními tabulkami. První a poslední bit vstupní hodnoty S-boxu určují číslo řádku v tabulce, prostřední 4 bity určují číslo sloupce. Průsečík řádku a sloupce určuje 4bitový výstup. Pokud je například vstup 011011, pak číslo řádku je 01 (řádek 1) a číslo sloupce je 1101 (sloupec 13). Hodnota v řádku 1 a sloupci 13 je 5, tzn. výstup je 0101.
Výsledná 32bitová hodnota je následně zpracována pomocí permutace P, jejímž účelem je co nejvíce přeuspořádat bity tak, aby v dalším kole šifrování byl každý bit pravděpodobně zpracován jiným S-boxem.
Klíč pro jednotlivé kolo K i se skládá ze 48 bitů. Klíče Ki se získají pomocí následujícího algoritmu. Pro 56bitový klíč použitý jako vstup do algoritmu se nejprve provede permutace v souladu s tabulkou Permuted Choice 1 (PC-1). Výsledný 56bitový klíč je rozdělen na dvě 28bitové části, označené jako C0 a D0. V každém kole jsou Ci a Di nezávisle cyklicky posunuty doleva o 1 nebo 2 bity, v závislosti na čísle kola. Výsledné hodnoty jsou vstupem pro další kolo. Jsou také vstupem do Permuted Choice 2 (PC-2), který vytváří 48bitovou výstupní hodnotu, která je vstupem pro funkci F(R i-1, K i).
Proces dešifrování je podobný procesu šifrování. Vstupem do algoritmu je šifrovaný text, ale klíče K i se používají v opačném pořadí. K 16 se použije v prvním kole, K 1 se použije v posledním kole. Nechť výstup i-tého šifrovacího kola je L i ||R i . Potom odpovídající vstup (16-i)-tého dešifrovacího kola bude R i ||L i.
Po posledním kole dešifrovacího procesu se obě poloviny výstupu prohodí tak, že vstup konečné permutace IP-1 je R 16 ||L 16 . Výstupem této fáze je prostý text.
Který ANSI nazývá algoritmus šifrování dat DEA (Data Encryption Algorithm) a ISO jej nazývá DEA-1, se za 20 let stal světovým standardem. Za léta své existence odolal náporu různých útoků a s určitými omezeními je stále považován za kryptoodolný.
DES je bloková šifra, která šifruje data v 64bitových blocích. Na jednom konci algoritmu je vložen 64bitový blok prostého textu a na druhém konci je výstupem 64bitový blok šifrovaného textu. DES je symetrický algoritmus: pro šifrování a dešifrování se používá stejný algoritmus a klíč (až na drobné rozdíly v použití klíče). Délka klíče je 56 bitů. (Klíč je obvykle reprezentován jako 64bitové číslo, ale každý osmý bit se používá pro paritu a je ignorován. Paritní bity jsou nejméně významné bity z bajtů klíče.) Klíč, kterým může být libovolné 56bitové číslo , lze kdykoli změnit.
Kryptografická síla je zcela určena klíčem. Základním stavebním kamenem DES je kombinace substitucí a permutací. DES se skládá ze 16 cyklů.
Celkový pohled na konverzní cyklus:
Jestliže L i a R i jsou levá a pravá polovina vyplývající z ité iterace, K i je 48bitový klíč pro smyčku i a f je funkce, která na klíči provádí všechny substituce, permutace a XOR, pak jedna konverzní smyčka může být reprezentována jako:
S přihlédnutím k substituci F i (*) a permutaci T (*) lze transformační cyklus znázornit tak, jak je znázorněno na Obr.
Je vidět, že každý cyklus DES je kompoziční šifra se dvěma po sobě jdoucími transformacemi - substitucí F i (*) a permutací T (*) (s výjimkou posledního, šestnáctého cyklu, kde je permutace vynechána).
Náhrada:
(L i, R i) = (R i −1, Li −1) ⊕ f (R i −1, K)
je involucí, protože
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 , Li −1 ⊕ (f (R i −1, K i)) ⊕ (f (R i −1, K i))) = (L i −1, R i −1)
A substituce
T (L i', Ri') = (Ri', Li'),
je také involucí, protože
T (T (L i ', R i ')) = T (R i ', Li ') = L i ', R i '
Označíme-li počáteční a konečnou permutaci jako (IP) a (IP) − 1, pak přímá transformace DES (šifrování) implementuje funkci:
DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1 ,
a zpětná transformace DES (dešifrování) implementuje funkci:
DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).
DES je tedy Feistelova šifra a je navržena tak, aby splňovala užitečnou vlastnost, že stejný algoritmus se používá pro šifrování a dešifrování. Jediný rozdíl je v tom, že klíče musí být použity v opačném pořadí.
To znamená, že pokud byly během šifrování použity klíče K 1, K 2, K 3, ..., K 16, pak dešifrovací klíče budou K 16, K 15, K 14, ..., K 1. Algoritmus používá pouze standardní 64bitové aritmetické a logické operace, takže jej lze snadno implementovat do hardwaru.
DES pracuje na 64bitovém bloku prostého textu. Po počátečním promíchání se blok rozdělí na pravou a levou polovinu po 32 bitech. Poté se provede 16 transformací (funkce f), ve kterých jsou data kombinována s klíčem. Po šestnáctém cyklu se spojí pravá a levá polovina a algoritmus končí konečnou permutací (opakem originálu). V každém cyklu (viz obrázek) jsou bity klíče posunuty a poté je vybráno 48 bitů z 56 bitů klíče. Pravá polovina dat je rozšířena na 48 bitů pomocí expanzní permutace, XORed pomocí 48 bitů posunutého a permutovaného klíče, prochází 8 S-boxy za vzniku 32 nových bitů a znovu permutována. Tyto čtyři operace provádí funkce f.
Výsledek f se pak spojí s levou polovinou pomocí dalšího XOR. V důsledku těchto akcí se objeví nová pravá polovina a ze staré pravé se stane nová levá polovina. Tyto kroky se opakují 16krát, což vede k 16 cyklům DES.
Ruská norma - GOST 28147-89
GOST 28147-89 je bloková šifra s 256bitovým klíčem a 32 cykly konverze, pracující na 64bitových blocích. Kryptoalgoritmus také používá další klíč, který je popsán níže. Pro šifrování je prostý text nejprve rozdělen na levou a pravou polovinu L a R. V i-tém cyklu se používá podklíč K i:
L i = R i −1,
R i = L i -1 ⊕ (f (R i - 1, K i)).
Funkce f je implementována následovně. Nejprve se přidá pravá polovina a i-tý podklíč modulo 2 32. Výsledek je rozdělen do osmi 4bitových podsekvencí, z nichž každá je vložena do vlastního S-boxu. GOST používá osm různých S-boxů, první 4 bity jdou do prvního S-boxu, druhé 4 bity do druhého S-boxu atd. Každý S-box je permutací čísel od 0 do 15. Například, S-box může vypadat takto: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. V tomto případě, pokud je vstup S-boxu 0, pak výstup je 7. Pokud je vstup 1, výstup je 10 atd. Všech osm S-boxů je odlišných, jsou vlastně dalším klíčovým materiálem. Výstupy všech osmi S-boxů jsou sloučeny do 32bitového slova, poté je celé slovo otočeno doleva o 11 bitů. Nakonec je výsledek XORed s levou polovinou, aby se vytvořila nová pravá polovina, a pravá polovina se stane novou levou polovinou. Pro generování podklíčů je původní 256bitový klíč rozdělen do osmi 32bitových bloků: k 1, k 2, ..., k 8. Každý cyklus používá svůj vlastní podklíč. Dešifrování se provádí stejným způsobem jako šifrování, ale pořadí podklíčů k i je obrácené. Norma nespecifikuje, jak se S-boxy generují.
Hlavní rozdíly mezi DES a GOST
Hlavní rozdíly mezi DES a GOST jsou následující:
- DES používá složitou proceduru ke generování podklíčů z klíčů. V GOST je tento postup velmi jednoduchý;
- v DES je 56bitový klíč a v GOST je 256bitový. Pokud přidáme tajné permutace S-boxů, bude celkový objem tajných informací GOST přibližně 610 bitů;
- DES S-boxy mají 6bitové vstupy a 4bitové výstupy, zatímco GOST S-boxy mají 4bitové vstupy a výstupy. Oba algoritmy používají osm S-boxů, ale velikost GOST S-boxu je rovna čtvrtině velikosti DES S-boxu;
- DES používá nepravidelné permutace zvané P-blok, zatímco GOST používá 11bitový cyklický posun doleva;
- v DES je 16 cyklů a v GOST - 32.
Silný útok na GOST je naprosto marný. GOST používá 256bitový klíč a pokud vezmete v úvahu tajné S-boxy, bude délka klíče ještě větší. GOST se zdá být odolnější vůči diferenciální a lineární kryptoanalýze než DES. I když náhodné GOST S-boxy, pokud mají určitý výběr, nezaručují vysokou kryptografickou sílu ve srovnání s pevnými DES S-boxy, jejich utajení zvyšuje odolnost GOST vůči diferenciální a lineární kryptoanalýze. Navíc účinnost těchto kryptoanalytických metod závisí na počtu konverzních cyklů – čím více cyklů, tím obtížnější je kryptoanalýza. GOST používá dvakrát tolik cyklů než DES, což může způsobit selhání diferenciální a lineární kryptoanalýzy.
GOST nepoužívá permutaci rozšíření existující v DES. Odstranění této permutace z DES jej oslabuje snížením lavinového efektu; Je rozumné předpokládat, že absence takové operace v GOST má negativní dopad na její kryptografickou sílu. Z hlediska šifrovací síly není operace aritmetického sčítání používaná v GOST o nic horší než operace XOR v DES.
Hlavním rozdílem se zdá být použití cyklického posunu místo permutace v GOST. Přeuspořádání DES zvyšuje lavinový efekt. V GOST změna jednoho vstupního bitu ovlivní jeden S-box jednoho konverzního cyklu, který pak ovlivní dva S-boxy dalšího cyklu, poté tři bloky dalšího cyklu atd. Trvá osm cyklů, než změna jednoho vstupního bitu ovlivní každý bit na výstupu; v DES to vyžaduje pouze pět cyklů. GOST se však skládá z 32 cyklů a DES pouze z 16.
Vývojáři GOST se snažili dosáhnout rovnováhy mezi kryptografickou silou a účinností. S využitím Feistelova návrhu jako základu vyvinuli kryptografický algoritmus, který se lépe hodí pro softwarovou implementaci než DES. Pro zvýšení šifrovací síly byl zaveden extra dlouhý klíč a počet cyklů byl zdvojnásoben. Otázka, zda bylo úsilí vývojářů korunováno vytvořením kryptografičtějšího algoritmu než DES, však zůstává otevřenou.
Vorobyová E., Lukyanova A.
Algoritmus DES
Hlavní výhody algoritmu DES:
· je použit pouze jeden klíč o délce 56 bitů;
· po zašifrování zprávy pomocí jednoho balíčku můžete k dešifrování použít jakýkoli jiný;
· relativní jednoduchost algoritmu zajišťuje vysokou rychlost zpracování informací;
· dostatečně vysoká stabilita algoritmu.
DES šifruje 64bitové bloky dat pomocí 56bitového klíče. Dešifrování v DES je obrácená operace šifrování a provádí se opakováním šifrovacích operací v opačném pořadí (i přes zdánlivou samozřejmost to není vždy provedeno. Později se podíváme na šifry, ve kterých se šifrování a dešifrování provádí pomocí různých algoritmů).
Proces šifrování se skládá z počáteční permutace bitů 64bitového bloku, šestnácti šifrovacích cyklů a nakonec zpětné permutace bitů (obr. 1).
Ihned je třeba poznamenat, že VŠECHNY tabulky uvedené v tomto článku jsou STANDARDNÍ, a proto by měly být součástí vaší implementace algoritmu beze změny. Všechny permutace a kódy v tabulkách vybírají vývojáři tak, aby výběrem klíče co nejvíce ztížili proces dešifrování. Struktura algoritmu DES je znázorněna na obr. 2.
Obr.2. Struktura šifrovacího algoritmu DES
Necháme načíst další 8bajtový blok T ze souboru, který je transformován pomocí počáteční permutační matice IP (tabulka 1) takto: bit 58 bloku T se stane bitem 1, bit 50 bitem 2 atd., což bude výsledkem je: T(0) = IP(T).
Výsledná bitová sekvence T(0) je rozdělena do dvou sekvencí po 32 bitech: L(0) - levý nebo vyšší bit, R(0) - pravý nebo nižší bit.
Tabulka 1: Počáteční permutační matice 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
Poté se provede šifrování, které se skládá z 16 iterací. Výsledek i-té iterace je popsán pomocí následujících vzorců:
R(i) = L(i-1) xor f(R(i-1), K(i)),
kde xor je operace EXCLUSIVE OR.
Funkce f se nazývá šifrovací funkce. Jeho argumenty jsou 32bitová sekvence R(i-1), získaná v (i-1)-té iteraci, a 48bitový klíč K(i), který je výsledkem převodu 64bitového klíče K. Níže je podrobně popsána šifrovací funkce a algoritmus pro získání klíčů K(i).
Při 16. iteraci jsou získány sekvence R(16) a L(16) (bez permutace), které jsou zřetězeny do 64bitové sekvence R(16)L(16).
Poté se pozice bitů této sekvence přeskupí v souladu s maticí IP-1 (tabulka 2).
Tabulka 2: Inverzní permutační matice 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
Matice IP -1 a IP spolu souvisí takto: hodnota 1. prvku matice IP -1 je 40 a hodnota 40. prvku matice IP je 1, hodnota 2. prvek matice IP -1 je 8 a hodnota 8. prvku matice IP je rovna 2 atd.
Proces dešifrování dat je inverzní k procesu šifrování. Všechny kroky musí být provedeny v opačném pořadí. To znamená, že dešifrovaná data jsou nejprve přeskupena podle matice IP-1 a poté jsou provedeny stejné akce na sekvenci bitů R(16)L(16) jako v procesu šifrování, ale v opačném pořadí.
Iterativní proces dešifrování lze popsat pomocí následujících vzorců:
R(i-1) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) xor f(L(i), K(i)), i = 1,2,...,16.
Při 16. iteraci jsou získány sekvence L(0) a R(0), které jsou zřetězeny do 64bitové sekvence L(0)R(0).
Bitové pozice této sekvence se pak přeskupí podle matice IP. Výsledkem takové permutace je původní 64bitová sekvence.
Nyní zvažte šifrovací funkci f(R(i-1),K(i)). Schematicky je to znázorněno na Obr. 3.
Obr.3. Výpočet funkce f(R(i-1), K(i))
Pro výpočet hodnoty funkce f se používají následující maticové funkce:
E - rozšíření 32bitové sekvence na 48bitovou,
S1, S2, ..., S8 - převod 6bitového bloku na 4bitový blok,
P - permutace bitů ve 32bitové sekvenci.
Expanzní funkce E je definována v tabulce 3. Podle této tabulky jsou první 3 bity E(R(i-1)) bity 32, 1 a 2 a poslední jsou 31, 32 a 1.
Tabulka 3: Funkce rozšíření 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
Výsledkem funkce E(R(i-1)) je 48bitová sekvence, ke které je přidán modulo 2 (operace xor) pomocí 48bitové klávesy K(i). Výsledná 48bitová sekvence je rozdělena do osmi 6bitových bloků B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). to je:
E(R(i-l)) xor K(i) = B(l)B(2)...B(8).
Funkce S1, S2, ..., S8 jsou definovány v tabulce 4.
Tabulka 4
K tabulce 4. je nutné další objasnění. Nechť je vstupem maticové funkce Sj 6bitový blok B(j) = b1b2b3b4b5b6, pak dvoubitové číslo b1b6 udává číslo řádku matice a b2b3b4b5 číslo sloupce. Výsledkem Sj(B(j)) bude 4bitový prvek umístěný na průsečíku zadaného řádku a sloupce.
Například B(1)=011011. Potom se S1(B(1)) nachází na průsečíku řádku 1 a sloupce 13. Ve sloupci 13 řádku 1 je hodnota 5. To znamená S1(011011)=0101.
Aplikováním operace výběru na každý z 6bitových bloků B(1), B(2), ..., B(8) získáme 32bitovou sekvenci S1(B(1))S2(B(2). ))S3(B(3))...S8(B(8)).
Nakonec, abychom získali výsledek šifrovací funkce, musí být bity této sekvence přeskupeny. K tomuto účelu se používá permutační funkce P (tabulka 5). Ve vstupní sekvenci se bity přeskupí tak, že z bitu 16 se stane bit 1, z bitu 7 se stane bit 2 a tak dále.
Tabulka 5: Permutační funkce P
Tím pádem,
f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))
Pro úplný popis algoritmu šifrování dat zbývá představit algoritmus pro získání 48bitových klíčů K(i), i=1...16. Při každé iteraci se použije nová hodnota klíče K(i), která se vypočítá z počátečního klíče K. K je 64bitový blok s osmi paritními bity umístěnými na pozicích 8,16,24,32,40,48, 56. 64.
K odstranění řídicích bitů a přeuspořádání zbytku se používá funkce G počáteční přípravy klíče (tabulka 6).
Tabulka 6
Matice G počáteční přípravy klíče
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
Výsledek transformace G(K) je rozdělen do dvou 28bitových bloků C(0) a D(0) a C(0) se bude skládat z bitů 57, 49, ..., 44, 36 klíče K, a D(0 ) se budou skládat z bitů 63, 55, ..., 12, 4 klíče K. Po definování C(0) a D(0), C(i) a D(i), i= 1...16, jsou určeny rekurzivně. Chcete-li to provést, použijte cyklický posun doleva o jeden nebo dva bity, v závislosti na čísle iterace, jak je uvedeno v tabulce 7.
Tabulka 7
Tabulka posunů pro výpočet klíče
| Iterační číslo | Shift (bity) |
| 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 |
Výsledná hodnota je opět „namíchána“ podle matice H (tabulka 8).
Tabulka 8: Klíčová matice 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
Klíč K(i) se bude skládat z bitů 14, 17, ..., 29, 32 sekvence C(i)D(i). Tím pádem:
K(i) = H(C(i)D(i))
Blokové schéma algoritmu výpočtu klíče je na obr. 4. Obr.
Obr.4. Blokové schéma algoritmu pro výpočet klíče K(i)
Obnovení původního textu se provádí pomocí tohoto algoritmu, ale nejprve použijete klíč
K(15), potom K(14) a tak dále. Nyní byste měli pochopit, proč autor vytrvale doporučuje používat dané matice. Pokud se zblázníte, můžete skončit s velmi tajným kódem, ale sami ho nerozluštíte!
Provozní režimy algoritmu DES
Aby byly plně splněny všechny požadavky na komerční šifrovací systémy, je implementováno několik režimů provozu algoritmu DES. Nejpoužívanější režimy jsou:
· elektronický číselník (Electronic Codebook) - ECB;
· řetězec digitálních bloků (Cipher Block Chaining) - CBC;
· digitální zpětná vazba (Cipher Feedback) - CFB;
· externí zpětná vazba (Output Feedback) - OFB.
V tomto režimu je zdrojový soubor M rozdělen na 64bitové bloky (každý 8 bajtů): M = M(1)M(2)...M(n). Každý z těchto bloků je zašifrován nezávisle pomocí stejného šifrovacího klíče (obr. 5). Hlavní výhodou tohoto algoritmu je jeho snadná implementace. Nevýhodou je, že je relativně slabý proti zkušeným kryptoanalytikům.
