RSA
RSA je asymetrický kryptografický algoritmus, takže pracuje se dvěma klíči:
* veřejný klíč se může komukoli ukázat a používá se k šifrování nebo ověřování podpisu
* soukromý klíč musí zůstat tajný a používá se k dešifrování nebo vytváření podpisu
1. Základní myšlenka RSA
* RSA stojí na tom, že je snadné vynásobit dvě velká prvočísla, ale je extrémně těžké z výsledného součinu zjistit, která prvočísla to byla
* například:
* p = 61
* q = 53
* n = p * q = 3233
* když známe p a q, snadno spočítáme n
* kdyby ale n bylo obrovské číslo s tisíci bity, rozložit ho zpět na p a q by bylo výpočetně velmi těžké
2. Generace klíčů
* nejprve si zvolíme dvě velká náhodná prvočísla:
* p a q
* potom spočítáme jejich součin:
* n = p * q
* číslo n se používá v obou klíčích
* říká se mu modulus
* dále spočítáme Eulerovu funkci:
* φ(n) = (p - 1)(q - 1)
* tato hodnota je důležitá pro konstrukci veřejného a soukromého exponentu
* poté vybereme číslo e, kterému se říká veřejný exponent
* musí platit, že e je nesoudělné s φ(n), tedy:
* gcd(e, φ(n)) = 1
* v praxi se často používá:
* e = 65537
* nakonec se vypočítá soukromý exponent d, který je inverzí čísla e modulo φ(n):
* d * e ≡ 1 mod φ(n)
* to znamená, že když vynásobíme d a e, výsledek dá po dělení φ(n) zbytek 1
* výsledkem jsou dva klíče:
* veřejný klíč: (n, e)
* soukromý klíč: (n, d)
* hodnoty p, q a φ(n) se musí uchovat v tajnosti nebo bezpečně smazat
3. Šifrování
* zprávu si nejprve převedeme na číslo m
* musí platit:
* 0 < m < n
* šifrování se provede pomocí veřejného klíče (n, e):
* c = m^e mod n
* kde:
* m = původní zpráva jako číslo
* e = veřejný exponent
* n = modulus
* c = zašifrovaný text
* výsledek c je šifrovaná zpráva
4. Dešifrování
* příjemce použije soukromý klíč (n, d) a vypočítá:
* m = c^d mod n
* tím získá původní zprávu m
* funguje to proto, že čísla e a d jsou matematicky propojená tak, aby se operace umocnění na e dala vrátit pomocí umocnění na d v modulu n
5. Malý číselný příklad
* zvolíme malá prvočísla:
* p = 61
* q = 53
* spočítáme:
* n = 61 * 53 = 3233
* Eulerova funkce:
* φ(n) = 60 * 52 = 3120
* zvolíme veřejný exponent:
* e = 17
* najdeme soukromý exponent d, aby platilo:
* 17 * d ≡ 1 mod 3120
* vyjde:
* d = 2753
* takže:
* veřejný klíč: (3233, 17)
* soukromý klíč: (3233, 2753)
* teď chceme zašifrovat zprávu:
* m = 65
* šifrování:
* c = 65^17 mod 3233
* c = 2790
* dešifrování:
* m = 2790^2753 mod 3233
* m = 65
* dostali jsme zpět původní zprávu
6. Proč útočník neumí snadno dešifrovat zprávu
* útočník zná veřejný klíč:
* (n, e)
* tedy například ví:
* n = 3233
* e = 17
* a zná šifrovaný text c
* aby mohl dešifrovat, potřeboval by znát d
* jenže d se počítá pomocí φ(n), a k výpočtu φ(n) potřebuje znát p a q
* u malého čísla 3233 je snadné zjistit, že:
* 3233 = 61 * 53
* ale u skutečného RSA má n běžně 2048 nebo více bitů, takže rozklad na prvočísla je extrémně obtížný
7. Důležitá poznámka: RSA se v praxi nepoužívá takto na holá data
* popsaný postup je tzv. učebnicové RSA
* to je dobré pro pochopení principu, ale samo o sobě není bezpečné
* v praxi se před šifrováním používá speciální doplnění zprávy, tzv. padding, například:
* RSA-OAEP
* bez paddingu by RSA mělo vážné bezpečnostní problémy, například by stejné zprávy dávaly stejné šifrované výstupy
8. RSA a digitální podpis
* RSA se nepoužívá jen k šifrování, ale také k digitálním podpisům
* princip je opačný
* při šifrování:
* šifrování: veřejný klíč
* dešifrování: soukromý klíč
* při podpisu:
* podpis: soukromý klíč
* ověření: veřejný klíč
* majitel soukromého klíče vytvoří podpis a kdokoli s veřejným klíčem může ověřit, že podpis opravdu vytvořil držitel soukromého klíče
* v praxi se ale nepodepisuje celá zpráva přímo
* nejprve se spočítá hash zprávy a ten se potom podepíše, obvykle se schématem jako RSA-PSS
9. Shrnutí
* RSA funguje tak, že se vytvoří veřejný a soukromý klíč z dvojice velkých prvočísel
* veřejný klíč umožní zprávu zašifrovat, ale dešifrovat ji lze jen pomocí soukromého klíče
* bezpečnost RSA stojí na obtížnosti rozkladu velmi velkého čísla n na dvě původní prvočísla p a q