Standardy blokových šifer. Šifrovací algoritmy DES a AES

Který ANSI nazývá DEA (Data Encryption Algorithm) algoritmus šifrování dat a ISO - 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. 64bitový blok prostého textu je na vstupu z jednoho konce algoritmu a 64bitový blok šifrovaného textu je na výstupu z druhého konce. DES je symetrický algoritmus: Pro šifrování a dešifrování se používá stejný algoritmus a klíč (s výjimkou malých rozdílů 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 transformační cyklus:

Jestliže L i a R i jsou levá a pravá polovina vyplývající z i-té iterace, K i je 48bitový klíč pro smyčku i a f je funkce, která pomocí klíče provádí všechny substituce, permutace a XOR, pak jednu konverzní smyčku si lze představit jako:

Vzhledem k substituci F i (*) a permutaci T (*) lze transformační cyklus znázornit tak, jak je to na Obr.

Je vidět, že každý cyklus DES je složená šifra se dvěma po sobě jdoucími transformacemi - substitucí F i (*) a permutací T (*) (kromě 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)

Náhrada

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 inverzní DES transformace (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 fungovala užitečná vlastnost: 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 pro šifrování použity klíče K1, K2, K3, ..., K16, pak dešifrovací klíče budou K16, K15, K14, ..., K1. Algoritmus používá pouze standardní aritmetiku 64bitových čísel a logické operace, takže je snadné jej implementovat do hardwaru.

DES pracuje na 64bitovém bloku prostého textu. Po počáteční permutaci 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í (obrácenou k původní). V každém cyklu (viz obrázek) se bity klíče posunou a poté se z 56 bitů klíče vybere 48 bitů. Pravá polovina dat se zvětší na 48 bitů pomocí rozšířené permutace, XORed se 48 bity posunutého a permutovaného klíče, projde 8 S-boxy za vzniku 32 nových bitů a znovu se permutuje. 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 akce se opakují 16krát a tvoří 16 cyklů 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. Kryptalgoritmus 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 přivedena na vstup svého S-boxu. GOST používá osm různých S-boxů, první 4 bity jdou do prvního S-boxu, druhé 4 bity jdou 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 různých, jsou to vlastně další klíčový materiál. Výstupy všech osmi S-boxů se spojí do 32bitového slova, poté se celé slovo otočí doleva o 11 bitů. Nakonec je výsledek XORed s levou polovinou, výsledkem je 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 nedefinuje, 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ý;
• DES má 56bitový klíč, zatímco GOST má 256bitový klíč. Pokud přidáme tajné permutace S-boxů, bude celkové množství tajných informací GOST přibližně 610 bitů;
• DES S-boxy mají 6bitové vstupy a 4bitové výstupy a GOST S-boxy mají 4bitové vstupy a výstupy. Oba algoritmy používají osm S-boxů, ale velikost GOST S-boxu je čtvrtina velikosti DES S-boxu;
• DES používá nepravidelné permutace, nazývané P-blok, a GOST používá 11bitový levý cyklický posun;
• v DES je 16 cyklů a v GOST - 32.

Mocenský útok na GOST je naprosto beznadějný. GOST používá 256bitový klíč, a pokud vezmete v úvahu tajné S-boxy, pak bude délka klíče ještě delší. GOST se zdá být odolnější vůči diferenciální a lineární kryptoanalýze než DES. Ačkoli náhodné GOST S-boxy s určitým výběrem 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 vést k selhání diferenciální a lineární kryptoanalýzy.

GOST nepoužívá expanzní permutaci, která existuje v DES. Odstranění této permutace z DES jej oslabí snížením lavinového efektu; je rozumné předpokládat, že absence takové operace v GOST má negativní vliv 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 je použití cyklického posunu v GOST namísto permutace. Záměna DES zvyšuje lavinový efekt. V GOST ovlivní změna jednoho vstupního bitu jeden S-box jednoho konverzního cyklu, který pak ovlivní dva S-boxy dalšího cyklu, poté tři bloky dalšího cyklu a tak dále. Trvá osm cyklů, než změna jednoho vstupního bitu ovlivní každý bit výsledku; v DES to trvá pouze pět cyklů. GOST se však skládá z 32 cyklů a DES pouze 16.

Vývojáři GOST se snažili dosáhnout rovnováhy mezi kryptografickou silou a účinností. Na základě Feistelova návrhu vyvinuli kryptalgoritmus, který je vhodnější pro softwarovou implementaci než DES. Pro zlepšení šifrovací síly byl zaveden extra dlouhý klíč a počet cyklů byl zdvojnásoben. Otázka, zda úsilí vývojářů vyústilo ve vytvoření kryptografického algoritmu, než je DES, však zůstává otevřená.

Vorobieva E., Lukyanova A.

• 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 holé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.

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ý 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-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. Š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.

Od přijetí algoritmu DES jako amerického šifrovacího standardu uplynulo více než 30 let. DES je šifrovací algoritmus s nejbohatší a nejzajímavější historií.

Historie vzniku algoritmu

Jeden z nejznámějších kryptologů světa Bruce Schneier ve své slavné knize Applied Cryptography takto popsal problémy uživatelů nástrojů informační bezpečnosti na počátku 70. let. XX století (samozřejmě mluvíme o uživatelích na druhé straně železné opony):

Neexistoval ani obecně přijímaný standard pro šifrování dat, ani jednoduše široce používané algoritmy zabezpečení informací, takže o kompatibilitě mezi různými šifrovacími software nebo hardwarem nemohla být řeč;

Téměř každý šifrovací nástroj byl „černou skříňkou“ s poněkud nejasným obsahem: jaký šifrovací algoritmus se používá, jak je kryptograficky silný, zda je správně implementován, zda jsou šifrovací klíče vytvořeny, uloženy, správně používány, zda existují nějaké nezdokumentované funkce vložené vývojáři do nástroje atd. – všechny tyto velmi důležité informace neměla drtivá většina kupujících kryptografických nástrojů k dispozici.

O tento problém se postaral National Bureau of Standards (NBS) USA. V důsledku toho byla v roce 1973 vyhlášena vůbec první otevřená soutěž na šifrovací standard. NBS byla ochotna pro výběr standardu prověřit algoritmy žadatelů, které splňují následující kritéria:

Algoritmus musí být kryptograficky silný;

Algoritmus musí být rychlý;

Struktura algoritmu by měla být jasná a přesná;

Síla šifrování by měla záviset pouze na klíči, samotný algoritmus by neměl být tajný;

Algoritmus by měl být snadno použitelný pro různé účely;

Algoritmus by měl být snadno implementován do hardwaru na stávající základně prvků.

Předpokládalo se, že zainteresované organizace či specialisté zašlou do NBS podrobné specifikace algoritmů dostatečné pro jejich implementaci, tedy bez „bílých míst“. Předpokládalo se také, že algoritmus bude certifikován NBS pro obecné použití, budou z něj odstraněna všechna patentová a exportní omezení, v důsledku čehož by takový standard musel vyřešit všechny problémy s kompatibilitou šifrovacích nástrojů. NBS navíc převzala funkce certifikace šifrovacích nástrojů – tedy „černé skříňky“ se měly nenávratně stát minulostí.

Ve skutečnosti existoval pouze jeden žadatelský algoritmus: byl to Luciferův šifrovací algoritmus vyvinutý CMM. (viz část 3.31). V průběhu dvou let byl algoritmus upřesněn:

Nejprve NBS společně s Národní bezpečnostní agenturou (NSA, NSA - National Security Agency) USA provedla důkladnou analýzu algoritmu, jejímž výsledkem bylo jeho poměrně významné zpracování;

Za druhé, připomínky a kritiky od všech zainteresovaných organizací a jednotlivců byly přijaty k posouzení.

Jako výsledek společné práce IBM, NBS a NSA byl v lednu 1977 publikován DES jako americký standard (nejnovější verze tohoto standardu je v dokumentu) pro algoritmus šifrování dat (s výjimkou informací o vysoké stupeň utajení). Algoritmus DES byl patentován UM, ale NBS ve skutečnosti získala bezplatnou a neomezenou licenci k použití tohoto algoritmu. Alternativní, ale méně běžně používaný název pro algoritmus je DEA (Data Encryption Algorithm).

Hlavní charakteristiky a struktura algoritmu

Algoritmus DES šifruje informace v blocích po 64 bitech pomocí 64bitového šifrovacího klíče, který používá pouze 56 bitů (postup rozšíření klíče je podrobně popsán níže).

Šifrování informací se provádí následovně (obr. 3.56):

1. Počáteční permutace se provede přes 64bitový datový blok podle tabulky. 3.16.

Tabulka 3.16

Tabulka je interpretována následovně: hodnota vstupního bitu 58 (dále jsou všechny bity číslovány zleva doprava, počínaje 1) se umístí do výstupního bitu 1, hodnota bitu 50 se umístí do bitu 2 atd.

2. Výsledek předchozí operace je rozdělen do 2 dílčích bloků po 32 bitech (per

rýže. 3,56 označeno A 0 a B 0), na kterých je vyrobeno 16 nábojů

následující transformace:

Jak bylo uvedeno výše, z 64bitového šifrovacího klíče používá algoritmus DES pouze 56 bitů. Každý 8. bit je zahozen a není v algoritmu nijak využit a použití zbývajících bitů šifrovacího klíče v implementacích algoritmu DES není standardem omezeno. Postup pro extrakci 56 platných bitů 64bitového klíče na Obr. 3.59 je označena jako E. Tato procedura kromě extrakce provádí také permutaci bitů klíče podle tabulky. 3.19 a 3.20.

Tabulka 3.19

Tabulka 3.20

V důsledku permutace se vytvoří dvě 28bitové hodnoty C a D. Tabulka 3.19 definuje výběr klíčových bitů pro C, Tabulka. 3,20 - za D.

Potom se provede 16 cyklů transformací, z nichž každý poskytne jeden z kulatých klíčů Kt. V každém kole procedury rozšíření klíče se provádějí následující akce:

1. Aktuální hodnoty C a D otočit doleva o proměnný počet bitů P. Pro kola 1, 2, 9 a 16 P= 1, zbývající kola se otočí o 2 bity.

2. S a D jsou sloučeny do 56bitové hodnoty, na kterou je aplikována kompresní permutace CP, výsledkem je 48bitový kulatý klíč K (. Kompresní permutace se provádí podle tabulky 3.21.

Tabulka 3.21

Při dešifrování dat můžete použít stejný postup rozšíření klíče, ale použijte kulaté klíče v opačném pořadí. Existuje další možnost: v každém kole procedury rozšiřování klíče místo kruhového posunu doleva proveďte kruhový posun doprava o n bitů, kde rc' = 0 pro první kolo a '=1 pro kola 2 , 9, 16 a n = 2 pro zbývající kola. Takový postup rozšíření klíče okamžitě poskytne kulaté klíče potřebné pro dešifrování.

Stojí za zmínku, že schopnost provádět rozšíření klíče za běhu (zejména pokud tato možnost existuje jak během šifrování, tak dešifrování) je považována za výhodu šifrovacích algoritmů, protože v tomto případě lze rozšíření klíče provádět paralelně s šifrováním a neplýtvat paměť pro uložení dalších klíčů.kole jiných než aktuální.

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 v roce 1980 byl přijat jako standard NIST (National Institute of Standards and Technology, USA).

DES je klasická síť Feishtel se dvěma pobočkami. Data jsou šifrována v 64bitových blocích pomocí 56bitového klíče. Algoritmus převádí 64bitový vstup na 64bitový výstup v několika kolech. Délka klíče je 56 bitů. Proces šifrování se skládá ze čtyř kroků. Prvním krokem je provedení počáteční permutace (IP) 64bitového otevřeného textu (vybělení), během kterého 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 se ve čtvrté fázi provede permutace 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íč Ki kombinací levého cyklické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í inverzní jsou určeny standardní tabulkou. Pokud je M libovolných 64 bitů, pak X = IP(M) - permutovaný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

Zvažte posloupnost transformací použitých v každém kole.

Obr.5. Ilustrace kola algoritmu DES

64bitový vstupní blok prochází 16 kola, přičemž při každé iteraci se získá mezilehlá 64bitová hodnota. S levou a pravou částí každé mezihodnoty se zachází jako se samostatnými 32bitovými hodnotami, označenými L a R. Každou iteraci lze popsat následovně:

Ri = Li-1 F(Ri-1, Ki)

Výstup levé poloviny Li je tedy roven vstupu pravé poloviny Ri-1. Výstup pravé poloviny Ri je výsledkem XORingu 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 Rj rozšíří na 48 bitů pomocí tabulky, která definuje permutaci plus rozšíření o 16 bitů. Rozšíření probíhá takto. 32 bitů je rozděleno do skupin po 4 bitech a poté rozšířeno na 6 bitů připojením krajní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 pak vložena do substituční funkce, 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 definuje 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.

Dále je výsledná 32bitová hodnota 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 s vysokou pravděpodobností každý bit zpracován jiným S -box.

Klíč pro jedno kolo K i se skládá ze 48 bitů. Klíče Ki jsou získány následujícím algoritmem. 56bitový klíč použitý jako vstup do algoritmu je nejprve permutován podle tabulky 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 D i nezávisle otočeny doleva o 1 nebo 2 bity, v závislosti na čísle kola. Výsledné hodnoty jsou vstupem do dalšího kola. Jsou také vstupem do Permuted Choice 2 (PC-2), který vytváří 48bitovou výstupní hodnotu, která je vstupem funkce F(R i-1, Ki).

Proces dešifrování je podobný procesu šifrování. Algoritmus používá jako vstup šifrový 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 kola dešifrování 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.