Klíčová slova

Princip algoritmu DES

„DES je typický blokový algoritmus, který bere text určité délky a transformuje ho pomocí mnoha komplikovaných operací na text stejné délky.“ [1]

Vrhneme se na vysvětlení komplikovaných operací.Princip algoritmu můžeme rozdělit na několik částí:

• generování klíčů (podklíčů z klíče)
• vstup, vstupní permutace a rozdělení na P a L
• aplikace rundy (funkce f) na P a L + použití klíče
• co se děje v rundě - S-box jako součást
• výstupní permutace a výstup

Generování klíčů (podklíčů z klíče)

Abychom mohli DES použít, potřebujeme mít 56 bitů dlouhý hlavní klíč, který se zadává jako 8 bytů (poznámka pro matematiky: 8 bytů = 64 bitů; my potřebujeme pouze 56 bitů dlouhý klíč, vynechají se paritní bity - 8, 16, 24...64). Z tohoto klíče získáme 16 podklíčů (iteračních klíčů, rundových klíčů), které jsou použity v jednotlivých kolech. Generování klíčů se jinak také říká expanze. Rozsah možných klíčů je tedy 2^56 = 72 057 594 037 927 936.Klíč, který vstupuje do algoritmu je označen K obr. 1. 

Obr. 1 Expanze klíče K1

Proběhne výběrová permutace PC-1 obr. 2, která přeskupí bity a rozdělí výstupní data z této operace na C₀ a D₀ (přeskupení bitů znamená, 57. bit bude na první pozici, 49. bit na druhé pozici, 41. bit na třetí pozici ..... a konečně 4. bit na poslední pozici; po přeskupení se celý blok rozdělí na dvě poloviny, které jsou zde označeny jako C₀ a D₀).

Obr. 2  DES - Výběrová permutace PC-1

Na obě tyto části je poté aplikován tzv. levý posun (posun jednotlivých bitů podle tabulky - probíhá pro všech 16 iterací, v první iteraci posune o 1 pozici, ve druhé rovněž o jednu pozici, při třetím průchodu o 2 pozice atd) a vzniknou bloky C₁ a D₁ (bloky C₁, D₁ tedy vzniknou aplikací levého posunu na bloky C₀, D₀)_, jak lze vidět v tabulce obr. 3.

Obr. 3 DES - Levý posun

Na bloky C₁, D₁ je poté aplikována permutace PC-2 obr. 4, která opět zpřehází bity (na prvním místě bude 14. bit, na druhém místě bit 17. atd) a zúží na 48 bitů (zúžení probíhá vynecháním některých bitů například 9. bit, 18. bit), výsledkem je první podklíč - označení K₁.

Obr. 4 DES - Výběrová permutace PC-2

Analogicky je takto vytvořeno všech 16 podklíčů - jak můžete vidět na obrázku obr. 5. Část této operace si můžete vyzkoušet v připraveném cvičení.

Obr. 5 Princip expanze všech 16 rundových klíčů

Vstup, vstupní permutace a rozdělení na P a L

Další, co nám vedle klíče vstupuje do algoritmu, je zpráva (bitový řetězec, který musí být rozdělen na 64 bitové bloky - popřípadě poslední blok doplněn na 64 bitů; tyto bity jsou poté uspořádány do tabulky, kam se zapisují po řádcích).Jednotlivé bity jsou „očíslovány“ podle své pozice z důvodu jednoduššího pochopení, co se s tabulkou děje obr. 6. 

Obr. 6 Vstupní matice

Tabulka je podrobena vstupní permutaci IP obr. 7, 

Obr. 7 Vstupní permutace IP

(vstupní permutace IP zpřehází jednotlivé bity - na prvním místě bude 58. bit, na druhém místě 50. bit, na posledním místě 7. bit.) a výstupem z ní jsou dva 32 bitové bloky - levý (L₁) a pravý (P₁) obr.8. 

Obr. 8 Vstup, permutace a rozdělení na L0 a R0 blok

Oba bloky tedy vzniknou rozdělením tabulky, po vstupní permutaci. Tyto dva bloky jsou 32 bitové a je na ně aplikována další permutace.Přehledně je to zobrazeno na obrázku obr. 9. 

Obr. 9 Polovina před doplněním

(Nahoře vidíme celkovou tabulku po permutaci, ta je rozdělena na dva bloky. Pro lepší názornost se jednotlivé bity v obou blocích opětovně očíslovaly dle pozice. Následně je na ně aplikována permutace.Př.: první 58 bit je současně v levé polovině, kde se nachází na pozici 1. Po permutaci se bude nacházet ve třetím řádku prvního sloupce, kde je rovněž označen 1)

Aplikace rundy (funkce f) na P a L + použití klíče

V tomto bodě se poprvé setkáme s aplikací vygenerovaného klíče - v první rundě to bude podklíč K₁. Pravá polovina P₀ má 32 bitů. Aby k ní mohl být přičten klíč, jenž má 48 bitů, musí být pravá část rozšířena na 48 bitů obr. 10. 

Obr. 10 DES - Expanze - rozšíření 32 bitů na 48 bitů

Toto rozšíření proběhne pomocí tzv. tabulky expanze - všimněte si dvojího zastoupení některých bitů. Takto upravená pravá polovina + podklíč vstupuje do šifrovací funkce f. Povšimněte si také jednotlivého prohazování z levé na pravou stranu.(např. výsledek L₂ se přesune na pravou stranu a tvoří tedy základ pro operace na pravé straně.Poznámka: zápis v celkovém grafu popisuje již to, co naznačují šipky. Neznamená tedy, že se provedou operace s již zmíněnou částí L₂, ta se přesune na pravou stranu a tam proběhnou operace znovu.)

Co se děje v rundě (f) - S-box jako součást

Osm S-boxů tvoří jeden z nejdůležitějších prvků, co se týče bezpečnosti DES obr. 11. 

Obr. 11  DES S-Boxy

Vyrobí z 6 příchozích bitů 4 výstupní bity. A záleží právě na vnitřním uspořádání S-boxu. Příklad: na vstupu budeme mít 6bitové slovo 000111 obr. 12

Obr. 12  S-box - příklad

• dva krajní bity (první a poslední) určují řádek S-boxu
• čtyři zbylé prostřední bity určují sloupec S-boxu
• průsečík je poté výstup
• v tomto případě se dostaneme na 04 - což binárně je 0100

Do S-boxu vstupuje výsledek, který je rozdělen na osm 6 bitových řetězců. Po transpozici, podle uvedené tabulky, zúží vstupní 6 bitové bloky na 4 bitové výstupní bloky, kterých je opět osm. Po spojení všech osmi řetězců dostaneme 32 bitový řetězec, který je znovu podroben permutaci (P).V roce 1990 v souvislosti s neustálou kritikou přijatého standardu bylo zjištěno, že náhodnou volbou S-boxu se bezpečnost ještě zvětší. (Do té doby byl S-box volen podle předem nastaveného řádu).

Výstupní permutace a výstup

Permutovaný výstup z S-boxů je opětovně permutován (permutace IP-1, inverzní ke vstupní obr. 13) a výstupem z algoritmu je zašifrovaný 64 bitový šifrovaný text. 

Obr. 13 Výstupní permutace IP-1

Celkový pohled na algoritmus tedy můžeme vidět zde obr. 14.

Obr. 14 DES a jeho blokové schéma

Shrnutí

Podrobně jsme si přiblížili generování podklíčů z hlavního klíče u algoritmu DES, stejně tak jsme si přiblížili princip celkového algoritmu i aplikaci vygenerovaných podklíčů.

Zdroje

Problematika blokových šifer a algoritmů je velice přehledně a srozumitelně popsána i v knize JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.[1] - http://www.kryptografie.wz.cz/data/des.html - ze dne 31.12.2011