Opracowany w 1977 roku przez Rona Rivesta, Adi Shamira i Leonarda Adlemana system kryptograficzny oparty na kluczu asymetrycznym. Może być wykorzystywany zarówno do szyfrowania jak i elektronicznego podpisywania dokumentów.
Prawa do algorytmu RSA posiada firma RSA Security Inc., udzielająca płatnej licencji na jego używanie w programach innych producentów (patent ważny jest jednak tylko w USA). RSA wkomponowany jest m.in. w dwie najważniejsze przeglądarki: Netscape Navigator oraz Internet Explorer.
Fundamentem RSA jest algorytm służący do generowania unikalnych i bezpiecznych (odpornych na próby odgadnięcia) par kluczy. Mnoży on dwie duże liczby pierwsze (podzielne tylko przez 1 i przez siebie) i z otrzymanego wyniku poprzez kilka innych dodatkowych operacji ustala klucz publiczny i zależny od niego klucz prywatny. Pierwszy z nich służy do szyfrowania wiadomości przeznaczonych dla właściciela kluczy i co za tym idzie powinien być jak najszerzej propagowany. Klucz prywatny jest tajny i tylko przy jego pomocy można odszyfrować to, co zostało zakodowane kluczem publicznym.
Algorytm RSA bazuje na dwóch dostatecznie dużych liczbach pierwszych. Na podstawie tych liczb (oznaczonych dalej jako p i q) obliczane są dwie kolejne wartości: n oraz e, z których:
n = p * q
e < n
i e jest liczbą względnie pierwszą (nie mającą żadnych wspólnych podzielników z wyjątkiem 1) do iloczynu:
( p - 1 ) ( q - 1 )
Ostatni etap to wyznaczenie takiej liczby d, że:
e * d jest podzielne przez ( p - 1 ) ( q - 1 )
Od tego momentu liczby pierwsze p i q nie biorą udziału w obliczeniach i mogą zostać zniszczone. W dalszych operacjach korzysta się już z wyznaczonego klucza publicznego (para liczb n oraz e) i klucza prywatnego (para liczb n oraz d). Chcąc uzyskać zaszyfrowaną postać s wiadomości tekstowej w należy przeprowadzić następującą operację dzielenia modulo z użyciem klucza publicznego:
s=w e mod n
Deszyfrowanie odbywa się w podobny sposób, lecz tym razem w operacji bierze udział klucz prywatny:
w=s d mod n
Przyjmując za wyjściowe p oraz q odpowiednio duże liczby pierwsze otrzymujemy szyfr odporny na złamanie.
Siła RSA wynika z faktu, iż odczytanie zakodowanej wiadomości wymaga rozłożenia wspomnianej wyżej, znanej liczby n na czynniki pierwsze. Przy dzisiejszym stanie nauk matematycznych i odpowiednio dużych liczbach jest to niezwykle trudne zadanie. Nawet największe superkomputery nie są w stanie wykonać go w rozsądnym czasie.
Algorytm RSA teoretycznie może wykorzystywać klucze dowolnej długości. Wysoki poziom bezpieczeństwa zapewniają klucze o długości 2048 bitów - i takie też najczęściej stosowane są w praktyce (dla porównania - 56 bitów dla algorytmu DES odpowiada 512 bitom dla RSA).
Naturalnie - można sobie wyobrazić, że w matematyce dochodzi do przełomowego odkrycia, które ukazuje nową, szybką metodę rozkładania dużych liczb na czynniki pierwsze. Wówczas opisywany algorytm oraz wykorzystujące go aplikacje staną się bezużyteczne. Sytuacja taka jest o tyle możliwa, że dotychczas nie dostarczono dowodu na to, iż metoda taka z pewnością nie istnieje.
Poważną wadą algorytmu RSA jest jego wolne działanie. Z tego powodu stosuje się go zazwyczaj w połączeniu z innymi algorytmami, np. DES, który operacje szyfrowania przeprowadza 1000 razy szybciej. W takich systemach hybrydowych DES służy do szyfrowania wiadomości, RSA natomiast koduje już tylko klucz używany w DES-ie. Klucz zamknięty w takiej elektronicznej kopercie może następnie zostać bezpiecznie przesłany kanałem nie zapewniającym poufności - np. przez Internet.
RSA wchodzi w skład wielu istniejących lub proponowanych standardów i protokołów sieciowych. Jest szeroko stosowany w komunikacji internetowej: poufnej poczcie elektronicznej i sygnowaniu dokumentów elektronicznymi podpisami, systemie PGP i protokołach SET, S/MIME, SSL oraz HTTPS.
Źródło:
http://www.republika.pl/podpis_elektroniczny/maint.htm
|
