OBSAH 1 Obsah 1 Úvod 2 2 Definice 2 2.1 Slovník výrazů a akronymů ...................... 2 2.2 Parametry algoritmů, symboly a funkce................ 3 3 Standard DES 4 3.1 Popis algoritmu............................. 4 3.2 Vlastnosti DES............................. 6 3.3 Módy DES................................ 6 4 Nedostatky šifry DES a její prolomení 8 4.1 Komplementárnost........................... 8 4.2 Nevhodný návrh S-boxů........................ 8 4.3 Slabé a poloslabé klíče......................... 9 4.4 Příliš krátký klíč ............................ 10 5 Nový standard AES 10 6 Označení a konvence AES 11 6.1 Vstupy a výstupy............................ 11 6.2 Byty................................... 11 6.3 Pole bytů................................ 12 6.4 Stav................................... 13 6.5 Stav jako pole sloupců......................... 13 7 Matematické operace potřebné pro AES 13 7.1 Sčítání.................................. 14 7.2 Násobení................................. 14 7.2.1 Násobení proměnnou x..................... 15 7.3 Polynomy s koeficienty v GF(28).................... 16 8 Specifikace algoritmu AES 17 8.1 Šifrování................................. 18 8.1.1 Transformace SubBytes() ................... 19 8.1.2 Transformace ShiftRowsQ................... 21 8.1.3 Transformace MixColumns().................. 22 8.1.4 Transformace AddRoundKeyQ ................ 23 8.2 Expanze klíče.............................. 23 8.3 Dešifrování ............................... 25 OBSAH 2 8.3.1 Transformace InvShiftRowsQ ................. 26 8.3.2 Transformace InvSubBytes().................. 27 8.3.3 Transformace InvMixColumnsQ................ 28 8.3.4 Inverze AddRoundKey() transformace ............ 28 8.3.5 Ekvivalentní dešifrování.................... 28 9 Implementace AES 30 9.1 Požadavky na délku klíče........................ 30 9.2 Klíčová omezení............................. 31 9.3 Parametrizace délky klíče, rozměru bloku a počtu cyklů....... 31 10 Módy AES 31 11 Útoky na AES 32 11.1 Diferenciální a lineární kryptoanalýza................. 33 11.2 Saturation útoky............................ 34 11.3 Algebraická struktura.......................... 34 11.4 Algebraické útoky............................ 35 11.4.1 Řetězové zlomky........................ 36 11.4.2 XL a XSL útoky........................ 36 11.5 Útoky hrubou silou........................... 37 2. Definice 3 1 Üvod Komunikace, ať už písemná nebo ústní, je stará jak lidstvo samo. Jakmile se lidé začali mezi sebou dorozumívat, vznikla potřeba přenášet některé informace takovým způsobem, aby se dostaly pouze ke konkrétní osobě. Tak vzniklo šifrování, z kterého se vyvinul obor zvaný kryptografie. Samozřejmě se způsoby i metody šifrování s novými poznatky a rozvojem myšlení hodně měnily, ale asi nejmarkantnější změna nastala s rozvojem počítačové technologie a nárůstem počítačové komunikace. V sedmdesátých letech se navíc začal používat elektronický bankovní systém a to bylo hlavním důvodem pro rozhodnutí ministerstva obchodu USA k vytvoření standardu pro ochranu dat zpracovávaných, ukládaných a přenášených počítači. Tento šifrový standard dostal jméno DES (Data Encryption Standard) a vstoupil v platnost roku 1977. Stal se nejrozšířenějším kryptografickým systémem na světě. Byl zárukou bezpečnosti ve veřejném i soukromém sektoru. Ve finančním sektoru se používal k ochraně komunikace po síti a dá se říct, že se stal mezinárodním standardem. Bohužel nic nevydrží věčně a tedy ani standard DES nevydržel technický pokrok a neodolal dešifrovacím útokům. Přestal být dostačující, jelikož byly vynalezeny přístroje, kterými se podařilo tuto šifru prolomit. Bylo tudíž nutné najít nový šifrový algoritmus, který by nahradil DES. Tento nový standard byl nazván AES (Advanced Encryption Standard) a je platný od roku 2002. Nyní doufáme, že bude spolehlivým ochráncem dat alespoň 10-15 let. Čas ukáže... 2 Definice 2.1 Slovník výrazů a akronymů AES - Advanced Encryption Standard (zdokonalený šifrovací standard) Afinní transformace - tranformace spočívající v násobení maticí s následným přičtením vektoru Bit - binární číslice mající hodnotu 1 nebo 0 Blok - sled bitů, který zahrnuje vstup, výstup, stav a rundovní klíč. Délka sledu je počet bitů, které obsahuje. Bloky jsou také interpretovány jako pole bytů Byte - skupina 8 bitů, která je brána jako samostatná jednotka nebo jako pole 8 jednotlivých bitů DES - Data Encryption Standard (datový šifrovací standard) Dešifrování - série transformací konvertující zašifrovaný text na otevřený text používaje šifrovací klíč 2. Definice 4 Expanze klíče - postup používaný k vygenerování série rundovních klíčů ze šifrovacího klíče Pole - očíslované seskupení identických jednotek (př.pole bitů) Rijndael - kryptografický algoritmus předepsaný v AES Rundovní klíč - rundovní klíče jsou hodnoty odvozené ze šifrovacího klíče pomocí procesu expanze, jsou aplikovány na stav při šifrování i dešifrování S-box - nelineární substituční tabulka používaná v některých transformacích nahrazujících byty a v procesu expanze klíče k provedení substituce bytové hodnoty Slovo - skupina 32 bitů, která je chápána jako samostatná jednotka nebo jako pole 4 bytů Stav - mezivýsledek šifrování, který může být znázorněn jako obdélníková matice bytů, která má 4 řádky a Nb sloupců Šifrovací klíč - tajný, kryptografický klíč, který je používaný v procesu expanze klíče k vygenerování množiny rundovních klíčů; může být znázorněn jako obdélníkové pole bytů mající 4 řádky a N k sloupců Šifrování - sled transformací, které konvertují otevřený text na zašifrovaný text používaje přitom šifrovací klíč Zašifrovaný text - výstupní data šifry nebo vstupní data inverzní šifry 2.2 Parametry algoritmů, symboly a funkce AddRoundKeyO - transformace při šifrování i dešiffování, ve které je rundovní klíč operací XOR přidán do stavu. Délka náhodného klíče se rovná velikosti stavu (např. pro Nb = 4, rundovní klíč se rovná 128 bitů/16 bytů) InvMixColumns() - transformace při dešifrování, která je inverzní k MixCo-lumns() InvshiftRows() - transformace při dešifrování, která je inverzní k ShiftRows() InvSubBytes() - transformace při dešifrování, která je inverzní k SubBytes() MixColumns() - transformace při šifrování, která vezme všechny sloupce stavu, zamíchá jejich data (nezávisle jeden na druhém) a vede k vytvoření nových sloupců 3. Standard DES 5 Nb - počet sloupců (32-bitová slova) ve stavu. Pro tento standard Nb = 4 Nk - počet 32-bitových slov v šifrovacím klíči. Pro tento standard Nk = 4, 6, nebo 8 Nr - počet cyklů, které jsou funkcí N k a Nb (je fixní). Pro tento standard Nr = 10, 12, 14 Rcon[] - rundovní konstantní pole slov RotWord() - funkce používaná v procesu expanze klíče, která bere 4-bytové slovo a provádí s ním cyklickou permutaci ShiftRows() - transformace při šifrování, která zpracovává stav cyklickým přesouváním posledních 3 řádků stavu různými ofsety SubBytes() - transformace při šifrování, která zpracovává stav za použití nelineárních bytových substitučních tabulek (S-boxy), které fungují na každém stavu bytové nezávisle SubWord() - funkce používaná v procesu expanze klíče, která bere 4-bytové slovo na vstupu a aplikuje S-box na každý ze 4 bytů, aby vytvořila výstupní slovo XOR - operace Exclusive-OR © - operace Exclusive-OR ® - násobení dvou polynomů (každý se stupněm < 4) modulo xA + 1. • - konečné prostorové násobení 3 Standard DES 3.1 Popis algoritmu DES je blokovou šifrou, která rozdělí vstupní text na části po 64 bitech a tyto 64-bitové bloky M otevřeného textu zpracovává na 64-bitové bloky C šifrového textu. Píšeme C = EK(M) a M = DK{C) K šifrování se používá klíč K o velikosti 56 bitů, který vznikne vynecháním paritních bitů z osmibytového slova. Algoritmus probíhá v 16-ti krocích. V každém z nich se vytvoří pracovní klíč ií^, kde i = 0,1,..., 15 následujícím způsobem. 56-bitový klíč K je permutován permutací PCI a poté vložen do dvou 28-bitových registrů. Obsah obou registrů je 3. Standard DES 6 cyklicky posouván v každém kroku o pi bitů, kde pi = 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1. Označme toto posunutí SHL. Jejich výsledné zřetězení, které má opět 56 bitů, je podrobeno další permutaci PC2, která zároveň redukuje počet bitů na 48. Výstup této permutace je již pracovní klíč K^ Postup vytváření pracovních klíčů je koncipován tak, aby každý bit klíče K byl obsažen v if0? • • • ? ^i5 dohromady 12 krát až 15 krát a probíhá buď před začátkem šifrovacího algoritmu nebo v jeho průběhu. Vlastní algoritmus zpracovávající blok M nejdříve provede počáteční permutaci IP, která permutuje všech 64 bitů otevřeného textu. Poté je rozdělen na pravou Ri a levou Li polovinu každou o velikosti 32 bitů. Pak probíhá 16 identických kroků, které vytvářejí dvojici (Lí+i, Rí+i) z dvojice (Z^, Ri) za pomocí pracovního klíče Ki. Ri je nejdříve rozšířen na 48 bitů prostřednictvím expanze E tak, že E(Ri) = E(r1,r2,...,r31,r32) (3.1) = (r32, ri, r2, r3, r4, r5, r4, r5, r6, r7, r8, r9, r8, r9, ri0, rn, ri2, n3, ri2, n3, ^14, ri5, rie, ri7, rie, ri7, ri8, ri9, r20, r2i, r20, r2i)r22, r23, r24, r25, r24, ^25, ^26, ^27, ^28, ^29, ^28, ^29, ^30, ^31, r32, rľ) a k výsledku je přičten klíč Ki modulo 2 (Toto sčítání je popsáno v části 7.1). Výstup E(Ri)®Ki je rozdělen do 8 částí po 6 bitech, které potom prochází přes S-boxy $i,..., S%. Tyto S-boxy jsou 6 x 4-bitové, což znamená, že výstup těchto S-boxů je 4 x 8 = 32-bitový. Tyto boxy se většinou zadávají tak, že 1. a 6. bit každé z osmi vstupních částí vybírá, jeden ze 4 možných 4 x 4-bitových boxů (odpovídá jednomu řádku v S-boxu). Vstupní i výstupní 4-bitová hodnota se pro jednoduchost zapisuje dekadicky jako 0 až 15 (viz. obr.l). Výstup S-boxů je upraven permutací P. Vznikne 32-bitové slovo, které je značeno f(Ri, Ki), poněvadž je vytvořeno z Ri a je funkcí klíče K^ Poslední operace v každém kroku je Li+! = Ri Rl+i = Lt® /(Äi, K,) (3.2) Po skončení 16.kroku proběhne záměna Li6 a i216 a blok o 64 bitech je permutován závěrečnou permutací IP~l (inverzní k IP) na výsledný šifrový text C. (x2,x3,x4,x5) X\ Xq 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 1 0 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 1 1 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 Obr.l Příklad S-boxu (S-box Si) 3. Standard DES 7 Dešifrování probíhá stejným způsobem jako šifrování, aby nemuselo být použito zcela jiné hardwarové schéma. Pouze pořadí výběru klíčů Ki je obrácené. Vytváříme-li klíče postupně, pak musíme výše popsané posunutí provádět doprava místo doleva a Pí = 0,1, 2, 2, 2, 2, 2, 2,1, 2, 2, 2, 2, 2, 2,1. Vše ostatní zůstane stejné. 3.2 Vlastnosti DES Počáteční a koncové permutace IP a IP~l jsou kryptograficky zanedbatelné. Ta první se používá pouze k rozprostření vlivu bitů z jedněch bytů otevřeného textu M do ostatních. Permutace IP~l zase napravuje vliv permutace IP. Závěrečná výměna slov L a i? je zde taky pouze kvůli tomu, aby dešifrovací proces byl shodný jako šifrovací. Základem algoritmu je transformace /. Skládá se ze substituce (S-boxy), permutace P a přitom zajišťuje vliv klíče na šifrování textu. Klíč je přičítán k proměnné R v modulu 2 jako heslo u proudových šifer, permutace P připomíná transpoziční systémy a S-Boxy substituční systémy. DES je jejich součinová šifra. DES je celkově substitučním systémem, ve kterém se pracuje se slovy délky 64 bitů. Je to tedy kódová kniha o 264 kódových výrazech. Bez znalosti klíče by mělo jít o neřešitelnou úlohu najít souvislost mezi klíčem if, otevřeným textem M a šifrovým textem C. Jednou z vlastností DESu je také vliv změny jednoho bitu v otevřeném textu M (respektive klíči if), na změnu každého bitu šifrového textu C. Pravděpodobnost této změny šifrového textu by měla být asi jedna polovina. To nám zajistí, aby dvě velmi podobné zprávy měli úplně jinou zašifrovanou podobu. Dalšími vlastnostmi, které požadujeme, jsou konfúze a difúze. Jde o to, aby každý bit klíče K a otevřeného textu M měl komplikovaný vliv na každý bit šifrového textu. Složitost nejvíce ovlivňují S-boxy. Každý výstupní bit S-boxu je nelineární funkcí všech vstupních bitů. Tato funkce musí být v každém případě nelineární, protože jinak bychom mohli schéma okamžitě rozluštit prostým vyřešením soustavy lineárních rovnic. Nelineárním vlastnostem DESu se věnovala velká pozornost, poněvadž zajišťují požadovanou konfúzi, ale bohužel kritéria tvorby S-boxů jsou doposud tajná, přestože právě zde byla objevena spousta slabin. 3.3 Módy DES DES pracuje na základě 4 módů, které vznikly podle různých potřeb, vycházíme z vlastního blokového algoritmu, tj. ze zobrazení EK : X —> X kde X je množina všech 64-bitových bloků. Počet prvků množiny X je 264 (X = {0, ljí1»2»-»64}). Tento algoritmus je zároveň prvním módem. ECB - (Electronic Code Book) Elektronická kódová kniha, která každý blok šifruje 3. Standard DES 8 zvlášť. Píšeme klasicky C = EK(M), kde M je otevřený text a C je šifrový text. Když budeme stejné bloky otevřeného textu opakovat, jejich zašifrovaná podoba bude též stejná. To způsobuje, že bez problému můžeme zfalšovat zprávy pouhým zopakováním šifrového bloku (tímto způsobem např. z částky 1 000 Kč jednoduše uděláme částku 1 000 000 Kč, aniž bychom znali klíč). Proto se tento mód nepoužívá k šifrování zpráv, ale jen k šifrování klíčů. CBC - (Cipher Block Chaining) Zřetězení šifrového textu, zapisujeme Cn = EK{Mn®Cn-l), kde Mn resp. Cn je n-tý blok otevřeného resp. šifrového textu. Tento mód používá výstup jednoho kroku šifrování k zašifrování následujícího bloku. CFB - (Cipher Feedback) Zpětná vazba ze šifrového textu, píšeme Cn = Mn®EK(In). In je vstupní registr, který je posunutý o k bitů doleva a zprava zase k bity Cn-\ doplněný. Mn je proud fc-bitových znaků otevřeného textu. Tento mód se používá, když je potřeba zpracovat data po znacích nebo po částech menších než 64 bitů. Zpětná vazba je vedena ze šifrového textu, ale jen v délce k bitů, přičemž u výstupu z blokového algoritmu je vyžíváno také jen k bitů. Tento systém zachovává vlastnost závislosti šifrového textu na předchozím otevřeném textu i předchozím šifrovém textu. OFB - (Output Feedback) Zpětná vazba z výstupu, symbolicky zapsáno jako Hn = EK(Jn), Cn = Mn © Hn. Jn je vstupní registr, který je o A; bitů posunutý doleva a zprava doplněný k bity Hn-i. Mn je opět proud fc-bitových znaků otevřeného textu a Hn je vytvořený proud hesla. Je to mód vhodný tam, kde je nežádoucí, aby se chyby vzniklé na komunikačním kanálu rozšiřovaly působením šifrového algoritmu do otevřeného textu. Jde například o přenosy dat s vysokou rychlostí a redundancí. U módů CBC, CBF a OFB je nezbytné vstupní registr na začátku naplnit nějakou hodnotou. Ta se nazývá inicializační vektor a odesílá se většinou na začátku zprávy. 4. Nedostatky šifry DES a její prolomení 9 4 Nedostatky šifry DES a její prolomení 4.1 Komplementárnost Vlastnost komplementárnosti je dána vztahem C = E k (M) implikuje nonC = EnonK(nonM), (4.1) kde non značí negaci bit po bitu. To je pravidelnost, která by se rozhodně neměla objevovat. Je umožněna tím, že negace klíče i vstupu se při jejich součtu mod 2 ve funkci f zruší: /(Ä, K) = f(nonR, nonK) (4.2) Totiž označíme-li R'Q = nonR0, LfQ = nonL0, a šifrujeme-li zprávu M' = (L^Rq) klíčem K' = nonK obdržíme postupně: M' = nonM , platí-li, že (L^R^) = non(Li, Ri), je i (L-+1, iž-+1) = non(Li+1, Äm), protože (LÍ+i,ií+i) = (ÄÍ,Líe/(ÄÍ,irí)) (4.3) = (nonRi, (nonLi) © /(iži, ÍQ)) = (nonRi, nonRi+i) = non(Li+1,Ri+1) Tedy (Z/16,i?i6) = non(Li6, i216) tj. nonEK(M) = EnonK(nonM). To se dá pak využít i k luštění v případě, že hledáme klíč K a máme k dispozici dvojice (M, C\) a (nonM, C2), které vznikly při šifrování tímto neznámým klíčem. Proveďme zašifrování Ek(M). Není-li tento výraz roven Ci, vylučujeme klíč K. Kdyby byl při šifrování non M použit klíč nonK, obdrželi bychom C2 = EnonK(nonM) = nonEK(M) (4.4) Nejsou-li si oba krajní výrazy, které máme k dispozici, rovny, můžeme vyloučit i klíč non K. Tím jsme nahradili jedno šifrování (klíčem nonK) za porovnávání výrazů, což je proti šifrování časově nesrovnatelně rychlejší. Prostor klíčů je tedy poloviční a hledání trvá polovinu času. 4.2 Nevhodný návrh S-boxů Dalším problémem šifry DES je velká korelovanost a nedostatečná nelinearitu výstupních bitů S-boxů. Například box S4 má pětasedmdesátiprocentní redundanci. 4. Nedostatky šifry DES a její prolomení 10 S-box S4 (xi,x6) (X2, X3, X4, £5) 00 01 10 11 0 0 0 0 0 0 0 1 0 0 10 0 0 11 0 10 0 0 10 1 0 110 0 111 0 111 110 1 1110 0 0 11 0 0 0 0 0 110 10 0 1 10 10 110 1 10 0 0 10 11 0 10 1 0 110 1111 0 0 0 0 0 0 11 10 10 0 110 10 0 1 0 0 0 0 110 0 10 11 0 111 110 1 0 0 11 1111 0 0 0 0 0 110 10 10 0 0 0 0 110 1 10 0 1 10 0 0 10 0 1 10 10 10 0 1 110 0 110 1 1110 1111 0 0 0 1 0 0 10 10 0 0 0 10 1 10 11 110 0 0 10 0 1111 0 10 0 0 111 0 0 10 110 0 0 0 0 1 10 10 1110 10 0 1 1111 0 0 0 1 0 0 11 1110 0 10 1 0 0 10 10 0 0 0 10 1 10 0 1 0 10 0 0 10 1 10 11 110 0 0 111 0 0 10 1110 Jeho 4 boxy 4x4 (při hodnotách krajních bitů Xi,xq = 00, 01,10,11) jsou jednoduše odvoditelné jen od prvního z nich (00). Platí dokonce vztah S4,(x © 000001) = (12)(34)S4(x) © (x6, nonx6, nonx6, x6), (4.5) kde x = (xi, x2) £3, £4, £5, xq) je vstup a symbolický zápis (1,2) znamená výměnu 1. a 2. bitu. Označíme-li y = (?/i, y2) 2/3, y a) jako výstup, potom součet (yi © y2) je na x6 závislý pouze lineárně a (yi © y2 © 2/3 © 2/4) na něm nezávisí vůbec. Taková pravděpodobnost je nežádoucí. 4.3 Slabé a poloslabé klíče Slabosti standardu se objevily též při studiu klíčů. Budou-li oba registry, používané při tvorbě pracovních klíčů, na počátku obsahovat konstantní bity (0 nebo 1), pak je operace SHL a PC2 nijak nezmění a klíče Ki si budou rovny. Tím nastane i nežádoucí rovnost EK = DK. Celkem existují 4 tyto klíče (podle toho, zda jeden z registrů obsahuje nuly nebo jedničky). Podobnou vlastnost má 6 dvojic tzv. poloslabých klíčů K\ a K2l pro něž platí Ek\Ek2 = Id neboli EK\ = DK2. (4.6) Takové klíče jsou shodné, ale pořadí jejich použití je opačné. Tak se nám objeví efekt, že při šifrování druhým klíčem probíhá postupně dešifrování klíčem prvním. 5. Nový standard ABS 11 Příklad: (01FE01FE01FE01FE, FE01FE01FE01FE01) (4.7) 4.4 Příliš krátký klíč Všechny předešlé nedostatky jsou závažné, ale příčinou pádu standardu DES se nakonec stala právě délka šifrovacího klíče. To, co nezvládli kryptologové svými analytickými útoky, docílil rozvoj výpočetní techniky. Vyluštit šifrový text tzv. hrubou silou znamená, že odzkoušíme všechny možné klíče. Právě malý objem klíče - 56 bitů se stal pro DES osudným. Již v roce 1975 Diffie a Hellman ze Stanfordské univerzity uvažovali, že by pomocí tehdejší technologie byli schopni sestrojit stroj na dešifrování DES algoritmu, který by stál 20 000 000 dolarů. Tento stroj by vyzkoušel cca 1017 klíčů za den. Nicméně dokud takový stroj nebyl na světě, stále bylo slyšet argumenty, že to a)není možné, b)bylo by to příliš drahé, c)stroj by se musel přehřívat, d)nikdo nebude investovat miliony dolarů do něčeho tak nejistého atd. Dnes je tento stroj na světě. V roce 1995 se na veřejnost dostává informace, že NSA (National Security Agency) vlastní stroj, který je schopen DES rozluštit do 5 minut. Toto zařízení sestrojila firma The Harris Corporation. Pro ty, kteří ještě stále pochybovali, bylo komerčně sestrojeno a předvedeno speciální zařízení DES-cracker(1998), které je schopno rozluštit všech 256 klíčů do 9 dnů a nalézt tak příslušné řešení. DES musel být nahrazen jiným standardem. Prozatímně jej NIST (National Institute of Standards and Technology) nahradil implementací TripleDES. V podstatě se jedná o opakované použití algoritmu DES. Kryptologické veřejnosti však bylo jasné, že řešení není optimální (především pro nižší rychlost), a proto v roce 1997 NIST vypisuje veřejnou soutěž na vytvoření nového komerčního standardu pro symetrické šifrování. 5 Nový standard AES Pro název tohoto nového algoritmu se vžilo označení AES (Advanced Encryption Standard). Vybraný standard měl být velice flexibilní, lehce implementovatelný, měl pracovat s 32-bitovým mikroprocesorem, 64-bitovým procesorem, ale i 8-bitovým (v tzv. režimu smart card). V červnu 1998, kdy byla stanovena uzávěrka pro podání návrhu, bylo celkem předloženo 15 kandidátů. Z nich bylo v květnu následujícího roku do dalšího kola vybráno pět: MARS, RC6, Rijndael, Serpent a Twofish. V říjnu 2000 byl vybrán vítěz a 26.11. roku 2001 byl vyhlášen nový šifrový symetrický standard pro šifrování senzitivních informací s platností od 26.5.2002. Tímto výtězem se stal algoritmus Rijndael, navržený týmem belgických kryptologů - Vincentem Rijnmenem a Joanem Deamenem. Rijndealův algoritmus je symetrická bloková šifra, která umí zpracovat datové bloky o 128 bitech. 6. Označení a konvence ABS 12 Používá šifrovací klíče s délkami 128, 192 a 256 bitů. Rijndeal je navržený tak, aby používal pouze celobytové operace. AES se na první pohled diametrálně liší od DES, ale opak je pravdou. AES ve skutečnosti vychází z těch teoretických principů, které byly použity u DES a za celých 25 let existence DES nikdy nebyly zpochybněny. Přejděme už ale k přesnému popisu nového standardu. 6 Označení a konvence AES 6.1 Vstupy a výstupy Každý vstup i výstup AES algoritmu se skládá z posloupnosti 128 bitů. Tato posloupnost bude nazývána bloky stejně jako u standardu DES a počet bitů, které obsahuje, bude nazýván jejich délkou. Šifrovací klíč AES algoritmu je posloupnost 128, 192 nebo 256 bitů. Vstup, výstup nebo klíč jiné délky není tímto standardem povolen. Bity v takovýchto posloupnostech budou očíslovány od nuly do čísla o jedno menšího než je délka posloupnosti (bloku nebo klíče). Číslo i odpovídající danému bitu je známo jako index a bude v rozsahu 0 < i < 128, 0 < i < 192, 0 < i < 256. 6.2 Byty Základní jednotka v AES algoritmu je byte, sekvence 8 bitů braná jako samostatná jednotka. Vstup, výstup nebo šifrovací klíč jsou zpracovávány jako pole bytů, které je vytvořeno rozdělením této posloupnosti do skupin po osmi bitech, které tvoří toto pole bytů (viz.6.3). Pro vstup, výstup nebo klíč značený a budou byty ve výsledném poli značeny an nebo a[n], kde n je v jednom z následujících rozsahů: Délka klíče = : 128 bitů, 0 < i < 16 Délka klíče = : 192 bitů, 0 < i < 24 Délka klíče = 256 bitů, 0 < i < 32 Délka bloku = = 128 bitů, 0 < i < 16 Všechny hodnoty bytů v AES algoritmu budou prezentovány jako zřetězení jednotlivých hodnot bitů (0 nebo 1) v závorkách v pořadí {67, b6l 65, 64, 63, b2l &i, b0}. Tyto byty jsou interpretovány jako konečné prvky pole používaje polynomiální reprezentace: 7 b7x7 + b6x6 + 65X5 + bAxA + b3x3 + b2x2 + bxxl + b0 = ^ b{x{ (6.1) i=0 6. Označení a konvence ABS 13 Například, {0100011} identifikuje určitý konečný prvek pole x6 + ŕ + x+ 1. To také vede k označení hodnot bytů pomocí hexadecimální notace. Každá ze dvou skupin čtyř bitů je označena jedním symbolem jako na obr.2. Bitový vzor symbol 0100 4 0101 5 0110 6 0111 7 Bitový vzor symbol 1100 c 1101 d 1110 e 1111 f Bitový vzor symbol 0000 0 0001 1 0010 2 0011 3 Bitový vzor symbol 1000 8 1001 9 1010 a 1011 b Obr.2 Hexadecimální reprezentace bitových vzorů Proto {01100011} může být reprezentováno jako {63}, kde symbol označující 4-bitovou skupinu obsahující vyšší očíslované bity je vlevo. Některé konečné operace pole zapojí jeden součtový bit (&8). Tento extra bit je reprezentován '{01}' a přímo předchází 8-bitovému bytu, například 9-bitová posloupnost bude reprezentována jako {01}{lb}. 6.3 Pole bytů Pole bytů bude reprezentován následujícím způsobem: a^a\a2... cli§ Byty a bitové řazení je odvozeno od 128-bitové vstupní sekvence inputoinputiinput2... inputs následovně a0 = {inputo, inputi..., inputs} cli = {inputs, inputg ..., inputs} <2i5 = {input i2o, input úl..., input 127} Vzor může být roztažen na delší posloupnosti (např. 192-bitové a 256-bitové klíče), zapíšeme-li to tedy obecně an = {inputsn, inputsn+u • • • > input8n+7} (6.2) Obr.3 nám ukáže, jak jsou bity v každém bytu číslovány. Vstupní bitová sekvence 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Číslo bytu 0 1 2 Čísla bitů v bytu 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Obr.3 Indexy pro byty a bity. 7. Matematické operace potřebné pro AES 14 6.4 Stav Interně jsou operace AES algoritmu prováděny na 2-dimenzionálním poli bytů, které se nazývá stav. Stav se skládá ze 4 řádků bytů obsahujících Nb bytů, kdeNb je velikost bloku dělitelná 32. Ve stavovém poli označeném symbolem s má každý jednotlivý byte 2 indexy: číslo řádku r v rozmezí 0 < r < 4 a číslo sloupce c v rozmezí 0 < c < Nb. To umožňuje jednotlivému bytu stavu, aby byl značen buď sc^r nebo s[c, r]. Na začátku šifrovacího i dešifrovacího algoritmu je vstup - pole bytů m0, mi,..., in^ - kopírován do stavu, jak je nakresleno na obr.4. Šifrovací a dešifrovací operace jsou poté prováděny v tomto stavovém poli a nakonec jejich konečná hodnota je kopírována na výstup - pole bytů outo, outi,..., out\§. Vstupní byty Stavové pole in0 in^ in8 in12 IU\ inh in9 in13 in2 in6 in10 mi4 in3 in>j inn mis 50,0 50,1 50,2 50,3 «1,0 Sl,l 5l,2 5l,3 52,0 52,1 52,2 52,3 53,0 53,1 53,2 53,3 Výstupní byty outo OUt^ outs OUt 12 outi out$ OUtg OUtis out2 out6 OUtio OUti4 outs OUťj outn OUtis Obr.4 Stavové pole, vstup a výstup Proto na začátku šifrování nebo dešifrování je vstupní pole in kopírováno do stavového pole podle následujícího schématu: in[r + 4c] pro 0 < r < 4 a 0 < c < Nb (6.3) 6.5 Stav jako pole sloupců Čtyři byty v každém sloupci stavového pole tvoří 32-bitová slova, kde číslo řádku r stanovuje index pro 4 byty v každém slově. Stav proto může být interpretován jako jednodimenzionální pole 32-bitových slov (sloupců), w0 ... w3, kde číslo sloupce c stanovuje index v tomto poli. Proto například v obr.4 může být stav považován za pole 4 slov následovně: W0 = S0,0Sl,0S2,0S3,0 Wl = 50,2 ^3]- Uvědomme si, že polynomy v této části se chovají trochu jinak, než polynomy používané v definici konečného pole prvků, i když oba typy polynomů používají stejnou neznámou x. Koeficienty v této části jsou samy členy konečného pole, např. bytů místo bitů; také násobení 4-členými polynomy používá jiné polynomické krácení, definované dále. Rozdíl můžeme vždy poznat z kontextu. Pro ilustraci sčítání a násobení nechť b{x) = b3x3 + b2x2 + b±x + b0 (7.6) definuje druhý 4-členný polynom. Sčítání se provádí sečtením koeficientů konečného pole stejné mocniny x. Toto sčítání odpovídá XOR operaci mezi odpovídajícími byty v každém slově - v ostatních slovech XOR operaci kompletních hodnot slov. Použijeme tedy rovnice (7.5) a (7.6): a{x) + b{x) = (a3 0 b3)x3 + (a2 0 b2)x2 + (aľ © bľ)x + (a0 © &0) (7.7) Násobení je docíleno ve dvou krocích. V prvním je součin polynomů c{x) = a{x) • b{x) algebraicky rozšířen, stejné mocniny jsou seskupeny a dají nám c{x) = CqX6 + C5X5 + C4X4 + C3X3 + C2X2 + C\X + Cq (7.8) kde c0 = a0 • b0 c\ = a\ • 60 © ^0 • b\ c2 = a2 • 60 © ai • h © a0 • b2 c3 = a3 • b0 © a2 • 61 © cli • b2 © a0 • b3 (7.9) c4 = a3 • 61 © a2 • b2 © ai • 63 c5 = a3 • 62 © &2 • &3 c6 = a3 • 63 Výsledek c(x) nereprezentuje 4-bytové slovo. Proto tedy druhý krok násobení je zkrátit c(x) modulo polynom stupně 4; výsledek však může být krácen i polynomem nižšího stupně. Pro AES algoritmus je toto prováděno polynomem xA + 1, aby xl mod (x4 + l) = ^mod4 (7.10) 8. Specifikace algoritmu AES 18 Modulový součin a{x) a b{x), značený a{x) ® b{x)1 je daný 4-členným polynomem d{x) definovaným následovně: d{x) = d3x3 + d2x2 + d\x + d0 (7.11) s d0 = (a0 • &o) © («3 • h) © («2 • h) © («i • M di = (ai • 60) © («o • &i) © (^3 • 62) © («2 • h) d2 = (a2 • &o) © (^i • &i) © (a0 • b2) © (a3 • 63) d3 = (a3 • 60) © (^2 • &i) © («i • h) © («o • 63) Když a(x) je fixní polynom, operace popsaná v rovnici (7.11) může být napsaná v maticové formě jako: po d\ \d2 Protože x4 +1 není ireducibilní polynom nad GF(28), násobení pevným 4-členným polynomem není nezbytně invertibilní. Ačkoliv AES algoritmus specifikuje pevný 4-člený polynom, k tomuto polynomu inverze existuje (viz.8.1.3 a 8.3.3): a{x) = {03}x3 + {01}x2 + {01}x + {02} (7.14) a~\x) = {0b}x3 + {0d}x2 + {09}x + {0e} (7.15) Jiný polynom používaný v AES algoritmu (viz funkce RotWordQ v 8.2) má a0 = a\ = a2 = {00} a a3 = {01}, tedy je to polynom x3. Zkoumání rovnice (7.13) nám ukáže, že jeho účel je vytvoření výstupního slova rotací bytů ve vstupním slově. To znamená, že [&0, &i, b2) b3] je transformováno na [&1? b2)b3) &o] 8 Specifikace algoritmu AES Pro AES algoritmus je velikost vstupního bloku, výstupního bloku a stavu 128 bitů. To je reprezentováno Nb = 4, což odráží číslo 32-bitovéhoslova (počet sloupců) ve stavu. Pro AES algoritmus, délka klíče K je 128, 192 nebo 256 bitů. Délka klíče je representována Nk = 4, 6 nebo 8, což odráží číslo 32-bitového slova (počet sloupců) v klíči. Počet cyklů, které provádí AES algoritmus během realizace algoritmu, záleží na délce (7.12) a0 a3 a2 ai bo <2i a0 a3 a2 61 a2 CL\ a0 a3 b2 a3 a2 CL\ a0 b3 (7.13) 8. Specifikace algoritmu AES 19 klíče. Počet cyklů je reprezentován Nr, kde Nr = 10 když Nk = 4 Nr = 12 když Nk = 6 Nr = 14 když Nk = 8 Jediné kombinace klíč-blok-cyklus, která se řídí tímto standardem jsou dány v obr.5. Délka klíče (Nk slov) Velikost bloku (Nb slov) Počet cyklů (A^r) AES-128 4 4 10 AES-192 6 4 12 AES-256 8 4 14 Obr.5 Kombinace klíč-blok-cyklus Pro šifrování i dešifrování používají AES algoritmus rundovní funkce, které jsou složeny ze 4 odlišných bytově-orientovaných transformací: 1) bytová substituce používá substituční tabulku (S-box) 2) posouvání řádku stavového pole různými ofsety 3) míchání dat v každém sloupci stavového pole 4) přidání náhodného klíče do stavu. Tyto transformace (a jejich inverze) budou popsány dále. 8.1 Šifrování Na začátku šifrování je vstup kopírován do stavového pole. Po počátečním přičtení náhodného klíče je stavové pole transformováno implementací rundovní funkce 10, 12 nebo 14krát (podle délky klíče) s posledním cyklem lišícím se jen nepatrně od předešlých Nr — 1 cyklů. Konečný stav je potom kopírován na výstup. Zaokrouhlovací funkce je parametrizována použitím klíčové tabulky, která je složena z 1-rozměrného pole 4-bytových slov odvozených pomocí procesu expanze klíče popsaného v paragrafu 8.2 Šifra je popsána v pseudokódu na obr.6. Jednotlivé transformace - SubBytes(), shiftRowsQ, MixColumns() a AddRoundKey() - které zpracovává stav, jsou popsány v následujících paragrafech. V obr.6 pole w[] se rovná klíčové tabulce, která je popsána v 8.2. Všech Nr cyklů je stejných s výjimkou posledního cyklu, který nezahrnuje transformaci MixColumnsQ. 8. Specifikace algoritmu AES 20 Cipher(byte in[4*Mb], byte out[4*Nb], word w[nb*(Nr+l)]) begin byte state[4,Mb] state = in AddRoundKey(state, w[0, Mb-1]) viz.5.1.4 for round = 1 step 1 to Nr-1 SubBytes(state) viz.5.1.1 shiftRows(state) viz.5.1.1 MixColumns(state) viz.5.1.1 AddRoundKey(state , w[round*Mb, (round+l)*Nb-l]) end for SubBytes(state) shiftRows(state) AddRoundKey(state, w[Mr*Mb, (Nr+l)*Nb-l]) out = state end Obr.6 Pseudokód pro šifrování 8.1.1 Transformace SubBytes() Transformace SubBytes() je nelineární bytová substituce, která pracuje nezávisle na každém bytu stavu používaje substituční tabulku (S-box). Tento S-box (obr.7), který je invertibilní, je sestrojen složením 2 transformací: 1. Vezměte násobnou inverzi v konečném poli GF(28), popsanou v paragrafu 7.2., prvek {00} je značen sám na sebe. 2. Aplikujte následující afinní transformaci (nad GF(2)): fy = bi® &(i+4) mod 8 © &(i+5) mod 8 © &(i+6) mod s © &(i+7) mod 8 © Q (8.1) pro 0 < i < 8, kde b{ je i-tý bit v bytu a q je i-tý bit bytu c s hodnotou {63} neboli {01100011}. Zde i kdekoli jinde bude čárka nad proměnnou značit, že proměnná je aktualizována hodnotou vpravo. 8. Specifikace algoritmu AES 21 V maticovém tvaru může být afinní transformace prvku z S-boxu vyjádřena jako: 10 0 0 1111" 110 0 0 111 1110 0 0 11 11110 0 0 1 111110 0 0 0 111110 0 0 0 111110 00011111 pól b[ b>2 % b'. K &6 kl M T 6i 1 62 0 63 &4 + 0 0 &5 1 &6 1 M 0 (8.2) Matice použitá v (8.2) je zřejmě regulární, protože její inverzní podoba je použita v inverzní transformaci InvSubBytes při dešifrování. Obr.7 ilustruje efekt transformace SubBytesQ na stav. 5o,o S0,1 50,2 50,3 5(3,0 50,1 50,2 50,3 Sl,0 5r,c _ Sl^ JlA. s-Box 5j,Q | Sl,2 Sl,3 ^2,0 52,1 52,2 52,3 52,0 52,1 52,2 52,3 53,0 53,1 53,2 53,3 53,0 53,1 53,2 53,3 Obr.7 SubBytes() aplikuje S-box na každý byte stavu S-box používaný v transformaci SubBytes() je reprezentován v hexadecimálním tvaru na obr.7. Například je-li s1}1 = {53}, potom substituční hodnota může být určena jako průsečík řádku s indexem '5' a sloupce s indexem '3'. Toto nám dá výsledek s[ ľ ={ed}. 8. Specifikace algoritmu AES 22 Y n 1 2 3 4 5 6 7 8 9 a b c d e f U ľoä" Vc V7 7 b t2 "6b "6T ~Č5~ ~3Ö~ "ÔT ~67~ ~2b Tě" ďT ab 76" 1 ca 82 c9 7d ta 59 47 fO ad d4 a2 af 9c a4 72 cO 2 bV td 93 26 36 3f f7 cc 34 a5 e5 fl 71 d8 31 15 3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75 4 09 83 2c la lb 6e 5a aO 52 3b d6 b3 29 e3 2f 84 5 53 dl 00 ed 20 fc bi 5b 6a cb be 39 4a 4c 58 cf 6 dO ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 8 cd Oc 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 9 60 81 4f de 22 2a 90 88 46 ee b8 14 de 5e Ob db a eO 32 3a Oa 49 06 24 5c c2 d3 ac 62 91 95 e4 79 b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08 c ba 78 25 2e lc a6 b4 c6 e8 dd 74 lf 4b bd 8b 8a d 70 3e b5 66 48 03 f6 Oe 61 35 57 b9 86 cl ld 9e e el f8 98 11 69 d9 8e 94 9b le 87 e9 ce 55 28 df f 8c al 89 Od bf e6 42 68 41 99 2d Of bO 54 bb 16 Obr.7 S-box: Substituční hodnoty pro byte xy (v hexadecimálním tvaru) 8.1.2 Transformace ShiftRows() V transformaci ShiftRows() jsou byty v posledních 3 řádcích stavu cyklicky zaměňovány přes odlišné počty bytů (ofsety). První řádek r = 0 není zaměňován. Přesněji transformace ShiftRows() postupuje následovně: S'rc = Sri(c+8hift(r,Nb))modNb Pr° 0 < r < 4 a 0 < Nb (8.3) kde hodnota shift{r) Nb) záleží na čísle řádku r následovně (připomeňme, že Nb = 4): shift(l, 4) = 1; shift(2, 4) = 2; shift(3, 4) = 3. (8.4) Toto má efekt pohyblivých bytů do "nižších' pozic v řádků. Nejnižší byty dáme na konec řádku. Obr.8 ilustruje transformaci ShiftRowsQ. 8. Specifikace algoritmu AES 23 ShiftRowsQ 5r,0 Sr,l 5r,2 5r,3 S So,o 50,1 50,2 50,3 Sl,0 Sl,l 5l,2 5l,3 ^2,0 52,1 52,2 52,3 53,0 53,1 53,2 53,3 Cf h h 5r,0 5r,l 5r,2 5r,3 s' 50,0 50,1 50,2 50,3 5l,l 5l,2 5l,3 5l,0 52,1 52,2 52,3 52,1 53,1 53,2 53,3 53,2 Obr.8 ShiftRows() cyklicky posouvá poslední 3 řádky stavu 8.1.3 Transformace MixColumnsQ Transformace MixColumns() pracuje na stavu sloupec po sloupci, zpracovává každý sloupec jako 4-členný polynom. Sloupce jsou považovány za polynomy nad GF(28) a násobeny modulo x4 + 1 pevným polynomem a(x) a(x) = {03}x3 + {01}x2 + {01}x + {02} (8.5) Jak popisuje paragraf 7.3, může to být zapsáno jako maticové násobení. Nechť sf(x) = a{x) (g) s{x): 30,c 52,c 33,c. 02 03 01 01" S0,c 01 02 03 01 Sl,c 01 01 02 03 $2,c 03 01 01 02 ý3,c_ pro 0 < c < Nb (8.6) Jako výsledek tohoto násobení jsou 4 byty ve sloupci přemísťovány následovně: 50,c / l,c / 2,c / 3,c ({02} • s0,c) © ({03} • si>c) © s2,c e S3,c 50,c © ({02} • S1>c) e ({03} • S2,c) e 53,c 50,c © Sl,c © ({02} • S2>c) 0 ({03} • S3>c) ({03} • S0jC) © Si>c 0 52,c 0 ({02} • S3>c) Obr. 10 ilustruje transformaci MixColumns(). 8. Specifikace algoritmu AES 24 MixColumnsQ 50,0 50,1 50,2 50,3 51,0 <1 51,2 51,3 52,0 52,1 52,2 52,3 53,0 53,1 53,2 53,3 50,0 50,1 50,2 50,3 Sl,0 SM r1,2 5i,3 ^2,0 52,1 52,2 52,3 53,0 53,1 53,2 53,3 Obr.10 MixColumns() pracuje na stavu sloupec po sloupci 8.1.4 Transformace AddRoundKey() V transformaci AddRoundKeyQ je rundovní klíč přidán do stavu jednoduchou bitovou XOR operací. Každý rundovní klíč se skládá z Nb slov z tabulky klíčů (je popsaná v paragrafu 8.2). Všechny tyto Nb slova jsou přidávány do sloupců stavu tak, že [sÓ,c> 5l,c> s2,c> 4,J = [50,c, Sl,c, S2,c, S3,c] © [™roimd*iW+c] pro 0 < C < Nb (8.7) fcdefí^] jsou slova tabulky klíčů a round je hodnota v řádku 0 < round < Nr. Při šifrování se provádí počáteční přičtení rundovního klíče (když round = 0) ještě před první aplikací rundovní funkce. Aplikace AddRoundKey() transformace na Nr cyklů šifry proběhne, když 1 < round < Nr. Průběh této transformace je ilustrován na obr. 11, kde l = round * Nb. I = round * Nb 50,0 50,c 50,2 50,3 wA Wl+c ^/+2 ^/+3 50,0 50,1 50,2 50,3 5l,Q 5i J 5i72 5l,3 gl,0 s' gl,2 51,3 52,0 p2^ 52,2 52,3 © S2,o] 52,1 52,2 52,3 53,0 S3,c 53,2 53,3 53,0 53,1 53,2 53,3 Obr.11 AddRoundKey()"XORuje" každý sloupec stavu slovem z tabulky klíčů 8.2 Expanze klíče AES algoritmus vezme šifrovací klíč K a provede postup expanze klíče pro vygenerování tabulky klíčů. Expanze klíče generuje celkově Nb(Nr + 1) slov. Čtveřice 8. Specifikace algoritmu AES 25 slov tvoří jeden mndovní klíč Ki, kde 0 < i < 10. Začneme klíčem K, roztáhneme ho a dostaneme lineární pole w. Toto pole je délky Nb(Nr + 1). Ukažme si, jak to funguje pro Nb = 4 a Nr = 10, tedy w má 4 * (10 + 1) = 44 slov po 32 bitech. Každý blok 4 slov má 128 bitů a je to podklíč K^. První rundovní klíč je Ko = (^0,^1,^2,^3), který je zkopírován ze šifrovacího klíče K. Další podklíč jsou získány z K0. Pravidlo je následující: W4 = w0 xor tempi wh = wľ xor W4 w6 = w2 xor W4 W7 = w3 xor W4 w8 = W4 xor temp2 W43 = w39 xor w42 W44 = W40 xor tempu Podívejme se na případy w^ kde (z mod TV/c 7^ 0). Pravidlo je Wi = ^-tv/c xor Wi-x s TVr = 4. Když (z mod N k = 0), pak máme Wi = Wi-ivfc xor tempk kde tempk = S^&Worc^SiWi-i xor i2con[A;]). SubWord je aplikován na i^_i s posunutým bytem a i?con[A;] je definován jako Rcon[k] = (RCk, 00, 00, 00) s i?Ci = 1, Rd=X x RCk-! = Xk~ľ a RCk G GF(28) for A; = z/4 a z = 4, 8,12,..., 44. Ukažme si to na příkladu. Uvažujme klíč KQ = K = 00 01 02 03 04 05 06 07 08 09 0A OB 0C OD 0E OF Výpočet Wi, když i je násobek 4, dostaneme za použití pravidla Wi = Wi-4 xor SubWord(SiWi-i) xor Rcon[k], výpočet Wi, když i není násobek 4, dostaneme za použití pravidla Wi = Wi_4 xor Wi-i Počítané hodnoty jsou: W4 = wq xor S^&Worc^SiWa) 8. Specifikace algoritmu AES 26 D7 = 00 xor D7 AA = 01 xor AB 74 = 02 xor 76 FD = 03 xor FE w^O] = tojO] xor rconfl] F>6 = D7 xor 02 w5 = = w\ xor w4 wq = Vú2 xor U>5 U>7 = - u>3 xor wq D2 = = 04 xor F>6 ZM = 08 xor D2 L>6 = = 0C xor DA AF-- = 05 xor AA A6 = 09 xor AF AS = = OD xor A6 72 = = 06 xor 74 78 = (L4 xor 72 76 = = 0E xor 78 FA-- = 07 xor FD Fl = OB xor FA FE-- = OF xor Fl Rundovní klíč Kx = D6 AA 74 FD D2 AF 72 FA DA A6 78 Fl D6 AB 76 FE Stejným způsobem určíme i další rundovní klíče K2)..., i^io 8.3 Dešifrování Šifrovcí transformace v paragrafu 8.1 mohou být převráceny a poté implementovány v opačném pořadí, aby přímo vytvořily inverzní šifru pro AES algoritmus. Jednotlivé transformace použité při dešifrování - InvShiftRowsQ, InvSubBy-tes(), InvMixColumnsQ a AddRoundKeyQ - zpracovávají stav a jsou popsány v následujících odstavcích. Dešifrování je popsáno v pseudokódu na obr. 12. Pole w[] obsahuje tabulku klíčů. 8. Specifikace algoritmu AES 27 InvCipher(byte in[4*Mb], byte out[4*Mb], word w[nb*(Nr+l)]) begin byte state[4,Mb] state = in AddRoundKeyCstate, w[Nr*Nb, (Mr+l)*Mb- -1]) viz.5.1.4 for round = Nr-1 step -1 downto 1 InvshiftRows(state) viz .5.3 1 InvSubBytes(state) viz.5.3. AddRoundKey(state, w[round*Mb, InvMixColumns(state) viz.5.3 1 (round+l)*Nb .1 -1]) end for InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[0 , Nb- 1]) out = state end Obr. 12 Pseudokód pro dešifrování 8.3.1 Transformace InvShiftRows() InvShiftRows() je inverze od ShiftRows() transformace. Byty v posledních 3 řádcích stavu jsou cyklicky posouvány přes různý počet bytů (ofsety). První řádek r = 0 není posouván. Dolní tří řádky jsou cyklicky posouvány o Nb-shift(r,Nb) bytů, kde hodnota shift(r,Nb) záleží na čísle řádku a je dosazena do rovnice (8.4). Speciálně InvShiftRows() transformace postupuje následovně: sr,(c+8hift(r,Nb))moáNb = Sr,c pro 0