DES

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. března 2015; kontroly vyžadují 72 úprav .

DES, standard šifrování dat
Tvůrce	IBM
Vytvořeno	1977 _
zveřejněno	1977 _
Velikost klíče	56 bitů + 8 test
Velikost bloku	64 bit
Počet kol	16
Typ	Síť Feistel
Mediální soubory na Wikimedia Commons

DES ( anglicky Data Encryption Standard ) je algoritmus pro symetrické šifrování vyvinutý společností IBM a schválený vládou USA v roce 1977 jako oficiální standard ( FIPS 46-3). Velikost bloku pro DES je 64 bitů . Algoritmus je založen na Feistelově síti s 16 cykly ( koly ) a klíčem 56 bitů . Algoritmus využívá kombinaci nelineárních (S-boxy) a lineárních (E, IP, IP-1 permutace) transformací. Pro DES se doporučuje několik režimů:

ECB ( anglicky e lectronic code book ) - režim "elektronický číselník" (jednoduchá náhrada) ;
CBC ( anglicky c ipher b lock c chaining ) - režim blokového řetězení;
CFB ( angl. c ipher f eed b ack ) - režim zpětné vazby šifrovaného textu ;
OFB ( eng. output f eed b ack ) - režim výstupní zpětné vazby;
Counter Mode (CM) - režim čítače.

Přímým vývojem DES je v současnosti algoritmus Triple DES (3DES). V 3DES se šifrování/dešifrování provádí trojím spuštěním algoritmu DES.

Historie

V roce 1972 byla provedena studie o potřebě počítačové bezpečnosti vládou USA . Americký "National Bureau of Standards" (NBS) (nyní známý jako NIST - "National Institute of Standards and Technology") identifikoval potřebu celovládního standardu pro šifrování nekritických informací.

NBS konzultovala s NSA (Národní bezpečnostní úřad USA) a 15. května 1973 vyhlásila první soutěž na vytvoření šifry. Byly formulovány přísné požadavky na novou šifru. IBM vstoupilo do soutěže se šifrou, kterou vyvinula, nazvanou „Lucifer “ . Šifry žádného ze soutěžících (včetně „Lucifera“) nezajistily splnění všech požadavků. V letech 1973-1974 dokončila IBM svůj „Lucifer“: použila dříve vytvořený algoritmus Horsta Feistela . 27. srpna 1974 začala druhá soutěž. Tentokrát byla šifra „Lucifer“ považována za přijatelnou.

17. března 1975 byl navrhovaný algoritmus DES zveřejněn ve federálním rejstříku. V roce 1976 se konala dvě veřejná sympozia k diskusi o DES. Na sympoziích byly změny provedené v algoritmu NSA silně kritizovány. NSA zmenšil původní délku klíče a S-boxy (náhradní boxy), jejichž konstrukční kritéria nebyla zveřejněna. NSA byla podezřelá ze záměrného oslabení algoritmu, aby NSA mohla snadno prohlížet šifrované zprávy. Americký Senát přezkoumal akce NSA a vydal prohlášení v roce 1978 , které uvedlo následující:

při vývoji algoritmu zástupci NBÚ přesvědčili tvůrce DES, že zkrácená délka klíče je více než dostatečná pro všechny komerční aplikace;
Zástupci NSA nepřímo asistovali při vývoji S-permutací;
konečná verze algoritmu byla podle názoru ověřovatelů nejlepším šifrovacím algoritmem, navíc bez statistických či matematických slabin;
Zástupci NSA nikdy nezasahovali do vývoje algoritmu DES.

V roce 1990 provedli Eli Biham a Adi Shamir nezávislý výzkum diferenciální kryptoanalýzy , hlavní metody pro prolomení blokových symetrických šifrovacích algoritmů . Tyto studie odstranily některá podezření o skryté slabosti S-permutací. Ukázalo se, že S-boxy algoritmu DES jsou mnohem odolnější vůči útokům, než kdyby byly náhodně vybrány. To znamená, že tato analytická technika byla NSA známa již v 70. letech 20. století.

Algoritmus DES byl „hacknut“ za 39 dní pomocí obrovské sítě desítek tisíc počítačů [1] .

Veřejná organizace " EFF " , zabývající se problémy informační bezpečnosti a soukromí na internetu , iniciovala studii " DES Challenge II " k identifikaci problémů s DES . V rámci studie postavili zaměstnanci RSA Laboratory superpočítač za 250 000 USD. V roce 1998 superpočítač dešifroval data kódovaná DES pomocí 56bitového klíče za méně než tři dny. Superpočítač byl pojmenován „EFF DES Cracker“. Speciálně pro tuto příležitost vědci uspořádali tiskovou konferenci a hovořili s obavami, že útočníci si pravděpodobně nenechají ujít příležitost využít takové zranitelnosti.

Někteří vládní úředníci a experti tvrdili, že prolomení kódu DES vyžaduje superpočítač v hodnotě mnoha milionů dolarů. "Je čas, aby vláda uznala nejistotu DES a podpořila vytvoření silnějšího šifrovacího standardu," řekl prezident EFF Barry Steinhardt. Vývozní omezení uložená vládou USA se vztahují na šifrovací technologie s klíči delšími než 40 bitů. Jak však ukázaly výsledky experimentu RSA Laboratory, existuje možnost prolomení ještě výkonnějšího kódu. Problém byl umocněn tím, že náklady na stavbu takového superpočítače neustále klesaly. „Za čtyři nebo pět let budou tyto počítače na každé škole,“ řekl John Gilmour, vedoucí projektu DES Challenge a jeden ze zakladatelů EFF.

DES je bloková šifra. Abychom pochopili, jak DES funguje, je nutné vzít v úvahu princip fungování blokové šifry , sítě Feistel .

Bloková šifra

Vstupní data pro blokovou šifru jsou:

velikost bloku n bitů;
klíč o velikosti k bitů.

Výstupem (po aplikaci šifrovacích transformací) je zašifrovaný blok o velikosti n bitů a drobné rozdíly ve vstupních datech zpravidla vedou k výrazné změně výsledku.

Blokové šifry jsou implementovány opakovaným aplikováním určitých základních transformací na bloky zdrojového textu .

Základní transformace:

komplexní transformace na jedné místní části bloku;
jednoduchá konverze mezi částmi bloku.

Jelikož se transformace provádějí blok po bloku, je nutné rozdělit zdrojová data do bloků požadované velikosti. V tomto případě nezáleží na formátu zdrojových dat (ať už se jedná o textové dokumenty, obrázky nebo jiné soubory). Data je nutné interpretovat v binární podobě (jako posloupnost nul a jedniček) a teprve poté je nutné je rozdělit do bloků. Vše výše uvedené lze implementovat jak softwarově, tak i hardwarově.

Transformace sítí Feistel

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

Schéma šifrování DES

Šifrovací schéma algoritmu DES je znázorněno na obr.3.

Zdrojový text je blok 64 bitů.

Proces šifrování se skládá z počáteční permutace, 16 šifrovacích cyklů a konečné permutace.

Počáteční permutace

Původní text (blok 64 bitů) je převeden pomocí počáteční permutace, která je určena tabulkou 1: $T$ $\mathrm{IP}$

Tabulka 1. Počáteční permutace IP

58	padesáti	42	34	26	osmnáct	deset	2	60	52	44	36	28	dvacet	12	čtyři
62	54	46	38	třicet	22	čtrnáct	6	64	56	48	40	32	24	16	osm
57	49	41	33	25	17	9	jeden	59	51	43	35	27	19	jedenáct	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	patnáct	7

Podle tabulky jsou první 3 bity výsledného bloku po počáteční permutaci bity 58, 50, 42 vstupního bloku a jeho poslední 3 bity jsou bity 23, 15, 7 vstupního bloku. $\mathrm{IP}(T)$ $\mathrm{IP}$ $T$

Šifrovací cykly

64bitový blok IP(T) získaný po počáteční permutaci se účastní 16 cyklů Feistelovy transformace.

- 16 cyklů Feistelovy transformace :

Rozdělte IP(T) na dvě části , kde je 32 vysokých bitů a 32 nízkých bitů bloku IP(T)= $L_0, R_0$ $L_0, R_0$ $T_{0}$ $L_0R_0$

Nechť výsledkem je (i-1) iterace, pak výsledek i-té iterace je určen: $T_{i-1} = L_{i-1}R_{i-1}$ $T_i = L_iR_i$

L_i = R_{i-1}

R_i = L_{i-1}\oplus f(R_{i-1},k_i)

Levá polovina se rovná pravé polovině předchozího vektoru . A pravá polovina je bitové sčítání modulo 2. $L_i$ $L_{i-1}R_{i-1}$ $R_i$ $L_{i-1}$ $f(R_{i-1},k_i)$

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

Základní šifrovací funkce (Feistelova funkce)

Argumenty funkce jsou 32bitový vektor a 48bitový klíč , který je výsledkem transformace původního 56bitového šifrovacího klíče . Pro výpočet funkce postupně použijte $F$ $R_{i-1}$ $k_i$ $k$ $F$

funkce rozšíření , $\mathrm{E}$
přídavné modulo 2 s klíčem $k_i$
transformace , skládající se z 8 transformačních bloků , $\mathrm{S}$ $\mathrm{S}$ $\mathrm{S}_1,\mathrm{S}_2,\mathrm{S}_3\ldots\ \mathrm{S}_8$
permutace . $\mathrm{P}$

Funkce rozšiřuje 32bitový vektor na 48bitový vektor duplikací některých bitů z ; bitové pořadí vektoru je uvedeno v tabulce 2. $\mathrm{E}$ $R_{i-1}$ $\mathrm{E}(R_{i-1})$ $R_{i-1}$ $\mathrm{E}(R_{i-1})$

Tabulka 2. Funkce rozšíření E

32	jeden	2	3	čtyři	5
čtyři	5	6	7	osm	9
osm	9	deset	jedenáct	12	13
12	13	čtrnáct	patnáct	16	17
16	17	osmnáct	19	dvacet	21
dvacet	21	22	23	24	25
24	25	26	27	28	29
28	29	třicet	31	32	jeden

První tři bity vektoru jsou bity 32, 1, 2 vektoru . 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 jsou bity 31, 32, 1 vektoru . Blok získaný po permutaci je přidán modulo 2 s klíči a poté prezentován ve formě osmi po sobě jdoucích bloků . $\mathrm{E}(R_{i-1})$ $R_{i-1}$ $E(R_{i-1})$ $R_{i-1}$ $\mathrm{E}(R_{i-1})$ $k_i$ $B_1, B_2,...B_8$

\mathrm{E}(R_{i-1})\oplus k_i= B_1B_2...B_8

Každý z nich je 6bitový blok. Dále je každý z bloků transformován na 4bitový blok pomocí transformací . Transformace jsou definovány v tabulce 3. $B_j$ $B_j$ $B'_j$ $S_j$ $S_j$

Tabulka 3. Transformace , i=1…8

S_{i}

	0	jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct

0	čtrnáct	čtyři	13	jeden	2	patnáct	jedenáct	osm	3	deset	6	12	5	9	0	7
jeden	0	patnáct	7	čtyři	čtrnáct	2	13	jeden	deset	6	12	jedenáct	9	5	3	osm	$S_{1}$
2	čtyři	jeden	čtrnáct	osm	13	6	2	jedenáct	patnáct	12	9	7	3	deset	5	0
3	patnáct	12	osm	2	čtyři	9	jeden	7	5	jedenáct	3	čtrnáct	deset	0	6	13

0	patnáct	jeden	osm	čtrnáct	6	jedenáct	3	čtyři	9	7	2	13	12	0	5	deset
jeden	3	13	čtyři	7	patnáct	2	osm	čtrnáct	12	0	jeden	deset	6	9	jedenáct	5	$S_{2}$
2	0	čtrnáct	7	jedenáct	deset	čtyři	13	jeden	5	osm	12	6	9	3	2	patnáct
3	13	osm	deset	jeden	3	patnáct	čtyři	2	jedenáct	6	7	12	0	5	čtrnáct	9

0	deset	0	9	čtrnáct	6	3	patnáct	5	jeden	13	12	7	jedenáct	čtyři	2	osm
jeden	13	7	0	9	3	čtyři	6	deset	2	osm	5	čtrnáct	12	jedenáct	patnáct	jeden	$S_{3}$
2	13	6	čtyři	9	osm	patnáct	3	0	jedenáct	jeden	2	12	5	deset	čtrnáct	7
3	jeden	deset	13	0	6	9	osm	7	čtyři	patnáct	čtrnáct	3	jedenáct	5	2	12

0	7	13	čtrnáct	3	0	6	9	deset	jeden	2	osm	5	jedenáct	12	čtyři	patnáct
jeden	13	osm	jedenáct	5	6	patnáct	0	3	čtyři	7	2	12	jeden	deset	čtrnáct	9	$S_4$
2	deset	6	9	0	12	jedenáct	7	13	patnáct	jeden	3	čtrnáct	5	2	osm	čtyři
3	3	patnáct	0	6	deset	jeden	13	osm	9	čtyři	5	jedenáct	12	7	2	čtrnáct

0	2	12	čtyři	jeden	7	deset	jedenáct	6	osm	5	3	patnáct	13	0	čtrnáct	9
jeden	čtrnáct	jedenáct	2	12	čtyři	7	13	jeden	5	0	patnáct	deset	3	9	osm	6	$S_5$
2	čtyři	2	jeden	jedenáct	deset	13	7	osm	patnáct	9	12	5	6	3	0	čtrnáct
3	jedenáct	osm	12	7	jeden	čtrnáct	2	13	6	patnáct	0	9	deset	čtyři	5	3

0	12	jeden	deset	patnáct	9	2	6	osm	0	13	3	čtyři	čtrnáct	7	5	jedenáct
jeden	deset	patnáct	čtyři	2	7	12	9	5	6	jeden	13	čtrnáct	0	jedenáct	3	osm	$S_6$
2	9	čtrnáct	patnáct	5	2	osm	12	3	7	0	čtyři	deset	jeden	13	jedenáct	6
3	čtyři	3	2	12	9	5	patnáct	deset	jedenáct	čtrnáct	jeden	7	6	0	osm	13

0	čtyři	jedenáct	2	čtrnáct	patnáct	0	osm	13	3	12	9	7	5	deset	6	jeden
jeden	13	0	jedenáct	7	čtyři	9	jeden	deset	čtrnáct	3	5	12	2	patnáct	osm	6	$S_7$
2	jeden	čtyři	jedenáct	13	12	3	7	čtrnáct	deset	patnáct	6	osm	0	5	9	2
3	6	jedenáct	13	osm	jeden	čtyři	deset	7	9	5	0	patnáct	čtrnáct	2	3	12

0	13	2	osm	čtyři	6	patnáct	jedenáct	jeden	deset	9	3	čtrnáct	5	0	12	7
jeden	jeden	patnáct	13	osm	deset	3	7	čtyři	12	5	6	jedenáct	0	čtrnáct	9	2	$S_8$
2	7	jedenáct	čtyři	jeden	9	12	čtrnáct	2	0	6	deset	13	patnáct	3	5	osm
3	2	jeden	čtrnáct	7	čtyři	deset	osm	13	patnáct	12	9	0	3	5	6	jedenáct

Předpokládejme, že a my chceme najít . První a poslední číslice jsou binární reprezentací čísla a, 0<=a<=3, prostřední 4 číslice reprezentují číslo b, 0<=b<=15. Řádky tabulky S3 jsou číslovány od 0 do 3, sloupce tabulky S3 jsou číslovány od 0 do 15. Dvojice čísel (a, b) určuje číslo na průsečíku řádku a a sloupce b. Binární reprezentace tohoto čísla dává . V našem případě , , a číslo definované dvojicí (3,7) je 7. Jeho binární reprezentace je =0111. Funkční hodnota (32 bitů ) se získá permutací P aplikovanou na 32bitový blok . Permutace P je dána tabulkou 4. $B_3 = 101111$ $B'_3$ $B_{3}$ $B'_3$ $a=11_2=3$ $b=0111_2=7$ $B'_3$ $f(R_{i-1},k_i)$ $B'_1B'_2...B'_8$

Tabulka 4. Permutace P

16	7	dvacet	21	29	12	28	17
jeden	patnáct	23	26	5	osmnáct	31	deset
2	osm	24	čtrnáct	32	27	3	9
19	13	třicet	6	22	jedenáct	čtyři	25

$f(R_{i-1},k_i) = P(B'_1B'_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'_1B'_2...B'_8$

Generování klíčů $k_i$

Klíče se získávají z počátečního klíče (56 bitů = 7 bajtů nebo 7 znaků v ASCII ) následovně. Bity se sčítají na pozicích 8, 16, 24, 32, 40, 48, 56, 64 klíče 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 v tabulce 5. $k_i$ $k$ $k$

Tabulka 5

57	49	41	33	25	17	9	jeden	58	padesáti	42	34	26	osmnáct	$C_{0}$
deset	2	59	51	43	35	27	19	jedenáct	3	60	52	44	36
63	55	47	39	31	23	patnáct	7	62	54	46	38	třicet	22	$D_0$
čtrnáct	6	61	53	45	37	29	21	13	5	28	dvacet	12	čtyři

Tato permutace je určena dvěma bloky a 28 bity každý. První 3 bity jsou bity 57, 49, 41 rozšířeného klíče. A první tři bity jsou bity 63, 55, 47 rozšířeného klíče. i=1,2,3…jsou získány z jednoho nebo dvou levých cyklických posunů podle tabulky 6. $C_{0}$ $D_0$ $C_{0}$ $D_0$ $C_i, D_i$ $C_{i-1}, D_{i-1}$

Tabulka 6

i	jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16
Číslo směny	jeden	jeden	2	2	2	2	2	2	jeden	2	2	2	2	2	2	jeden

Klíč , i=1,…16 se skládá ze 48 bitů vybraných z vektorových bitů (56 bitů ) podle tabulky 7. První a druhý bit jsou bity 14, 17 vektoru $k_i$ $C_iD_i$ $k_i$ $C_iD_i$

Tabulka 7

čtrnáct	17	jedenáct	24	jeden	5	3	28	patnáct	6	21	deset	23	19	12	čtyři
26	osm	16	7	27	dvacet	13	2	41	52	31	37	47	55	třicet	40
51	45	33	48	44	49	39	56	34	53	46	42	padesáti	36	29	32

Konečná permutace

Konečná permutace působí na (kde ) a je inverzní k původní permutaci. Konečná permutace je určena tabulkou 8. $\mathrm{IP}^{-1}$ ${\displaystyle T_{16}^{-1))$ ${\displaystyle T_{16}^{-1}=R_{16}+L_{16))$

Tabulka 8. Reverzní permutace

\mathrm{IP}^{-1}

40	osm	48	16	56	24	64	32	39	7	47	patnáct	55	23	63	31
38	6	46	čtrnáct	54	22	62	třicet	37	5	45	13	53	21	61	29
36	čtyři	44	12	52	dvacet	60	28	35	3	43	jedenáct	51	19	59	27
34	2	42	deset	padesáti	osmnáct	58	26	33	jeden	41	9	49	17	57	25

Schéma dešifrování

Při dešifrování dat se všechny akce provádějí v opačném pořadí. V 16 kolech dešifrování, na rozdíl od šifrování pomocí přímé transformace sítí Feistel, je zde použita inverzní transformace sítí Feistel.

$R_{i-1} = L_i$
$L_{i-1} = R_i \oplus f(L_i,k_i)$

Schéma dešifrování je na obr.6.
Klíč , i=16,…,1, funkce f, permutace IP a jsou stejné jako v procesu šifrování. Algoritmus generování klíčů závisí pouze na klíči uživatele, takže jsou při dešifrování identické. $k_i$ $IP^{-1}$

Způsoby použití DES

DES lze použít ve čtyřech režimech.

Režim elektronického číselníku ( ECB ) : Běžné použití DES jako blokové šifry . Šifrovaný text je rozdělen do bloků, přičemž každý blok je zašifrován samostatně bez interakce s jinými bloky (viz obr. 7).
Režim řetězení šifrových bloků ( CBC - Cipher Block Chaining ) (viz obr. 8). Každý další blok i>=1 před zašifrováním je přidán modulo 2 k předchozímu bloku šifrovaného textu . Vektor je počáteční vektor, mění se denně a je držen v tajnosti. $M_{i}$ $C_{{i-1}}$ $C_{0}$
Šifrovací režim zpětné vazby ( viz obr.9). V režimu CFB se vytváří bloková gama . Počáteční vektor je synchronizační zpráva a je navržena tak, aby zajistila, že různé datové sady budou zašifrovány odlišně pomocí stejného tajného klíče. Synchronizační zpráva je odeslána příjemci jako prostý text spolu se zašifrovaným souborem. Algoritmus DES se na rozdíl od předchozích režimů používá pouze jako šifrování (v obou případech). $Z_0, Z_1,...$ $Z_i=DES_k(C_{i-1})$ $C_i = M_i \oplus Z_i$ $C_{0}$
Režim výstupní zpětné vazby ( OFB - Output Feedback ) (viz obr. 10). V režimu OFB se generuje blok "gama" , i>=1. Režim také používá DES pouze jako šifrování (v obou případech). $Z_0, Z_1,...$ $Z_i=DES_k(Z_{i-1}) C_i = M_i \oplus Z_i$

Výhody a nevýhody režimů:

V režimech ECB a OFB vede zkreslení během přenosu jednoho 64bitového bloku šifrovaného textu ke zkreslení po dešifrování pouze odpovídajícího otevřeného bloku , takže tyto režimy se používají pro přenos komunikačními kanály s velkým počtem zkreslení. $C_i$ $M_i$

Kryptografická síla algoritmu DES

Nelinearita transformací v DES pomocí pouze S-boxů a použití slabých S-boxů umožňuje vykonávat kontrolu nad šifrovanou korespondencí. Výběr S-boxů vyžaduje splnění několika podmínek:

Každý řádek každého bloku musí být permutací množiny {0, 1, 2, ..., 15}
S-boxy nesmí být lineární nebo afinní funkcí svých argumentů.
Změna jednoho bitu na vstupu S-boxu musí změnit alespoň dva bity na výstupu.
Pro každý S-box a jakýkoli argument x se hodnota S ( x ) a musí lišit alespoň o dva bity. $S(x\oplus 001100_2)$

Vzhledem k malému počtu možných klíčů (pouze ), je možné je vyčerpávajícím způsobem vyjmenovat na vysokorychlostních počítačích v reálném čase. V roce 1998 se Electronic Frontier Foundation pomocí speciálního počítače DES-Cracker podařilo prolomit DES za 3 dny. $2^{56}$

Slabé klíče

Slabé klíče jsou klíče k takové, že , kde x je 64bitový blok. $DES_k(DES_k(x)) = x$

Známé jsou 4 slabé klíče, ty jsou uvedeny v tabulce 9. Pro každý slabý klíč jsou pevné body , tedy takové 64bitové bloky x , pro které . $2^{32}$ $DES_k(x) = x$

Tabulka 9. DES-slabé klíče

Slabé klíče (hexadecimální)	$C_{0}$	$D_0$
0101-0101-0101-0101	$[0]^{28}$	$[0]^{28}$
FEFE-FEFE-FEFE-FEFE	$[1]^{28}$	$[1]^{28}$
1F1F-1F1F-0E0E-0E0E	$[0]^{28}$	$[1]^{28}$
E0E0-E0E0-F1F1-F1F1	$[1]^{28}$	$[0]^{28}$

$[0]^{28}$ označuje vektor sestávající z 28 nulových bitů.

Částečně slabé klávesy

V algoritmu DES jsou slabé a částečně slabé klíče. Částečně slabé klíče jsou dvojice klíčů takové , že $(k_1, k_2)$ $DES_{k1}(DES_{k2}(x)) = x.$

Existuje 6 částečně slabých párů klíčů, které jsou uvedeny v tabulce 10. Pro každý z 12 částečně slabých klíčů existují „anti-fixed points“, tj. bloky x takové, že $2^{32}$ $DES_k(x) = \tilde{x}.$

Tabulka 10. Částečně slabé klávesy

$C_{0}$	$D_0$	Páry částečně slabých kláves	$C_{0}$	$D_0$
$[01]^{14}$	$[01]^{14}$	01FE-01FE-01FE-01FE,----FE01-FE01-FE01-FE01	$[10]^{14}$	$[10]^{14}$
$[01]^{14}$	$[01]^{14}$	1FE0-1FE0-1FE0-1FE0,----E0F1-E0F1-E0F1-E0F1	$[10]^{14}$	$[10]^{14}$
$[01]^{14}$	$[0]^{28}$	01E0-01E0-01F1-01F1,----E001-E001-F101-F101	$[10]^{14}$	$[0]^{28}$
$[01]^{14}$	$[1]^{28}$	1FFE-1FFE-0EFE-0EFE,----FE1F-FE1F-FE0E-FE0E	$[0]^{28}$	$[1]^{28}$
$[0]^{28}$	$[01]^{14}$	011F-011F-010E-010E,----1F01-1F01-0E01-0E01	$[0]^{28}$	$[10]^{14}$
$[1]^{28}$	$[01]^{14}$	E0FE-E0FE-F1FE-F1FE,----FEE0-FEE0-FEF1-FEF1	$[1]^{28}$	$[10]^{14}$

Známé útoky proti DES

Tabulka 11. Známé útoky proti DES.

Metody útoku	Známé objevy texty	Vybráno otevřené texty	Velikost paměti	Počet operací
Úplné vyhledávání	qweqweqweqerqe	-	Méně důležitý	$2^{55}$
Lineární kryptoanalýza	$2^{43}(85\%)$	-	Pro text	$2^{43}$
Lineární kryptoanalýza	$2^{38}(10\%)$	-	Pro text	$2^{50}$
Lišit. Kryptoanalýza	-	$2^{47}$	Pro text	$2^{47}$
Lišit. Kryptoanalýza	$2^{55}$	-	Pro text	$2^{55}$

Metoda hrubou silou vyžaduje jeden známý pár šifrovaného a dešifrovaného textu, malé množství paměti a její provedení vyžaduje přibližně kroků. $2^{55}$
Diferenciální kryptoanalýza - Biham a Shamir prohlásili první takový útok na DES . Tento útok vyžaduje šifrování holého textu zvoleného útočníkem a jeho dokončení trvá přibližně 10 kroků. Teoreticky jde o bod zlomu, tento útok je nepraktický kvůli přehnaným požadavkům na dolování dat a složitosti organizace útoku na zvolený prostý text. Autoři tohoto útoku, Biham a Shamir, sami uvedli, že považují DES za bezpečný pro takový útok. $2^{47}$ $2^{47}$
Lineární kryptoanalýza vyvinutá Matsui. Tato metoda umožňuje obnovit klíč DES analýzou známého otevřeného textu a vyžaduje přibližně kroků k dokončení. První experimentální DES kryptoanalýza založená na Matsuiho objevu byla úspěšně provedena během 50 dnů na 12 pracovních stanicích HP 9735. $2^{43}$ $2^{43}$

Pro lineární a diferenciální kryptoanalýzu je zapotřebí dostatečně velké množství paměti pro uložení vybraných (známých) otevřených textů před začátkem útoku.

Zvýšení síly DES

Pro zvýšení kryptografické síly DES se objevuje několik možností: dvojité DES ( 2DES ), trojité DES ( 3DES ), DESX , G-DES .

Metody 2DES a 3DES jsou založeny na DES, ale zvyšují délku klíčů (2DES - 112 bitů, 3DES - 168 bitů), a proto zvyšují šifrovací sílu .
Schéma 3DES má tvar , kde jsou klíče pro každou šifru DES. Tato varianta je známá jako v EEE, protože tři operace DES jsou šifrování. Existují 3 typy algoritmu 3DES: $DES(k_3,DES(k_2,DES(k_1,M)))$ $k_1, k_2, k_3$

DES-EEE3 : Šifrováno třikrát pomocí 3 různých klíčů.
DES-EDE3 : Operace 3DES šifrování-dešifrování-šifrování se 3 různými klíči.
DES-EEE2 a DES-EDE2 : Jako výše, až na to, že první a třetí operace používají stejnou klávesu.

Nejoblíbenějším typem při použití 3DES je DES-EDE3, pro který algoritmus vypadá takto: Šifrování : .

C = E_{k_3}(E^{-1}_{k_2}(E_{k_1}(P)))

Dešifrování :

P = E^{-1}_{k_1}(E_{k_2}(E^{-1}_{k_3}(C)))

Při provádění algoritmu 3DES lze klíče zvolit následovně:

$k_1, k_2, k_3$ nezávislý.
$k_1, k_2$ nezávislý a $k_1 = k_3$
$k_1=k_2=k_3$ .

Metodu DESX vytvořil Ronald Rivest a formálně ji předvedli Killian a Rogaway. Tato metoda je vylepšenou verzí DES podporovanou sadou nástrojů RSA Security. DESX se liší od DES v tom, že každý bit vstupního otevřeného textu DESX je logicky sečten modulo 2 s 64 bity dalšího klíče a poté zašifrován pomocí algoritmu DES. Každý bit výsledku je také logicky přidán modulo 2 k dalším 64 bitům klíče. Hlavním důvodem pro použití DESX je výpočetně jednoduchý způsob, jak výrazně zvýšit odolnost DES vůči útokům hrubou silou .
Metoda G-DES byla vyvinuta společností Schaumuller-Bichl ke zlepšení výkonu DES zvětšením velikosti bloku šifry. G-DES se tvrdilo, že je stejně bezpečný jako DES. Biham a Shamir však ukázali, že G-DES s doporučenými parametry je snadno prolomitelný a při jakýchkoli změnách parametrů se šifra stává ještě méně bezpečnou než DES.
Další varianta DES používá nezávislé podklíče. Na rozdíl od DES, ve kterém DES na základě 56bitového soukromého klíče uživatele získává šestnáct 48bitových podklíčů pro použití v každém ze 16 kol, používá tato verze 768bitový klíč (rozdělený na 16 48bitových podklíčů ) namísto 16 závislých 48bitových klíčů generovaných klíčovým grafem algoritmu DES. I když je jasné, že použití nezávislých podklíčů značně zkomplikuje kompletní hledání klíče, odolnost vůči útoku diferenciální nebo lineární kryptoanalýzou není o moc vyšší než síla běžného DES. Podle Bihama vyžaduje diferenciální kryptoanalýza DES s nezávislými podklíči vybrané otevřené texty, zatímco lineární kryptoanalýza vyžaduje známé otevřené texty. $2^{61}$ $2^{60}$

Aplikace

DES byl americkým národním standardem v letech 1977-1980 , ale v současnosti se DES používá (s 56bitovým klíčem) pouze pro starší systémy, nejčastěji využívající jeho kryptograficky silnější formu ( 3DES , DESX ). 3DES je jednoduchou a účinnou náhradou za DES a nyní je považován za standard. V blízké budoucnosti budou DES a Triple DES nahrazeny algoritmem AES (Advanced Encryption Standard). Algoritmus DES je široce používán k ochraně finančních informací: například modul THALES (Racal) HSM RG7000 plně podporuje operace TripleDES pro vydávání a zpracování kreditních karet VISA , EuroPay a dalších. Kanálové scramblery THALES (Racal) DataDryptor 2000 používají TripleDES k transparentnímu šifrování datových toků. Algoritmus DES se také používá v mnoha dalších zařízeních a řešeních THALES-eSECURITY.

Poznámky

↑ distribution.net: projekt RSA DES II-1 . Staženo 1. 1. 2018. Archivováno z originálu 31. 12. 2017. (neurčitý)

Literatura

A. P. Alferov, A. Yu. Zubov, A. S. Kuzmin, A. V. Cheremushkin Základy kryptografie.
A. Menezes, Pvan Oorschot, S. Vanstone. Příručka aplikované kryptografie .
Semenov Yu.A. DES algoritmus .
Dotaz na DES

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) blowfish Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher