Šifrování RSA (pojmenovaný z iniciál svých tří vynálezců) je algoritmus z asymetrické kryptografie , široce používané v elektronickém obchodu , a obecněji k výměně důvěrných dat na internetu . Tento algoritmus popsali v roce 1977 Ronald Rivest , Adi Shamir a Leonard Adleman . RSA byla patentována Massachusetts Institute of Technology (MIT) v roce 1983 ve Spojených státech . Platnost patentu vypršela 21. září 2000.
Šifrování RSA je asymetrická : používá dvojici klíčů (celá čísla) se skládá z veřejného klíče k šifrování a soukromý klíč pro dešifrování důvěrných údajů. Oba klíče vytváří osoba, často pojmenovaná podle konvence Alice , která chce, aby mu byla zaslána důvěrná data. Alice zpřístupňuje veřejný klíč. Tento klíč používají jeho korespondenti ( Bob atd.) K šifrování dat, která mu byla odeslána. Soukromý klíč je vyhrazen pro Alici a umožňuje jí dešifrovat tato data. Soukromý klíč může Alice také použít k podepisování dat, která odesílá, veřejný klíč umožňuje kterémukoli z jejích korespondentů ověřit podpis.
Podstatnou podmínkou je, že je „výpočetně nemožné“ dešifrovat pouze pomocí veřejného klíče, zejména rekonstituovat soukromý klíč z veřejného klíče, to znamená, že dostupné způsoby výpočtu a metody známé v době výměna (a čas, který je třeba uchovat v tajnosti) to neumožňují.
Šifrování RSA se často používá ke komunikaci symetrického šifrovacího klíče , což pak umožňuje důvěrné pokračování výměny: Bob pošle Alici symetrický šifrovací klíč, který pak může Alice a Bob použít k výměně dat.
Ronald Rivest, Adi Shamir a Leonard Adleman publikovali své šifrování v roce 1978 v Metodě získávání digitálních podpisů a kryptosystémů veřejného klíče . Používají kongruence na celá čísla a Fermatovu malou větu , aby získali jednosměrné funkce s tajným porušením (nebo zadními vrátky).
Všechny výpočty se provádějí modulo celé číslo n, které je součinem dvou prvočísel . Na Fermat je malý teorém hraje důležitou roli při navrhování šifrování.
Jasné a šifrované zprávy jsou celá čísla menší než celé číslo n . K šifrování a dešifrování se operace ve zvyšování zprávu do určité modulo n energie (to je modulární umocňování operace ).
Pouhý popis matematických principů, na nichž je založen algoritmus RSA, není dostatečný. Jeho praktická implementace vyžaduje zohlednění dalších problémů, které jsou nezbytné pro bezpečnost. Například pár (soukromý klíč, veřejný klíč) musí být generován skutečně náhodným procesem, který, i když je známý, neumožňuje rekonstituci soukromého klíče. Šifrovaná data nesmí být příliš krátká, aby dešifrování skutečně vyžadovalo modulární výpočet a aby byla dokončena vhodným způsobem (například pomocí Optimální asymetrické šifrovací výplně ).
Za krok vytváření klíčů odpovídá Alice. Nezasahuje do každého šifrování, protože klíče lze znovu použít. První obtíž, kterou šifrování nevyřeší, je, že Bob si je docela jistý, že veřejný klíč, který drží, je Alice. K obnově klíčů dojde pouze v případě, že dojde k prolomení soukromého klíče, nebo preventivně po určité době (kterou lze počítat v letech).
Protože e je prvočíslo s φ ( n ), podle věty Bachet-Bézout existují dvě celá čísla d a k taková, že ed = 1 + k φ ( n ), to znamená, že ed ≡ 1 (mod φ ( n ) ): e je skutečně invertibilní modulo φ ( n ).
V celém předchozím odstavci můžeme použít indikátor Carmichaela , který rozděluje φ ( n ) .
Pár ( n , e ) - nebo ( e , n ) - je veřejný klíč šifrování, zatímco jeho soukromý klíč je číslo d , protože ví, že operace dešifrování vyžaduje pouze soukromý klíč d a celé číslo n , známé veřejný klíč (soukromý klíč je někdy také definován jako pár ( d , n ) nebo triplet ( p, q , d )).
Pokud M je přirozené číslo striktně menší než n představující zprávu, zašifrovaná zpráva bude reprezentována
přirozené číslo C je zvoleno přísně menší než n .
Dešifrovat C používáme d , inverzní e modulo ( p - 1) ( q - 1), a najdeme prostý zprávy M o
Příklad s malými prvočísly (v praxi potřebujete velmi velká prvočísla):
Alicin veřejný klíč je ( n , e ) = (33, 3) a její soukromý klíč je ( n , d ) = (33, 7). Bob pošle zprávu Alici.
Mechanismus podpisu Alice pomocí jejího soukromého klíče je analogický výměnou klíčů.
Důkaz je založen na Fermatově malé větě , a to, že jelikož p a q jsou dvě prvočísla, pokud M není násobkem p, máme první rovnost a druhou, pokud nejde o násobek q :
Vskutku
Zlato
což znamená, že existuje celé číslo k takové, že
proto, pokud M není násobkem p podle Fermatovy malé věty
a podobně, pokud M není násobkem q
Dvě rovnosti jsou ve skutečnosti dosaženy pro jakékoli celé číslo M , protože pokud M je násobkem p , M a všechny jeho nenulové síly jsou shodné s 0 modulo p . Podobně pro q .
Celé číslo je tedy násobkem p a q , které jsou zřetelnými prvočísly, tedy jejich součinem pq = n (můžeme to vidět jako důsledek jedinečnosti rozkladu na prvočíselné faktory , nebo přímo z Gaussova lematu , s vědomím, že p a q jsou mezi sebou prvočísla, jsou prvočísla a odlišují se).
Vidíme, že k zašifrování zprávy stačí znát e a n . Na druhou stranu, k dešifrování potřebujeme d a n .
Pro výpočet d s použitím e i n , musíme najít modulární inverze s e modulo ( p - 1) ( q - 1), kterou nemůžeme udělat, aniž by znali celá čísla p a q , to znamená, že rozklad n do prime faktory.
Šifrování proto vyžaduje schopnost ověřit, že „velmi velká“ čísla jsou prvočísla, aby bylo možné najít p a q , ale také to, že součin těchto dvou velmi velkých čísel není prakticky faktorizovatelný. Známé efektivní algoritmy, které umožňují kontrolovat, zda číslo není prvočíslo, ve skutečnosti neposkytují faktorizaci.
Hodnota φ ( n ) Eulerovy indikatury v n je pořadí skupiny invertibilních prvků prstenu ℤ / nℤ . To umožňuje okamžitě vidět, podle Eulerovy věty (důsledek Lagrangeovy věty ), že pokud M je prvočíslo s n , tedy invertibilní (což je případ „většiny“ přirozených celých čísel M přísně menší než n )
nebo ospravedlnit šifrování RSA (pro takové M ).
Ukazuje se, že když n je produktem různých prvočísel, platí rovnost pro všechny M (důkaz je v zásadě ten, který byl proveden výše pro RSA, ve zvláštním případě, kde n je produktem dvou prvočísel).
Dvojice klíčů žádá o výběr dvou prvočísel velké velikosti, takže je výpočetně nemožné rozložit jejich součin.
K určení velkého prvočísla se používá metoda, která na vyžádání poskytuje náhodné liché celé číslo dostatečné velikosti, test primality umožňuje určit, zda je prvočíslo nebo ne, a zastavíme, jakmile se získá prvočíslo . Tyto teorém prvočísla , zajišťuje, že prvočíslo se nalézá po přiměřeném počtu pokusů.
Metoda však vyžaduje velmi rychlý test primality. V praxi se používá pravděpodobnostní test, Miller-Rabinův test primality nebo varianta. Takový test nezaručuje přesně to, že číslo je prvočíslo, ale pouze (velmi) vysoká pravděpodobnost, že je.
Požadované vlastnostiAby nedošlo k narušení bezpečnosti, první dvě čísla a rozhodli postavit dvojici klíčů musí splňovat následující vlastnosti:
Vybraný exponent musí ověřit následující vlastnosti:
Výpočet nelze provést nejprve výpočtem c d , poté zbytkem modulo n , protože by to vyžadovalo zpracování celých čísel, která jsou příliš velká. Existují účinné metody pro výpočet modulární umocňování .
Můžeme si ponechat jinou formu soukromého klíče, abychom umožnili rychlejší dešifrování pomocí věty o čínském zbytku .
Musíme rozlišovat mezi útoky hrubou silou , které spočívají v nalezení p a q pouze na základě znalostí n , a útoky na základě znalostí n, ale také způsobu, jakým byly generovány p a q , z kryptografického použitý software, jedna nebo více zpráv možná zachyceno atd.
Zabezpečení algoritmu RSA proti útokům hrubou silou je založeno na dvou domněnkách:
Je možné, že jeden ze dvou dohadů je nesprávný, nebo obojí. Dosud to, co dělá RSA tak úspěšným, je to, že vědecké komunitě není znám žádný algoritmus, který by provedl útok hrubou silou s konvenčními počítači.
The 2. prosince 2019, největší počet započítaný tímto způsobem, pomocí metody distribuovaného výpočtu, byl dlouhý 795 bitů . Klíče RSA mají obvykle délku 1024 až 2048 bitů. Někteří odborníci se domnívají, že je možné, že v blízké budoucnosti dojde k prolomení 1024bitových klíčů (i když je to kontroverzní ), ale jen málokdo vidí způsob, jak v dohledné budoucnosti takto rozbít 4096bitové klíče. . Lze však předpokládat, že RSA zůstane zabezpečená, pokud je velikost klíče dostatečně velká. Faktorizaci klíče menšího než 256 bitů lze zjistit na osobním počítači během několika minut pomocí volně dostupného softwaru. Pro velikost až 512 bitů a od roku 1999 musí být společně vyrobeno několik stovek počítačů. Z bezpečnostních důvodů se v současné době doporučuje, aby velikost klíčů RSA byla alespoň 2048 bitů.
Pokud má člověk „rychlý“ způsob výpočtu čísla n , byly by zpochybněny všechny šifrovací algoritmy založené na tomto principu, stejně jako všechna data šifrovaná v minulosti pomocí těchto algoritmů.
V roce 1994 byl pro kvantové počítače napsán algoritmus pro factoring čísel v neexponenciálním čase . Toto je Shorův algoritmus . Aplikace kvantových počítačů teoreticky umožňují rozbít RSA hrubou silou, což aktivovalo výzkum na toto téma; ale v současné době tyto počítače generují náhodné chyby, které je činí neúčinnými.
Jiné typy útoků (viz Útoky níže), které jsou mnohem efektivnější, se zaměřují na způsob , jakým byla vygenerována prvočísla p a q, na to, jak bylo vybráno e , zda jsou k dispozici kódované zprávy nebo jakékoli další informace, které lze použitý. Některé z výzkumů na toto téma jsou publikovány, ale nejnovější techniky vyvinuté společnostmi pro dešifrování a zpravodajskými agenturami, jako je NSA, zůstávají pod pokličkou.
Nakonec je třeba poznamenat, že prolomení klíče faktorováním čísla n nevyžaduje čekání na zpřístupnění šifrované zprávy. Tuto operaci lze spustit pouze na základě znalosti veřejného klíče , ke kterému je obecně přístup zdarma. Za těchto podmínek, pokud je započítáno n , je soukromý klíč okamžitě odvozen. Důsledky tohoto pozorování jsou také to, že kód lze rozbít ještě před jeho použitím.
Pokud si chtějí dva lidé důvěrně vyměňovat digitální informace, například na internetu s elektronickým obchodem , musí použít mechanismus pro šifrování těchto digitálních dat. Protože RSA je asymetrický šifrovací algoritmus , dědí rozsah těchto šifrovacích mechanismů. Citujeme:
Ten je ve skutečnosti integrován do mechanismu RSA. Problém se symetrickými algoritmy skutečně spočívá v tom, že si musíte být jisti, že šifrovací klíč je zpřístupněn pouze lidem, kteří chtějí sdílet tajemství. RSA umožňuje bezpečnou komunikaci tohoto symetrického klíče. Za tímto účelem si Alice nejprve vybere symetrický klíč. Chtěla si s Bobem vyměnit tajemství a prostřednictvím RSA mu tento symetrický klíč předá. Za tímto účelem zašifruje symetrický klíč veřejným klíčem Boba (RSA), takže bude jisté, že tento symetrický klíč může dešifrovat pouze Bob. Jakmile Bob zprávu přijme, dešifruje ji a poté může pomocí symetrického klíče nastaveného Alicí posílat šifrované zprávy, které pak může dešifrovat pouze on a Alice.
Bylo navrženo několik útoků k prolomení šifrování RSA.
Útok Wiener (1989), lze využít v případě, že tajný exponent d je menší než . V tomto případě můžeme tajný exponent najít pomocí pokračujícího rozšiřování zlomků .
Útok Håstad , jeden z prvních objevených útoků (v roce 1985), se opírá o možnost, že veřejný exponent e je dostatečně malý. Zachycením stejné zprávy odeslané alespoň různým příjemcům je možné najít původní zprávu pomocí čínské věty o zbytku .
Paul Kocher popsal v roce 1995 nový útok na RSA: za předpokladu, že útočník Eve věděl dost o dokumentech Alice a byl schopen měřit dešifrovací časy několika šifrovaných dokumentů, byla by schopna rychle odvodit dešifrovací klíč. Totéž by platilo pro podpis.
V roce 2003 ukázali Boneh a Brumley praktičtější útok, který umožnil najít faktorizaci RSA na síťovém připojení ( SSL ) tím, že se spoléhal na informace, které mohou některé optimalizace aplikované na čínskou větu zbytku odfiltrovat. Jedním ze způsobů, jak zmařit tyto útoky, je zajistit, aby dešifrovací operace zabrala konstantní dobu. Tento přístup však může výrazně snížit výkon. To je důvod, proč většina implementací (implementována) RSA spíše použít jinou techniku známou pod názvem „kryptografického slepoty“ ( oslepující ).
Slepota využívá multiplikativní vlastnosti RSA vložením náhodné tajné hodnoty do výpočtu, jejíž účinek lze zrušit. Tato hodnota je odlišná pro každé šifrování, doba dešifrování již přímo nekoreluje s daty, která mají být šifrována, což znemožňuje útok načasování: místo výpočtu si Alice nejprve vybere tajnou náhodnou hodnotu r a vypočítá . Výsledkem tohoto výpočtu je, a proto lze účinek r zrušit vynásobením jeho inverzní funkce.
Jak je popsáno v tomto článku, RSA je deterministická šifra, a proto nemůže být sémanticky bezpečná . Protiopatření je použití pravděpodobnostního výplňového schématu takovým způsobem, že žádná hodnota zprávy, jakmile je zašifrována, neposkytuje nezabezpečený výsledek, například pokud C = M e ≤ N , jednoduchý útok je výpočet přímo z e-tého kořene C, který nebude snížen modulo N.
V roce 1998 Daniel Bleichenbacher popsal první praktický útok „adaptabilní vybrané šifry“ proti zprávám RSA. Kvůli chybám v polstrovacím schématu PKCS # 1 v1 bylo možné obnovit klíče relace SSL . Na základě této práce kryptografové nyní doporučují použití formálně bezpečných metod plnění , jako jsou OAEP a RSA Laboratories, vydaly nové verze PKCS # 1, které jsou vůči těmto útokům odolné.