RSA (kryptografia)

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 $2^{256}$ (ponad $10^{77}$) 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.

Zobacz też

• kryptografia kwantowa
• algorytmy kryptograficzne

Parser nie mógł rozpoznać (błąd składni): {\displaystyle W tym miejscu [[Grafika:[[Media:Example.jpg]]<nowiki>--~~~~Wstaw tu tekst niesformatowany ---- --~~~~[[[http://www.example.com tytuł strony]]'''''Tekst pochylony'''guj''u[u == uuu == ]'''']</nowiki>]]wprowadź wzór}

Link zewnętrzny

• RSA Security

Bibliografia

• Thomas H. Cormen. Rozdział 31. Algorytmy Teorioliczbowe we Wprowadzenie do algorytmów. Wyd. VII. Warszawa, 2005 WNT, s. 902 - 909