9. Algoritmus AES

Algoritmus AES

(Advanced Encryption Standard)

Vítěz vypsané soutěže o nový šifrovací standard, algoritmus Rijndael, je pojmenován přesmyčkou jmen svých autorů Joana Daemena (vlevo) a Vincenta Rijmena (vpravo) obr. 1, představuje symetrickou blokovou šifru. AES nahradil v roce 2002 do té doby platný šifrový standard DES, který byl prolomen a nadále tedy již méně odolný vůči dalším útokům kryptoanalytiků.

Obr. 1 Autoři systému Rijndael - Joan Daemen a Vincent Rijmen

AES dokáže zpracovávat data o velikosti 128 bitů, pomocí šifrovacích klíčů o délce 128, 192 a 256 bitů. (AES tedy existuje ve třech variantách - se 128, 192 a 256 bitovými klíči. My si zde vysvětlíme princip na algoritmu se 128 bitovým klíčem).

Bloky 128 bitového klíče jsou zapisovány jako 16 bytů (1 byte = 8 bitů, 128 : 8 = 16), a zapisujeme je v hexadecimální podobě (tabulka ukazuje převody mezi soustavami obr. 2) do matice.

Obr. 2 Převody mezi soustavami

Dokázali byste si vybavit, jak se zapisují bity do algoritmu DES?

jednotlivé bity se zapisují po řádcích

Velký rozdíl oproti algoritmu DES je, že zde se zapisují jednotlivé byty a že se zapisují po sloupcích.

Před samotným principem šifrování AES se podíváme na jednotlivé operace, které musíme znát, abychom mohli tento standard použít. Jako obvykle potřebujeme z hlavního klíče, jenž má 128 bitů, vytvořit subklíče. Této operaci se opět říká expanze klíčů.

Expanze klíčů

Hlavní klíč je dlouhý 128 bitů, čili 16 bytů. Těchto 16 bytů umístíme do matice po sloupcích.

Princip generování je velmi jednoduchý, ovšem na vysvětlení se může zdáti dost chaotickým.

Musíme vygenerovat deset podklíčů.

Napadlo by vás, jak by mohl takový podklíč vypadat? Jestli je to matice? Jak by mohl být dlouhý? Co s ním vlastně budeme dále dělat a k čemu ho potřebujeme...

klíče potřebujeme k přičtení k upravenému bloku dat, který šifrujeme
jelikož zde mluvíme o bitovém přičtení - čili operaci modulo - musí být klíč stejně dlouhý jako text, ke kterému ho chceme přičíst
každý podklíč tedy musí mít rovněž 16 bytů
a těchto 16 bytů musí být umístěno do matice po sloupcích

Poznámka: Předtím, než se pustíme do samotného generování, je důležité si říci, že podklíče se nedají generovat tak, jak bychom chtěli - například teď bychom chtěli vygenerovat podklíč K5. To nelze. Jednotlivé sloupce totiž generujeme postupně dle vzorečků a ty jsou na sebe navzájem navázané. Tudíž nejdřív musíme vygenerovat sloupce pro podklíč K1, poté sloupce pro podklíč K2 a takhle postupně až pro podklíč K10.

Generování sloupců W4, W8, W12....Kde se vzali sloupce? Hlavní klíč jsme umístili do matice po sloupcích. Tyto sloupce označíme W0, W1, W2 a W3. Podklíč K1 budou tedy logicky tvořit sloupce W4, W5, W6 a W7.Nyní si ukážeme vzorce pro výpočet bytů prvního sloupce každého podklíče. Jedná se tedy o sloupce s označením W4, W8, W12, W16 .... W40. Přehledně je to vyobrazeno na obrázku 3.
Obr. 3

Následně se podíváme na generování zbylých sloupců.Generování sloupců W5, W6....W41, W42, W43Generování ostatních sloupců probíhá takto obr. 4

Obr. 4

Tímto způsobem tedy postupně dostaneme všech deset podklíčů.Pro generování podklíčů jsou připravena zvláštní cvičení.Vedle klíče vstupuje do algoritmu i otevřený text - v tomto případě je zadáván jako blok bitů, které se převedou na byty. Operace, které na otevřený text budou aplikovány, jsou čtyři:

1. SubByte (X, Y) - bytová substituce2. ShiftRow - rotace3. MixColumns - vynásobení mixovací maticí4. AddRoundKey - k transformované matici je přičten klíč.

1. SubByte (X, Y) - bytová substituce

Vstupem do algoritmu je text, tento text uspořádáme do matice podle schématu a operace SubByte nahradí - substituuje každý byte podle tabulky obr. 5. Tím se zabraňuje možnosti použití útoků založených na algebraických vlastnostech.

Obr. 5 Tabulka operace SubByte

Příklad: pokud budeme mít byte 1 a 9, první souřadnice (X) určuje řádek nahrazení, druhá souřadnice (Y) ukazuje sloupec nahrazení. Průsečík je potom výsledný nahrazující byte. Zde je tedy X = 1, Y = 9 a nahrazující byte můžete odečíst z obrázku obr. 6.

Obr. 6 Příklad substituce u operace SubByte

2. ShiftRow - rotace

Po substituci je matice podrobena rotaci. Rotace (či operace ShiftRow) probíhá v jednotlivých řádcích matice a to tak, že první řádek zůstane nezměněn, druhý bude posunut o jednu pozici vlevo, třetí řádek o dvě pozice vlevo a čtvrtý řádek o tři pozice vlevo. Schematicky je to uvedeno zde obr. 7.Operace ShiftRow je pak použita i u generování klíčů, ale je aplikována na sloupce. Jednotlivé byty sloupce tedy „poskočí“ o jednu pozici nahoru a první byte se posune na poslední pozici.

Obr. 7 Operace ShiftRow

3. MixColumns - vynásobení mixovací maticí

Zrotovaná matice se dále upraví operací MixColumns. Vedle zrotované matice je zde vstupem i matice mixovací, která zabezpečí vynásobení. Pokud dojde k přetečení u jednotlivých operací, je zde použito XORování tzv. Galoisovým číslem. Operace MixColumns je výpočetně složitější a je jí věnováno jedno z připravených cvičení, kde je postup podrobně vysvětlen na příkladu. Využívá se zde násobení matice maticí, jak jste si mohli vyzkoušet v minulém jednoduchém cvičení a operace modulo.

4. AddRoundKey - k transformované matici je přičten klíč

K substituované, zrotované a vynásobené matici už tedy nezbývá nic jiného než přičíst subklíč, který jsme získali hned na začátku expanzí. Přičtením zde rozumíme operaci modulo.Celý tento postup je nutno aplikovat v deseti po sobě jdoucích iteracích. Jediný rozdíl poslední iterace je ten, že vynechává operaci MixColumns.Nyní jsme si popsali průběh všech operací, které v algoritmu probíhají, pojďme se tedy podívat přímo na princip, který je demonstrován na příkladu.

Binární operace sčítání modulo a XOR

Jelikož se zde stále bavíme o bytech, které jsou umístěny v matici, bylo by užitečné ukázat si, jak taková matice vypadá binárně, neboť operace, o kterých je řeč, probíhají v oblíbených jedničkách a nulách.Na obrázku jsou tedy dvě matice, první představuje otevřený text (OT), druhá potom znázorňuje matici s klíčem. Obě jsou v hexadecimálním tvaru a poté v binárním tvaru. Na prvních sloupcích obou matic je ukázán postup operace sčítání modulo a poté XOR, čili porovnávání jedinečnosti obr. 8. Poznámka: Binární operace jsou zde nastíněny velmi obecně, protože je připraveno cvičení, kde na sebe logicky navazují a budete si moci jejich aplikaci náležitě vyzkoušet a užít.

Obr. 8 Ukázka operace modulo a XOR

Shrnutí

Obecně jsme si přiblížili podstatu algoritmu AES, který nahradil již nevyhovující DES. Ukázali jsme si jednotlivé operace a dílčí segmenty, které budeme muset při aplikování tohoto algoritmu použít.

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.