RSA

algoritmus kryptografie s veřejným klíčem (algoritmus asymetrické kryptografie)
Možná hledáte: Jihoafrická republika.

RSA (iniciály autorů Rivest, Shamir, Adleman) je šifra s veřejným klíčem, jedná se o první algoritmus, který je vhodný jak pro podepisování, tak šifrování. Používá se i dnes, přičemž při dostatečné délce klíče je považován za bezpečný.

Adi Šamir (2009), jeden ze tří spoluautorů algoritmu RSA

Princip

editovat

Bezpečnost RSA je postavena na předpokladu, že rozložit velké číslo na součin prvočísel (faktorizace) je velmi obtížná úloha. Z čísla   je tedy v rozumném čase prakticky nemožné zjistit činitele   a  , neboť není znám žádný algoritmus faktorizace, který by pracoval v polynomiálním čase vůči velikosti binárního zápisu čísla  . Naproti tomu násobení dvou velkých čísel je elementární úloha.

Popis činnosti algoritmu

editovat

Alice a Bob chtějí komunikovat prostřednictvím otevřeného (nezabezpečeného) kanálu a Bob by chtěl Alici poslat soukromou zprávu.

Tvorba klíčového páru

editovat

Nejprve si bude Alice muset vyrobit pár veřejného a soukromého klíče:

  1. Zvolí dvě různá velká náhodná prvočísla   a  .
  2. Spočítá jejich součin  .
  3. Spočítá hodnotu Eulerovy funkce  .
  4. Zvolí celé číslo   menší než  , které je s   nesoudělné.
  5. Nalezne číslo   tak, aby platilo  , kde symbol   značí kongruenci zbytkových tříd.
  6. Jestli   je prvočíslo, tak  , kde  

Veřejným klíčem je dvojice  , přičemž   se označuje jako modul,   jako šifrovací či veřejný exponent. Soukromým klíčem je dvojice  , kde   se označuje jako dešifrovací či soukromý exponent. V praxi se klíče uchovávají v mírně upravené formě, která umožňuje rychlejší zpracování. Veřejný klíč poté Alice uveřejní, respektive zcela otevřeně pošle Bobovi. Soukromý klíč naopak uchová v tajnosti.

V bodě 5 je použit rozšířený Eukleidův algoritmus na   a  , čímž nalezneme   a   do rovnice  .

Zašifrování zprávy

editovat

Bob nyní chce Alici zaslat zprávu  . Tuto zprávu převede nějakým dohodnutým postupem na číslo   ( ). Šifrovým textem odpovídajícím této zprávě pak je číslo

 

Tento šifrový text poté zašle nezabezpečeným kanálem Alici.

Dešifrování zprávy

editovat

Alice od Boba získá šifrovaný text  . Původní zprávu   získá následujícím výpočtem:

 

Fakt, že je výsledek tohoto výpočtu původní zprávou, je důsledek následující rovnosti:

 

A jelikož   a  , díky malé Fermatově větě platí, že

 

a zároveň

 

Jelikož   a   jsou různá prvočísla, pomocí čínské věty o zbytcích je dáno

 

Tudíž

 

Hodnoty   ani   se při dešifrování nepočítají, slouží pouze pro důkaz správnosti dešifrování spolu s čínskou větou o zbytcích. Kongruence platí i pro   .

Příklad

editovat

V tomto příkladu jsou pro jednoduchost použita extrémně malá čísla, v praxi se používají o mnoho řádů větší.

  •  ;   (dvě náhodná prvočísla, soukromá)
  •   (modul, veřejný)
  •   (veřejný, šifrovací exponent – číslo menší a nesoudělné s  )
  •   (soukromý, dešifrovací exponent – tak aby  )

Pro zašifrování zprávy 123 probíhá výpočet:

 

Pro dešifrování pak:

 

Útoky proti RSA

editovat
  • Pokud je pro šifrování použita nízká hodnota exponentu   (např.  ) a nízké hodnoty   je výsledek   nižší než  . V tomto případě může být dešifrovaná hodnota (například text rezprezentovaný číselně) získána jako  -tá odmocnina zašifrované hodnoty (textu).
  • Pokud je stejná nezašifrovaná zpráva po zašifrování poslána   nebo více příjemcům a příjemci mají stejné  , ale jiné  ,  , a tím pádem i  , potom je možné původní zprávu snadno dešifrovat pomocí Čínské věty o zbytcích. Johan Hastad zjistil, že tento útok je možný i v případě, že zprávy nejsou stejné, ale útočník zná lineární vztah mezi nimi. Tento útok byl dále vylepšen Donem Coppersmithem.
  • Protože šifra RSA je deterministický šifrovací algoritmus (tj. nemá žádnou náhodnou část) útočník může zkusit generovat pravděpodobný text zprávy, následně jej zašifruje pomocí veřejného klíče a porovná jej se zašifrovaným textem. Šifra je nazývána sémanticky bezpečnou, pokud útočník není schopen rozlišit od sebe dva zašifrované texty i když zná (nebo zkouší) původní text. Šifra RSA bez náhodného doplnění není sémanticky bezpečná.
  • Vlastností RSA je, že násobek dvou zašifrovaných hodnot (textů) je roven zašifrování násobku dvou jejich původních hodnot (textů). Tedy  . Kvůli této vlastnosti je možný útok pomocí luštění se znalostí vybraných původních hodnot (textů). Tj. útočník, který chce zjistit obsah zašifrovaného textu   může požádat držitele soukromého klíče aby odšifroval nevině vypadající zašifrovaný text   pro nějakou hodnotu   vybranou útočníkem. Kvůli této vlastnosti   je zašifrování  . Tedy pokud je útočník při tomto útoku úspěšný, dozví se  , z čehož může odvodit zprávu   násobením   modulární inverzí   modulo  .
  • Pseudonáhodná čísla nejsou náhodná. Ovlivněním generátoru pseudonáhodných čísel lze dosáhnout prolomení.[zdroj?]

Schéma doplnění

editovat

Aby se předešlo problémům, tak se v praktické implementaci RSA používají nějaké strukturované náhodné posunutí hodnoty   než je zašifrována. Toto posunutí zaručuje, že   nebude spadat do rozsahu nebezpečných původních textů, a že se daná zpráva po posunutí zašifruje do různých možných zašifrovaných textů.

Standardy jako PKCS#1 byly pečlivě navrženy, aby bezpečně posunuly zprávu před RSA zašifrováním. Protože tato schémata posunují nezašifrovaný text   nějakým množstvím přidaných bitů, velikost neposunuté zprávy   musí být o tolik menší. Schémata pro RSA posunutí musí být pečlivě navržena, aby zabránila sofistikovaným útokům, které by mohly být založené na předvídatelné struktuře zprávy. Rané verze standardu PKCS#1 (do verze 1.5) užívaly konstrukci, která vypadala jako sémanticky bezpečná, ale na Eurokriptu 2000 Coron et al. ukázal, že pro některé typy zpráv toto doplnění neposkytuje dostatečnou úroveň zabezpečení. Navíc na Crypto 1998 Bleichenbacher ukázal, že tato verze je náchylná k praktickému adaptivnímu útoku se znalostí vybraných otevřených textů. Pozdější verze používají Optimal Asymmetric Encryption Padding (OAEP), aby předešly tomuto typu útoku. Z toho důvodu by OAEP mělo být použito ve všech nových aplikacích a PKCS#1 v1.5 doplňování by mělo být nahrazeno kdekoli je to možné. PKCS#1 standard také obsahuje schémata navržená tak, aby poskytovala dodatečnou bezpečnost pro RSA podpisy.

Vygenerování chybného klíče

editovat

Hledání velkých prvočísel   a   se provádí testováním náhodných čísel správné velikosti pomocí Testů prvočíselnosti (např. Millerův-Rabinův), které rychle eliminují prakticky všechna neprvočísla.

Čísla   a   by neměla být „příliš blízko“, jinak je Fermatova faktorizace pro   úspěšná, pokud  , například je méně než   (což i pro malé 1024bitové hodnoty   je  ) řešení pro    je triviální. Navíc, pokud   nebo   jsou násobky pouze malých prvočísel,   může být rychle rozloženo Pollardovým   algoritmem, a tyto hodnoty   nebo   by tedy neměly být použity. Nejsou známy žádné útoky proti malé hodnotě veřejného exponentu jako např.  , pokud je použito správné doplnění. Ale pokud doplnění použito není nebo je špatně implementováno, malý veřejný exponent způsobuje větší riziko. Běžně používaná hodnota   je 65537, což je považováno za kompromis mezi ochranou proti potenciálnímu útoku proti malému exponentu a efektivitou šifrování (nebo podpisu).

Digitální podpis

editovat

Algoritmus RSA lze snadno využít pro digitální podpis. Základním principem takového využití je „opačné“ použití šifry – pokud Alice chce poslat Bobovi podepsanou zprávu, připojí k ní číslo získané „dešifrováním“ haše své zprávy pomocí svého soukromého klíče. Bob poté jakoby zpětně „zašifruje“ tento podpis pomocí Alicina veřejného klíče a porovná výsledek s hašem zprávy. Pokud zpráva nebyla změněna, vyjde stejná hodnota, neboť algoritmus je z hlediska šifrování i dešifrování symetrický (lze zaměnit   a  ). Jelikož jediný, kdo zná tajný klíč Alice, je Alice, je tím zaručeno, že ho zašifrovala Alice.

Reference

editovat


Literatura

editovat

Související články

editovat

Externí odkazy

editovat