Rabinův kryptosystém
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. srpna 2021; ověření vyžaduje 1 úpravu .Rabinův kryptosystém je kryptografický systém s veřejným klíčem, jehož bezpečnost je zajištěna obtížným nalezením druhých odmocnin v kruhu zbytků modulo složené číslo . Bezpečnost systému, stejně jako bezpečnost metody RSA , je způsobena obtížností faktorizace velkých čísel. Zašifrovanou zprávu lze dešifrovat 4 způsoby. Nevýhodou systému je nutnost vybrat pravdivou zprávu ze 4 možných.
Historie
V lednu 1979 zveřejnil Michael O. Rabin popis svého systému. Bylo prokázáno, že obnovení otevřeného textu ze šifrovaného textu je stejně obtížné jako faktorizace velkých čísel. Rabinův systém se stal prvním asymetrickým kryptosystémem, pro který byl takový důkaz proveden. Složitost obnovy souvisí s obtížností extrahování druhé odmocniny modulo složené číslo N = p · q . Problém faktorizace a problém odmocniny jsou ekvivalentní, to znamená:
- když znáte prvočíselníky čísla N , můžete extrahovat odmocniny modulo N ;
- vědět, jak extrahovat druhé odmocniny modulo N , lze faktor N rozložit na prvočinitele.
Generování klíčů
Rabinův systém, stejně jako jakýkoli asymetrický kryptosystém , používá veřejný a soukromý klíč. Veřejný klíč se používá k šifrování zpráv a lze jej zpřístupnit veřejnosti. Soukromý klíč je nutný pro dešifrování a měli by ho znát pouze příjemci zašifrovaných zpráv.
Proces generování klíčů je následující:
- dvě náhodná čísla p a q jsou vybrána s ohledem na následující požadavky:
- čísla musí být velká (viz bitová hloubka );
- čísla musí být prvočísla ;
- musí být splněna následující podmínka: p ≡ q ≡ 3 mod 4 .
- vypočítá se číslo n = p · q ;
- číslo n je veřejný klíč; čísla p a q jsou uzavřená.
Příklad. Nechť p = 7 a q = 11 . Potom n = p · q = 7 · 11 = 77 . Číslo n = 77 je veřejný klíč a čísla p = 7 a q = 11 jsou soukromý klíč. Příjemce sdělí odesílatelům číslo 77. Odesílatelé zašifrují zprávu pomocí čísla 77 a odešlou ji příjemci. Příjemce dešifruje zprávu pomocí čísel 7 a 11. Uvedené klíče jsou pro praktické použití špatné, protože číslo 77 lze snadno rozložit na prvočinitele (7 a 11).
Šifrování
Původní zpráva m (text) je zašifrována pomocí veřejného klíče - čísla n podle následujícího vzorce:
c = m² mod n .Díky použití modulo násobení je rychlost šifrování systému Rabin větší než rychlost šifrování metody RSA , i když v druhém případě je zvolena malá hodnota exponentu.
Příklad (pokračování). Nechť je zdrojový text m = 20 . Potom by šifrový text byl: c = m² mod n = 20² mod 77 = 400 mod 77 = 15 .
Dešifrování
K dešifrování zprávy potřebujete soukromý klíč – čísla p a q . Proces dešifrování je následující:
- nejprve, pomocí Euklidova algoritmu , čísla a jsou nalezena z rovnice ;
- pak se pomocí čínské věty o zbytku vypočítají čtyři čísla:
Příklad (konec). V důsledku dekódování dostaneme: . Vidíme, že jedním z kořenů je původní text m .
Vyhodnocení algoritmu
Účinnost
Rozluštění textu kromě správného vede k dalším třem chybným výsledkům. To je hlavní nevýhoda kryptosystému Rabin a jeden z faktorů, který mu bránil v širokém praktickém využití.
Pokud je zdrojovým textem textová zpráva, není určení správného textu obtížné. Pokud je však zpráva proudem náhodných bitů (například pro generování klíčů nebo digitálního podpisu ), pak se určení správného textu stává skutečným problémem. Jedním ze způsobů, jak tento problém vyřešit, je přidat ke zprávě před zašifrováním známé záhlaví nebo nějaký štítek.
Rychlost výpočtu
Rabinův algoritmus je podobný kódování RSA, ale místo toho, aby se zpráva zvýšila na moc e , šifrování používá operaci kvadratury bloku zprávy, což příznivě ovlivňuje rychlost algoritmu bez obětování kryptografické síly.
Pro dekódování se používá čínská věta o zbytku spolu se dvěma umocněními modulo. Zde je účinnost srovnatelná s RSA.
Výběr požadovaného textu ze čtyř vede k dalším nákladům na výpočetní techniku. A to zajistilo, že Rabinův kryptosystém nenašel široké praktické využití.
Zabezpečení
Velkou výhodou Rabinova kryptosystému je to, že náhodný text lze zcela obnovit ze šifrovaného textu pouze v případě, že dešifrovač je schopen efektivně rozdělit veřejný klíč n.
Rabinův kryptosystém je prokazatelně odolný vůči útoku typu „všechno nebo nic“ založeného na zvoleném jednoduchém šifrovaném textu tehdy a jen tehdy, když je problém zahrnutí celého čísla do prvočísel neřešitelný.
Zabezpečení typu „všechno nebo nic“ znamená, že po zašifrování textu pomocí určitého algoritmu musí útočník obnovit blok původního textu, jehož velikost je obvykle určena bezpečnostním parametrem kryptosystému. Vzhledem k originálu a šifrovanému textu musí útočník obnovit celý blok soukromého klíče . V tomto případě útočník buď dosáhne úplného úspěchu, nebo nedostane nic. Slovo „nic“ znamená, že útočník nemá žádné tajné informace ani před, ani po neúspěšném útoku.
Rabinův kryptosystém je zcela bezbranný proti útokům založeným na zvoleném šifrovém textu . Útočník zpravidla využívá všech možností, které má. Naváže kontakt s napadeným uživatelem, zašle mu šifrovaný text k následnému dešifrování a požaduje vrácení původního textu.
Například přidáním redundance, jako je opakování posledních 64 bitů, může být kořen jedinečný. Dešifrovací algoritmus v tomto případě vytvoří jediný kořen, který je útočníkovi již znám.
Proces je navíc zranitelný, protože při kódování se používají pouze čtvercové zbytky. V příkladu s n = 77 je použito pouze 23 ze 76 možných stavů.
Viz také
Literatura
- Mao V. Šifrování - asymetrické metody // Moderní kryptografie : Teorie a praxe / přel. D. A. Klyushina - M. : Williams , 2005. - 768 s. — ISBN 978-5-8459-0847-6
- Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .