RSA

Z Wikipedie, otevřené encyklopedie

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ý.

Obsah 1 Princip 2 Popis činnosti algoritmu 2.1 Tvorba klíčového páru 2.2 Zašifrování zprávy 2.3 Dešifrování zprávy 2.4 Příklad 2.5 Digitální podpis 2.6 Vyplňovací schémata 3 Historie 4 Bezpečnost 5 Praktické pokyny 5.1 Generování klíčů 5.2 Rychlost 5.3 Distribuce klíčů 5.4 Časované útoky 5.5 Útoky pomocí měnícího se textu 6 Podívejte se také na 7 Reference 8 Externí odkazy

[editovat] Princip

Bezpečnost RSA je postavena na předpokladu, že rozložit číslo na součin prvočísel (faktorizace) je velmi obtížná úloha. Z čísla n = pq je tedy v rozumném čase prakticky nemožné zjistit činitele p a q.

[editovat] Popis činnosti algoritmu

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.

[editovat] Tvorba klíčového páru

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 p a q.
2. Spočítá jejich součin n = pq.
3. Spočítá hodnotu Eulerovy funkce φ(n) = (p − 1)(q − 1).
4. Zvolí celé číslo e menší než φ(n), které je s φ(n) nesoudělné.
5. Nalezne číslo d tak, aby platilo de ≡ 1 (mod φ(n)).

Veřejným klíčem je dvojice (n, e), přičemž n se označuje jako modul, e jako (šifrovací, příp. 'veřejný' exponent) exponent. Soukromým klíčem je dvojice (n, d), kde d se označuje jako dešifrovací či soukromý. (V praxi se klíče uchovávají v mírně upravené formě, která umožňují rychlejší zpracování.)

Veřejný klíč poté Alice uveřejní, respektive zcela nepokrytě pošle Bobovi. Soukromý klíč naopak uchová v tajnosti.

[editovat] Zašifrování zprávy

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

c = m^e mod n

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

[editovat] Dešifrování zprávy

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

m = c^d mod n.

Fakt, že tímto výpočtem získáme původní zprávu, je důsledkem následující rovnosti:

c^d ≡ (m^e)^d ≡ m^ed (mod n).

A jelikož ed ≡ 1 (mod p − 1) a ed ≡ 1 (mod q − 1), díky malé Fermatově větě platí, že

m^ed ≡ m (mod p)

a zároveň

m^ed ≡ m (mod q)

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

m^ed ≡ m (mod pq).

Tudíž

c^d ≡ m mod n.

[editovat] Příklad

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

• p = 61 (první prvočíslo)
• q = 53 (druhé prvočíslo)
• n = pq = 3233 (modul, veřejný)
• e = 17 (veřejný, šifrovací exponent)
• d = 2753 (soukromý, dešifrovací exponent)

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

šifruj(123) = 123¹⁷ mod 3233 = 855

Pro dešifrování pak:

dešifruj(855) = 855²⁷⁵³ mod 3233 = 123

[editovat] Digitální podpis

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é jakoby „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 e a d). Jelikož jediný, kdo zná tajný klíč Alice, je Alice, je tím zaručeno, že haš zašifrovala Alice.

---

[editovat] Vyplňovací schémata

V praxi se musí RSA kombinovat s nějakým typem tzv padding scheme – vyplňovacího schématu, jelikož hodnoty M způsobují ztrátu bezpečnosti šifrovaného textu RSA použité bez v.s. může trpět množstvím potenciálních potíží :

• Hodnoty m = 0 nebo m = vždy produkují šifrovaný text rovný 0 nebo 1, z důvodů možnosti exponentování.

• Když je použito šifrování s malým exponentem (e.g., e = 3) a malé hodnoty m, výsledek m^e může být podstatně nižší než n. V tomto případě šifrované texty mohou být snadno dešifrovány použitím e- kořenu šifrovaného textu bez nutnosti vyžadování znalosti modulu.

• Jelikož je RSA deterministický šifrovací algoritmus, nemá žádné proměnné komponenty. Útočník může snadno použít útok nešifrovaným textem za pomocí slovníku a porovnáváním jednotlivých částí šifrovaného textu s ním.

V praxi mohou první dva problémy nastat hlavně při posílání krátkých ASCII zpráv, kde m je řetězec jednoho nebo více ASCII znaků. Zpráva obsahující ASCII znak NUL (kterého numerická hodnota je 0) může být dekódována jako m = 0, což produkuje šifrovaný text jako nuly, bez ohledu na to, jaké e a N je použito. Rovněž ASCII znak SOH (numerická hodnota je 1) vždy vyprodukuje šifrovaný text jedniček V systémech, které používají malé hodnoty e jako třeba 3, všechny ASCII znakové zprávy mohou být málo bezpečné., jelikož největší hodnota m = 255, a 255³ je méně než snesitelný modul. Takové texty mohou být obnoveny jednoduše použitím umocňování / odmocňování.

K zabránění těchto problémů, praktické implementace RSA v sobě obvykle skrývají některý typ náhodného vyplnění hodnoty m před jejím zašifrováním. Vyplnění způsobí, že m nemůže klesnout na nebezpečnou hodnotu a takto získaná „zaplněná“ zpráva bude zašifrována do nějaké vysoké hodnoty šifrovaného textu. Navíc to pomůže snížit možnost útoku pomocí porovnávání se slovníkem.

Standardy jako PKCS byly vytvořeny k bezpečnému vyplnění zpráv před jejich zašifrováním pomocí RSA. Jelikož tato schémata zaplní nešifrovaný text m určitým počtem dodatečných znaků, musí být velikost nevyplněné zprávy M o něco menší. RSA vyplňovací schémata musí být opatrně navržena k tomu, aby zabránila i velmi sofistikovaným útokům usnadněným rovněž předvídatelnou strukturou zprávy. První verze PKCS používaly ad-hoc strukturu, která se později ukázala jako nedostatečně účinná proti útoku pomocí srovnávání šifrovaného textu se slovníkem. Moderní konstrukce používají bezpečnostní techniky jako Optimální Asymetrické Šifrovací Vyplňování (OAEP) k ochraně zpráv proti tomuto typu útoku. PKCS standard rovněž začleňuje zpracovávací schémata k poskytnutí bezpečnosti pro RSA podpisy, např. jako (RSA-PSS).

[editovat] Historie

Algoritmus popsali v roce 1977 Ron Rivest, Adi Shamir a Len Adleman v MIT; písmena RSA jsou iniciály jejich příjmení.

Clifford Cocks, britský matematik pracující pro GCHQ, popsal ekvivalentní systém ve svém interním dokumentu v roce 1973. Z důvodu nutnosti použití relativně drahé výpočetní techniky pro uvedení algoritmu do praxe, nebyl jeho systém v podstatě uznán jako veřejně použitelný. Jeho výzkum nebyl navíc až do roku 1997 prozrazen z důvodu označení jako „přísně tajné“.

Algoritmus byl v USA v roce 1983 patentován jako patent č. 4,405,829. Patent vypršel 21. září 2000. Protože algoritmus byl podán dříve než byl publikovaný, tak nařízení zabraňovalo patentování jinde ve světě. Cocksova práce byla veřejně známá a patent by nebyl možný ani v USA.

[editovat] Bezpečnost

Bezpečnost šifrovacího systému RSA je založena na dvou matematických problémech: problém faktorizace velmi vysokých čísel a RSA problém. Plné dešifrování RSA šifrovaného textu je obtížné v podstatě neproveditelné, jelikož neexistuje žádný známý algoritmus, pomocí nějž by se to dalo provést. Odolnost vůči částečnému dešifrování zprávy může vyžadovat použití některého ze známých způsobů vyplňování.

RSA problém je definován jako úloha získání e-tého kořenu modulu množiny n , obnovení hodnoty m jako m^e=c mod n, kde (e, n) jsou RSA veřejné klíče a c je RSA šifrovaný text. Nyní nejslibnější přístup k vyřešení RSA problému je faktor modulu n. Se schopností obnovit primární faktory, útočník může spočítat tajný exponent d z veřejného klíče (e, n), pak dešifrovat c použitím standardního postupu. Útočník tohoto dosáhne faktorem n do p a q, a vypočítá (p-1)(q-1) a to umožní stanovení d pro e. Nebyla nalezena polynomial-time metoda pro faktory celých velkých čísel na klasických počítačích, ale nebylo dokázané že neexistuje. Prohlédněte si integer factorization pro diskuzi o tomto problému.

V r. 2005, největší číslo faktoru univerzálními metodami bylo 663 bitů dlouhé, použitím distribučních metod. RSA klíče jsou typicky dlouhé 1024 – 2048 bitů. Někteří experti věří že klíče 1024 bitů se mohou v blízké době stát prolomitelnými (ačkoli toto je sporné), ale není žádná známa cesta která by mohla v nejbližší budoucnosti prolomit klíč 4096 bitů dlouhý. Proto, se obecně předpokládá, že RSA je bezpečný jestliže n je dostatečně velké. Jestliže n je 256 bitů nebo kratší, může být za pár hodin faktorizován na osobním počítači, za použití volně dostupného softvéru . Jestliže n je 512 bitů nebo kratší, může být faktorizován několika sty počítačů od r.1999. Teoretické hardwarové zařízení pojmenované TWIRL a popsané Shamirem a Tromerem v r. 2003 vyvolal otázku na bezpečnost 1024 bitového klíče. V současné době je doporučováno aby n bylo alespoň 2048 bitů dlouhé.

V 1993, Peter Shor publikoval Shor's algoritmus, který ukazoval že by kvantový počítač mohl v principu vykonávat faktorizaci v polynomiálním čase, což dělá RSA a příbuzné algoritmy zastaralými. Nicméně, neočekáváme, že solidní kvantové výpočty budou vyvinuty v nejbližší době.

Viz též : RSA Factoring Challenge

[editovat] Praktické pokyny

[editovat] Generování klíčů

K nalezení velkých prvočísel p a q obyčejně vezmeme náhodná čísla správné velikosti a to, zda jsou s velkou pravděpodobností prvočísly, otestujeme za pomoci testu prvočíselnosti.

p a q by neměla být 'příliš blízká', pro případ že Fermat faktorizace pron bude úspěšná. Dále , jestliže p-1 nebo q-1 má pouze malé prvotní faktory, n může být faktorizován rychle a proto by hodnoty p nebo q měly být vyřazeny.

Člověk by neměl použít primární vyhledávací metodu, která dá nějaké informace útočníkovi. Prakticky, pro začátek potřebujeme použít dobrý generátor náhodných čísel. Všimněte si obou požadavků 'náhodný ' a 'nepředvídatelný'. Toto nejsou stejná kritéria; číslo může být vybráno náhodným procesem (žádný model výsledku), ale i to je nějakým způsobem předvídatelné, použitá metoda bude mít za následek ztrátu bezpečnosti. Například, přehled čísel které by dost dobře mohly byt náhodný publikoval Rand Corp v r. 1950, ale bylo to publikované a tak to může sloužit k útokům. Jestliže útočník může odhadnout polovinu čísel p nebo q, může rychle vypočítat druhou polovinu (to ukázal Coppersmith v r. 1997).

Je důležité, aby tajný klíč d byl dost velký. Wiener ukázal v r. 1990 že jestli je p mezi q a 2q (která je úplně typické) a d < n^1/4/3, pak d může být účinně vypočítáno z n a e.Není žádný známý útok proti malému veřejnému exponentu jako například e=3, za předpokladu že je použita správná výplň. Avšak, když žádná výplň použitá není nebo když výplň je nevhodná, potom nástroj s malým veřejným exponentem má větší riziko útoku, tak jako například rozbalit bezbranný holý text. 65537 je běžně používaná hodnota pro e. Tato hodnota může být považován za kompromis mezi potenciálními útoky na malý exponent a stále účinnému šifrování (či podpisovému ověřování). NIST návrh FIPS PUB 186-3 (Březen 2006) nedovoluje dělat veřejné exponenty e menší než 65537, ale neuvádí důvod pro toto omezení.

[editovat] Rychlost

RSA je o hodně pomalejší než DES a symmetric cryptosystems. V praxi, Bob typicky zašifruje tajnou zprávu symetrickým algoritmem, šifrování (poměrně krátké) pro symetrický klíč s RSA,a přenese oba RSA- symetricky šifrované klíče a symetricky -šifrovanou zprávu Alici.

Tato procedura zvýší další bezpečnostní záležitosti. Například, je to důležité k použití silného generátoru náhodných čísel pro symetrický klíč, protože jinak by mohla Eva vynechat RSA, odhadnout symetrický klíč.

[editovat] Distribuce klíčů

Pro bezpečnost je důležité, jak jsou rozděleny veřejné klíče RSA u všech šifer. Distribuce klíčů musí být zabezpečena pro případ man-in-the-middle útoku. Předpoklad Eva má nějaký způsob jak dát Bobovi libovolný klíč a přinutit jej věřit, že patří Alici. Předpoklad že Eva může zachytit přenosy mezi Alicí a Bobem. Eva pošle Bobovi její veřejný klíč, Bob věří že je Alice. Eva pak může zachytit jakýkoliv šifrovaný text poslaný Bobovi, dešifrovat zprávu s jejím klíčem, získat kopii zprávy, zašifrovat zprávu veřejným klíčem Alice, a poslat nový šifrovaný text k Alici. V principu, Alice ani Bob by nebyli schopni odhalit přítomnost Evy. Obrana proti takovým útokům je často založena na elektronickém podpisu.

[editovat] Časované útoky

Kocher popsal nový útok na RSA v 1995: Jestliže útočník Eva zná dostatečně hardware Alice a je schopna změřit dešifrovací časy na několika známých šifrovaných textech, může odvodit klíč dešifrování d rychle. Tento útok může také být aplikován proti RSA podpisovému schématu. V 2003, Boneh a Brumley demonstrovali praktický útok schopný obnovovat RSA faktorizací přes síťové připojení (např., do Secure Socket Layer (SSL) - umožnil webserver). Tento útok využívá informací poskytnutými čínskou větou o zbytcích, optimalizace používané mnoha RSA implementacemi.

Jeden způsob, jak zmařit tyto útoky - musíme zajistit, že operace dešifrování vezme konstantní množství času na každý šifrovaný text. Nicméně, tento přístup může významně redukovat výkon. Místo toho, RSA nejvíce používají implementace střídavou techniku známou jako šifrovací oslepení (blinding). RSA oslepování využívat multiplikativní vlastnost RSA. Místo toho, aby Alice vypočítala c^d mod n, nejprve si vybere náhodnou tajnou hodnotu r a vypočítá (r^ec)^d mod n. Výsledek tohoto výpočtu je rm mod n a účinek r pak může být odstraněn násobením jeho inverzní. Nová hodnota r je vybrána pro každý šifrovaný text. S použitým oslepení je již rozluštění času nezávislé na hodnotě vstupního šifrovaného textu, a proto časovaný útok selže.

[editovat] Útoky pomocí měnícího se textu

V 1998, Daniel Bleichenbacher popisoval první praktický Útoky pomocí měnícího se textu, proti RSA- používají zašifrované zprávy PKCS #1 v1 padding scheme (náhodné výplňové schéma přidá strukturu k RSA- zašifrované zprávy, tak je možné stanovit zda dešifrovaná zpráva je platná.) kvůli nedostatkům ve schématu PKCS #1 , Bleichenbacher byl schopný připravit praktický útok proti RSA implementacím (protokolu bezpečné zásuvné vrstvy) a obnově klíče. V důsledku této práce cryptographers nyní pravděpodobně doporučí použití bezpečných vyplňovacích schémat takových jako jeOptimální asymetrická šifrovací výplň (Optimal Asymmetric Encryption Padding) a RSA laboratoře vydaly nové verze PKCS #1 které nejsou bezbrané vůči těmto útokům.

[editovat] Podívejte se také na

• Hašovací funkce
• Generátor pseudonáhodných čísel
• Symetrická kryptografie
• Random seed
• SSL
• SSH

[editovat] Reference

• R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120–126. 1978. Previously released as an MIT „Technical Memo“ in April 1977. Initial publication of the RSA scheme.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 31.7: The RSA public-key cryptosystem, pp.881–887.

[editovat] Externí odkazy

• Standard PKCS #1 – RSA Cryptography Standard