RSA (kryptografia)

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

RSA to pierwszy i obecnie jeden z dwóch najpopularniejszych (obok ElGamala) algorytmów kryptografii asymetrycznej. Stworzony w roku 1978 przez zespół: Ronald Rivest, Adi Shamir, Leonard Adleman. RSA jest akronimem utworzonym z pierwszych liter nazwisk jego twórców. RSA opiera się na trudności faktoryzacji dużych liczb – znalezienie szybkiej metody faktoryzacji doprowadziłoby do złamania RSA, aczkolwiek nie ma dowodu, że nie da się złamać RSA w inny sposób.

Żeby wygenerować klucz RSA losujemy dwie duże liczby pierwsze $p$ i $q$ , oraz liczbę $e$ względnie pierwszą z $(p - 1)(q - 1)$ .

Następnie obliczamy $d = e^{-1} \mod (p-1)(q-1)$ (ponieważ wybraliśmy względnie pierwsze $e$ , ma ono odwrotność i obliczyć ją możemy szybko rozszerzonym algorytmem Euklidesa).

Obliczamy też $n=p\cdot q$ .

Klucz publiczny to para $(e, n)$ , klucz prywatny zaś to para $(d, n)$ . Liczby $p$ i $q$ należy zniszczyć.

Żeby szyfrować podnosimy liczbę reprezentującą wiadomość do potęgi $e$ modulo $n$ :

$c = m^e \mod n$

Żeby ją zdeszyfrować podnosimy zaszyfrowaną wiadomość do potęgi $d$ . Zgodnie z twierdzeniem Eulera dostaniemy oryginalną wiadomość:

$c^d = m^{ed} = m\mod n$

Nie znając $d$ nie potrafimy łatwo odzyskać wiadomości z kryptogramu. Nie znając faktoryzacji $n$ na $p$ i $q$ nie znamy też prostej metody odtworzenia $d$ z $e$ .

RSA może też być używane do podpisów cyfrowych – żeby podpisać daną wiadomość podnosimy ją do potęgi $d$ . Żeby ją zweryfikować podnosimy podpis do potęgi $e$ . De facto nie podpisujemy jednak wiadomości jako takiej, ale specjalnie spreparowany pakiet składający się z hasza (tzw. funkcji skrótu) wiadomości oraz ustalonych bitów.

Jest to ważne, ponieważ każdy może generować za nas podpisy losowych wiadomości. Algorytm generowania takich podpisów jest następujący:

wybierz podpis

p

podnieś go do potęgi

e

– otrzymasz przypadkowe

m

p

jest prawidłowym podpisem dla (prawie na pewno bezsensownej) wiadomości

m

Jeśli zamiast pozwalać na dowolne $m$ wymusimy pewną strukturę, uniemożliwiamy ataki tego typu – np. jeśli ostatnie 256 bitów mają stanowić naprzemienne zera i jedynki, średnio tylko jeden atak na $2256$ (ponad $1077$ ) prób się powiedzie, a i tak podpisze prawie na pewno jedynie jakieś śmieci.

Jak dotąd (maj 2004) udały się ataki na klucze o długości do ok. 600 bitów. Potencjalnym zagrożeniem dla RSA jest skonstruowanie komputera kwantowego.