RSA

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

Princip

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

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)).
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á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.

Dešifrování zprávy

Alice od Boba získá šifrovaný 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.

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; q = 53 (dvě náhodná prvočísla, soukromá)
• n = pq = 3233 (modul, veřejný)
• e = 17 (veřejný, šifrovací exponent - číslo menší a nesoudělné s φ(n)=60×52=3120)
• d = 2753 (soukromý, dešifrovací exponent - tak aby de ≡ 1 (mod φ(n)))

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

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

Související články

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

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 0-262-03293-7. Section 31.7: The RSA public-key cryptosystem, pp.881–887.

Externí odkazy

• Standard PKCS #1 – RSA Cryptography Standard