Úvod One-way Integrita a autenticita Uživatel 9. Autentičnost a digitální podpisy Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 13. 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 Uživatel 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 Uživatel MAC • Message-Authentication-Code O Integrita a autenticita • Symetrická autenticita • Asymetrická autenticita i m 11íxv^c 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. Úvod One-way Integrita a autenticita Uživatel Symetrie metri MAC 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. Úvod One-way Integrita a autenticita Uživatel 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). Úvod One-way Integrita a autenticita Uživatel 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). 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. □ t3 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. Úvod Integrita a autenticita One-way Uživatel Symetrie MAC metri 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. Uvod Integrita a autenticita One-way Uživatel 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é. Uvod Integrita a autenticita One-way Uživatel 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é. Pojem digitálního podpisu byl zaveden W. Diffiem a M. Hellmanem. Uvod Integrita a autenticita One-way Uživatel 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é. 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). 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. Uvod Integrita a autenticita One-way Uživatel Symetrie Asymetrie MAC Příklady takovýchto jsou následující: libovolné podpisy, kde proces podpis a verifikace zahrnuje interakci s třetí stranou, Úvod One-way Integrita a autenticita Uživatel Symetrie Asymetrie 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, Uvod Integrita a autenticita One-way Uživatel Symetrie Asymetrie MAC 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 Uvod Integrita a autenticita One-way Uživatel Symetrie Asymetrie MAC 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. 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 One-way Integrita a autenticita Uživatel 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 Uživatel V MAC 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". Úvod Integrita a autenticita One-way Uživatel V MAC 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. Úvod Integrita a autenticita One-way Uživatel V MAC 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. Úvod Integrita a autenticita One-way Uživatel VI MAC 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). Úvod Integrita a autenticita One-way Uživatel VI MAC 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. Úvod Integrita a autenticita One-way Uživatel VI MAC 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^). Úvod Integrita a autenticita One-way Uživatel VI MAC 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 = //c(Ci © M2). Úvod Integrita a autenticita One-way Uživatel VI MAC 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 = //c(Ci © 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. Uvod Integrita a autenticita One-way Uživatel Symetrie Asymetrie MAC 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í). • Definice • Zanedbatelné funkce • Jednosměrné funkce • Aplikace na kryptografické pojmy Úvod ■ ■ Q Jednosměrná funkce 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ý pnmerený 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é". 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. 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. 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. 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. 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. 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. 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. 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. 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. 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ě. 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)\). 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ť l/c 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. Není lehké najít matematickou explicitní definici jednosměrné funkce. Uveďme následující příklad. 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. 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. = 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íč. 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. 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! 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á. 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. 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. 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. One-way Uživatel Definice Zanedbatelnost One-way Aplikace Připomeňme, co se snažíme zachytit v následujících definicích • Za prvé, když mluvíme o efektivním šifrovacím nebo dešifrovacím algoritmu, obvykle máme na mysli takový, který běží velmi rychle a šifruje data rychlostí řekněme 10-100 počítačových cyklů na byte dat. Úvod Integrita a autenticita One-way Uživatel Definice One-way Zanedbatelnost Aplikace UR ^3 Připomeňme, co se snažíme zachytit v následujících definicích. • Za prvé, když mluvíme o efektivním šifrovacím nebo dešifrovacím algoritmu, obvykle máme na mysli takový, který běží velmi rychle a šifruje data rychlostí řekněme 10-100 počítačových cyklů na byte dat. • Za druhé, když mluvíme o efektivním protivníkovi, obvykle máme na mysli algoritmus, který běží během nějaké velké, ale stále proveditelné doby (a dalších zdrojů). Obvykle se předpokládá že protivník, který se snaží prolomit kryptosystém, je ochoten utratit mnohem více zdroje než uživatel kryptosystému. Tedy 10 000 paralelně běžících počítačů 10 let může být považováno za horní hranici toho, co je proveditelně vyčíslitelné trpělivý a finančně dobře situovaným protivníkem. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost • Za třetí, když mluvíme o výhodě protivníka jako o zanedbatelné, myslíme tím, že ji lze považovat za tak malou, že ji lze pro všechny praktické účely chápat rovnou nule. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost • Za třetí, když mluvíme o výhodě protivníka jako o zanedbatelné, myslíme tím, že ji lze považovat za tak malou, že ji lze pro všechny praktické účely chápat rovnou nule. Přijmeme rovnítko mezi pojmem efektivního algoritmu a pojmem (pravděpodobnostní) polynomiální-časový algoritmus. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost • Za třetí, když mluvíme o výhodě protivníka jako o zanedbatelné, myslíme tím, že ji lze považovat za tak malou, že ji lze pro všechny praktické účely chápat rovnou nule. Přijmeme rovnítko mezi pojmem efektivního algoritmu a pojmem (pravděpodobnostní) polynomiální-časový algoritmus. V dobrém i ve zlém nám to dává formální rámec, který je nezávislý na konkrétních detailech jakéhokoli konkrétního modelu výpočtu. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost V rámci celé kapitoly budeme automaticky předpokládat, že všechny polynomy jsou pozitivní, tj. p(k) > 1 pro všechna přirozená čísla k > 1. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost V rámci celé kapitoly budeme automaticky předpokládat, že všechny polynomy jsou pozitivní, tj. p(k) > 1 pro všechna přirozená čísla k > 1. Definition 3.1 Funkce r : N R>0 je zanedbatelná, jestliže pro každý (pozitivní) polynom p : N N, existuje celé číslo /c0 takové, že r(/c) < 1/p(/c) pro /c > /c0. Budeme používat označení neg(-), které označuje libovolnou zanedbatelnou funkci. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost V rámci celé kapitoly budeme automaticky předpokládat, že všechny polynomy jsou pozitivní, tj. p(k) > 1 pro všechna přirozená čísla k > 1. Definition 3.1 Funkce r : N R>0 je zanedbatelná, jestliže pro každý (pozitivní) polynom p : N N, existuje celé číslo /c0 takové, že r(/c) < 1/p(/c) pro /c > /c0. Budeme používat označení neg(-), které označuje libovolnou zanedbatelnou funkci. Takže zanedbatelná funkce bude časem menší, než je inverze jakéhokoliv (pozitivního) polynomu. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost Zaveďme si pro funkce r, s : N R>0 následující relaci r k0 Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost Zaveďme si pro funkce r, s : N R>0 následující relaci: r k0 Tato relace je evidentně reflexivní a tranzitivní a funkce r : N R>0 je zanedbatelná právě tehdy, když r 0 následující relaci: r k0 Tato relace je evidentně reflexivní a tranzitivní a funkce r : N R>0 je zanedbatelná právě tehdy, když r 0 je zanedbatelná právě tehdy, když pro všechna o 0 máme lim r(n) • n° = 0. a?gN Úvod Integrita a autenticita One-way Uživatel Definice One-way Zanedbatelnost Aplikace EE Alternativní charakterizace zanedbatelné funkce, se kterou se snad lépe pracuje, je následující: Věta 3.2 Funkce r\ N R>0 je zanedbatelná právě tehdy, když pro všechna o 0 máme lim r(n) • n° = 0. a?gN Důkaz. Buď r: N R>0 zanedbatelná funkce, o 0. Pak 0 < limnGN r(n) • n° < limnGN n-(c+1) • n° = limnGN n~1 = 0, Obráceně z definice limity existuje k0 tak, že pro n > k0 1 r(n)< 2nc < n c. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost One-way Aplikace Příklad 3.3 O Příkladem zanedbatelných funkcí jsou 2~n, 2_v^, n'°9n. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost Příklad 3.3 O Příkladem zanedbatelných funkcí jsou 2~n, 2_v7í, n'°^n, O Příkladem funkcí, které nejsou zanedbatelné, jsou 1 1 1oooa75+a72/o0a7' a?1000 ' I Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost One-way Aplikace Tvrzení 3.4 Funkce r je zanedbatelná tehdy a jen tehdy pokud existuje zanedbatelná funkce s taková, že r 1 /p(/c). Úvod Integrita a autenticita One-way Uživatel Definice One-way Zanedbatelnost Aplikace ^3 Uvědomme si, že funkce r : N R není zanedbatelná, právě když existuje pozitivní polynom p(n) a nekonečně mnoho hodnot k e N tak, že r (k) > 1 /p(/c). Následující výsledek nám říká, že naše definice zanedbatelnosti perfektně zapadá do myšlenky, že pouze polynomiální časové výpočty jsou proveditelné. Uvědomme si, že funkce r : N -> R není zanedbatelná, právě když existuje pozitivní polynom p(n) a nekonečně mnoho hodnot k e N tak, že r (k) > 1 /p(/c). Následující výsledek nám říká, že naše definice zanedbatelnosti perfektně zapadá do myšlenky, že pouze polynomiální časové výpočty jsou proveditelné. Říká tedy, že pokud algoritmus má zanedbatelnou naději na úspěch, pak jeho opakování polynomiálně mnohokrát nemůže změnit tuto skutečnost. Tvrzení 3.5 i Pokud je pravděpodobnost toho, že algoritmus E bude úspešný (vdané výpočetní úloze) na vstupech velikosti k, zanedbatelná (v k), pak pravděpodobnost toho, že uspěje alespoň jednou, když se mnohokrát polynomiálně opakuje, je také zanedbatelná. Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost z Věty 3.5 Předpokládejme, že existuje pozitivní polynom q(n) tak, že pravděpodobnost alespoň jednoho úspěchu na vstupech velikosti k, pokud je algoritmus E opakován g(/c)-krát, není zanedbatelná. Úvod One-way Integrita a autenticita Uživatel Definice Zanedbatelnost One-way Aplikace ■ Důkaz Věty 3.5 Důkaz. Předpokládejme, že existuje pozitivní polynom q(ri) tak, že pravděpodobnost alespoň jednoho úspěchu na vstupech velikosti k, pokud je algoritmus E opakován g(/c)-krát, není zanedbatelná. Stačí pak ukázat, že pravděpodobnost úspěchu r(k) algoritmu E na vstupech velikosti k nemohla být zanedbatelná. Úvod One-way Integrita a autenticita Uživatel Definice Zanedbatelnost One-way Aplikace ■ Důkaz Věty 3.5 Důkaz. Předpokládejme, že existuje pozitivní polynom q(ri) tak, že pravděpodobnost alespoň jednoho úspěchu na vstupech velikosti k, pokud je algoritmus E opakován g(/c)-krát, není zanedbatelná. Stačí pak ukázat, že pravděpodobnost úspěchu r(k) algoritmu E na vstupech velikosti k nemohla být zanedbatelná. Ale to znamená, že existuje pozitivní polynom p(n) a nekonečně mnoho hodnot k e N tak, že q(k)r(k) > 1 /p(/c). Důkaz. Předpokládejme, že existuje pozitivní polynom q(ri) tak, že pravděpodobnost alespoň jednoho úspěchu na vstupech velikosti k, pokud je algoritmus E opakován g(/c)-krát, není zanedbatelná. Stačí pak ukázat, že pravděpodobnost úspěchu r(k) algoritmu E na vstupech velikosti k nemohla být zanedbatelná. Ale to znamená, že existuje pozitivní polynom p(n) a nekonečně mnoho hodnot k e N tak, že q(k)r(k) > 1 /p(/c). To je ale ekvivalentní s tím, že pro nekonečně mnoho hodnot ke N platí r(k) > 1 /(q(k)p(k)). Úvod One-way Integrita a autenticita Uživatel Definice Zanedbatelnost One-way Aplikace ■ Důkaz Věty 3.5 Důkaz. Předpokládejme, že existuje pozitivní polynom q(ri) tak, že pravděpodobnost alespoň jednoho úspěchu na vstupech velikosti k, pokud je algoritmus E opakován g(/c)-krát, není zanedbatelná. Stačí pak ukázat, že pravděpodobnost úspěchu r(k) algoritmu E na vstupech velikosti k nemohla být zanedbatelná. Ale to znamená, že existuje pozitivní polynom p(n) a nekonečně mnoho hodnot k e N tak, že q(k)r(k) > 1 /p(/c). To je ale ekvivalentní s tím, že pro nekonečně mnoho hodnot ke N platí r(k) > 1 /(q(k)p(k)). Tedy r není zanedbatelná, spor. I Úvod Integrita a autenticita One-way Uživatel Definice One-way Zanedbatelnost Aplikace EE Okamžitým důsledkem je pak následující tvrzení Důsledek 3.6 Úvod Integrita a autenticita One-way Uživatel Definice One-way Zanedbatelnost Aplikace EE Okamžitým důsledkem je pak následující tvrzení Důsledek 3.6 Buď neglÁ (h) a negl2(ri) zanedbatelné funkce, p(n) pozitivní polynom. Pak O p(n) neglA (n) je zanedbatelná funkce. © Součet neglÁ (n) + negl2{n) je zanedbatelná funkce. Důkaz. První část okamžite plyne z důkazu Vety 3.5. Úvod Integrita a autenticita One-way Uživatel Definice One-way Zanedbatelnost Aplikace EE Okamžitým důsledkem je pak následující tvrzení Důsledek 3.6 Buď neglÁ (h) a negl2(ri) zanedbatelné funkce, p(n) pozitivní polynom. Pak O p(n) neglA (n) je zanedbatelná funkce. © Součet neglÁ (n) + negl2{n) je zanedbatelná funkce. ■ Důkaz. První část okamžite plyne z důkazu Vety 3.5. Druhá část plyne z toho, že pro c g N existuje k0 e N takové, že Unegl^k) + negl2(k)) < k -c pro k > k0. Úvod Integrita a autenticita One-way Uživatel Definice One-way Zanedbatelnost Aplikace EE Okamžitým důsledkem je pak následující tvrzení Důsledek 3.6 Buď neglÁ (h) a negl2{h) zanedbatelné funkce, p(n) pozitivní polynom. Pak O p(n) neglA (n) je zanedbatelná funkce. © Součet neglÁ (n) + negl2(n) je zanedbatelná funkce. ■ Důkaz. První část okamžite plyne z důkazu Vety 3.5. Druhá část plyne z toho, že pro c g N existuje k0 e N takové, že Unegl^k) + negl2(k)) < k -c pro k > k0. Ale funkce 2\ (neg\A (n) + negl2(n)) = neglÁ (n) + negl2(n) je dle první části zanedbatelná. I 0 0,0 Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost Než budeme pokračovat, pokusme si vysvětlit, co přesně znamená "inverze" f(x)? One-way Uživatel Definice Zanedbatelnost One-way Aplikace Než budeme pokračovat, pokusme si vysvětlit, co přesně znamená "inverze" f(x)? Vzhledem k tomu, že někdy budeme muset vzít v úvahu funkce, které nejsou prosté, bude to znamenat, že pro y, které je tvaru y = f (x), najdeme nějaké z, které bude splňovat ř(z) = y. Označme pak One-way Uživatel Definice Zanedbatelnost One-way Aplikace Než budeme pokračovat, pokusme si vysvětlit, co přesně znamená "inverze" f(x)? Vzhledem k tomu, že někdy budeme muset vzít v úvahu funkce, které nejsou prosté, bude to znamenat, že pro y, které je tvaru y = f (x), najdeme nějaké z, které bude splňovat ř(z) = y. Označme pak Některé funkce jsou ale těžko i nve r to vate Iné ze zcela triviálního důvodu: délka každého takového z je mnohem delší, než je délka f(x). One-way Uživatel Definice Zanedbatelnost One-way Aplikace Než budeme pokračovat, pokusme si vysvětlit, co přesně znamená "inverze" f(x)? Vzhledem k tomu, že někdy budeme muset vzít v úvahu funkce, které nejsou prosté, bude to znamenat, že pro y, které je tvaru y = f (x), najdeme nějaké z, které bude splňovat ř(z) = y. Označme pak Některé funkce jsou ale těžko i nve r to vate Iné ze zcela triviálního důvodu: délka každého takového z je mnohem delší, než je délka f(x). Jednosměrnou funkci by ale mělo být těžké invertovat, protože je těžké najít takovéto z, ne proto, že pokud je takovéto z nalezeno, trvá příliš dlouho jeho vlastní zápi% (3 ~ = t OOvO Uvod Integrita a autenticita One-way Uživatel Definice Zanedbatelnost One-way Aplikace Příklad 3.7 Uvažme například funkci f: {0,1 }* {0,1 }*, ř(x) = posledních log2 \x\ bitů binárního zápisu čísla x. One-way Uživatel Definice Zanedbatelnost One-way Aplikace Příklad 3.7 Uvažme například funkci f: {0,1 }* {0,1 }*, ř(x) = posledních log2 \x\ bitů binárního zápisu čísla x. Je zřejmé, že jakékoliv z je exponenciálně delší než f {z) samo o sobě. Tedy žádný algoritmus nemůže invertovat f(x) v polynomiálním čase. Příklad 3.7 Uvažme například funkci f: {0,1 }* {0,1 }*, ř(x) = posledních log2 \x\ bitů binárního zápisu čísla x. Je zřejmé, že jakékoliv z je exponenciálně delší než f {z) samo o sobě. Tedy žádný algoritmus nemůže invertovat f(x) v polynomiálním čase. Chceme-li se vyhnout tomuto problému, budeme předpokládat, že vstup do jakéhokoli invertující algoritmu pro f(x) bude zahrnovat délku x, zakódovanou do posloupnosti jedniček. One-way Uživatel Definice Zanedbatelnost One-way Aplikace Příklad 3.7 Uvažme například funkci f: {0,1 }* {0,1 }*, ř(x) = posledních log2 \x\ bitů binárního zápisu čísla x. Je zřejmé, že jakékoliv z je exponenciálně delší než f {z) samo o sobě. Tedy žádný algoritmus nemůže invertovat f(x) v polynomiálním čase. Chceme-li se vyhnout tomuto problému, budeme předpokládat, že vstup do jakéhokoli invertující algoritmu pro f(x) bude zahrnovat délku x, zakódovanou do posloupnosti jedniček. Takže pokud |x| = k potom se jako vstup invertujícího algoritmu bere dvojice (f(x), 1^) a výstupem by měl být prvek zef~\f(x)). One-way Uživatel Definice Zanedbatelnost One-way Aplikace Příklad 3.7 Uvažme například funkci f: {0,1 }* {0,1 }*, ř(x) = posledních log2 \x\ bitů binárního zápisu čísla x. Je zřejmé, že jakékoliv z je exponenciálně delší než f {z) samo o sobě. Tedy žádný algoritmus nemůže invertovat f(x) v polynomiálním čase. Chceme-li se vyhnout tomuto problému, budeme předpokládat, že vstup do jakéhokoli invertující algoritmu pro f(x) bude zahrnovat délku x, zakódovanou do posloupnosti jedniček. Takže pokud |x| = k potom se jako vstup invertujícího algoritmu bere dvojice (f(x), 1^) a výstupem by měl být prvek zef~\f(x)). To nám zaručuje, že alespoň jedno takovéto z může být zapsáno v polynomiálním čase. ,DMflMlMl, t Pak lze přeformulovat definici jednosměrné funkce f: {0,1}* ^{0,1}* následovně: (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ě. (II) Pro každý pravděpodobnostní algoritmus A pracující v polynomiálním čase, je pravděpodobnost toho, že A úspěšně provede inverzi ř(x), pro náhodně vybrané x g {0,1 }k, zanedbatelná. Pak lze přeformulovat definici jednosměrné funkce f: {0,1}* ^{0,1}* následovně: (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ě. (II) Pro každý pravděpodobnostní algoritmus A pracující v polynomiálním čase, je pravděpodobnost toho, že A úspěšně provede inverzi ř(x), pro náhodně vybrané x g {0,1 }k, zanedbatelná. (II) lze pak přepsat následovně: (lľ) Pro každý pozitivní polynom q(n) a každý pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase, platí »ro dostatečné velké k. Poznamenejme, že výše uvedený přepis platí za předpokladu, že uvažujeme pouze spočetnou množinu takovýchto algoritmů. Přitom (lľ) lze chápat jako lze chápat jako uniformní jednosměrnost funkce f. Poznamenejme, že výše uvedený přepis platí za předpokladu, že uvažujeme pouze spočetnou množinu takovýchto algoritmů. Přitom (lľ) lze chápat jako lze chápat jako uniformní jednosměrnost funkce f. Buď v dalším f vypočitatelná v polynomiálně omezené době. Označme pak pro každý pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase a pro každé k g N (což chápeme jako bezpečnostní parametr) hodnotu lmiA{k) = P{A{f{x), 1 *) g ŕ"1 {f{x)) | x g {0,1 Ý). Poznamenejme, že výše uvedený přepis platí za předpokladu, že uvažujeme pouze spočetnou množinu takovýchto algoritmů Přitom (lľ) lze chápat jako lze chápat jako uniformní jednosměrnost funkce f. Buď v dalším f vypočitatelná v polynomiálně omezené době. Označme pak pro každý pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase a pro každé k g N (což chápeme jako bezpečnostní parametr) hodnotu lmiA{k) = P{A{f{x), 1 *) g ŕ"1 {f{x)) | x g {0,1 }*). Máme tedy pro každý pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase přiřazenou funkci \vna : N -> R>0. Úvod One-way Integrita a autenticita Uživatel finice nedbatelnost One-way Aplikace Z výše uvedeného plyne, že: f je jednosměrná právě tehdy, když pro každý pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase je funkce \nvA zanedbatelná. Z výše uvedeného plyne, že: f je jednosměrná právě tehdy, když pro každý pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase je funkce \nvA zanedbatelná. Tedy funkce není jednosměrná, pokud existuje pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase, který má nezanedbatelnou pravděpodobnost úspěchu. Z výše uvedeného plyne, že: f je jednosměrná právě tehdy, když pro každý pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase je funkce \nvA zanedbatelná. Tedy funkce není jednosměrná, pokud existuje pravděpodobnostní algoritmus A na provedení inverze pracující v polynomiálním čase, který má nezanedbatelnou pravděpodobnost úspěchu. Řekneme, že f je uniformně jednosměrná právě tehdy, když existuje zanedbatelná funkce S tak, že \nvA