Wikipedista:Zagothal/TEMP

Název tohoto článku není z technických důvodů zcela správný. Správný název by měl být RSA.

__NOTOC__

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

PrincipEditovat

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 n = pq je tedy v rozumném čase prakticky nemožné zjistit činitele p a q, neboť není znám žádný algoritmus faktorizace, který by pracoval v polynomiálním čase vůči velikosti binárního zápisu čísla n. Naproti tomu násobení dvou velkých čísel je elementární úloha.

Popis činnosti algoritmuEditovat

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áruEditovat

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)).
  6. Jestli e je prvočíslo tak d = (1+r*φ(n))/e, kde r = [(e-1)φ(n)^(e-2)]

Veřejným klíčem je dvojice (n, e), přičemž n se označuje jako modul, e jako šifrovací či veřejný exponent. Soukromým klíčem je dvojice (n, d), kde d 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 nepokrytě pošle Bobovi. Soukromý klíč naopak uchová v tajnosti.

Zašifrování zprávyEditovat

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 = me mod n

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

Dešifrování zprávyEditovat

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

m = cd mod n.

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

cd ≡ (me)dmed (mod n).

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

medm (mod p)

a zároveň

medm (mod q)

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

medm (mod pq).

Tudíž

cdm mod n.

PříkladEditovat

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) = 12317 mod 3233 = 855

Pro dešifrování pak:

dešifruj(855) = 8552753 mod 3233 = 123

Digitální podpisEditovat

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 ho zašifrovala Alice.


{{upravit část}} {{Přeložit/dne|20100910192223}}

Vyplňovací schémataEditovat

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

  • Hodnoty m = 0 nebo m = 1 vždy produkují šifrovaný text rovný 0 nebo 1.
  • Když je použito šifrování s malým exponentem (např. e = 3) a malé hodnoty m, výsledek   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, mohou být všechny ASCII znakové zprávy málo bezpečné, jelikož m může nabývat nejvýše hodnoty 255 a 2553 je méně než snesitelný modul. Takové texty mohou být obnoveny jednoduše použitím umocňování a odmocňování.

K zabránění těchto problémů v sobě praktické implementace RSA 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).

HistorieEditovat

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.

BezpečnostEditovat

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ému. Plné dešifrování RSA šifrovaného textu je obtížné v podstatě neproveditelné, jelikož neznáme algoritmus, pomocí nějž by se to dalo provést v přijatelně krátkém čase. 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 me=c mod n, kde (e, n) jsou RSA veřejné klíče a c je RSA šifrovaný text. V současnosti nejslibnější přístup k vyřešení RSA problému je faktor modulu n. Se schopností obnovit primární faktory může útočník spočítat tajný exponent d z veřejného klíče (e, n), a 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 polynomiálně časově složitá metoda pro faktory celých velkých čísel na klasických počítačích, ale nebylo dokázána, že by to nešlo.

V roce 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 softwaru . 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 roce 1993 publikoval Peter Shor Shorův algoritmus, který ukazoval, že by kvantový počítač mohl v principu vykonávat faktorizaci v polynomiálním čase, což by učinilo RSA a příbuzné algoritmy zastaralými. Realizace principů kvantového počítání se však v současnosti potýká s takovými praktickými problémy, že se o bezpečnost zašifrovaných dat zatím není třeba bát.

Viz též : RSA Factoring Challenge

Praktické pokynyEditovat

Generování klíčůEditovat

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á', aby Fermatova faktorizace pro n nebyla úspěšná. Dále , jestliže p-1 nebo q-1 se rozkládá pouze na malá prvočísla, n může být rychle faktorizováno 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ěme si obou požadavků 'náhodný' a 'nepředvídatelný'. Tato kritéria nejsou totožná; čí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 mohla být dostatečně náhodná, publikoval Rand Corp v r. 1950, ale právě tato publikace může sloužit jako návod 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 < n1/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í.

RychlostEditovat

RSA a obecně celé asymetrické šifrování je o dost pomalejší než symetrická kryptografie. V praxi se pro běžnou zabezpečenou komunikaci většinou asymetrické šifrování používá pouze k výměně klíče symetrického a komunikace se pak šifruje symetricky.

Takovýto postup klade další nároky na zabezpečení celého procesu. Například je důležité použít dobrý generátor náhodných čísel pro symetrický klíč, protože jinak by mohla Eva vynechat RSA a odhadnout symetrický klíč.

Distribuce klíčůEditovat

Pro bezpečnost, tak jako u všech šifer, je důležité jak si uživatelé předají klíče. Distribuce klíčů musí být zabezpečena před třetí osobou (man-in-the-middle attack). Dejme tomu, že Eva (třetí osoba) zná nějaký způsob jak podstrčit Bobovi svůj klíč a navléknout vše tak, aby si Bob myslel, že tento klíč patří Alici. Předpokládejme dále, že Eva je napíchnutá na přenosy mezi Alicí a Bobem. Eva pošle Bobovi svůj veřejný klíč, Bob věří že jde o Alici. Eva pak může zachytit jakýkoliv šifrovaný text poslaný Bobem, dešifrovat zprávu podstrčený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.

== Útok

Časované útokyEditovat

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 Sockets 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 cd mod n, nejprve si vybere náhodnou tajnou hodnotu r a vypočítá (rec)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.

Útok pomocí měnícího se textuEditovat

V 1998, Daniel Bleichenbacher popisoval první praktický Útok 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 je Optimá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.

Související článkyEditovat

ReferenceEditovat

Externí odkazyEditovat

[[Kategorie:Kryptografické algoritmy]] [[ar:خوارزمية آر إس إيه]] [[bg:RSA]] [[ca:RSA]] [[da:RSA]] [[de:RSA-Kryptosystem]] [[el:RSA]] [[en:RSA]] [[eo:RSA]] [[es:RSA]] [[et:RSA (algoritm)]] [[eu:RSA]] [[fa:آراس‌ای]] [[fi:RSA]] [[fr:Rivest Shamir Adleman]] [[gl:RSA]] [[he:RSA]] [[hr:RSA]] [[hu:RSA-eljárás]] [[id:RSA]] [[is:RSA]] [[it:RSA]] [[ja:RSA暗号]] [[ka:RSA ალგორითმი]] [[ko:RSA 암호]] [[lt:RSA]] [[lv:RSA šifrēšanas algoritms]] [[nl:RSA (cryptografie)]] [[no:RSA]] [[pl:RSA (kryptografia)]] [[pt:RSA]] [[ro:RSA]] [[ru:RSA]] [[simple:RSA]] [[sl:RSA]] [[sr:RSA]] [[sv:RSA]] [[th:RSA]] [[tr:RSA]] [[uk:RSA]] [[vi:RSA (mã hóa)]] [[zh:RSA加密演算法]] [[Kategorie:Neindexované stránky]]