RSA

RSA (od nazwisk wynalazców Rona Rivesta, Adi Shamira i Leonarda Adlemana) jest jednym z najważniejszych algorytmów kryptografii asymetrycznej, wykorzystywanym zarówno do szyfrowania, jak i podpisu cyfrowego. System został opracowany w 1977 roku i od tego czasu stał się podstawą wielu protokołów bezpieczeństwa w Internecie.

Historia

Pierwsze publikacje opisujące metodę pojawiły się w raporcie technicznym MIT 1977. W 1978 algorytm został upubliczniony w artykule „A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” w czasopiśmie Communications of the ACM. Od tego czasu RSA przeszło liczne modyfikacje i optymalizacje, a jego bezpieczeństwo jest ściśle powiązane z trudnością faktoryzacji dużych liczb pierwszych.

Zasada działania

RSA opiera się na trzech podstawowych koncepcjach matematycznych:

• Teoria liczb – zwłaszcza własności liczb pierwszych i działań modulo.
• Rozkład na czynniki pierwsze – trudność faktoryzacji dużych liczb jest fundamentem bezpieczeństwa.
• Algorytm Euklidesa – wykorzystywany do wyznaczania odwrotności modularnej.

Generowanie kluczy

1. Wybiera się dwie duże, przypadkowe liczby pierwsze p i q.
2. Oblicza się ich iloczyn n = p·q. Liczba n jest częścią zarówno klucza publicznego, jak i prywatnego.
3. Wyznacza się funkcję Eulera φ(n) = (p‑1)(q‑1).
4. Wybiera się liczbę e taką, że 1 < e < φ(n) oraz gcd(e, φ(n)) = 1. Liczba e staje się wykładnikiem publicznym.
5. Oblicza się d, czyli odwrotność modularną e względem φ(n) (czyli e·d ≡ 1 (mod φ(n))). Liczba d jest wykładnikiem prywatnym.

Klucz publiczny: (e, n) – udostępniany wszystkim użytkownikom.

Klucz prywatny: (d, n) – zachowywany w tajemnicy przez właściciela.

Szyfrowanie i odszyfrowywanie

Zakładając, że wiadomość m (reprezentowana jako liczba całkowita 0 ≤ m < n) ma zostać zaszyfrowana:

• Szyfrowanie: c = m^e mod n
• Odszyfrowanie: m = c^d mod n

Podpis cyfrowy

Aby podpisać wiadomość m, nadawca oblicza:

• Podpis: s = m^d mod n
• Weryfikacja: odbiorca sprawdza, czy m ≡ s^e (mod n)

Zastosowania

• TLS/SSL – zabezpieczanie połączeń internetowych.
• PGP i GPG – szyfrowanie poczty elektronicznej.
• Podpisy cyfrowe w infrastrukturze klucza publicznego (PKI).
• Systemy uwierzytelniania i wymiany kluczy w aplikacjach mobilnych i IoT.

Bezpieczeństwo

Bezpieczeństwo RSA zależy głównie od rozmiaru klucza. Typowe zalecane długości to:

• 2048 bit – standardowy poziom bezpieczeństwa w zastosowaniach komercyjnych.
• 3072 bit – wymóg dla bardzo wrażliwych danych.
• 4096 bit i więcej – używany w systemach o długoterminowym wymaganiu ochrony.

W praktyce ataki na RSA obejmują:

• Metody faktoryzacji, takie jak algorytm kuryliowy czy rozklad metodą siatki.
• Ataki boczne (side‑channel attacks), np. analiza czasu działania lub wycieki mocy.
• Wybielanie klucza (key‑blinding) i użycie przyrostowych aktualizacji e i d w celu zwiększenia odporności.

Alternatywy i rozwinięcia

Choć RSA jest szeroko stosowane, istnieją inne algorytmy kryptografii asymetrycznej, które w niektórych sytuacjach oferują lepszą wydajność lub bezpieczeństwo:

• ElGamal – oparty na problemie logarytmu dyskretnego.
• ECDSA i ECDH – wykorzystujące krzywe eliptyczne.
• Kryptografia post‑kwantowa – przygotowująca się na potencjalne zagrożenia ze strony komputerów kwantowych.

Literatura i źródła

• R. Rivest, A. Shamir, L. Adleman, „A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, 1978.
• W. Diffie, M. Hellman, „New Directions in Cryptography”, IEEE Transactions on Information Theory, 1976.
• J. Koblitz, Algebraic Aspects of Cryptography, Springer, 1998.

RSA pozostaje jednym z filarów współczesnej kryptografii, zapewniając zarówno poufność, jak i integralność danych w cyfrowym świecie.