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
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
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).
Aby zaszyfrować wiadomość m, oblicz szyfrogram c = m^e mod n, gdzie e i n to klucz publiczny odbiorcy.
Aby odszyfrować szyfrogram c, oblicz tekst jawny m = c^d mod n, gdzie d i n to klucz prywatny.
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
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 DOISkopiowano.Koblitz, N. (1987). A Course in Number Theory and Cryptography. Springer-Verlag.
ISBN: 978-0387966618Skopiowano.