Standardy blokových šifer. Algoritmus DES a jeho varianty

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 poskytuje vysoká 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ý je transformován pomocí počáteční permutační matice IP (tabulka 1) takto: bit 58 bloku T se stane bitem 1, bit 50 bit 2 atd. výsledkem je: 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 iterace je popsána následujícími vzorci:

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. Šifrovací funkce a algoritmus pro odvození klíčů K(i) jsou 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. prvek matice IP -1 je 8 a hodnota 8. prvku matice IP je 2 a tak dále.

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) a C(0) se bude skládat z bitů 57, 49, ..., 44, 36 z K. klíč a D(0 ) se bude 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 definovány rekurzivně. 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.

• 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í bity α. se rovnají XOR výstupních bitů překrývajících se na bitech β, tj.:
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. 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, při které levá strana se rovná 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.

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ý 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 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á 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 odvození 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 2 a tak dále.

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) se bude skládat z bitů 63, 55,…, 12, 4 klíče K. Po určení C(0) a D(0) budou C(i) a D(i), i=1 …16, jsou určeny rekurzivně. 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!

Algoritmus DES je docela vhodný jak pro šifrování, tak pro autentizaci dat. Umožňuje přímou konverzi 64bitového vstupu otevřeného textu na výstup 64bitového šifrovaného textu, ale data jsou zřídka omezena na 64 bitů.

Pro použití algoritmu DES pro řešení různých kryptografických problémů byly vyvinuty čtyři provozní režimy:

Elektronický číselník ECB (Electronic Code Book);

řetězení CBC šifrovacích bloků (Cipher Block Chaining);

zpětná vazba šifrovaného textu CFB (Cipher Feed Back);

zpětná vazba na výstupu OFB (Output Feed Back).

Režim "Elektronická kódová kniha".

Dlouhý soubor je rozdělen na 64bitové segmenty (bloky) po 8 bajtech. Každý z těchto bloků je zašifrován nezávisle pomocí stejného šifrovacího klíče (obrázek 3.6).

Hlavní výhodou je snadná implementace. Nevýhodou je relativně slabá odolnost vůči zkušeným kryptoanalytikům. Vzhledem k pevné povaze šifrování s omezenou délkou bloku 64 bitů je možná „slovníková“ kryptoanalýza. Blok této velikosti se může ve zprávě opakovat kvůli velké redundanci v textu v přirozeném jazyce.

Obrázek 3.6 - Schéma algoritmu DES v režimu elektronického číselníku

To způsobí, že identické bloky otevřeného textu ve zprávě jsou reprezentovány identickými bloky šifrovaného textu, což dává kryptoanalytikovi určitou informaci o obsahu zprávy.

Režim "Zřetězení šifrových bloků".

V tomto režimu je zdrojový soubor M rozdělen do 64bitových bloků: M = M 1 M 2 ... M n . První blok M 1 je modulo 2 s přidaným 64bitovým počátečním IV, který se denně mění a je uchováván v tajnosti (obrázek 3.7). Přijatá částka je poté zašifrována pomocí klíče DES známého odesílateli i příjemci informace. Výsledná 64bitová šifra C1 se přidá modulo 2 do druhého bloku textu, výsledek se zašifruje a získá se druhá 64bitová šifra C2 atd. Postup se opakuje, dokud nejsou zpracovány všechny bloky textu.

Pro všechna i = 1…n (n je počet bloků) je tedy výsledek šifrování С i určen následovně: С i =

DES (M i  C i –1), kde C 0 = IV je počáteční hodnota šifry, rovna počátečnímu vektoru (inicializačnímu vektoru).

Je zřejmé, že poslední 64bitový blok šifrovaného textu je funkcí tajného klíče, počátečního vektoru a každého bitu

Obrázek 3.7 - Schéma algoritmu DES v režimu řetězení šifrových bloků

prostý text bez ohledu na jeho délku. Tento blok šifrovaného textu se nazývá ověřovací kód zprávy (MAC).

MAC kód může být snadno ověřen příjemcem, který vlastní tajný klíč a počáteční vektor, opakováním postupu provedeného odesílatelem. Osoba zvenčí však nemůže vygenerovat CAS, který je příjemcem akceptován jako pravý, aby jej mohl přidat do návnady, nebo oddělit CAS od skutečné zprávy pro použití s ​​upravenou nebo návnadou.

Výhodou tohoto režimu je, že neumožňuje hromadění chyb během přenosu.

Blok Mi je funkcí pouze C i –1 a C i . Chyba přenosu tedy způsobí ztrátu pouze dvou bloků zdrojového textu.

Režim "Šifrovaná zpětná vazba".

V tomto režimu se může velikost bloku lišit od 64 bitů (obr.3.8). Soubor, který má být zašifrován (dešifrován), se čte v po sobě jdoucích blocích o k bitech (k=1…64).

Vstupní blok (64bitový posuvný registr) nejprve obsahuje inicializační vektor, zarovnaný vpravo.

Předpokládejme, že v důsledku rozdělení do bloků jsme dostali n bloků o délce k bitů každý (zbytek je připojen nulami nebo mezerami). Pak pro jakékoli i=1…n blok šifrovaného textu

C i \u003d M i  P i -1,

kde P i-1 označuje k nejvýznamnějších bitů předchozího zašifrovaného bloku.

Posuvný registr se aktualizuje vymazáním jeho horních k bitů a zápisem C i do registru. Obnova zašifrovaných dat je také poměrně jednoduchá: P i -1 a C i se počítají podobným způsobem a

M i \u003d C i  R i -1.

Obrázek 3.8 - Schéma algoritmu DES v režimu zpětné vazby šifrovaného textu

Režim výstupní zpětné vazby

Tento režim také používá proměnnou velikost bloku a posuvný registr inicializovaný stejným způsobem jako v režimu CFB, jmenovitě vstupní blok nejprve obsahuje inicializační vektor IV, zarovnaný vpravo (obrázek 3.9). V tomto případě je pro každou relaci šifrování dat nutné použít nový počáteční stav registru, který musí být odeslán kanálem jako prostý text.

M \u003d M 1 M 2 ... M n.

Pro všechna i = 1…n

C i \u003d M i  P i,

kde Р i je horních k bitů operace DES (С i –1).

Odlišností od režimu zpětné vazby šifrovaného textu je způsob aktualizace posuvného registru.

To se provádí vyřazením nejvýznamnějších k bitů a připojením P i doprava.

Obrázek 3.9 - Schéma algoritmu DES v režimu výstupní zpětné vazby

3.3. Oblasti použití algoritmu DES

Každý z uvažovaných režimů (ESB, SHS, CFB, OFB) má své výhody a nevýhody, což určuje oblasti jejich použití.

Režim ECB je vhodný pro šifrování klíčů: režim CFB je obvykle určen pro šifrování jednoho znaku, zatímco režim OFB se často používá pro šifrování v satelitních komunikačních systémech.

Pro autentizaci dat jsou vhodné režimy CBC a CFB. Tyto režimy vám umožňují používat algoritmus DES k:

· interaktivní šifrování během výměny dat mezi terminálem a hlavním počítačem;

Šifrování kryptografického klíče v praxi automatizované distribuce klíčů;

· šifrování souborů, pošty, satelitních dat a další praktické úkoly.

Původně byl standard DES určen pro šifrování a dešifrování počítačových dat. Jeho aplikace však byla zobecněna na autentizaci.

V systémech automatického zpracování dat není osoba schopna zobrazit data, aby zjistila, zda v nich byly provedeny nějaké změny. S obrovskými objemy dat procházejícími moderními systémy zpracování by procházení trvalo příliš dlouho. Navíc redundance dat nemusí být dostatečná k detekci chyb. I v případech, kdy je možné pozorování člověkem, lze data upravit tak, že pro člověka je velmi obtížné tyto změny detekovat. Například „do“ lze nahradit „ne“, „1900 $“ za „9100 $“. Bez dalších informací může člověk při prohlížení snadno zaměnit upravená data za pravá. Taková nebezpečí mohou existovat i při použití šifrování dat. Proto je žádoucí mít automatické prostředky pro detekci záměrných a neúmyslných změn dat.

Běžné kódy pro detekci chyb jsou nevhodné, protože pokud je znám algoritmus pro generování kódu, může protivník po provedení změn v datech vygenerovat správný kód. Pomocí algoritmu DES je však možné vytvořit kryptografický kontrolní součet, který může chránit před náhodnými i úmyslnými, ale neoprávněnými změnami dat.

Tento proces popisuje standard pro ověřování počítačových dat (FIPS 113). Podstatou standardu je, že data jsou šifrována v režimu zpětné vazby šifrovaného textu (režim CFB) nebo v režimu zřetězení šifrového bloku (režim CBC), výsledkem čehož je finální šifrový blok, který je funkcí všech bitů otevřeného textu. Zprávu, která obsahuje prostý text, lze poté přenést pomocí vypočítaného konečného bloku šifry, který slouží jako kryptografický kontrolní součet.

Stejná data lze chránit pomocí šifrování i ověřování. Data jsou chráněna před odhalením šifrováním a změny jsou detekovány autentizací. Autentizační algoritmus lze použít jak na prostý text, tak na šifrovaný text. Ve finančních transakcích, kdy je ve většině případů implementováno jak šifrování, tak autentizace, platí to druhé také pro otevřené

mu text.

K ochraně dat uložených v počítači se používá šifrování a ověřování. V mnoha počítačích jsou hesla nevratně zašifrována a uložena v paměti zařízení. Když uživatel přistoupí k počítači a zadá heslo, heslo je zašifrováno a porovnáno s uloženou hodnotou. Pokud jsou obě zašifrované hodnoty stejné, je uživateli povolen přístup k počítači, jinak je odepřen.

Často se pomocí algoritmu DES generuje zašifrované heslo a předpokládá se, že klíč je roven heslu a prostý text identifikačnímu kódu uživatele.

Pomocí algoritmu DES můžete také šifrovat počítačové soubory pro ukládání.

Jeden z nejdůležitější aplikace algoritmus DES je ochrana zpráv elektronického platebního styku (EPS) při transakcích s širokou klientelou a mezi bankami.

Algoritmus DES je implementován v bankomatech, POS terminálech, pracovních stanicích a hostitelských počítačích. Škála jím chráněných dat je velmi široká – od plateb 50 dolarů až po převody za mnoho milionů dolarů. Flexibilita základního algoritmu DES umožňuje jeho použití v široké škále aplikací elektronického platebního systému.