RSA (kryptografia)

Z Wikipedii

RSA - pierwszy i obecnie jeden z dwóch najpopularniejszych (obok ElGamala) algorytmów kryptografii asymetrycznej.

Został stworzony w 1978 przez zespół: Ronald Rivest, Adi Shamir, Leonard Adleman (nazwa 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ę go złamać w inny sposób.

Spis treści 1 Algorytm 1.1 Szyfrowanie 1.2 Podpis 1.3 Przykład 2 Próby złamania 3 Zobacz też 4 Linki zewnętrzne 5 Bibliografia

[edytuj] Algorytm

[edytuj] Szyfrowanie

Ż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 (ponieważ wybraliśmy względnie pierwsze e, ma ono odwrotność i obliczyć ją możemy szybko rozszerzonym algorytmem Euklidesa).

Obliczamy też .

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:

Żeby ją zdeszyfrować podnosimy zaszyfrowaną wiadomość do potęgi d. Zgodnie z twierdzeniem Eulera dostaniemy oryginalną wiadomość (o ile m nie jest wielokrotnością p lub q):

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.

[edytuj] Podpis

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 funkcji skrótu (tzw. hasza) 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²⁵⁶ (ponad 10⁷⁷) prób się powiedzie, a i tak podpisze prawie na pewno jedynie jakieś śmieci.

[edytuj] Przykład

1. Wybieramy dwie liczby pierwsze

   p = 61 i q = 53

2. Wyliczamy

   

3. Obliczamy

   

4. Wybieramy e > 1 względnie pierwsze do 3120

   e = 17

5. Obliczamy takie, że :

   d = 2753

   

Kluczem publicznym jest (n = 3233,e = 17). Funkcją szyfrującą dla tego klucza jest więc:

Kluczem prywatnym jest (n = 3233,d = 2753). Funkcja deszyfrująca:

Dla przykładowego m = 123

By odszyfrować c = 855, liczymy

.

[edytuj] Próby złamania

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.

[edytuj] Zobacz też

• kryptografia kwantowa
• algorytmy kryptograficzne

[edytuj] Linki zewnętrzne

• RSA Security

[edytuj] Bibliografia

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