Veřejný klíč Asymetrie Podpis Padací dveře 6. Asymetrické šifrovací systémy neboli systémy s veřejným klíčem Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 25. října 2021 Veřejný klíč Asymetrie Podpis Padací dveře Q Veřejný klíč Ä o Úvod ™ Idea funkce s vlastr Fl Doposud jsme pracovali se šifrovacími systémy následujících vlastností: O Kdo může zašifrovat zprávu, může ji i dešifrovat. O Každá dvojice partnerů musí mít svůj společný tajný kl Fl Doposud jsme pracovali se šifrovacími systémy následujících vlastností: O Kdo může zašifrovat zprávu, může ji i dešifrovat. O Každá dvojice partnerů musí mít svůj společný tajný klíč. Druhá vlastnost je nepochybně nevýhodná. Pokud by počítačová síť měla n navzájem propojených účastníků, museli by používat í^tl) různých šifrovacích klíčů, které by si účastníci museli mezi sebou vyměnit. Fl Doposud jsme pracovali se šifrovacími systémy následujících vlastností: O Kdo může zašifrovat zprávu, může ji i dešifrovat. O Každá dvojice partnerů musí mít svůj společný tajný klíč. Druhá vlastnost je nepochybně nevýhodná. Pokud by počítačová síť měla n navzájem propojených účastníků, museli by používat í^tl) různých šifrovacích klíčů, které by si účastníci museli mezi sebou vyměnit. Zvolíme-li např. n = 500, bylo by nutno mít v systému cca 125000 klíčů. Vzhledem k nutné obnově za nové klíče bychom se dostali do prakticky nerealizovatelné situace. Veřejný klíč Asymetrie Podpis Padací dveře O šifrovacím systému s první vlastností pak obvykle mluvíme jako o symetrickém šifrovacím systému. První vlastnost můžeme považovat za výhodnou, protože lze k šifrování a dešifrování použít stejný stroj. Veřejný klíč Asymetrie Podpis Padací dveře O šifrovacím systému s první vlastností pak obvykle mluvíme jako o symetrickém šifrovacím systému. První vlastnost můžeme považovat za výhodnou, protože lze k šifrování a dešifrování použít stejný stroj. Asymetrické algoritmy se vyznačují tím, že jsou od první vlastnosti co nejvíce možná vzdáleny. Ukážeme, že takovéto systémy nemají druhou vlastnost a tedy práce s klíči je jednoduchá. Veřejný klíč Asymetrie Podpis Padací dveře O šifrovacím systému s první vlastností pak obvykle mluvíme jako o symetrickém šifrovacím systému. První vlastnost můžeme považovat za výhodnou, protože lze k šifrování a dešifrování použít stejný stroj. Asymetrické algoritmy se vyznačují tím, že jsou od první vlastnosti co nejvíce možná vzdáleny. Ukážeme, že takovéto systémy nemají druhou vlastnost a tedy práce s klíči je jednoduchá. Budeme hlavně používat pojem asymetrického algoritmu; občas budeme mluvit o public-key algoritmu. Takovéto postupy byly vyvinuty v roce 1976 Whitfieldem Diffiem a Martinem Hellmanem v jejich práci New Directions in Cryptography, za kterou tito američtí matematici obdrželi v temže roce výroční cenu M.I.T. Veřejný klíč Podpis Asymetrie Padací dveře Uvod ■ ■ r Asymetrické šifrovací systémy Budeme předpokládat, že každý účastník T má dvojici klíčů, to Veřejný klíč Asymetrie Podpis Padací dveře Budeme předpokládat, že každý účastník T má dvojici klíčů, a to • veřejný klíč E = ET k zašifrování; • soukromý (tajný) klíč D = DT k dešifrování; které se vyznačují následující vlastností: Ze znalosti klíče ET nelze zjistit soukromý klíč DT. Budeme předpokládat, že každý účastník T má dvojici klíčů, a to • veřejný klíč E = ET k zašifrování; • soukromý (tajný) klíč D = DT k dešifrování; které se vyznačují následující vlastností: Ze znalosti klíče ET nelze zjistit soukromý klíč DT. Kryptosystém s touto vlastností se nazývá asymetrický kryptosystém. Budeme předpokládat, že každý účastník T má dvojici klíčů, to • veřejný klíč E = ET k zašifrování; • soukromý (tajný) klíč D = DT k dešifrování; které se vyznačují následující vlastností: Ze znalosti klíče ET nelze zjistit soukromý klíč DT. Kryptosystém s touto vlastností se nazývá asymetrický kryptosystém. Pokud navíc předpokládáme, že pro každou zprávu M platí D(E(M)) = M, mluvíme o asymetrickém šifrovacím systému. Veřejný klíč Asymetrie Podpis Padací dveře Asymetrický kryptosystém se nazývá asymetrické podpisovací schéma, pokud pro každou zprávu M lze pomocí veřejného klíče E prověřit, zda se k sobě M a D(M) hodí. Veřejný klíč Asymetrie Podpis Padací dveře Asymetrický kryptosystém se nazývá asymetrické podpisovací schéma, pokud pro každou zprávu M lze pomocí veřejného klíče E prověřit, zda se k sobě M a D(M) hodí. Všechny veřejné klíče jsou uloženy ve veřejně dostupném souboru (podobnému telefonnímu seznamu), zatímco soukromé klíče jsou tajné tj. známé pouze jejich vlastníkům. Veřejný klíč Podpis Asymetrie Padací dveře Úvod ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Asymetrické šifrovací systémy III Šifrování a dešifrování pomocí asymetrického šifrovacího systému probíhá ve 3 krocích: O Chce-li A zaslat B zprávu M, pak o najde veřejný klíč EB pro B, o zašifruje zprávu M pomocí klíče EB a o odešle EB(M) k B. O B může kryptogram EB(M) dešifrovat, protože zná jako jediný tajný klíč DB : DB(EB(M)) = M. O Žádný jiný účastník nemůže EB(M) rozluštit, protože podle předpokladu ze znalosti EB a EB(M) nelze získat znalost o DB. Veřejný klíč Podpis Asymetrie Padací dveře Úvod ^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^H Asymetrické šifrovací systémy - Výhody IV • Není potřeba výměna klíčů. Tímto je vyřešen hlavní problém symetrického algoritmu. Zejména je tedy s pomocí asymetrického algoritmu možná bezprostřední komunikace. Můžeme tedy navzájem komunikovat, aniž bychom se složitě dohadovali o klíči. Asymetrické algoritmy jsou ideální pro otevřenou komunikaci. Veřejný klíč Podpis Asymetrie Padací dveře Úvod ^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^H Asymetrické šifrovací systémy - Výhody IV • Není potřeba výměna klíčů. Tímto je vyřešen hlavní problém symetrického algoritmu. Zejména je tedy s pomocí asymetrického algoritmu možná bezprostřední komunikace. Můžeme tedy navzájem komunikovat, aniž bychom se složitě dohadovali o klíči. Asymetrické algoritmy jsou ideální pro otevřenou komunikaci. • Není potřeba mnoho klíčů. U symetrického algoritmu se zvyšuje počet klíčů kvadraticky s počtem uživatelů, u asymetrického algoritmu je počet klíčů roven dvojnásobku počtu uživatelů. Veřejný klíč Podpis Asymetrie Padací dveře Úvod ^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^H Asymetrické šifrovací systémy - Výhody IV • Není potřeba výměna klíčů. Tímto je vyřešen hlavní problém symetrického algoritmu. Zejména je tedy s pomocí asymetrického algoritmu možná bezprostřední komunikace. Můžeme tedy navzájem komunikovat, aniž bychom se složitě dohadovali o klíči. Asymetrické algoritmy jsou ideální pro otevřenou komunikaci. • Není potřeba mnoho klíčů. U symetrického algoritmu se zvyšuje počet klíčů kvadraticky s počtem uživatelů, u asymetrického algoritmu je počet klíčů roven dvojnásobku počtu uživatelů. • Lze přijmout bez problémů nové uživatele. Je-li přijat nový účastník do symetrického systému, musí si s ním všichni původní účastníci vyměnit klíč. U asymetrického systému není naproti tomu nutno, aby původní účastníci aktualizovali svoje data. Veřejný klíč Podpis Asymetrie Padací dveře Úvod ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^H Asymetrické šifrovací systémy - Výhody V • Mnoho asymetrických systémů poskytuje skvělé možnosti pro elektronický podpis. Veřejný klíč Podpis Asymetrie Padací dveře Úvod ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^H Asymetrické šifrovací systémy - Výhody V • Mnoho asymetrických systémů poskytuje skvělé možnosti pro elektronický podpis. Nevýhody asymetrického šifrovacího systému jsou pak: • Doposud není znám žádný asymetrický kryptosystém, který by byl zároveň rychlý a bezpečný. Postup, kterým se budeme hlavně zabývat, je tzv. RSA-algoritmus. V poslední době se také pracuje s algoritmy, které spočívají na "diskrétních logaritmech". Veřejný klíč Podpis Asymetrie Padací dveře Úvod ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^H Asymetrické šifrovací systémy - Výhody V • Mnoho asymetrických systémů poskytuje skvělé možnosti pro elektronický podpis. Nevýhody asymetrického šifrovacího systému jsou pak: • Doposud není znám žádný asymetrický kryptosystém, který by byl zároveň rychlý a bezpečný. Postup, kterým se budeme hlavně zabývat, je tzv. RSA-algoritmus. V poslední době se také pracuje s algoritmy, které spočívají na "diskrétních logaritmech". 9 Asymetrické algoritmy potřebují jistý dohled nad klíči. Může se totiž stát, že Mr. X opatří svoji schránku s falešným jménem, ke kterému se však hodí jeho klíč. Pak může zachytit všechny zprávy, které byly adresovány původnímu adresátovi. Veřejný klíč Asymetrie Podpis Padací dveře Lamport Veřejný klíč schéma • Rabínovo pravděpodobnostní podpisovací schéma • Asymetrické šifrování Q Elektronický podpis • Diffie-Lamportovo Další důležitou myšlenkou Diffieho a Hellmana je elektronický neboli digitální podpis. Nejdříve si ujasněme vlastnosti obvyklého podpisu rukou. Další důležitou myšlenkou Diffieho a Hellmana je elektronický neboli digitální podpis. Nejdříve si ujasněme vlastnosti obvyklého podpisu rukou. Předpokládejme, že osoba A se podepsala rukou na nějaký dokument D. Pak má tento podpis v ideálním případu následující vlastnosti: • Pouze osoba A může vytvořit tento podpis. • Každý jiný účastník může prověřit, že se opravdu jedná o podpis osoby A. Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Veřejný klíč Diskutujme nejprve digitální podpis s použitím symetrického šifrovacího systému (např. DES). Popíšeme dva možné přístupy. Diffie-Lamportovo schéma Odesílatel A, který si přeje podepsat n-bitovou binární zprávu M = Mi ... Mn, si předem vybere 2n klíčů šifrovacího systému (M, K, C). Označme je po řadě jako 3.\, . . . , Sn'i b-\, . . . , bn- Diskutujme nejprve digitální podpis s použitím symetrického šifrovacího systému (např. DES). Popíšeme dva možné přístupy. Diffie-Lamportovo schéma Odesílatel A, který si přeje podepsat n-bitovou binární zprávu M= Mi...Mn, si předem vybere 2n klíčů šifrovacího systému (M, K, C). Označme je po řadě jako 3.\, . . . , 5/7Í b-\, . . . , bn- Tyto klíče jsou tajné. Je-li šifrovací algoritmus e, osoba A vygeneruje 4n parametrů {(X,, Yh Uh Vj) : 1 < / < n}, kde Xh Y\ leží v definičním oboru e a U, = e{Xh ai) a V, = e{Yh b,) (1 < / < n). (3.1) Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Veřejný klíč Je-li šifrovací algoritmus e, osoba A vygeneruje 4n parametrů {(X,, Yh Uh Vj) : 1 < / < n}, kde Xh Y\ leží v definičním oboru e a U, = e{Xh ai) a V, = e{Yh b,) (1 < / < n). (3.1) Tyto parametry jsou dopředu zaslány příjemci a zároveň jsou odeslány nezávislému prověřovateli (veřejný registr). Nyní předpokládejme, že osoba A chce odeslat podepsanou n-bitovou zprávu M = M1 ... Mn. Bude postupovat podle následující procedury. Jejím podpisem bude řetězec kde pro všechna /, 1 < i < n platí a, pokud M,■ = 0, Ď, pokud M, = 1. Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Veřejný klíč Ověřovací protokol osoby B probíhá následovně: pro všechna / (1 < / < ri) použije osoba B bit M, a klíč S/5 aby ověřila, že í pokud Mi = 0 pak e(Xh Si) = Uh \ pokud Mi = 1 pak e(Yh Sf) = V,. Osoba B pak akceptuje podepsanou zprávu pouze za předpokladu, že ověřovací protokol je splněn pro všechna i. Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Veřejný klíč Ověřovací protokol osoby B probíhá následovně: pro všechna / (1 < / < ri) použije osoba B bit M, a klíč S/5 aby ověřila, že í pokud Mi = 0 pak e(Xh Si) = Uh \ pokud Mi = 1 pak e(Yh Sf) = V,. Osoba B pak akceptuje podepsanou zprávu pouze za předpokladu, že ověřovací protokol je splněn pro všechna i. Ačkoliv tento systém je jednoduchý pro použití a snadno pochopitelný, má minimálně dvě nevýhody. První je nutná předběžná komunikace s parametry. Důležitější je však zvýšení rozměru zprávy - např. v případě DESu, kdy klíče mají délku 64 bitů, by se zpráva zvětšila 64-krát. Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Rabin Veřejný klíč Rabínovo pravděpodobnostní podpisovací schéma I Rabin (1978) navrhl jiný přístup. Buď e šifrovací funkce nějakého šifrovacího systému (M, K, C). Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Rabin Veřejný klíč Rabínovo pravděpodobnostní podpisovací schéma I Rabin (1978) navrhl jiný přístup. Buď e šifrovací funkce nějakého šifrovacího systému (M, K, C). Buď dále (Kj: 1 < / < 2r) posloupnost náhodně vybraných klíčů, které odesílatel A uchová v tajnosti. Příjemce B obdrží seznam 2r parametrů (X,, L/,-), (1 < / < 2r), kde e(Xi,Ki) = Ui (1 |KAC23BZxel| veřejný klíč příjemce (B) lyAl soukromý klíč VJkodesilatele (A) soukromý klíč příjemce (B) shoduje se vypočtený výtah zprávy s výtahem zprávy, který poslal odesilatel A zprava nebyla zfalšována nebezpečný kanál 3^ digitální podpis (ť\ veřejný klíč odesilatele (A) výtah zprávy KAC23BZxe1 ^ zprava byla zfalšována Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Rabin Veřejný klíč Asymetrické šifrování a podpisy V Nyní je příjemce B ve velmi výhodné pozici. Vlastní dvojici (M, S). V případě sporu, potřebuje-li přesvědčit soudce, že odesílatel A opravdu odeslal zprávu, požádá A o vytvoření jeho soukromého klíče KA. Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Rabin Veřejný klíč Asymetrické šifrování a podpisy V Nyní je příjemce B ve velmi výhodné pozici. Vlastní dvojici (M, S). V případě sporu, potřebuje-li přesvědčit soudce, že odesílatel A opravdu odeslal zprávu, požádá A o vytvoření jeho soukromého klíče KA. Odesílatel A musí opravdu vytvořit svůj soukromý klíč KA, protože ho lze otestovat na identitě e^(č//\(M)) = M. Soudci pak pouze stačí prověřit, že S = dA(M). Veřejný klíč Asymetrie Podpis Padací dveře Diffie-Lamport Rabin Veřejný klíč Asymetrické šifrování a podpisy V Nyní je příjemce B ve velmi výhodné pozici. Vlastní dvojici (M, S). V případě sporu, potřebuje-li přesvědčit soudce, že odesílatel A opravdu odeslal zprávu, požádá A o vytvoření jeho soukromého klíče KA. Odesílatel A musí opravdu vytvořit svůj soukromý klíč KA, protože ho lze otestovat na identitě e^(č//\(M)) = M. Soudci pak pouze stačí prověřit, že S = dA(M). Ze stejného důvodu musí příjemce B zůstat poctivý. Předpokládejme, že změnil zprávu M na zprávu M'. Pak by ale musel být schopen změnit podpis S na S', aby platilo, že Sř = dA(Mř). Ale to může provést pouze A. Veřejný klíč Podpis Asymetrie Padací dveře Padací dveře Q Idea funkce s vlastností padacích dveří • Shrnutí • Vlastnost padacích dveří Zopakujme si vlastnosti systému s veřejným klíčem z odstavce 2 - Asymetrické šifrovací systémy. Veřejný klíč Asymetrie Podpis Padací dveře Padací dveře Zopakujme si vlastnosti systému s veřejným klíčem z odstavce 2 - Asymetrické šifrovací systémy. Všichni uživatelé systému, kteří si přejí navzájem komunikovat, používají tentýž šifrovací algoritmus e a tentýž dešifrovací algoritmus d. Každý uživatel U, má dvojici klíčů (Kh /_,) tak, že pro každou možnou zprávu M platí identita d(e(MJKÍ-)J/./) = MJ (4.1) kde Kj je zveřejněn a uložen ve veřejném souboru; /_, zůstane utajen a mluvíme o něm jako o soukromém klíči, Kj se nazývá verejný klic. Veřejný klíč Asymetrie Podpis Padací dveře Padací dveře Pokud chce jiný uživatel Uj odeslat uživateli U\ zprávu M, postupuje následovně. (a) Uživatel U, najde veřejný klíč K, uživatel U, ve veřejném souboru. Pokud chce jiný uživatel Uj odeslat uživateli \J\ zprávu M, postupuje následovně. (a) Uživatel Uj najde veřejný klíč K, uživatel U, ve veřejném souboru. (b) Uživatel (V, odešle kryptogram ^ ... v 1 J ^ * C = e(M,Kj) k uživateli Uj veřejným kanálem. Pokud chce jiný uživatel Uj odeslat uživateli U, zprávu M, postupuje následovně. (a) Uživatel Uj najde veřejný klíč K, uživatel U, ve veřejném souboru. (b) Uživatel (V, odešle kryptogram ^ ... v 1 J ^ * C = e(M,Kj) k uživateli Uj veřejným kanálem. Bezpečnost systému závisí na funkcích ead, které mají následující vlastnosti. Pokud chce jiný uživatel Uj odeslat uživateli U, zprávu M, postupuje následovně. (a) Uživatel Uj najde veřejný klíč K, uživatel U, ve veřejném souboru. (b) Uživatel (V, odešle kryptogram ^ ... v 1 J ^ * C = e(M,Kj) k uživateli Uj veřejným kanálem. Bezpečnost systému závisí na funkcích ead, které mají následující vlastnosti. Vlastnost 1 Známe-li M a K, mělo by být snadné vypočíst C = e(M, K). Pokud chce jiný uživatel Uj odeslat uživateli U, zprávu M, postupuje následovně. (a) Uživatel Uj najde veřejný klíč K, uživatel U, ve veřejném souboru. (b) Uživatel (V, odešle kryptogram ^ ... v 1 J ^ * C = e(M,Kj) k uživateli Uj veřejným kanálem. Bezpečnost systému závisí na funkcích ead, které mají následující vlastnosti. Vlastnost 1 Známe-li M a K, mělo by být snadné vypočíst C = e(M, K). Vlastnost 2 Je-li dán pouze kryptogram C, není snadné výpočetně najít M. Veřejný klíč Podpis Asymetrie Padací dveře Padací dveře Pokud chce jiný uživatel Uj odeslat uživateli U, zprávu M, postupuje následovně. (a) Uživatel Uj najde veřejný klíč K, uživatel U, ve veřejném souboru. (b) Uživatel (V, odešle kryptogram ^ ... v 1 J ^ * C = e(M,Kj) k uživateli Uj veřejným kanálem. Bezpečnost systému závisí na funkcích e ad, které mají následující vlastnosti. Vlastnost 1 Známe-li M a K, mělo by být snadné vypočíst C = e(M, K). Vlastnost 2 Je-li dán pouze kryptogram C, není snadné výpočetně najít M. Vlastnost 3 Je-li znám kryptogram C a tajný klíč Lh je snadné určit zprávu M. Jinak řečeno, vlastnosti 1 a 2 tvrdí, že šifrovací funkce e používající veřejný klíč by měla být jednosměrná, ale vlastnost 3 požaduje navíc existenci "veřejného klíče". Takováto jednosměrná funkce se nazývá funkce s vlastností padacích dveří. Jinak řečeno, vlastnosti 1 a 2 tvrdí, že šifrovací funkce e používající veřejný klíč by měla být jednosměrná, ale vlastnost 3 požaduje navíc existenci "veřejného klíče". Takováto jednosměrná funkce se nazývá funkce s vlastností padacích dveří. Aby byl takovýto systém prakticky použitelný, je nutné splnění následující podmínky. Vlastnost 4 Mělo by být snadné generovat "náhodné" dvojice veřejný/soukromý klíč (Kh /_,). Jinak řečeno, vlastnosti 1 a 2 tvrdí, že šifrovací funkce e používající veřejný klíč by měla být jednosměrná, ale vlastnost 3 požaduje navíc existenci "veřejného klíče". Takováto jednosměrná funkce se nazývá funkce s vlastností padacích dveří. Aby byl takovýto systém prakticky použitelný, je nutné splnění následující podmínky. Vlastnost 4 Mělo by být snadné generovat "náhodné" dvojice veřejný/soukromý klíč (Kh /_,). Jinak řečeno, mělo by být dostatečně "mnoho" dvojic (K, L) tak, že je pro Mr. X nemožné sestrojit tabulku vhodných funkčních hodnot. Veřejný klíč Podpis Asymetrie Padací dveře Padací dveře aO = Gen(l") f:D^R easy hard easy given t D R