Przejdź do treści
Wróć do wyników wyszukiwania

Kryptosystem RSA

Autor metody
Ronald Rivest
Rok
1978
Typ
asymmetric encryption algorithm
Rodzina
Public-key cryptography

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

RSA to fundamentalny kryptosystem klucza publicznego, opracowany przez Rivesta, Shamira i Adlemana w 1978 roku.

Umożliwia bezpieczne szyfrowanie i podpisy cyfrowe poprzez zastosowanie pary matematycznie powiązanych kluczy: klucza publicznego do szyfrowania i klucza prywatnego do deszyfrowania. Bezpieczeństwo RSA opiera się na trudności obliczeniowej faktoryzacji dużych liczb złożonych na ich czynniki pierwsze.

Intuicja stojąca za metodą

RSA działa na prostej zasadzie matematycznej: łatwo jest pomnożyć dwie duże liczby pierwsze, ale niezwykle trudno jest odwrócić ten proces poprzez faktoryzację ich iloczynu. Każdy użytkownik generuje dwa klucze z iloczynu dwóch dużych liczb pierwszych. Klucz publiczny jest udostępniany jawnie i służy do szyfrowania wiadomości, natomiast klucz prywatny jest utrzymywany w tajemnicy i służy do ich deszyfrowania. Bezpieczeństwo wynika z faktu, że bez znajomości czynników pierwszych atakujący nie może praktycznie wyprowadzić klucza prywatnego z klucza publicznego.

Historia

RSA zostało opublikowane w 1978 roku i stało się jednym z pierwszych praktycznych kryptosystemów klucza publicznego. Zasadniczo zmieniło kryptografię, umożliwiając bezpieczną komunikację bez wcześniej udostępnionych tajnych kluczy. Algorytm był opatentowany w Stanach Zjednoczonych do 2000 roku, po czym wszedł do domeny publicznej. RSA było nieustannie analizowane i udoskonalane przez prawie pięć dekad, a współczesne warianty zawierają schematy dopełniania i większe rozmiary kluczy, aby przeciwdziałać ewoluującym atakom.

Kiedy stosować

RSA jest odpowiednie do szyfrowania małych ilości danych, ustanawiania bezpiecznych kanałów i tworzenia podpisów cyfrowych. Jest powszechnie stosowane w protokołach TLS/SSL, szyfrowaniu poczty e-mail (PGP) i urzędach certyfikacji. RSA wymaga starannych schematów dopełniania (OAEP dla szyfrowania, PSS dla podpisów), aby było bezpieczne. Współczesne implementacje powinny używać kluczy o długości co najmniej 2048 bitów dla rozsądnego bezpieczeństwa w obliczu obecnej mocy obliczeniowej.

Ograniczenia i uwagi

  • Obliczeniowo kosztowny w porównaniu do szyfrowania symetrycznego; zazwyczaj używany do wymiany kluczy, a nie do szyfrowania dużych ilości danych
  • Rozmiar klucza musi być duży (2048 bitów lub więcej) dla odpowiedniego bezpieczeństwa, co sprawia, że szyfrowanie i deszyfrowanie są wolniejsze niż w przypadku alternatyw symetrycznych
  • Podatny na ataki komputerów kwantowych, jeśli staną się praktyczne, co wymaga alternatyw postkwantowych

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Szeroko standaryzowany i wspierany na różnych platformach i w bibliotekach
  • Umożliwia zarówno szyfrowanie, jak i generowanie podpisów cyfrowych za pomocą tej samej pary kluczy
  • Matematycznie eleganckie podstawy oparte na problemie faktoryzacji
  • Kompatybilny wstecz z dziesięcioleciami istniejącej infrastruktury

Zastosowania

  • Protokoły HTTPS i TLS/SSL do zabezpieczania komunikacji internetowej i handlu elektronicznego
  • Pretty Good Privacy (PGP) i S/MIME do szyfrowania wiadomości e-mail
  • Certyfikaty cyfrowe i infrastruktura klucza publicznego (PKI) do uwierzytelniania tożsamości online
  • Systemy blockchain i kryptowaluty do podpisywania i weryfikacji transakcji
  • Uwierzytelnianie kart inteligentnych i szyfrowanie dowodów tożsamości wydawanych przez rząd
  • Sprzętowe moduły bezpieczeństwa (HSM) do zarządzania kluczami w przedsiębiorstwach

Jak to działa

Jak to działa

1

Wybierz dwie duże, różne liczby pierwsze p i q, oblicz ich iloczyn n = p × q, oblicz tocjent Eulera φ(n) = (p-1)(q-1), wybierz e takie, że 1 < e < φ(n) i e jest względnie pierwsze z φ(n), oblicz d takie, że e × d ≡ 1 (mod φ(n)). Klucz publiczny to (e, n), a klucz prywatny to (d, n).

2

Aby zaszyfrować wiadomość m, oblicz szyfrogram c = m^e mod n, gdzie e i n to klucz publiczny odbiorcy.

3

Aby odszyfrować szyfrogram c, oblicz tekst jawny m = c^d mod n, gdzie d i n to klucz prywatny.

4

Podpisy cyfrowe tworzy się poprzez zaszyfrowanie skrótu wiadomości kluczem prywatnym, a weryfikuje się je poprzez odszyfrowanie kluczem publicznym w celu potwierdzenia zgodności skrótu.

Częste pułapki

  • Używanie RSA bez odpowiednich schematów dopełniania (OAEP lub PSS) może narazić algorytm na różne ataki
  • Ponowne użycie tego samego klucza RSA zarówno do operacji szyfrowania, jak i podpisywania zwiększa powierzchnię ataku; preferowane są dedykowane pary kluczy
  • Nieprawidłowe generowanie liczb pierwszych lub słaba losowość w generowaniu kluczy może całkowicie zagrozić bezpieczeństwu

Najczęściej zadawane pytania

Dlaczego RSA jest wolne w porównaniu do szyfrowania symetrycznego, takiego jak AES?

RSA obejmuje potęgowanie modularne na bardzo dużych liczbach (2048 bitów lub większych), co wymaga rzędów wielkości więcej obliczeń niż wydajne operacje na poziomie bajtów w AES. W praktyce RSA jest używane do szyfrowania małego klucza, który następnie szyfruje duże ilości danych za pomocą AES.

Co się stanie, jeśli ktoś rozłoży na czynniki mój moduł klucza publicznego n?

Jeśli atakujący rozłoży n na jego czynniki pierwsze p i q, może obliczyć φ(n), a następnie wyprowadzić twój klucz prywatny d z twojego wykładnika publicznego e. Dlatego kluczowe jest używanie wystarczająco dużych liczb pierwszych i rozmiarów kluczy.

Czy podpisy RSA mogą zostać sfałszowane bez klucza prywatnego?

Nie, jeśli podpisy są prawidłowo dopełnione (PSS). Jednak nie dopełnione lub nieprawidłowo dopełnione podpisy RSA są podatne na różne ataki matematyczne. Zawsze należy używać standardowych schematów dopełniania.

Czy RSA jest nadal bezpieczne w 2026 roku?

RSA z kluczami 2048-bitowymi jest nadal uważane za bezpieczne przed klasycznymi komputerami, chociaż klucze 4096-bitowe są zalecane dla długoterminowego bezpieczeństwa. Jednak RSA będzie podatne na ataki komputerów kwantowych, jeśli zostaną one zbudowane na dużą skalę, dlatego aktywnie prowadzone są badania nad kryptografią postkwantową.

Jak wybrać odpowiednie liczby pierwsze p i q?

Użyj kryptograficznie bezpiecznego generatora liczb losowych do wygenerowania dużych liczb, a następnie przetestuj każdą z nich pod kątem pierwszości za pomocą algorytmów takich jak test Millera-Rabina. Współczesne biblioteki obsługują to automatycznie.

Pokrewne metody

Źródła

  1. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Koblitz, N. (1987). A Course in Number Theory and Cryptography. Springer-Verlag.

    ISBN: 978-0387966618
    Skopiowano.