Algoritmus DES a jeho varianty. Šifrovací algoritmy DES a AES

• tutorial

Ahoj %username%!
Mnoho lidí ví, že výchozí standard v této oblasti symetrické šifrování na dlouhou dobu byl považován Algoritmus DES. 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 párů prostých/šifrovaných textů umožňuje otevřít Tajný klíčŠifra DES ve 243 operacích.
Pod střihem se pokusím shrnout hlavní body tohoto útoku.

Lineární kryptoanalýza

V obecném případě je útok založený na lineární kryptoanalýze redukován na následující podmínky. Útočník má velké množství dvojice prostý text/šifrovaný text získané 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ý analog, 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 Pn, Cn, Kn jsou n-té bity textu, šifrového textu a klíče.
Po nalezení takové rovnice může útočník obnovit 1 bit informací o klíči pomocí následujícího algoritmu

Algoritmus 1
Nechť T je počet textů, pro které levá strana rovnice (1) je tedy 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ěch algoritmu přímo závisí na hodnotě |P-1/2| a na počtu dostupných dvojic otevřeného textu/soukromého textu N. Čím více se pravděpodobnost P rovnosti (1) liší od 1/2, tím menší je počet otevřených textů N potřebných k útoku.

Pro úspěšnou implementaci útoku je třeba vyřešit dva problémy:

• Jak najít efektivní rovnici tvaru (1).
• Jak získat více než jeden bit informací o klíči pomocí takové rovnice.

Popis DES

DES je tedy bloková šifra založená na síti Feistel. Šifra má velikost bloku 64 bitů a velikost klíče 56 bitů. Zvažte schéma šifrování algoritmu DES.

Jak je vidět z obrázku, během šifrování se s textem provádějí následující operace:

1. Počáteční bitová výměna. V této fázi jsou bity vstupního bloku zamíchány v určitém pořadí.
2. Poté se zamíchané 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.
3. 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:

Zvažte operace provedené v této fázi:

1. Vstupní blok prochází rozšiřující funkcí E, která převádí 32bitový blok na 48bitový blok.
2. Výsledný blok se přidá ke kulatému klíči K i.
3. Výsledek předchozího kroku je rozdělen do 8 bloků po 6 bitech.
4. Každý z výsledných bloků B i prochází substituční funkcí S-Box i, která nahrazuje 6bitovou sekvenci 4bitovým blokem.
5. Výsledný 32bitový blok je předán permutací P a vrácen jako výsledek funkce f.

Nejzajímavější z hlediska kryptoanalýzy šifry jsou pro nás bloky S, 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é protějšky pro každý z S-boxů a poté je rozšíříme na celou šifru.

Analýza S bloků

Zvažte, jak můžete 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 překrývajících se na bitech α se rovná XOR na výstupních bitech, β překrývají bity
kde symbol je logické AND.
Hodnoty α a β, pro které se NS a (α, β) nejvíce liší od 32, popisují nejúčinnější statistický analog 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 permutací.
Výsledná rovnice je provedena ve všech kolech algoritmu DES se stejnou pravděpodobností P=12/64.
V následující tabulce jsou uvedeny efektivní, tzn. mající největší odchylku od P=1/2, statistické analogy pro každý s-blok algoritmu DES.

Vytváření statistických analogů pro více kol DES

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) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
dostaneme to
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3(4) s pravděpodobností 12/64.

Získáme rovnítko mezi pravé části rovnic (3) a (4).
СL ⊕ СL ⊕ СL ⊕ СL ⊕ 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 provádí s pravděpodobností (12/64) 2 +(1-12/64) 2 =0,7.
Výše popsaný statistický analog 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. Ukažme si, jak pomocí tohoto statistického analoga je možné otevřít ne 1, ale 12 bitů šifrovacího klíče K.

Útok na DES se známým prostým textem

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. Ukažme si, jak je možné obnovit hodnotu K1 tím, že máme pouze sadu otevřených/uzavřených textů. K tomu používáme 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 taková hodnota i, pro kterou platí výraz |T i -N/2| má maximální hodnotu.

S dostatečným počtem známých otevřených textů algoritmus s největší pravděpodobností vrátí správnou hodnotu šesti bitů podklíče K1 prvního kola. To se vysvětluje tím, že pokud proměnná i nebude rovna K1, pak bude hodnota funkce F1(PR j, K) náhodná a počet rovnic pro takovou hodnotu i, při které je levá strana rovna nule, bude mít tendenci k N/2. Pokud je podklíč uhodnut správně, bude levá část rovna 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 je k tomu potřeba, 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í, jen je obrácená sekvence klíčů. Takže v prvním kole dešifrování se použije klíč K3 a v posledním kole 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ů potřebných pro úspěšný útok závisí na pravděpodobnosti statistického protějšku. K prolomení 12bitového 3kolového klíče DES stačí 100 párů veřejného/soukromého textu. Prolomení 12bitového 16kolového klíče DES by vyžadovalo asi 244 párů textů. Zbývajících 44 bitů klíče se otevře obvyklým výčtem.

Anotace: Jedním z nejznámějších kryptografických systémů s privátním klíčem je DES – Data Encryption Standard. Tento systém jako první získal status státního standardu v oblasti šifrování dat. A přestože starý americký standard DES již ztratil svůj oficiální status, tento algoritmus si stále zaslouží pozornost při studiu kryptografie. Kromě toho tato přednáška vysvětluje, co je to „dvojitý DES“, útok „setkání uprostřed“ a jak jej opravit. Stejná přednáška krátce pojednává o novém americkém standardu blokové šifry, Rijndaelově algoritmu.

Účel přednášky: seznámit studenta se základními informacemi o šifrovacím algoritmu DES.

Základní informace

Jedním z nejznámějších kryptografických systémů se soukromým klíčem je DES - Data Encryption Standard. Tento systém jako první získal status státního standardu v oblasti šifrování dat. Byl vyvinut specialisty IBM a vstoupil v platnost v USA v roce 1977. Algoritmus DESširoce používané při ukládání a přenosu dat mezi různými výpočetními systémy; v poštovních systémech, v systémech elektronického kreslení a v elektronické výměně komerční informace. Standard DES implementovány jak softwarově, tak hardwarově. Podniky z různých zemí zahájily hromadnou výrobu digitálních zařízení pomocí DES pro šifrování dat. Všechna zařízení prošla povinnou certifikací pro shodu s normou.

Navzdory skutečnosti, že tento systém již nějakou dobu nemá status státního standardu, je stále široce používán a zaslouží si pozornost při studiu blokových šifer se soukromým klíčem.

Délka klíče v algoritmu DES je 56 bitů. Právě s touto skutečností je hlavní kontroverze týkající se schopnosti DES odolávat různým útokům. Jak víte, každou blokovou šifru se soukromým klíčem lze prolomit vyzkoušením všech možných kombinací klíčů. S délkou klíče 56 bitů je možných 256 různých klíčů. Pokud počítač vyčíslí 1 000 000 klíčů za jednu sekundu (což se přibližně rovná 220), pak bude vyjmenování všech 256 klíčů trvat 236 sekund nebo o něco více než dva tisíce let, což je samozřejmě pro útočníky nepřijatelné.

Nicméně dražší a rychlejší výpočetní systémy než Osobní počítač. Pokud je například možné zkombinovat milion procesorů pro paralelní výpočty, pak se maximální doba výběru klíče zkrátí na přibližně 18 hodin. Tato doba není příliš dlouhá a kryptoanalytik vybavený tak drahým vybavením může snadno provést útok šifrovaný DES v rozumném čase.

Zároveň lze poznamenat, že systém DES lze dobře použít v malých až středních aplikacích k šifrování dat malé hodnoty. K šifrování dat národního významu nebo významné komerční hodnoty systém DES v současné době by se samozřejmě neměl používat. V roce 2001, po speciálně vyhlášené soutěži ve Spojených státech, byl přijat nový standard blokových šifer, tzv. AES (Advanced Encryption Standard), který byl založen na šifře Rijndael vyvinuté belgickými specialisty. Tato šifra je diskutována na konci přednášky.

Hlavní nastavení DES: velikost bloku 64 bitů, délka klíče 56 bitů, počet kol - 16. DES je klasická síť Feishtel se dvěma větvemi. Algoritmus převádí 64bitový vstupní datový blok na 64bitový výstupní blok v několika kolech. Standard DES postavený na kombinovaném použití permutace, substituce a gamutingu. Šifrovaná data musí být v binární podobě.

Šifrování

Obecná struktura DES znázorněno na Obr. 4.1. Proces šifrování každého 64bitového bloku zdrojových dat lze rozdělit do tří fází:

1. počáteční příprava datového bloku;
2. 16 kol „hlavního cyklu“;
3. konečné zpracování datového bloku.

V první fázi, počáteční permutace 64bitový původní blok textu, během kterého se bity určitým způsobem přeuspořádají.

V další (hlavní) fázi je blok rozdělen na dvě části (větve) po 32 bitech. Pravá větev je transformována pomocí nějaké funkce F a odpovídající částečný klíč, získaný z hlavního šifrovacího klíče pomocí speciálního algoritmu konverze klíče. Poté dochází k výměně dat mezi levou a pravou větví bloku. Toto se opakuje 16x v cyklu.

Nakonec ve třetí fázi je výsledek získaný po šestnácti krocích hlavní smyčky permutován. Tato permutace je opakem původní permutace.

Rýže. 4.1.

Podívejme se podrobněji na všechny fáze kryptografické transformace podle standardu DES.

V první fázi prochází 64bitový blok zdrojových dat počáteční permutací. V literatuře se této operaci někdy říká „whitening“ – bělení. Během počáteční permutace se bity datového bloku určitým způsobem přeuspořádají. Tato operace vnáší do původní zprávy určitou „náhodnost“ a snižuje možnost použití kryptoanalýzy statistickými metodami.

Současně s počáteční permutací datového bloku je provedena počáteční permutace 56 bitů klíče. Z Obr. 4.1. je vidět, že v každém z kol je použit odpovídající 48bitový dílčí klíč Ki. Klíče Ki jsou získány podle určitého algoritmu, přičemž každý z bitů počátečního klíče se používá několikrát. V každém kole je 56bitový klíč rozdělen na dvě 28bitové poloviny. Poloviny se pak posunou doleva o jeden nebo dva údery, v závislosti na čísle kola. Po posunu se určitým způsobem vybere 48 z 56 bitů. Protože se tím nejen vybere podmnožina bitů, ale také se změní jejich pořadí, nazývá se tato operace operace „swap-swap“. Jeho výsledkem je sada 48 bitů. V průměru je každý bit původního 56bitového klíče použit ve 14 ze 16 podklíčů, i když ne všechny bity jsou použity stejně často.

Dále je proveden hlavní transformační cyklus organizovaný podle sítě Feishtel a sestávající z 16 stejných kol. V tomto případě se v každém kole (obr. 4.2) získá mezilehlá 64bitová hodnota, která je následně zpracována v dalším kole.

Levá a pravá větev každé mezihodnoty jsou považovány za samostatné 32bitové hodnoty, označené L a R .

Nejprve se pravá strana bloku R i rozšíří na 48 bitů pomocí tabulky, která definuje permutaci plus rozšíření o 16 bitů. Tato operace upraví velikost pravé poloviny tak, aby odpovídala velikosti klíče pro provedení operace XOR. Navíc se díky provedení této operace rychleji zvyšuje závislost všech bitů výsledku na bitech původních dat a klíče (říká se tomu „lavinový efekt“). Čím silnější je lavinový efekt při použití toho či onoho šifrovacího algoritmu, tím lépe.

Po provedení expanzní permutace je výsledná 48bitová hodnota XORed s 48bitovým podklíčem Ki. Poté je výsledná 48bitová hodnota přivedena na vstup substitučního bloku S (z angl. Substituce - substituce), výsledek což je 32bitová hodnota . Střídání se provádí v osmi střídačích nebo osmi S-boxech. Při provádění tohoto DES vypadá na papíře poměrně složitě, natož jeho softwarová implementace! Vypracujte správně a optimálně fungující program zcela v souladu s DES asi jen pro zkušené programátory. Některé potíže vznikají při implementaci softwaru, jako je počáteční permutace nebo expanzní permutace. Tyto potíže souvisejí s tím, že se původně počítalo s realizací DES pouze v hardwaru. Všechny operace používané ve standardu jsou snadno prováděny hardwarovými jednotkami a s implementací nejsou žádné potíže. Nějakou dobu po zveřejnění standardu se však vývojáři softwaru rozhodli nezůstat stranou a pustit se také do tvorby šifrovacích systémů. Dále DES implementovány jak hardwarově, tak softwarově.

Algoritmus DES

Hlavní výhody algoritmu DES:

Je použit pouze jeden 56bitový klíč;

· 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í;

poměrně 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 zřejmost to není vždy provedeno. Později se budeme zabývat šiframi, ve kterých se šifrování a dešifrování provádějí pomocí různých algoritmů).

Proces šifrování se skládá z počátečního bit-swapu 64-bitového bloku, šestnácti kol šifrování a nakonec reverzního bit-swapu (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ázku 2.

Obr.2. Struktura šifrovacího algoritmu DES

Necháme načíst další 8bajtový blok T ze souboru, který se transformuje pomocí počáteční permutační matice IP (tabulka 1) následovně: bit 58 bloku T se stane bitem 1, bit 50 - bit 2 atd., což bude mít za následek: T(0) = IP(T).

Výsledná bitová sekvence T(0) je rozdělena na dvě sekvence po 32 bitech: L(0) - levé nebo horní bity, R(0) - pravé nebo nízké bity.

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á při (i-1)-té iteraci a 48bitový klíč K(i), který je výsledkem konverze 64bitového klíče K. Šifrovací funkce a algoritmus odvozování klíče K(i) jsou podrobně popsány níže.

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).

Potom 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. prvku matice IP -1 je 8 a hodnota 8. prvku matice IP je 2 atd.

Proces dešifrování dat je opakem procesu šifrování. Všechny kroky musí být provedeny v opačném pořadí. To znamená, že data, která mají být dešifrována, se nejprve přeskupí podle matice IP-1 a poté se provedou stejné operace s bitovou sekvencí 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 této 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))

K výpočtu 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 je bitová permutace ve 32bitové sekvenci.

Rozšiřující 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ýsledkem je 48bitová sekvence, která 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

Ke stolu.4. jsou vyžadována další vysvětlení. 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)) je 4bitový prvek umístěný na průsečíku zadaného řádku a sloupce.

Například B(1)=011011. Potom se S1(В(1)) nachází na průsečíku řádku 1 a sloupce 13. Sloupec 13 řádku 1 je nastaven na 5. 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, abyste získali výsledek šifrovací funkce, musíte změnit uspořádání bitů této sekvence. K tomu se používá permutační funkce P (tabulka 5). Ve vstupní sekvenci jsou bity obráceny tak, že bit 16 se stane bitem 1, bit 7 bitem 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)))

K dokončení popisu algoritmu šifrování dat zbývá uvést 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.

Pro 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), kde C(0) se bude skládat z bitů 57, 49, ..., 44, 36 klíče K a D(0) bude sestávat z bitů 63, 55, ..., 12, 4 klíče K. Po definování C1 a D6 jsou znovu C(i)... kurzivně . K tomu se použije cyklický posun doleva o jeden nebo dva bity, v závislosti na iteračním čísle, jak je uvedeno v tabulce 7.

Tabulka 7

Tabulka posunů pro výpočet klíče

Výsledná hodnota je opět "namíchána" v souladu s maticí H (tabulka 8).

Tabulka 8: Klíčová dokončovací 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.4. Blokové schéma algoritmu pro výpočet klíče K(i)

Obnova původního textu se provádí podle tohoto algoritmu, ale nejprve použijete klíč

K(15), pak - K(14) a tak dále. Nyní byste měli pochopit, proč autor důrazně doporučuje používat výše uvedené matice. Pokud začnete svévolně chodit, musíte získat velmi tajnou šifru, ale sami ji později nebudete moci otevřít!

Provozní režimy algoritmu DES

Pro co nejúplnější uspokojení všech požadavků na komerční šifrovací systémy bylo 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 zakódován nezávisle pomocí stejného šifrovacího klíče (obrázek 5). Hlavní výhodou tohoto algoritmu je snadná implementace. Nevýhodou je relativně slabá odolnost vůči zkušeným kryptoanalytikům.

Standard DES je navržen tak, aby chránil před neoprávněným přístupem k citlivým, ale neutajovaným informacím ve vládních a komerčních organizacích USA. Algoritmus, který je základem standardu, se poměrně rychle rozšířil a již v roce 1980 byl schválen americkým Národním institutem pro standardy a technologie. Od této chvíle se DES stává standardem nejen jménem, ​​ale i fakticky. Existuje software a specializované mikropočítače určené k šifrování a dešifrování informací v datových sítích.

K dnešnímu dni je DES nejběžnějším algoritmem používaným v komerčních systémech informační bezpečnosti. Navíc se implementace algoritmu DES v takových systémech stává známkou dobrého vkusu.

Hlavní výhody algoritmu DES:

Je použit pouze jeden 56bitový klíč;

· 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í;

poměrně 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 zřejmost to není vždy provedeno. Později se budeme zabývat šiframi, ve kterých se šifrování a dešifrování provádějí pomocí různých algoritmů).

Proces šifrování se skládá z počáteční bitové výměny 64bitového bloku, šestnácti kol šifrování a nakonec zpětné výměny bitů (obrázek 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.

Rýže. 2.

Necháme načíst další 8bajtový blok T ze souboru, který se transformuje pomocí počáteční permutační matice IP (tabulka 1) následovně: bit 58 bloku T se stane bitem 1, bit 50 bit 2 atd., což bude mít za následek: T(0) = IP(T).

Výsledná bitová sekvence T(0) je rozdělena na dvě sekvence po 32 bitech: L(0) - levé nebo horní bity, R(0) - pravé nebo nízké bity.

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á při (i-1) - th iteraci a 48bitový klíč K(i), který je výsledkem konverze 64bitového klíče K. Šifrovací funkce a algoritmus pro odvození klíčů K(i) jsou podrobně popsány níže.

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. prvku matice IP -1 je 8 a hodnota 8. prvku matice IP je 2 atd.

Proces dešifrování dat je opakem procesu šifrování. Všechny kroky musí být provedeny v opačném pořadí. To znamená, že data, která mají být dešifrována, se nejprve přeskupí podle matice IP-1 a poté se provedou stejné operace s bitovou sekvencí 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 této 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.

Rýže. 3.

K výpočtu hodnoty funkce f se používají následující maticové funkce:

E - rozšíření 32bitové sekvence na 48bitovou,

S1, S2,…, S8 - převod 6bitových na 4bitové bloky,

P je bitová permutace ve 32bitové sekvenci.

Rozšiřující 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é se přidá modulo 2 (operace xor) pomocí 48bitové klávesy K(i). Získá se 48bitová sekvence, která 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-1)) x nebo K(i) = B(1) B(2)… B(8).

Funkce S1, S2, ..., S8 jsou definovány v tabulce. 4.

Tabulka 4

Ke stolu. 4. Jsou vyžadována další vysvětlení. 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. Sloupec 13 řádku 1 je nastaven na 5. Takže 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, abyste získali výsledek šifrovací funkce, musíte změnit uspořádání bitů této sekvence. K tomu se používá permutační funkce P (tabulka 5). Ve vstupní sekvenci jsou bity obráceny tak, že bit 16 se stane bitem 1, bit 7 bitem 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)))

K dokončení popisu algoritmu šifrování dat zbývá uvést 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.

Pro 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), kde C(0) se bude skládat z bitů 57, 49,…, 44, 36 klíče K a D(0) bude sestávat z bitů 63, 55,…, 12, 4 klíče K. Po určení C(i) a D(0) se určí znovu D(i) a C(0)…6 prakticky K tomu se použije cyklický posun doleva o jeden nebo dva bity, v závislosti na iteračním čísle, jak je uvedeno v tabulce 1. 7.

Tabulka 7. Tabulka posunů pro výpočet klíče

Výsledná hodnota je opět "namíchána" v souladu s maticí H (tabulka 8).

Tabulka 8: Klíčová dokončovací 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 znázorněno na Obr. 4.

Rýže. 4.

Obnova původního textu se provádí podle tohoto algoritmu, ale nejprve použijete klávesu K(15), poté K(14) a tak dále. Nyní byste měli pochopit, proč autor důrazně doporučuje používat výše uvedené matice. Pokud začnete svévolně chodit, musíte získat velmi tajnou šifru, ale sami ji později nebudete moci otevřít!

Snadná konverze mezi částmi bloku. Vzhledem k tomu, že transformace se provádí blok po bloku, jako samostatný krok je nutné rozdělit zdrojová data do bloků požadované velikosti. V tomto případě bez ohledu na formát zdrojových dat, ať už se jedná o textové dokumenty, obrázky nebo jiné soubory, je nutné je interpretovat do binární podoby a teprve poté rozdělit do bloků. Vše výše uvedené lze implementovat softwarovými a hardwarovými prostředky.

Síťové transformace Feistel

Jedná se o transformaci přes vektory (bloky) představující levou a pravou polovinu posuvného registru. Algoritmus DES využívá dopřednou transformaci sítí Feistel v šifrování (viz obr. 1) a inverzní transformaci sítí Feistel do dešifrování (viz obr. 2).

Schéma šifrování DES

Zdrojový text - blok 64 bitů.
Šifrovaný text je 64bitový blok.

Proces šifrování se skládá z počáteční permutace, 16 šifrovacích cyklů a konečné permutace.
Zvažte 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 je 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ího bloku. Dále se 64bitový blok IP(T) účastní 16 cyklů Feistelovy transformace.

16 cyklů Feistelovy transformace:

Rozdělte IP(T) na dvě části L 0 , R 0 , kde L 0 , R 0 je 32 vysokých bitů a 32 nízkých bitů bloku T0 IP(T)= L 0 R 0

Nechť T i -1 = L i -1 R i -1 je výsledek (i-1) iterace, pak výsledek i-té iterace T i = L i R i je určen:

Li = Ri-1 Levá polovina L i se rovná pravé polovině předchozího vektoru L i - 1 R i - 1 . A pravá polovina Ri je bitovým sčítáním Li-1 a f(Ri-1, ki) modulo 2.

V 16 cyklech Feistelovy transformace hraje funkce f roli šifrování. Podívejme se podrobně na funkci f.

Argumenty funkce f jsou 32bitový vektor R i-1, 48bitový klíč ki, které jsou výsledkem transformace 56bitového původního šifrového klíče k.

Pro výpočet funkce f se používá rozšiřující funkce E, transformace S, skládající se z 8 transformací S-boxů a permutace P.

Funkce E rozšiřuje 32bitový vektor R i - 1 na 48 bitový vektor E(R i - 1) duplikací některých bitů z R i - 1, přičemž bitové pořadí vektoru E(R i - 1) je specifikováno v tabulce 2. První tři bity vektoru E(Ri-1) jsou bity 32, 1, 2 vektoru Ri-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-i. Blok E(Ri-1) získaný po permutaci je přidán modulo 2 pomocí klíčů ki a poté prezentován jako osm 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ů Bj transformován na 4bitový blok B"j pomocí transformací Sj. Transformace Sj 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ím zápisem čí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 k i se získají z počátečního klíče k (56 bitů = 7 bajtů nebo 7 znaků v ASCII) tímto způsobem. Ke klíči k se přidá osm bitů umístěných na pozicích 8, 16, 24, 32, 40, 48, 56, 64, 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). Taková 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 Co 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… se získají z Cj-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 převrácená hodnota permutace IP. Konečná permutace je určena tabulkou 8.
Způsoby použití DES DES lze použít ve čtyřech režimech.

Režim elektronické kódové knihy (ECB): Běžné použití DES jako blokové šifry (viz obrázek 7).

Režim blokového řetězení (CBC - Cipher Block Chaining) (viz obr. 8). Každý další blok C i i>=1 před šifrováním je přidán modulo 2 s dalším blokem otevřeného textu Mi + 1 . Vektor C 0 je počáteční vektor, denně se mění a je držen v tajnosti.

Režim Cipher Feed Back (CFB) (viz obrázek 9). V režimu CFB je generován blok "gama" Z 0 ,Z 1 ,...Zi = DESk(C i - 1). Počáteční vektor Co je držen v tajnosti.

Režim Output Feed Back (OFB) (viz obr.10). V režimu OFB se generuje blok "gama" Z 0 ,Z 1 ,... , i>=1