9. Autentičnost a digitální podpisy
Jan Paseka
Ústav matematiky a statistiky Masarykova univerzita
6. prosince 2021
□ -
Fl  V předchozích kapitolách jsme předvedli metody, které mohou pomoci proti pasivnímu útoku; pomocí zašifrování lze data pro nepovolané osoby udělat nečitelná. Téma této kapitoly je věnováno metodám proti aktivnímu útoku.
Fl  V předchozích kapitolách jsme předvedli metody, které mohou pomoci proti pasivnímu útoku; pomocí zašifrování lze data pro nepovolané osoby udělat nečitelná. Téma této kapitoly je věnováno metodám proti aktivnímu útoku.
Kryptografický protokol specifikuje, jakým způsobem každá strana začíná a odpovídá na zprávy a to včetně chybných nebo ilegálních zpráv.
Fl  V předchozích kapitolách jsme předvedli metody, které mohou pomoci proti pasivnímu útoku; pomocí zašifrování lze data pro nepovolané osoby udělat nečitelná. Téma této kapitoly je věnováno metodám proti aktivnímu útoku.
Kryptografický protokol specifikuje, jakým způsobem každá strana začíná a odpovídá na zprávy a to včetně chybných nebo ilegálních zpráv.
Protokol může rovněž specifikovat požadavky na nastavení jako je např. nastavení knihovny veřejných klíčů. Strana, která se řídí protokolem, bude ochráněna proti jistým specifikovaným nebezpečím i v tom případě, že ostatní strany se protokolem neridi.
Úvod Integrita a autenticita One-way
Je zřejné, že Mr. X může způsobit podstatně větší škodu, jestliže neumí pouze pasivně číst data, nýbrž je dokonce aktivně změnit.
Je zřejné, že Mr. X může způsobit podstatně větší škodu, jestliže neumí pouze pasivně číst data, nýbrž je dokonce aktivně změnit.
Skutečně se u většiny dnešních aplikací v kryptologii požaduje autentičnost dat a ne jejich utajení.
Je zřejné, že Mr. X může způsobit podstatně větší škodu, jestliže neumí pouze pasivně číst data, nýbrž je dokonce aktivně změnit.
Skutečně se u většiny dnešních aplikací v kryptologii požaduje autentičnost dat a ne jejich utajení.
Je zvykem rozlišovat 3 základní typy problémů, které vzniknou z různých variant aktivního útoku. Odpovídající 'bezpečnostní architektura" byla vytvořena institucí International Standards Organisation (\SO) v "Security Addendum k referenčnímu modelu ISO".
Je zřejné, že Mr. X může způsobit podstatně větší škodu, jestliže neumí pouze pasivně číst data, nýbrž je dokonce aktivně změnit.
Skutečně se u většiny dnešních aplikací v kryptologii požaduje autentičnost dat a ne jejich utajení.
Je zvykem rozlišovat 3 základní typy problémů, které vzniknou z různých variant aktivního útoku. Odpovídající 'bezpečnostní architektura" byla vytvořena institucí International Standards Organisation (\SO) v "Security Addendum k referenčnímu modelu ISO".
Nejdříve je třeba ptát se, zda byla zpráva přenesena bez změny nebo zfalšování; jedná se o požadavek integrity zprávy.
Je-li Mr. X v pozici, že může měnit zprávy, nezbývá než doufat, že příjemce zpozoruje případnou změnu. Musí být schopen rozhodnout, zda byla zpráva změněna či nikoliv.
Je-li Mr. X v pozici, že může měnit zprávy, nezbývá než doufat, že příjemce zpozoruje případnou změnu. Musí být schopen rozhodnout, zda byla zpráva změněna či nikoliv.
Druhý typ útoku je prvnímu podobný; zde je položen důraz na otázku, zda si příjemce může být jistý, že zpráva skutečně pochází od údajného odesilatele. Mluvíme pak o autentičnosti zprávy.
Je-li Mr. X v pozici, že může měnit zprávy, nezbývá než doufat, že příjemce zpozoruje případnou změnu. Musí být schopen rozhodnout, zda byla zpráva změněna či nikoliv.
Druhý typ útoku je prvnímu podobný; zde je položen důraz na otázku, zda si příjemce může být jistý, že zpráva skutečně pochází od údajného odesilatele. Mluvíme pak o autentičnosti zprávy.
Poslední varianta je autentičnost uživatele: Může osoba dokázat svoji identitu? Příjemce potřebuje prostředek, aby se mohl přesvědčit o tom, že skutečně komunikuje s tou osobou, o které si myslí, že je s ní spojen.
Po pěti letech byla šifra AES schválena jako nejvhodnější z patnácti návrhů. Dne 26. května 2002 začala být ke svému účelu používána jako federální standard USA. AES je první šifra, dostupná široké veřejnosti, která je zároveň uznána Národní bezpečností agenturou NSA.
Po pěti letech byla šifra AES schválena jako nejvhodnější z patnácti návrhů. Dne 26. května 2002 začala být ke svému účelu používána jako federální standard USA. AES je první šifra, dostupná široké veřejnosti, která je zároveň uznána Národní bezpečností agenturou NSA.
V současnoti se využívá k šifrování elektronické pošty, elektronického bankovnictví, různých druhů dálkové autentizace, čipových karet, elektronických peněz, přenosu hovorů v síti GSM, signálu wi-fi, bluetooth a satelitů.
Úvod Integrita a autenticita One-way   Symetrie MAC
Asymetrie
O čem to bude
• Asymetrická autenticita a      . • Message-
™ Authentication-Code
Q Integrita a autenticita f% iprinnqmprná funkrp
• Symetrická autenticita
□ s
Ochrana autentičnosti informace sestává z dvou následujících aspektů:
o ochrana původce informace neboli dle terminologie ISO autenticita původu dat,
Ochrana autentičnosti informace sestává z dvou následujících aspektů:
o ochrana původce informace neboli dle terminologie ISO autenticita původu dat,
o skutečnost, že informace nebyla změněna neboli dle terminologie ISO integrita informace.
Ochrana autentičnosti informace sestává z dvou následujících aspektů:
o ochrana původce informace neboli dle terminologie ISO autenticita původu dat,
o skutečnost, že informace nebyla změněna neboli dle terminologie ISO integrita informace.
První aspekt lze prezentovat tak, že je informace načítána např. z harddisku osobního počítače a my implicitně důvěřujeme zdroji informace.
Ochrana autentičnosti informace sestává z dvou následujících aspektů:
o ochrana původce informace neboli dle terminologie ISO autenticita původu dat,
o skutečnost, že informace nebyla změněna neboli dle terminologie ISO integrita informace.
První aspekt lze prezentovat tak, že je informace načítána např. z harddisku osobního počítače a my implicitně důvěřujeme zdroji informace.
Jiným aspektem je časování, umístění do fronty vzhledem k jiným zprávám a určení zprávy.
Ochrana autentičnosti informace sestává z dvou následujících aspektů:
o ochrana původce informace neboli dle terminologie ISO autenticita původu dat,
o skutečnost, že informace nebyla změněna neboli dle terminologie ISO integrita informace.
První aspekt lze prezentovat tak, že je informace načítána např. z harddisku osobního počítače a my implicitně důvěřujeme zdroji informace.
Jiným aspektem je časování, umístění do fronty vzhledem k jiným zprávám a určení zprávy.
Až donedávna se obecně předpokládalo, že zašifrování informace je dostatečné k tomu, aby se prokázala její autenticita.
Použitý argument byl ten, že pokud šifrový text dal po dešifrování smysluplnou informaci, tato by měla vzniknout od někoho, kdo zná tajný klíč, což garantuje autenticitu zprávy a odesílatele.
Použitý argument byl ten, že pokud šifrový text dal po dešifrování smysluplnou informaci, tato by měla vzniknout od někoho, kdo zná tajný klíč, což garantuje autenticitu zprávy a odesílatele.
Ve dvou příkladech ukážeme, že tato víra není správná: ochrana integrity závisí na šifrovacím algoritmu a na módu, ve kterém je algoritmus použit.
Použitý argument byl ten, že pokud šifrový text dal po dešifrování smysluplnou informaci, tato by měla vzniknout od někoho, kdo zná tajný klíč, což garantuje autenticitu zprávy a odesílatele.
Ve dvou příkladech ukážeme, že tato víra není správná: ochrana integrity závisí na šifrovacím algoritmu a na módu, ve kterém je algoritmus použit.
Vernamova šifra, kde je náhodný klíč přičítán modulo 2 k šifrovému textu nám poskytuje perfektní bezpečnost, ale aktivní útočník může změnit libovolný bit zdrojového textu tím, že změní odpovídající bit šifrového textu.
Použitý argument byl ten, že pokud šifrový text dal po dešifrování smysluplnou informaci, tato by měla vzniknout od někoho, kdo zná tajný klíč, což garantuje autenticitu zprávy a odesílatele.
Ve dvou příkladech ukážeme, že tato víra není správná: ochrana integrity závisí na šifrovacím algoritmu a na módu, ve kterém je algoritmus použit.
Vernamova šifra, kde je náhodný klíč přičítán modulo 2 k šifrovému textu nám poskytuje perfektní bezpečnost, ale aktivní útočník může změnit libovolný bit zdrojového textu tím, že změní odpovídající bit šifrového textu.
Tato informace analogicky platí pro libovolnou přičítací proudovou šifru a pro OFB mód (Output FeedBack) každé blokové šifry.
Uvod
Integrita a autenticita
One-way Symetrie metri
MAC
Částečně toto platí i pro případ, že šifra je použita CFB módu (Cipher FeedBack) nebo CBC módu (Cipher Block Chaining).
□ - =
Částečně toto platí i pro případ, že šifra je použita CFB módu (Cipher FeedBack) nebo CBC módu (Cipher Block Chaining).
Je-li zdrojový text delší než jeden blok zašifrován pomocí blokové šifry v ECB módu, aktivní útočník může snadno přeuspořádat bloky.
Částečně toto platí i pro případ, že šifra je použita CFB módu (Cipher FeedBack) nebo CBC módu (Cipher Block Chaining).
Je-li zdrojový text delší než jeden blok zašifrován pomocí blokové šifry v ECB módu, aktivní útočník může snadno přeuspořádat bloky.
Jiným příkladem zranitelnosti aktivním útočníkem je zdrojový text zašifrovaný pomocí CFB módu. Vzhledem k synchronizačním vlastnostem každá modifikace šifrového textu způsobí odpovídající modifikaci zdrojového textu a následně zkomolí následující části zdrojového textu. Poté co chyba opustí FB registr, bude šifrový text opět správně dešifrován.
Částečně toto platí i pro případ, že šifra je použita CFB módu (Cipher FeedBack) nebo CBC módu (Cipher Block Chaining).
Je-li zdrojový text delší než jeden blok zašifrován pomocí blokové šifry v ECB módu, aktivní útočník může snadno přeuspořádat bloky.
Jiným příkladem zranitelnosti aktivním útočníkem je zdrojový text zašifrovaný pomocí CFB módu. Vzhledem k synchronizačním vlastnostem každá modifikace šifrového textu způsobí odpovídající modifikaci zdrojového textu a následně zkomolí následující části zdrojového textu. Poté co chyba opustí FB registr, bude šifrový text opět správně dešifrován.
Je-li ale modifikována poslední část šifrového textu, je zcela nemožné najít tuto modifikaci. Pokud se zkomolení vyskytne uprostřed zdrojového textu, lze chybu detekovat pomocí redundance.
V jiných módech (jako např. CBC mód) je každý šifrový text složitou funkcí předchozích bitů zdrojového textu a nějaké počáteční hodnoty.
V jiných módech (jako např. CBC mód) je každý šifrový text složitou funkcí předchozích bitů zdrojového textu a nějaké počáteční hodnoty.
Pokud modifikace jednoho bitu šifrového textu způsobí zkomolení t bitů zdrojového textu, pravděpodobnost, že že nový zdrojový text bude akceptován jako smysluplný, je rovna 2~řD, kde D je redundance informace.
V jiných módech (jako např. CBC mód) je každý šifrový text složitou funkcí předchozích bitů zdrojového textu a nějaké počáteční hodnoty.
Pokud modifikace jednoho bitu šifrového textu způsobí zkomolení t bitů zdrojového textu, pravděpodobnost, že že nový zdrojový text bude akceptován jako smysluplný, je rovna 2~řD, kde D je redundance informace.
V případě přirozeného jazyka zakódovaného pomocí 5 bitů na charakter je redundance na bit D ~ 0.74 a tato pravděpodobnost je rovna 2~22 2 pro t = 30.
V jiných módech (jako např. CBC mód) je každý šifrový text složitou funkcí předchozích bitů zdrojového textu a nějaké počáteční hodnoty.
Pokud modifikace jednoho bitu šifrového textu způsobí zkomolení t bitů zdrojového textu, pravděpodobnost, že že nový zdrojový text bude akceptován jako smysluplný, je rovna 2~řD, kde D je redundance informace.
V případě přirozeného jazyka zakódovaného pomocí 5 bitů na charakter je redundance na bit D ~ 0.74 a tato pravděpodobnost je rovna 2~22 2 pro t = 30.
Avšak, je-li D = 0 a zašifrování neposkytuje žádnou autenticitu jsou všechny zprávy smysluplné a to nezávisle na šifrovacím algoritmu nebo na módu šifrování.
To pak znamená, že útočník může modifikovat zprávy nebo padělat zprávy dle svého výběru.
To pak znamená, že útočník může modifikovat zprávy nebo padělat zprávy dle svého výběru.
Omezení je pak to, že útočník neví dopředu, co bude obsahem odpovídajícího zdrojového textu, ale pro mnohé aplikace lze takovýto útok považovat za zdroj vážných problémů.
To pak znamená, že útočník může modifikovat zprávy nebo padělat zprávy dle svého výběru.
Omezení je pak to, že útočník neví dopředu, co bude obsahem odpovídajícího zdrojového textu, ale pro mnohé aplikace lze takovýto útok považovat za zdroj vážných problémů.
Poznamenejme, že i v případě existence redundance se požaduje kontrola lidským faktorem nebo vhodným počítačovým programem.
To pak znamená, že útočník může modifikovat zprávy nebo padělat zprávy dle svého výběru.
Omezení je pak to, že útočník neví dopředu, co bude obsahem odpovídajícího zdrojového textu, ale pro mnohé aplikace lze takovýto útok považovat za zdroj vážných problémů.
Poznamenejme, že i v případě existence redundance se požaduje kontrola lidským faktorem nebo vhodným počítačovým programem.
Abychom zajistili integritu zprávy, je nutno přidat speciální redundanci, a je-li informace spojena s původcem zprávy, musí být použit v tomto procesu tajný klíč (to předpokládá spojení osoby a jejího klíče) nebo zvláštního kanálu pro zajištění integrity.
Můžeme pak identifikovat dvě základní metody.
Můžeme pak identifikovat dvě základní metody.
o První metoda je analogická metodě symetrické šifry, kde utajení velkého množství dat je založeno na utajení a autenticitě krátkého klíče. V tomto případě autenticita informace závisí na utajení a autenticitě klíče.
Můžeme pak identifikovat dvě základní metody.
o První metoda je analogická metodě symetrické šifry, kde utajení velkého množství dat je založeno na utajení a autenticitě krátkého klíče. V tomto případě autenticita informace závisí na utajení a autenticitě klíče.
Abychom dosáhli tohoto účelu, informace se zkomprimuje na kvantitu pevné délky, kterou nazýváme hešovacím kódem. Poté se hešovací kód připojí k informaci. Funkce, která provede tuto operaci komprese, se nazývá hešovací funkce.
Můžeme pak identifikovat dvě základní metody.
o První metoda je analogická metodě symetrické šifry, kde utajení velkého množství dat je založeno na utajení a autenticitě krátkého klíče. V tomto případě autenticita informace závisí na utajení a autenticitě klíče.
Abychom dosáhli tohoto účelu, informace se zkomprimuje na kvantitu pevné délky, kterou nazýváme hešovacím kódem. Poté se hešovací kód připojí k informaci. Funkce, která provede tuto operaci komprese, se nazývá hešovací funkce.
Základní myšlenkou zabezpečení integrity je přidat redundanci k informaci. Přítomnost redundance dovoluje příjemci provést rozlišení autentické informace a podvodné informace.
Abychom garantovali původ dat, je nutno v procesu použít tajný klíč. Tajný klíč může být obsažen v procesu komprese nebo může být použit, aby ochránil hešovací kód a/nebo informaci. V prvním případě mluvíme o MACu (Message Authentication Code), zatímco v druhém případě se hešovací kód nazývá M DC {Manipulation Detection Code).
Abychom garantovali původ dat, je nutno v procesu použít tajný klíč. Tajný klíč může být obsažen v procesu komprese nebo může být použit, aby ochránil hešovací kód a/nebo informaci. V prvním případě mluvíme o MACu (Message Authentication Cocte), zatímco v druhém případě se hešovací kód nazývá MDC (Manipulation Detection Codé).
o Druhá metoda sestává na zajištění autenticity (jak integrity a autenticity původu) informace o autenticitě MDC. Typickým příkladem této metody je uživatel počítače, který počítá MDC pro všechny své důležité soubory. Může si pak uložit soubor všech MDC na disketě, kterou si bezpečně uschová. Pokud tyto soubory zašle vzdálenému příteli, může jednoduše poslat soubory a sdělit příteli po telefonu jejich MDC. Autenticita telefonního kanálu je zajištěna hlasovou identifikací.
Přidání redundance není jistě dostatečné. Speciální důraz musíme klást na obranu proti útokům na vysoké úrovni, jako je například opakování autentifikované zprávy. Oba případy nefungují, pokud si odesílatel a příjemce navzájem nedůvěřují. V prvním případě sdílejí stejný tajný klíč. Pokud jedna ze stran tvrdí, že informace byla změněna druhou stranou, nemůže soudce rozhodnout, kdo má pravdu, i když obě strany vydají společný tajný klíč. Druhý přístup může pouze zajistit nepřevzetí, pokud obě strany věří autenticitě MDC: v praxi je to však obtížné realizovat, protože obě strany mají podobný přístup ke kanálu.
Úvod            Integrita a autenticita                          One-way Symetrie Asymetrie		MAC	
			
Jestliže chceme být ochráněni proti vniřnímu napadnutí, potřebujeme elektronický ekvivalent podpisu. V tomto případě třetí strana bude schopna rozlišit dvě strany a to na základě skutečnosti, že způsobilosti obou stran jsou různé.
Jestliže chceme být ochráněni proti vniřnímu napadnutí, potřebujeme elektronický ekvivalent podpisu. V tomto případě třetí strana bude schopna rozlišit dvě strany a to na základě skutečnosti, že způsobilosti obou stran jsou různé.
Pojem digitálního podpisu byl zaveden W. Diffiem a M. Hellmanem.
Jestliže chceme být ochráněni proti vniřnímu napadnutí, potřebujeme elektronický ekvivalent podpisu. V tomto případě třetí strana bude schopna rozlišit dvě strany a to na základě skutečnosti, že způsobilosti obou stran jsou různé.
Pojem digitálního podpisu byl zaveden W. Diffiem a M. Hellmanem.
Požadavky na elektronický podpis jsou, že podpis závisí na podepisované informaci (protože není fyzicky spjat s dokumentem) a že podepsaný je jediná osoba, která je schopna vytvořit podpis (to znamená, že nikdo jiný nemůže zfalšovat podpis tj. podepsaný nemůže zapřít, že informaci podepsal právě on).
Úvod            Integrita a autenticita                          One-way Symetrie Asymetrie		MAC	
			
Digitální podpisové schéma sestává z následujících prvků:
o inicializační fáze (např. generování klíče a obecné nastavení),
o procesu podpisu, kdy je vytvořen podpis,
o procesu verifikace, kdy příjemce (nebo soudce) ověří, zda je podpis správný.
Digitální podpisové schéma sestává z následujících prvků:
o inicializační fáze (např. generování klíče a obecné nastavení),
o procesu podpisu, kdy je vytvořen podpis,
o procesu verifikace, kdy příjemce (nebo soudce) ověří, zda je podpis správný.
Digitální podpis v tomto smyslu lze vytvořit pomocí zařízení bezpečných proti falšování, konvenčních jednosměrných funkcí nebo technik veřejného klíče.
Digitální podpisové schéma sestává z následujících prvků:
o inicializační fáze (např. generování klíče a obecné nastavení),
o procesu podpisu, kdy je vytvořen podpis,
o procesu verifikace, kdy příjemce (nebo soudce) ověří, zda je podpis správný.
Digitální podpis v tomto smyslu lze vytvořit pomocí zařízení bezpečných proti falšování, konvenčních jednosměrných funkcí nebo technik veřejného klíče.
Poznamenejme dále, že bylo definováno několik zobecnění -např. s různými stupni bezpečnosti a více hráči ve hře.
Úvod Integrita a autenticita One-way   Symetrie MAC
Asymetrie
Asymetrická autenticita III
Příklady takovýchto jsou následující: libovolné podpisy, kde proces podpis a verifikace zahrnuje interakci s třetí stranou,
Úvod Integrita a autenticita One-way   Symetrie MAC
Asymetrie
Asymetrická autenticita III
Příklady takovýchto jsou následující: libovolné podpisy, kde proces podpis a verifikace zahrnuje interakci s třetí stranou, skupinové podpisy, kde podpisující a/nebo kontroloři jsou členy skupiny,
Příklady takovýchto jsou následující: libovolné podpisy, kde proces podpis a verifikace zahrnuje interakci s třetí stranou, skupinové podpisy, kde podpisující a/nebo kontroloři jsou členy skupiny, slepé podpisy, kde podpisující podepíše "slepou " nebo " maskovanou" zprávu a
Příklady takovýchto jsou následující: libovolné podpisy, kde proces podpis a verifikace zahrnuje interakci s třetí stranou, skupinové podpisy, kde podpisující a/nebo kontroloři jsou členy skupiny, slepé podpisy, kde podpisující podepíše "slepou " nebo " maskovanou" zprávu a neviditelné nebo nepopiratelné zprávy, kde lze podpis verifikovat pouze ve spolupráci s podpisujícím.
Pripomeňme si, že při integritě a autentičnosti zprávy jde o to, abychom vyvinuli metody, které příjemci umožní rozhodnout, zda zpráva došla neporušená a autentická. K tomu potřebuje příjemce něco, s čím může být zpráva ověřena: Potřebuje dodatečnou informaci od odesilatele.
Pripomeňme si, že při integritě a autentičnosti zprávy jde o to, abychom vyvinuli metody, které příjemci umožní rozhodnout, zda zpráva došla neporušená a autentická. K tomu potřebuje příjemce něco, s čím může být zpráva ověřena: Potřebuje dodatečnou informaci od odesilatele.
Takový informační blok se nazývá kryptografický zkušební součet, kryptografický otisk prvku neboli Message-Authentication-Code, zkráceně MAC.
Pripomeňme si, že při integritě a autentičnosti zprávy jde o to, abychom vyvinuli metody, které příjemci umožní rozhodnout, zda zpráva došla neporušená a autentická. K tomu potřebuje příjemce něco, s čím může být zpráva ověřena: Potřebuje dodatečnou informaci od odesilatele.
Takový informační blok se nazývá kryptografický zkušební součet, kryptografický otisk prvku neboli Message-Authentication-Code, zkráceně MAC.
Protokol k vytvoření a verifikaci kryptografického zkušebního součtu je založen na použití tajného klíče k, který je znám jak odesilateli tak příjemci, a kryptografickém algoritmu A, který budeme v dalším diskutovat.
Odesílatel neposílá pouze holou zprávu M, nýbrž dodatečně příslušný MAC; ten se vypočte pomocí klíče k algoritmem A ze zprávy M následovně:
MAC = Ak (M).
Odesílatel neposílá pouze holou zprávu M, nýbrž dodatečně příslušný MAC; ten se vypočte pomocí klíče k algoritmem A ze zprávy M následovně:
MAC = Ak (M).
Poznamenejme, že M je odesíláno nezašifrované, protože cílem odesílatele není utajit obsah zprávy, nýbrž zprávu zabezpečit. Pokud chceme navíc důvěrnost, musí být m a MAC zašifrovány.
Odesílatel neposílá pouze holou zprávu M, nýbrž dodatečně příslušný MAC; ten se vypočte pomocí klíče k algoritmem A ze zprávy M následovně:
MAC = Ak (M).
Poznamenejme, že M je odesíláno nezašifrované, protože cílem odesílatele není utajit obsah zprávy, nýbrž zprávu zabezpečit. Pokud chceme navíc důvěrnost, musí být m a MAC zašifrovány.
Nyní přijde na řadu příjemce. Jeho zájem je zjistit, zda přijatá zpráva souhlasí se zprávou odeslanou a zda skutečně pochází od uvedeného odesilatele.
Úvod Integrita a autenticita One-way   Symetrie MAC
Asymetrie
Message-Authentication-Code III
Aby to provedl, simuluje proceduru odesilatele: Použije algoritmus A s klíčem k na přijatou zprávu Mř a prověří, zda výsledek souhlasí s obrženým MACem.
Aby to provedl, simuluje proceduru odesilatele: Použije algoritmus A s klíčem k na přijatou zprávu Mř a prověří, zda výsledek souhlasí s obrženým MACem.
Je-li Ak(Mf) ^ MACví příjemce, že se "něco" stalo: proto neakceptuje zprávu jako autentickou a odmítne ji.
Aby to provedl, simuluje proceduru odesilatele: Použije algoritmus A s klíčem k na přijatou zprávu M' a prověří, zda výsledek souhlasí s obrženým MACem.
Je-li Ak(Mf) ^ MACví příjemce, že se "něco" stalo: proto neakceptuje zprávu jako autentickou a odmítne ji.
Je-li ale Ak(Mř) = MAC, může si být dostatečně jistý, že zpráva nebyla změněna. Přirozeně tato jistota závisí ve velké míře na kvalitě algoritmu A a velikosti množiny možných klíčů. Představy o MAC-mechanismu jsou následující:
• Podvodu ze strany Mr. X bude zamezeno, protože nezná klíč k. Musel by totiž spočítat odpovídající MAC pro svou zprávu.
Příjemce může pouze rozpoznat, či je zpráva neporušená a autentická; v záporném případě nemá žádnou možnost zrekonstruovat původní zprávu. To znamená, že v tomto případě je nutný nový přenos zprávy.
MAC-mechanismus je metoda k dosažení integrity a autentičnosti. Už jsme viděli, že lze poznat integritu. Pokud proběhne verifikace kladně, je příjemce rovněž přesvědčen o autentičnosti zprávy, protože odesílatel je jedinou jinou instancí, která zná tajný klíč.
Úvod Integrita a autenticita One-way   Symetrie MAC
Asymetrie
Message-Authentication-Code V
Jaké algoritmy A můžeme použít k výpočtu MACu?
Jaké algoritmy A můžeme použít k výpočtu MACu?
Okamžitá odpověď je jednoduchá: použijme jednoduše šifrovací algoritmus, přičemž MAC je kryptogram, který odpovídá zprávě M.
Úvod Integrita a autenticita One-way   Symetrie MAC
Asymetrie
Message-Authentication-Code V
Jaké algoritmy A můžeme použít k výpočtu MACu?
Okamžitá odpověď je jednoduchá: použijme jednoduše šifrovací algoritmus, přičemž MAC je kryptogram, který odpovídá zprávě M.
Odhlédneme-li od toho, že takovýto slabý algoritmus není vhodné doporučit, má tento návrh tu nevýhodu, že přenášená data jsou dvojnásobně delší než "vlastní zpráva".
Jaké algoritmy A můžeme použít k výpočtu MACu?
Okamžitá odpověď je jednoduchá: použijme jednoduše šifrovací algoritmus, přičemž MAC je kryptogram, který odpovídá zprávě M.
Odhlédneme-li od toho, že takovýto slabý algoritmus není vhodné doporučit, má tento návrh tu nevýhodu, že přenášená data jsou dvojnásobně delší než "vlastní zpráva".
Přirozeně každý MAC prodlouží zprávu, ale chtěli bychom délku tohoto dodatečného bloku držet v nějakých rozumných mezích.
Jaké algoritmy A můžeme použít k výpočtu MACu?
Okamžitá odpověď je jednoduchá: použijme jednoduše šifrovací algoritmus, přičemž MAC je kryptogram, který odpovídá zprávě M.
Odhlédneme-li od toho, že takovýto slabý algoritmus není vhodné doporučit, má tento návrh tu nevýhodu, že přenášená data jsou dvojnásobně delší než "vlastní zpráva".
Přirozeně každý MAC prodlouží zprávu, ale chtěli bychom délku tohoto dodatečného bloku držet v nějakých rozumných mezích.
V praxi používáme k výpočtu MACu také šifrovací algoritmus, ale ne přímo, nýbrž v tzv. Cipher-Block-Chaining módu.
Představme si šifrovací algoritmus f (v praxi se většinou používá algoritmus DES nebo AES), který zobrazuje bloky zprávy složených z n znaků pomocí nějakého klíče K na bloky kryptogramu, rovněž složených z n znaků (typická hodnota je n = 64).
Představme si šifrovací algoritmus f (v praxi se většinou používá algoritmus DES nebo AES), který zobrazuje bloky zprávy složených z n znaků pomocí nějakého klíče K na bloky kryptogramu, rovněž složených z n znaků (typická hodnota je n = 64).
Abychom mohli vypočítat MAC, rozdělíme zprávu M do bloků M15 M2, ..., Ms délky n.
Představme si šifrovací algoritmus f (v praxi se většinou používá algoritmus DES nebo AES), který zobrazuje bloky zprávy složených z n znaků pomocí nějakého klíče K na bloky kryptogramu, rovněž složených z n znaků (typická hodnota je n = 64).
Abychom mohli vypočítat MAC, rozdělíme zprávu M do bloků M15 M2, ..., Ms délky n.
Pak aplikujeme f na blok M-i a obdržíme první blok kryptogramu C-i = ík(M^).
Představme si šifrovací algoritmus f (v praxi se většinou používá algoritmus DES nebo AES), který zobrazuje bloky zprávy složených z n znaků pomocí nějakého klíče K na bloky kryptogramu, rovněž složených z n znaků (typická hodnota je n = 64).
Abychom mohli vypočítat MAC, rozdělíme zprávu M do bloků M15 M2, ..., Ms délky n.
Pak aplikujeme f na blok M-i a obdržíme první blok kryptogramu C-i = ík(M^).
Potom přičteme C-i k M2 a položíme C2 = ík(C^ © M2).
Představme si šifrovací algoritmus f (v praxi se většinou používá algoritmus DES nebo AES), který zobrazuje bloky zprávy složených z n znaků pomocí nějakého klíče K na bloky kryptogramu, rovněž složených z n znaků (typická hodnota je n = 64).
Abychom mohli vypočítat MAC, rozdělíme zprávu M do bloků M15 M2, ..., Ms délky n.
Pak aplikujeme f na blok M-i a obdržíme první blok kryptogramu C-i = ík(M^).
Potom přičteme C-i k M2 a položíme C2 = ík(C^ © M2).
Tento postup opakujeme až skončíme výstupem Cs = ř/c(Cs_i © Ms), který vybereme za MAC.
Takto vypočtený MAC má následující přednosti: - MAC má pevnou délku n nezávislou na délce zprávy.
Úvod Integrita a autenticita One-way   Symetrie MAC
Asymetrie
Message-Authentication-Code VII
Takto vypočtený MAC má následující přednosti:
- MAC má pevnou délku n nezávislou na délce zprávy.
- MAC závisí na všech blocích zprávy.
Takto vypočtený MAC má následující přednosti:
- MAC má pevnou délku n nezávislou na délce zprávy.
- MAC závisí na všech blocích zprávy.
Protože všechny možné zprávy jsou zkomprimovány na MACy pevné délky, má mnoho zpráv tentýž MAC.
Takto vypočtený MAC má následující přednosti:
- MAC má pevnou délku n nezávislou na délce zprávy.
- MAC závisí na všech blocích zprávy.
Protože všechny možné zprávy jsou zkomprimovány na MACy pevné délky, má mnoho zpráv tentýž MAC.
To nepředstavuje žádný problém pro příjemce, protože ten nemusí rekonstruovat původní zprávu z MACu.
Takto vypočtený MAC má následující přednosti:
- MAC má pevnou délku n nezávislou na délce zprávy.
- MAC závisí na všech blocích zprávy.
Protože všechny možné zprávy jsou zkomprimovány na MACy pevné délky, má mnoho zpráv tentýž MAC.
To nepředstavuje žádný problém pro příjemce, protože ten nemusí rekonstruovat původní zprávu z MACu.
Ne všechny algoritmy jsou vhodné k tomu, aby byl Mr. X postaven před nepřekonatelné problémy.
Algoritmus pro výpočet MACu by měl mít následující vlastnosti.
O Mělo by být prakticky nemožné najít pro daný MAC
odpovídající zprávu (pokud tato vlastnost platí, nazýváme algoritmus jednosměrnou (one-way) funkcí). "Prakticky nemožné" znamená, že s dnešními metodami a počítači by vyřešení problému trvalo příliš dloho (několik století).
Algoritmus pro výpočet MACu by měl mít následující vlastnosti.
O Mělo by být prakticky nemožné najít pro daný MAC
odpovídající zprávu (pokud tato vlastnost platí, nazýváme algoritmus jednosměrnou (one-way) funkcí). "Prakticky nemožné" znamená, že s dnešními metodami a počítači by vyřešení problému trvalo příliš dloho (několik století).
Q Mělo by být prakticky nemožné najít dvě zprávy, které mají tentýž MAC (jednosměrná funkce splňující tuto podmínku se nazývá bezkolizní).
Uvod
Integrita a autenticita
One-way
Definice InvMixColumns
InvShiftRows InvSubBytes
Q Jednosměrná funkce
• Definice
• Procedura InvMixColumns
• Procedura InvShiftRows
• Procedura InvSubBytes
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce I
Je velmi obtížné podat precizní matematickou definici jednosměrné funkce. Neformálně je jednosměrná funkce funkce f: S -> T, kde S a T jsou množiny takové, že (1)  pro všechna x g S je f (x) "snadno" vypočitatelné,
Je velmi obtížné podat precizní matematickou definici jednosměrné funkce. Neformálně je jednosměrná funkce funkce f: S -> T, kde S a T jsou množiny takové, že
(1) pro všechna x g S je f (x) "snadno" vypočitatelné,
(2) máme-li k dispozici informaci, že f (x) = y, neexistuje zadný přiměřený způsob
jak získat (výpočtem) x pro 'dostatečně velké1 množství prvků y z T.
Je velmi obtížné podat precizní matematickou definici jednosměrné funkce. Neformálně je jednosměrná funkce funkce f: S -> T, kde S a T jsou množiny takové, že
(1) pro všechna x g S je f (x) "snadno" vypočitatelné,
(2) máme-li k dispozici informaci, že f (x) = y, neexistuje zadný přiměřený způsob
jak získat (výpočtem) x pro "dostatečně velké" množství prvků y z T.
Pracovní slova zde jsou "snadno", "přiměřeně" a "dostatečně velké".
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce I
Je velmi obtížné podat precizní matematickou definici jednosměrné funkce. Neformálně je jednosměrná funkce funkce f: S -> T, kde S a T jsou množiny takové, že
(1) pro všechna x g S je f (x) "snadno" vypočitatelné,
(2) máme-li k dispozici informaci, že f (x) = y, neexistuje zadný pnmerený způsob
jak získat (výpočtem) x pro "dostatečně velké" množství prvků y z T.
Pracovní slova zde jsou "snadno", "přiměřeně" a "dostatečně velké".
Je zřejmé, že je-li dáno f(x), jeden způsob, jak získat x je prohledávat všechny možné hodnoty x e S. Nepovažujeme to za přiměřené, protože S sestává obvykle z posloupnosti binárních řetězců délky n ~ 200.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce II
Požadujeme, že výpočet pro nalezení x ze znalosti y je příliš dlouhotrvající nebo nákladný, kdykoliv y leží v "dosti velké" podmnožině množiny T.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce II
Požadujeme, že výpočet pro nalezení x ze znalosti y je příliš dlouhotrvající nebo nákladný, kdykoliv y leží v "dosti velké" podmnožině množiny T.
Příklad. Elementárním příkladem kandidáta na jednosměrnou funkci je, pro dostatečně velké prvočíslo p, funkce f(x), kde f(x) je polynom nad tělesem Zp.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce II
Požadujeme, že výpočet pro nalezení x ze znalosti y je příliš dlouhotrvající nebo nákladný, kdykoliv y leží v "dosti velké" podmnožině množiny T.
Příklad. Elementárním příkladem kandidáta na jednosměrnou funkci je, pro dostatečně velké prvočíslo p, funkce f(x), kde f(x) je polynom nad tělesem Zp.
Pak je relativně snadné vypočíst f(x) (1 < x < p - 1), ale obvykle je těžké nalézt řešení rovnice
f(x) = y.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce II
Požadujeme, že výpočet pro nalezení x ze znalosti y je příliš dlouhotrvající nebo nákladný, kdykoliv y leží v "dosti velké" podmnožině množiny T.
Příklad. Elementárním příkladem kandidáta na jednosměrnou funkci je, pro dostatečně velké prvočíslo p, funkce f(x), kde f(x) je polynom nad tělesem Zp.
Pak je relativně snadné vypočíst f(x) (1 < x < p - 1), ale obvykle je těžké nalézt řešení rovnice
f{x) = y.
Výše uvedená nepřesná definice znamená, že to, co je jednosměrná funkce, se mění s dobou.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce III
Například, výpočet požadující milión instrukcí a 10 000 slov paměti nemohl být v roce 1950 považován za snadný, ale nyní by trval několik sekund na osobním počítači.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce III
Například, výpočet požadující milión instrukcí a 10 000 slov paměti nemohl být v roce 1950 považován za snadný, ale nyní by trval několik sekund na osobním počítači.
Tedy funkce považovaná v roce 1950 za jednosměrnou nemusí být za ni považovaná nyní.
Jedna metoda podání formální definice by mohlo být užitím fyzikálního přístupu.
Například, výpočet požadující milión instrukcí a 10 000 slov paměti nemohl být v roce 1950 považován za snadný, ale nyní by trval několik sekund na osobním počítači.
Tedy funkce považovaná v roce 1950 za jednosměrnou nemusí být za ni považovaná nyní.
Jedna metoda podání formální definice by mohlo být užitím fyzikálního přístupu.
Např. 1060-bitová paměť vždy zůstane nedosažitelnou, protože i kdybychom potřebovali pouze jednu molekulu na bit paměti, její konstrukce by vyžadovala více hmoty než existuje v slunečním systému.
Například, výpočet požadující milión instrukcí a 10 000 slov paměti nemohl být v roce 1950 považován za snadný, ale nyní by trval několik sekund na osobním počítači.
Tedy funkce považovaná v roce 1950 za jednosměrnou nemusí být za ni považovaná nyní.
Jedna metoda podání formální definice by mohlo být užitím fyzikálního přístupu.
Např. 1060-bitová paměť vždy zůstane nedosažitelnou, protože i kdybychom potřebovali pouze jednu molekulu na bit paměti, její konstrukce by vyžadovala více hmoty než existuje v slunečním systému.
Podobně, termodynamika nám dává omezení maximálně 1070 operací, které lze provést s využitím celkové energie slunce.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce III
Například, výpočet požadující milión instrukcí a 10 000 slov paměti nemohl být v roce 1950 považován za snadný, ale nyní by trval několik sekund na osobním počítači.
Tedy funkce považovaná v roce 1950 za jednosměrnou nemusí být za ni považovaná nyní.
Jedna metoda podání formální definice by mohlo být užitím fyzikálního přístupu.
Např. 1060-bitová paměť vždy zůstane nedosažitelnou, protože i kdybychom potřebovali pouze jednu molekulu na bit paměti, její konstrukce by vyžadovala více hmoty než existuje v slunečním systému.
Podobně, termodynamika nám dává omezení maximálně 1070 operací, které lze provést s využitím celkové energie slunce.
Nižší úroveň nedosažitelnosti je použití myšlenek výpočetní složitosti.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce IV
Nejdříve uvažujme některé z vlastností, které bychom rádi požadovali po jednosměrné funkci.
(I) Výpočet f(x) z x musí být přiměřený: vyjádříme to tím, že f je vypočitatelná v polynomiálně omezené době (říkáme, že feP).
Nejdříve uvažujme některé z vlastností, které bychom rádi požadovali po jednosměrné funkci.
(I) Výpočet f(x) z x musí být přiměřený: vyjádříme to tím, že f je vypočitatelná v polynomiálně omezené době (říkáme, že feP).
(II) Výpočet ř~1 nesmí být snadný; budeme tudíž požadovat, že není znám žádný algoritmus pro výpočet ŕ-1 v polynomiálně omezené době.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce IV
Nejdříve uvažujme některé z vlastností, které bychom rádi požadovali po jednosměrné funkci.
(I) Výpočet f(x) z x musí být přiměřený: vyjádříme to tím, že f je vypočitatelná v polynomiálně omezené době (říkáme, že řeP).
(II) Výpočet ř~1 nesmí být snadný; budeme tudíž požadovat, že není znám žádný algoritmus pro výpočet ŕ-1 v polynomiálně omezené době.
Třetí podmínka bude tzv. upřímnost funkce tj., že existuje polynom p splňující |x| < p(\f(x)\).
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce IV
Nejdříve uvažujme některé z vlastností, které bychom rádi požadovali po jednosměrné funkci.
(I) Výpočet f(x) z x musí být přiměřený: vyjádříme to tím, že f je vypočitatelná v polynomiálně omezené době (říkáme, že feP).
(II) Výpočet ř~1 nesmí být snadný; budeme tudíž požadovat, že není znám žádný algoritmus pro výpočet ŕ-1 v polynomiálně omezené době.
(III) Třetí podmínka bude tzv. upřímnost funkce tj., že existuje polynom p splňující |x| < p(\f(x)\).
Poslední podmínka je technická podmínka pro vyloučení funkcí jako
f(x) = [log logx],
která zcela jistě splňuje (I) a (II), ale kterou bychom nemohli obvykle považovat za jednosměrnou funkci,     fl ►<,►,, ► t
Funkce f splňující (l),(ll) a (III) se nazývá slabě jednosměrná funkce.
Funkce f splňující (l),(ll) a (III) se nazývá slabě jednosměrná funkce.
Příklad. Nechť \k značí množinu všech /c-bitových přirozených čísel tj.
I* = {2*-\...,2*-1} (/c = 1,2,...)-
Nechť S/c = l/c x 1^ a nechť f: S/c    Z+ je definována jako
f(/?7. n) = m • n.
Položíme-li S = IJ{S/c: 1 < k < oc} a rozšiříme-li ř na S, získáme slabě jednosměrnou funkci. Přitom v současné době není známo, že by inverzní funkce ležela v P.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VI
Není lehké najít matematickou explicitní definici jednosměrné funkce. Uveďme následující příklad.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VI
Není lehké najít matematickou explicitní definici jednosměrné funkce. Uveďme následující příklad.
Příklad. Buď F šifrovací algoritmus, který zobrazuje zprávu M pomocí klíče K na kryptogram C, FK(M) = e(M,/í) = Ca předpokládejme, že M c K.
Není lehké najít matematickou explicitní definici jednosměrné funkce. Uveďme následující příklad.
Příklad. Buď F šifrovací algoritmus, který zobrazuje zprávu M pomocí klíče K na kryptogram C, FK(M) = e(M,/í) = Ca předpokládejme, že M c K.
Změňme trochu tuto funkci. Zafixujme za tímto účelem (ne tajnou) zprávu M0 (např. M0 = 00... 0); tato "zpráva" se objeví v algoritmu místo obvyklé zprávy, nehraje ale roli variabilní zprávy.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VI
Není lehké najít matematickou explicitní definici jednosměrné funkce. Uveďme následující příklad.
Příklad. Buď F šifrovací algoritmus, který zobrazuje zprávu M pomocí klíče K na kryptogram C, FK(M) = e(M,/í) = Ca předpokládejme, že M c K.
Změňme trochu tuto funkci. Zafixujme za tímto účelem (ne tajnou) zprávu M0 (např. M0 = 00... 0); tato "zpráva" se objeví v algoritmu místo obvyklé zprávy, nehraje ale roli variabilní zprávy.
Variabilní zpráva se vloží do algoritmu F na místě klíče. Krátce: uvažujeme funkci
ř = e(M0,-) : M^C. Tvrdíme pak, že f je jednosměrná funkce. =
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VII
Představme si, že Mr. X zná jak M0 tak i C a chtěl by nají M. V řeči šifrovacího algoritmu F to lze vyjádřit následovně: Mr. X zná sobě odpovídající dvojici zpráva-kryptogram (M0, C) a chtěl by vy počíst klíč.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VII
Představme si, že Mr. X zná jak M0 tak i C a chtěl by nají M. V řeči šifrovacího algoritmu F to lze vyjádřit následovně: Mr. X zná sobě odpovídající dvojici zpráva-kryptogram (M0, C) a chtěl by vy počíst klíč.
Je-li algoritmus F kryptologicky bezpečný, je rezistentní proti tomuto known-plaintext útoku a proto je /"jednosměrná funkce.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VII
Představme si, že Mr. X zná jak M0 tak i C a chtěl by nají M. V řeči šifrovacího algoritmu F to lze vyjádřit následovně: Mr. X zná sobě odpovídající dvojici zpráva-kryptogram (M0, C) a chtěl by vy počíst klíč.
Je-li algoritmus F kryptologicky bezpečný, je rezistentní proti tomuto known-plaintext útoku a proto je /"jednosměrná funkce.
Položme si otázku, zda lze matematicky dokázat, že tato funkce f je jednosměrná. Odpověď zní: Ne!
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VII
Představme si, že Mr. X zná jak M0 tak i C a chtěl by nají M. V řeči šifrovacího algoritmu F to lze vyjádřit následovně: Mr. X zná sobě odpovídající dvojici zpráva-kryptogram (M0, C) a chtěl by vy počíst klíč.
Je-li algoritmus F kryptologicky bezpečný, je rezistentní proti tomuto known-plaintext útoku a proto je /"jednosměrná funkce.
Položme si otázku, zda lze matematicky dokázat, že tato funkce f je jednosměrná. Odpověď zní: Ne!
Matematici nemohli ještě o žádné funkci dokázat, že je jednosměrná.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VIII
To znamená, že neznáme žádnou funkci, jejíž funkční hodnoty lze spočítat v polynomiálně omezené době, ale která při výpočtu funkce inverzní potřebuje exponenciální dobu.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VIII
To znamená, že neznáme žádnou funkci, jejíž funkční hodnoty lze spočítat v polynomiálně omezené době, ale která při výpočtu funkce inverzní potřebuje exponenciální dobu.
Nevíme tedy, zda teoreticky jednosměrné funkce existují. Pro praktické účely mají ale výše popsané funkce dostatečně dobré vlastnosti.
Uvod Integrita a autenticita One-way   Definice InvShiftRows
InvMixColumns InvSubBytes
Definice jednosměrné funkce VIII
To znamená, že neznáme žádnou funkci, jejíž funkční hodnoty lze spočítat v polynomiálně omezené době, ale která při výpočtu funkce inverzní potřebuje exponenciální dobu.
Nevíme tedy, zda teoreticky jednosměrné funkce existují. Pro praktické účely mají ale výše popsané funkce dostatečně dobré vlastnosti.
Totiž, kdybychom to uměli, uměli bychom dokázat, že P^NP.
Uvod
Integrita a autenticita
One-way
InvMixColur
InvShiftRows InvSubBytes
V proceduře InvMixColumns dojde ke změně jednotlivých sloupců pole State. Každý bajt se změní na novou hodnotu, která je funkcí všech čtyř bajtů sloupce.
Uvod
Integrita a autenticita
One-way
InvMixColur
InvShiftRows InvSubBytes
LVI V i>|    \VM V á I FAwlVJ IV K1
V proceduře InvMixColumns dojde ke změně jednotlivých sloupců pole State. Každý bajt se změní na novou hodnotu, která je funkcí všech čtyř bajtů sloupce.
Stejně jako v proceduře MixColumns se i zde operace provádí modulo m(x) = x8 + x4 + x3 + x1 + 1.
Uvod
Integrita a autenticita
One-way
InvMixColur
InvShiftRows InvSubBytes
LVI V i>|    \VM V á I FAwlVJ IV K1
V proceduře InvMixColumns dojde ke změně jednotlivých sloupců pole State. Každý bajt se změní na novou hodnotu, která je funkcí všech čtyř bajtů sloupce.
Stejně jako v proceduře MixColumns se i zde operace provádí modulo m(x) = x8 + x4 + x3 + x1 + 1.
CB	79	6A	90		" 0E OB OD 09 "		"CB"		"CB
77	11	1F	C1		09 0E OB OD		77		CD
8E	5A	A7	5D		OD 09 OE OB		8E		96
3E	7A	5A	77		OB OD 09 OE		3E		9C
Tabulka 1: Procedura InvMixColumns
Při proceduře InvShiftRows dojde k posunu v rámci řádků v poli State.
Uvod
Integrita a autenticita
One-way
Definice InvMixColumns
InvShiftRows InvSubBytes
Procedura InvShiftRows
Při proceduře InvShiftRows dojde k posunu v rámci řádků v poli State.
První řádek zůstává stejný, druhý řádek se posune o jednu pozici doprava, třetí řádek o dvě pozice a čtvrtý řádek o tři pozice.
Uvod
Integrita a autenticita
One-way
Definice InvMixColumns
InvShiftRows InvSubBytes
Procedura InvShiftRows
Při proceduře InvShiftRows dojde k posunu v rámci řádků v poli State.
První řádek zůstává stejný, druhý řádek se posune o jednu pozici doprava, třetí řádek o dvě pozice a čtvrtý řádek o tři pozice.
CB	1B	3D	A5		CB	1B	3D	A5
CD	OE	DF	82		82	CD	OE	DF
96	A8	FB	9E		FB	9E	96	A8
9C	F5	91	C2	^>   =^> =^>	F5	91	C2	9C
Tabulka 2: Procedura InvShiftRows
Úvod Integrita a autenticita One-way
InvShiftRows InvSubBytes
Pro proceduru InvSubBytes byla vytvořena inverzní substituční tabulka InvS-Box.
y
	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	52	09	6A	D5	30	36	A5	38	BF	40	A3	9E	81	F3	D7	FB
1	7C	E3	39	82	9B	2F	FF	87	34	8E	43	44	C4	DE	E9	CB
2	54	7B	94	32	A6	C2	23	3D	EE	4C	95	OB	42	FA	C3	4E
3	08	2E	A1	66	28	D9	24	B2	76	5B	A2	49	6D	8B	D1	25
4	72	F8	F6	64	86	68	98	16	D4	A4	5C	CC	5D	65	B6	92
5	6C	70	48	50	FD	ED	B9	DA	5E	15	46	57	A7	8D	9D	84
6	90	D8	AB	00	8C	BC	D3	OA	F7	E4	58	05	B8	B3	45	06
7	DO	2C	1E	8F	CA	3F	0F	02	C1	AF	BD	03	01	13	8A	6B
8	3A	91	11	41	4F	67	DC	EA	97	F2	CF	CE	FO	B4	E6	73
9	96	AC	74	22	E7	AD	35	85	E2	F9	37	E8	1C	75	DF	6E
A	47	F1	1A	71	1D	29	C5	89	6F	B7	62	OE	AA	18	BE	1B
B	FC	56	3E	4B	C6	D2	79	20	9A	DB	CO	FE	78	CD	5A	F4
C	1F	DD	A8	33	88	07	C7	31	B1	12	10	59	27	80	EC	5F
D	60	51	7F	A9	19	B5	4A	OD	2D	E5	7A	9F	93	C9	9C	EF
E	AO	E0	3B	4D	AE	2A	F5	BO	C8	EB	BB	3C	83	53	99	61
F	17	2B	04	7E	BA	77	D6	26	E1	69	14	63	55	21	OC	7D
Úvod Integrita a autenticita One-way
InvShiftRows InvSubBytes
Všechny prvky pole State nahradíme pomocí InvS-Boxu. První čtyři bity prvku označují řádek v tabulce InvS-Box, další čtyři sloupec.
y
	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	52	09	6A	D5	30	36	A5	38	BF	40	A3	9E	81	F3	D7	FB
1	7C	E3	39	82	9B	2F	FF	87	34	8E	43	44	C4	DE	E9	CB
2	54	7B	94	32	A6	C2	23	3D	EE	4C	95	OB	42	FA	C3	4E
3	08	2E	A1	66	28	D9	24	B2	76	5B	A2	49	6D	8B	D1	25
4	72	F8	F6	64	86	68	98	16	D4	A4	5C	CC	5D	65	B6	92
5	6C	70	48	50	FD	ED	B9	DA	5E	15	46	57	A7	8D	9D	84
6	90	D8	AB	00	8C	BC	D3	OA	F7	E4	58	05	B8	B3	45	06
7	DO	2C	1E	8F	CA	3F	OF	02	C1	AF	BD	03	01	13	8A	6B
8	3A	91	11	41	4F	67	DC	EA	97	F2	CF	CE	FO	B4	E6	73
9	96	AC	74	22	E7	AD	35	85	E2	F9	37	E8	1C	75	DF	6E
A	47	F1	1A	71	1D	29	C5	89	6F	B7	62	OE	AA	18	BE	1B
B	FC	56	3E	4B	C6	D2	79	20	9A	DB	CO	FE	78	CD	5A	F4
C	1F	DD	A8	33	88	07	C7	31	B1	12	10	59	27	80	EC	5F
D	60	51	7F	A9	19	B5	4A	OD	2D	E5	7A	9F	93	C9	9C	EF
E	AO	EO	3B	4D	AE	2A	F5	BO	C8	EB	BB	3C	83	53	99	61
F	17	2B	04	7E	BA	77	D6	26	E1	69	14	63	55	21	OC	7D
Úvod Integrita a autenticita One-way
InvShiftRows InvSubBytes
Například prvek "D4"ukazuje v S-Boxu na čtrnáctý řádek, čtvrtý sloupek a to je hodnota "19".
y
	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	52	09	6A	D5	30	36	A5	38	BF	40	A3	9E	81	F3	D7	FB
1	7C	E3	39	82	9B	2F	FF	87	34	8E	43	44	C4	DE	E9	CB
2	54	7B	94	32	A6	C2	23	3D	EE	4C	95	OB	42	FA	C3	4E
3	08	2E	A1	66	28	D9	24	B2	76	5B	A2	49	6D	8B	D1	25
4	72	F8	F6	64	86	68	98	16	D4	A4	5C	CC	5D	65	B6	92
5	6C	70	48	50	FD	ED	B9	DA	5E	15	46	57	A7	8D	9D	84
6	90	D8	AB	00	8C	BC	D3	OA	F7	E4	58	05	B8	B3	45	06
7	DO	2C	1E	8F	CA	3F	OF	02	C1	AF	BD	03	01	13	8A	6B
8	3A	91	11	41	4F	67	DC	EA	97	F2	CF	CE	FO	B4	E6	73
9	96	AC	74	22	E7	AD	35	85	E2	F9	37	E8	1C	75	DF	6E
A	47	F1	1A	71	1D	29	C5	89	6F	B7	62	OE	AA	18	BE	1B
B	FC	56	3E	4B	C6	D2	79	20	9A	DB	CO	FE	78	CD	5A	F4
C	1F	DD	A8	33	88	07	C7	31	B1	12	10	59	27	80	EC	5F
D	60	51	7F	A9	19	B5	4A	OD	2D	E5	7A	9F	93	C9	9C	EF
E	AO	EO	3B	4D	AE	2A	F5	BO	C8	EB	BB	3C	83	53	99	61
F	17	2B	04	7E	BA	77	D6	26	E1	69	14	63	55	21	OC	7D
Uvod
Integrita a autenticita
One-way
InvShiftRows InvSubBytes
CB	1B	3D	A5		59	44	8B	29
82	CD	OE	DF	=$>■	11	80	D7	EF
FB	9E	96	A8		63	DF	35	6F
F5	91	C2	9C		77	AC	A8	1C
Tabulka 3: Procedura InvSubBytes
y
	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	52	09	6A	D5	30	36	A5	38	BF	40	A3	9E	81	F3	D7	FB
1	7C	E3	39	82	9B	2F	FF	87	34	8E	43		C4	DE	E9	CB
2	54	7B	94	32	A6	C2	23	3D	EE	4C	95	OB	42	FA	C3	4E
3	08	2E	A1	66	28	D9	24	B2	76	5B	A2	49	6D		D1	25
4	72	F8	F6	64	86	68	98	16	D4	A4	5C	CC	5D	65	B6	92
5	6C	70	48	50	FD	ED	B9	DA	5E	15	46	57	A7	8D	9D	84
6	90	D8	AB	00	8C	BC	D3	OA	F7	E4	58	05	B8	B3	45	06
7	DO	2C	1E	8F	CA	3F	OF	02	C1	AF	BD	03	01	13	8A	6B
8	3A	91	11	41	4F	67	DC	EA	97	F2	CF	PĚ,	F(L		£6	73