6. Asymetrické šifrovací systémy neboli systémy s veřejným klíčem RSA-algoritmus Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 1. listopadu 2021 RSA-algoritmus Diskuse k RSA Ruksak • Korektnost O RSA-algoritmus RSA-algoritmu • Úvod • Postup při šifrování RSA-algoritmu • RSA-podpisovací schéma □ t3 RSA-algoritmus Diskuse k RSA Ruksak úvod Postu Podpis s RSA Korektnost RS Připomeňme dvě zásadní tvrzení z teorie čísel. RSA-algoritmus Diskuse k RSA Ruksak úvo Podpis s RSA Korektnost R Připomeňme dvě zásadní tvrzení z teorie čísel. Věta 1.1 (Euler) Nechť (c, m) = 1. Pak platíc^ = 1 mod m. RSA-algoritmus Diskuse k RSA Ruksak úvo Podpis s RSA Korektnost R Připomeňme dvě zásadní tvrzení z teorie čísel. ' Věta 1.1 I (Euler) Nechť (c, m) = 1. Pak platíc^ = 1 A770C/ m. I Věta 1.2_ (Fermat) Nechť p je prvočíslo (c, p) = 1. Pa/c p/atf cp_1 = 1 mod p. j O Najděme dvě "velká" prvočísla p a q a položme n = p • q. O Najděme dvě "velká" prvočísla p a q a položme n = p • q O Najděme "velké a náhodné" přirozené číslo d tak, že je nesoudělné s číslem (p - 1) • (q - 1). O Najděme dvě "velká" prvočísla p a q a položme n = p • q. O Najděme "velké a náhodné" přirozené číslo d tak, že je nesoudělné s číslem (p - 1) • (q - 1). O Vypočtěme jediné přirozené číslo e ležící v oboru hodnot 1 < e < (p - 1) • (q - 1) ze vztahu e • d = 1 mod (p - 1) • (q - 1). O Zveřejněme veřejný klíč, který se skládá z dvojice přirozených čísel (e, n). O Najděme dvě "velká" prvočísla p a q a položme n = p • q. O Najděme "velké a náhodné" přirozené číslo d tak, že je nesoudělné s číslem (p - 1) • (q - 1). O Vypočtěme jediné přirozené číslo e ležící v oboru hodnot 1 < e < (p - 1) • (q - 1) ze vztahu e • d = 1 mod (p - 1) • (q - 1). O Zveřejněme veřejný klíč, který se skládá z dvojice přirozených čísel (e, n). O Reprezentujme zprávu M jako přirozené číslo z intervalu {1,..., n}\ rozdělme zprávu M do bloků, je-li příliš velká. Najděme dvě "velká" prvočísla p a q a položme n = p • q. O Najděme "velké a náhodné" přirozené číslo d tak, že je nesoudělné s číslem (p - 1) • (q - 1). O Vypočtěme jediné přirozené číslo e ležící v oboru hodnot 1 < e < (p - 1) • (q - 1) ze vztahu e • d = 1 mod (p - 1) • (q - 1). O Zveřejněme veřejný klíč, který se skládá z dvojice přirozených čísel (e, n). O Reprezentujme zprávu M jako přirozené číslo z intervalu {1,..., n}\ rozdělme zprávu M do bloků, je-li příliš velká. O Zakódujme M do kryptogramu C dle předpisu C = Me mod n. Q Dešifrujme pomocí soukromého klíče d a předpisu D = mod r?. Kú) GiiiHiilip /» JLÍkd q botíl pri Ď k, /t ^ é/ Cfllculůlr n = p x q Cakukiiiľ \h\t\\ = ijr - £pd (^(ír>, ť] = 1: J <ŕ<^fl) ..v ílu J lýlJTl = 1 PiiľiLíľ- kit Ptivatť key U£= \ti.n1 [jeílmi ľl;i;i.\-m Í. IJjliĽrlĽÄC. C= if* (ruLuJ m CiphertutL PlilllStĽIlL RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Zp rára Po dep Podep RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost R Označme veřejný klíč uživatele / dvojici (e/, n/) a soukromý klíč RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Označme veřejný klíč uživatele / dvojici (e/, nt) a soukromý klíč di. V praxi je n\ obvykle voleno jako číslo, které je součin dvou náhodně zvolených asi 100-místných prvočísel (300-600 bitů), ni = Pr Qh RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Označme veřejný klíč uživatele / dvojici (e/, nt) a soukromý klíč di. V praxi je n\ obvykle voleno jako číslo, které je součin dvou náhodně zvolených asi 100-místných prvočísel (300-600 bitů), ni = Pr Qh Prvočísla pi a Q/ jsou osobním tajemstvím uživatele I. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Označme veřejný klíč uživatele / dvojici (e/, nt) a soukromý klíč di. V praxi je n\ obvykle voleno jako číslo, které je součin dvou náhodně zvolených asi 100-místných prvočísel (300-600 bitů), ni = Pr Qh Prvočísla pi a Q/ jsou osobním tajemstvím uživatele I. Dále si uživatel I zvolí tzv. šifrovací exponent e/ tak, aby byl nesoudělný s (f(rii). RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Označme veřejný klíč uživatele / dvojici (e/, ni) a soukromý klíč V praxi je n\ obvykle voleno jako číslo, které je součin dvou náhodně zvolených asi 100-místných prvočísel (300-600 bitů), ni = pr qi. Prvočísla pi a Q/ jsou osobním tajemstvím uživatele I. Dále si uživatel I zvolí tzv. šifrovací exponent e/ tak, aby byl nesoudělný s 1. RSA-algoritmus m Lemma 1.3 Diskuse k RSA 7mW«ÍLf Lij Ruksak Podpis s RSA Korektnost R Pro všechna vhodně zvolená M platí S = MdA(mod nA) M= SeA(modnA). Důkaz Můžeme bez újmy na obecnosti předpokládat, že (M, nA) > 1. Dle předpokladu RSA-algoritmu e& • d& = (qA - 1) • c + 1 pro vhodné číslo c. RSA-algoritmus m Lemma 1.3 Diskuse k RSA 7mW«ÍLf Lij Ruksak Podpis s RSA Korektnost R Pro všechna vhodně zvolená M platí S = MdA(mod nA) M= SeA(modnA). Důkaz Můžeme bez újmy na obecnosti předpokládat, že (M, nA) > 1. Dle předpokladu RSA-algoritmu eA • dA = (qA - 1) • c + 1 pro vhodné číslo c. Z Fermatovy věty máme py.cu-i =(py-i)c = 1modQ^ RSA-algoritmus m Lemma 1.3 Diskuse k RSA 7mW«ÍLf Lij Ruksak Podpis s RSA Korektnost R Pro všechna vhodně zvolená M platí S = MdA(mod nA) M= SeA(modnA). Důkaz Můžeme bez újmy na obecnosti předpokládat, že (M, nA) > 1. Dle předpokladu RSA-algoritmu eA • dA = (qA - 1) • c + 1 pro vhodné číslo c. Z Fermatovy věty máme py.cu-i =(py-i)c = 1modQ^ Po vynásobení číslem pA máme PAA'dA = Pa^oú pA- qA. RSA-algoritmus Diskuse k RSA Ruksak úvod Postup Podpis s RSA Korektnost RSA Korektnost RSA-algoritmu II Pokračování důkazu Lemmatu 1.3. Je-li (M, nA) > 1, je M dělitelné buď pA nebo qA. Nechť např. M = a • pA, 1 < a < qA. Pak (MdA)eA = MeAdA = aeA'dA • pAeA'dA = aeA'dA • pAmod • qA. RSA-algoritmus Diskuse k RSA Ruksak úvod Postup Podpis s RSA Korektnost RSA Korektnost RSA-algoritmu II Pokračování důkazu Lemmatu 1.3. Je-li (M, n a) > 1, je M dělitelné buď pA nebo qA. Nechť např. m = a • pa, 1 < a < Pak (MdA)eA = MeAdA = aeA'dA • pA6A'dA = aeA'dA • mod pA • Protože (a, = 1, máme dle Eulerovy věty aeA-dA = a m0c| qA. RSA-algoritmus Diskuse k RSA Ruksak úvod Postup Podpis s RSA Korektnost RSA Korektnost RSA-algoritmu II Pokračování důkazu Lemmatu 1.3. Je-li (M, nA) > 1, je M dělitelné buď pA nebo qA. Nechť např. M = a • pA, 1 < a < qA. Pak (MdA)eA = MeAdA = aeA'dA • pAeA'dA = aeA'dA • pAmod • qA. Protože (a, = 1, máme dle Eulerovy věty aeA'dA = a m0c| qA. Po vynásobení číslem pA máme (MdA)eA = p^ • aeA'dA — pA - a — M mod p^ • qA. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS urektnost RSA-algoritmu II Pokračování důkazu Lemmatu 1.3 Je-li (M, nA) > 1, je M dělitelné buď pA nebo qA. Nechť např. M = a • pA, 1 < a < qA. Pak (MdA)eA = MeAdA = aeA'dA • pAeA'dA = aeA'dA • p^mod pA • cfa. Protože (a, = 1, máme dle Eulerovy věty aeA-dA = a moc| qAm Po vynásobení číslem pA máme (M^)e^ = pA • ae^ — pA - a — M mod p^ • q^. Pro M = Ď • 1 < Ď < p/\ se důkaz provede analogicky. Pokud (M, = 1, pak z Eulerovy věty máme (MdA)eA = M0^ = M1+/c^) = M mod p^ • qA. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost R Poznamenejme, že odhlédneme-li od nutného požadavku na komutování šifrovací a dešifrovací funkce, musí být nutně podpis S vypočtený odesílatelem A v definičním oboru šifrovací procedury ee- RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Poznamenejme, že odhlédneme-li od nutného požadavku na komutování šifrovací a dešifrovací funkce, musí být nutně podpis S vypočtený odesílatelem A v definičním oboru šifrovací procedury ee- Tato poslední podmínka nemusí platit, když použitý systém je RSA; podpis S může být větší přirozené číslo, než je veřejný klíč nB. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Poznamenejme, že odhlédneme-li od nutného požadavku na komutování šifrovací a dešifrovací funkce, musí být nutně podpis S vypočtený odesílatelem A v definičním oboru šifrovací procedury ee- Tato poslední podmínka nemusí platit, když použitý systém je RSA; podpis S může být větší přirozené číslo, než je veřejný klíč nB. Můžeme však zajistit platnost této podmínky tím, že přizpůsobíme velikost bloků naší zprávy tak, že výsledek padne do požadovaného definičního oboru. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS urektnost RSA-algoritmu IV Zvolme {eA, nA) = (5,35), (ee, nB) = (3,15), M = 3. Pak dA = 5,dB = 3. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS urektnost RSA-algoritmu IV Zvolme (eA, nA) = (5,35), (eB, nB) = (3,15), M = 3. Pak dA = 5,dB = 3. Máme pak S = 35 = 33 (moc/35), C = 333 = 12 (moc/15). RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS urektnost RSA-algoritmu IV Zvolme (eA, nA) = (5,35), (eB, nB) = (3,15), M = 3. Pak dA = 5,dB = 3. Máme pak S = 35 = 33 (moc/35), C = 333 = 12 (moc/15). B vypočte podpis S' = 123 = 3 (moc/15) a z něho zprávu M' = 35 = 33 (moc/35). RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS urektnost RSA-algoritmu IV Zvolme {eA, nA) = (5,35), (ee, nB) = (3,15), M = 3. Pak dA = 5,dB = 3. Máme pak S = 35 = 33 (mod35), C = 333 = 12 (moc/15). S vypočte podpis S' = 123 = 3 (modl 5) a z ně/70 zprávu M' = 35 = 33 (moc/35). Protože 3 ^ 33, není pro uživatele B splněna podmínka komutování šifrovací a dešifrovací funkce a M se nám zobrazí na zcela jinou zprávu M'. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS urektnost RSA-algoritmu IV Zvolme (eA, nA) = (5,35), (eB, nB) = (3,15), M = 3. Pak dA = 5,dB = 3. Máme pak S = 35 = 33 (moc/35), C = 333 = 12 (moc/15). B vypočte podpis S' = 123 = 3 (moc/15) a z něho zprávu M' = 35 = 33 (moc/35). Protože 3 ^ 33, není pro uživatele B splněna podmínka komutování šifrovací a dešifrovací funkce a M se nám zobrazí na zcela jinou zprávu M'. Pokud by však bylo nA < nB (zvolme např. (eB, nB) = (5,35), (eA, nA) = (3,15), M = 3, dB = 5, dA = 3), máme S = 33 = 12 (moc/15), C = 125 = 17 (moc/35), S' = 175 = 12 (moc/35), M' = 123 = 3 (moc/15). RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost R Rivest, Shamir a Adleman (1978) navrhli mnohem elegantnější řešení: Je zvolena mezní hodnota h pro systém s veřejným klíčem (řekněme /?- 10199). RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Rivest, Shamir a Adleman (1978) navrhli mnohem elegantnější řešení: Je zvolena mezní hodnota h pro systém s veřejným klíčem (řekněme /?- 10199). Každý uživatel pak má dvě dvojice veřejných klíčů, jednu pro zašifrování a druhou pro ověření podpisu. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Rivest, Shamir a Adleman (1978) navrhli mnohem elegantnější řešení: Je zvolena mezní hodnota h pro systém s veřejným klíčem (řekněme /?- 10199). Každý uživatel pak má dvě dvojice veřejných klíčů, jednu pro zašifrování a druhou pro ověření podpisu. Označme je po řadě (e/, n{) a (ř/, m/), kde / probíhá množinu uživatelů. RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Rivest, Shamir a Adleman (1978) navrhli mnohem elegantnější řešení: Je zvolena mezní hodnota h pro systém s veřejným klíčem (řekněme /?- 10199). Každý uživatel pak má dvě dvojice veřejných klíčů, jednu pro zašifrování a druhou pro ověření podpisu. Označme je po řadě (e/, n{) a (ř/, m/), kde / probíhá množinu uživatelů. Soukromý klíč odpovídající dvojici pro ověření podpisu budeme značit (Gř/,flr/). RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost R Rivest, Shamir a Adleman (1978) navrhli mnohem elegantnější řešení: Je zvolena mezní hodnota h pro systém s veřejným klíčem (řekněme /?- 10199). Každý uživatel pak má dvě dvojice veřejných klíčů, jednu pro zašifrování a druhou pro ověření podpisu. Označme je po řadě (e/, n{) a (ř/, m/), kde / probíhá množinu uživatelů. Soukromý klíč odpovídající dvojici pro ověření podpisu budeme značit (Gř/,flr/). Zvolený předpis se řídí tím, že šifrovací modul n, a podpisovací modul A7?/ by měly pro každého uživatele / splňovat A77/ < h < 77/. RSA-algoritmus Diskuse k RSA Ruksak Počítáme pak následovně: O Odesílatel A vypočte podpis S jako S = M9A(modmA). RSA-algoritmus Diskuse k RSA Ruksak Počítáme pak následovně: O Odesílatel A vypočte podpis S jako S = M9A(modmA). O Pak A vypočte kryptogram C= See(mod nB). ■šumní Počítáme pak následovně: O Odesílatel A vypočte podpis S jako S= M9A(moámA). O Pak A výpočte kryptogram C= Ses(mod nB). Q Po obdržení kryptogramu C výpočte B podpis S= Cde(mod nB). □ t3 RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Počítáme pak následovně: O Odesílatel A vypočte podpis S jako S = M9A(modmA). O Pak A vypočte kryptogram C= See(mod nB). O Po obdržení kryptogramu C vypočte B podpis S= Cde(mod nB). O Dále B vypočte zprávu M= SfA(vnodmA). RSA-algoritmus Diskuse k RSA Ruksak Podpis s RSA Korektnost RS Snadno se ověří, že tento systém opravdu pracuje a aby bylo zprávy možno podepsat a ověřit všemi uživateli systému, vše co potřebujeme, aby platilo 0 < max M < min {m/: / e U}, (1.1) kde U je množina uživatelů systému. RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS • Prvočísla • Nevýhody RSA-systému Q Diskuse k RSA V uvedené verzi RSA-algoritmu vystupují veřejné parametry (e/, nj) a tajné parametry oř/, p/ a Q/ spolu s číselným vyjádřením (části) zprávy M. Rozeberme si požadavky na jejich výběr. • Při použití RSA-algoritmu každý účastník systému používá dvě (čtyři) cca. 100-místná prvočísla. V uvedené verzi RSA-algoritmu vystupují veřejné parametry (e/, nj) a tajné parametry oř/, p/ a Q/ spolu s číselným vyjádřením (části) zprávy M. Rozeberme si požadavky na jejich výběr. • Při použití RSA-algoritmu každý účastník systému používá dvě (čtyři) cca. 100-místná prvočísla. Obvykle se dnes volí prvočísla o velikosti alespoň 1024 bitů, tj. čísla řádově kolem 21024. Modul n má tedy velikost 2048 bitů. RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS V uvedené verzi RSA-algoritmu vystupují veřejné parametry (e/, nj) a tajné parametry oř/, p/ a Q/ spolu s číselným vyjádřením (části) zprávy M. Rozeberme si požadavky na jejich výběr. • Při použití RSA-algoritmu každý účastník systému používá dvě (čtyři) cca. 100-místná prvočísla. Obvykle se dnes volí prvočísla o velikosti alespoň 1024 bitů, tj. čísla řádově kolem 21024. Modul n má tedy velikost 2048 bitů. Kolik jich máme k dispozici? Použitím prvočíselné funkce 7T, která udává počet prvočísel menších než dopředu zvolené číslo n a odhaduje se pomocí odhadu v ' In n získáme přibližný počet prvočísel 8 ležících v intervalu ro1023 o1024i L ' J ■ RSA-algoritmus Diskuse k RSA Ruksak Počítejme: O — 7Y{Č ) 7Y{Č ) — |n2l024 |n 21023 _ 21024 21023 _l_ 21023 _l. 21023 1024-1112 1023-ln2 1024-ll12 Pravděpodobnost, že by si dva účastníci systému vybrali tutéž dvojici 100-místných prvočísel, je pak řádově 2~4092. RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS • Dalším problémem je nalezení 100-místného náhodného prvočísla. RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS • Dalším problémem je nalezení 100-místného náhodného prvočísla. Nejprve pomocí generátoru pseudonáhodných čísel sestrojíme 100-místné náhodné číslo m. • Dalším problémem je nalezení 100-místného náhodného prvočísla. Nejprve pomocí generátoru pseudonáhodných čísel sestrojíme 100-místné náhodné číslo m. V případě, že m bude sudé, nahradíme ho číslem m + 1. Pak nové číslo m otestujeme některým z testů na prvočíselnost. • Dalším problémem je nalezení 100-místného náhodného prvočísla. Nejprve pomocí generátoru pseudonáhodných čísel sestrojíme 100-místné náhodné číslo m. V případě, že m bude sudé, nahradíme ho číslem m + 1. Pak nové číslo m otestujeme některým z testů na prvočíselnost. Pokud m nebude prvočíslo, vyzkoušíme číslo m+ 2 a postup opakujeme až do té doby, než nenajdeme první prvočíslo větší než m. • Dalším problémem je nalezení 100-místného náhodného prvočísla. Nejprve pomocí generátoru pseudonáhodných čísel sestrojíme 100-místné náhodné číslo m. V případě, že m bude sudé, nahradíme ho číslem m + 1. Pak nové číslo m otestujeme některým z testů na prvočíselnost. Pokud m nebude prvočíslo, vyzkoušíme číslo m+ 2 a postup opakujeme až do té doby, než nenajdeme první prvočíslo větší než m. Lze ověřit, že počet pokusů nutných k nalezení prvočísla v okolí čísla A77 je logaritmickou funkcí čísla m. Jako příklad uvedeme prvočísla o délce 1024 bitů. Jako příklad uvedeme prvočísla o délce 1024 bitů. Podle výše uvedeného odhadu je z 21024 čísel této délky 21013 prvočísel. RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS Jako příklad uvedeme prvočísla o délce 1024 bitů. Podle výše uvedeného odhadu je z 21024 čísel této délky asi 21013 prvočísel. Pravděpodobnost, že náhodně vybrané číslo je prvočíslo, je přibližně 2~10. Jako příklad uvedeme prvočísla o délce 1024 bitů. Podle výše uvedeného odhadu je z 21024 čísel této délky asi 21013 prvočísel. Pravděpodobnost, že náhodně vybrané číslo je prvočíslo, je přibližně 2~10. Pokud od počátku vyloučíme sudá čísla, zlepší se pravděpodobnost na 2~9. Jako příklad uvedeme prvočísla o délce 1024 bitů. Podle výše uvedeného odhadu je z 21024 čísel této délky asi 21013 prvočísel. Pravděpodobnost, že náhodně vybrané číslo je prvočíslo, je přibližně 2~10. Pokud od počátku vyloučíme sudá čísla, zlepší se pravděpodobnost na 2~9. Máte tedy v průměru kolem 512 pokusů na nalezení prvočísla o délce 1024 bitů. Jako příklad uvedeme prvočísla o délce 1024 bitů. Podle výše uvedeného odhadu je z 21024 čísel této délky asi 21013 prvočísel. Pravděpodobnost, že náhodně vybrané číslo je prvočíslo, je přibližně 2~10. Pokud od počátku vyloučíme sudá čísla, zlepší se pravděpodobnost na 2~9. Máte tedy v průměru kolem 512 pokusů na nalezení prvočísla o délce 1024 bitů. Jako další krok uvedeme příklad jednoduchého pravděpodobnostního algoritmu na zjištění prvočíselnosti čísla m. RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS Algoritmus na zjištění prvocíselnosti čísla m na k po kusů BEGIN READ (m, k); RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS Algoritmus na zjištění prvocíselnosti čísla m na k pokusů BEGIN READ (m, k); FOR / := 1 TO k DO BEGIN a :=RANDOM(1,m- 1); b := (a**(m - 1) MOD ni); IF o o 1 THEN BEGIN WRITE (m, "je složené číslo"); GO TO KONEC END END: RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS Algoritmus na zjištění prvocíselnosti čísla m na k pokusů BEGIN READ (m, k); FOR / := 1 TO k DO BEGIN a :=RANDOM(1,m- 1); b := (a**(m - 1) MOD ni); IF o o 1 THEN BEGIN WRITE (m, "je složené číslo"); GO TO KONEC END END; WRITE (m, "je prvočíslo"); KONEC: END. RSA-algoritmus Diskuse k RSA Ruksak Nevýhody RS Funkce RANDOM vybírá pseudonáhodná celá čísla z určeného intervalu. Funkce RANDOM vybírá pseudonáhodná celá čísla z určeného intervalu. Algoritmus na vstupu načte číslo m a číslo k a na výstupu obdržíme buď pravdivou odpověď, že A77 je složené číslo nebo odpověď, že se asi jedná o prvočíslo. Funkce RANDOM vybírá pseudonáhodná celá čísla z určeného intervalu. Algoritmus na vstupu načte číslo m a číslo k a na výstupu obdržíme buď pravdivou odpověď, že A77 je složené číslo nebo odpověď, že se asi jedná o prvočíslo. V případě, že je k dostatečně velké, je pravděpodobnost, že se nejedná o prvočíslo, v případě kladné odpovědi velmi malá. V praxi máme několik nevýhod RSA-systému: V praxi máme několik nevýhod RSA-systému: (a) Odesílatel A může úmyslně "ztratit" svůj soukromý klíč tak, že, ačkoliv je uložen v "bance soukromých klíčů" před startem systému, jí odeslané zprávy se stanou neověřitelnými. V praxi máme několik nevýhod RSA-systému: (a) Odesílatel A může úmyslně "ztratit" svůj soukromý klíč tak, že, ačkoliv je uložen v "bance soukromých klíčů" před startem systému, jí odeslané zprávy se stanou neověřitelnými. (b) Odesílatel A může úmyslně vydat svůj soukromý klíč ofo a dovolit tak, aby všechny jí adresované zprávy byly řešitelné. (c) Doba věnovaná šifrování, podepsání, dešifrování a prověření může být nepřiměřená. Totiž teprve nedávno byla nalezena rozumná implementace RSA-algoritmu a v současné době jsou na trhu RSA-čipy, které ale mají rychlost asi 10 Kbit/s. K dispozici jsou i speciální RSA-karty, které zvládnou 100 Kbit/s. Uvážíme-li však, že budoucí ISDN síťový standard elektronické pošty pracuje s 64Kbit/s a že se v půmyslu (lokální sítě apod.) pracuje s rychlostmi kolem 10 Mbit/s, vidíme, že nebude ještě dlouho možno použít RSA-algoritmus za účelem šifrování zpráv, nýbrž hlavně pro správu klíčů a elektronické podpisování. Při tvorbě elektronického podpisu se totiž nejdříve text zkomprimuje a podpisovací algoritmus se aplikuje na komprimát; není tedy nutno podpisovat velké soubory. Q Systémy založené na ruksakové metodě • Popis metody • Základ systému • Výhody a nevýhody O í\ I lvJ/~V Jeden z prvních (1978) sytému s veřejným klíčem byl vyvinut Merklem a Hellmanem a byl založen na tzv. ruksakovém problému. Jeden z prvních (1978) sytému s veřejným klíčem byl vyvinut Merklem a Hellmanem a byl založen na tzv. ruksakovém problému. Přesněji, jedná se o výpočetní problém známý jako PODMNOŽINOVÝSO(7ČE7definovaný následovně: Jeden z prvních (1978) sytému s veřejným klíčem byl vyvinut Merklem a Hellmanem a byl založen na tzv. ruksakovém problému. Přesněji, jedná se o výpočetní problém známý jako PODMNOŽINOVÝSO(7ČE7definovaný následovně: Vstup: Otázka: Jeden z prvních (1978) sytému s veřejným klíčem byl vyvinut Merklem a Hellmanem a byl založen na tzv. ruksakovém problému. Přesněji, jedná se o výpočetní problém známý jako PODMNOŽINOVÝSO(7ČE7definovaný následovně: Vstup: Kladná reálná čísla a^, a2,..., am t Otázka: Jeden z prvních (1978) sytému s veřejným klíčem byl vyvinut Merklem a Hellmanem a byl založen na tzv. ruksakovém problému. Přesněji, jedná se o výpočetní problém známý jako PODMNOŽINOVÝSO(7ČE7definovaný následovně: Vstup: Kladná reálná čísla a^, a2,..., am t Otázka: Existuje podmnožina J c {1,..., n} tak, že E/ej a/ = t? Jeden z prvních (1978) sytému s veřejným klíčem byl vyvinut Merklem a Hellmanem a byl založen na tzv. ruksakovém problému. Přesněji, jedná se o výpočetní problém známý jako PODMNOŽINOVÝSO(7ČE7definovaný následovně: Vstup: Kladná reálná čísla a^, a2,..., am t Otázka: Existuje podmnožina J c {1,..., n} tak, že E/ej a/ = t? Tento problém je jedním z klasických NP-úplných problémů. RSA-algoritmus Diskuse k RSA Ruksak p0pis metody Výhody a nevýhody Základ systému Popis metody II - Zašifrování zprávy O Odesílaná zpráva je odeslána v binárním tvaru m. Q Veřejné klíče tvoří soubor n-tic (a-i,..., an) kladných přirozených čísel. Q Binární zpráva m je rozdělena do bloků a n znacích tak, že m = m1... mt, kde každé rrij je n-tice nul a jedniček. O Pro každé y, 1 e-i + e2 + ... + en. RSA-algoritmus Diskuse k RSA Ruksak p0pis metody Výhody a nevýhody Základ systému Základ Merkle-Hellmanova systému II Lemma 3.2 Buď c kryptogram odeslaný uživatelem A při použití obtížného veřejného klíče 7"(e-i),..., T(en) uživatele A a předpisu r(e,) = w • e, (modN). Lehký kryptogram d pak získáme z následujícího vzorce: d = w 1 • c (mod N). RSA-algoritmus Diskuse k RSA Ruksak p0pis metody Základ systému Výhody a nevýhody Základ Merl