algorytm RSA jest podstawą kryptosystemu – zestawu algorytmów kryptograficznych, które są używane do określonych usług lub celów bezpieczeństwa – który umożliwia szyfrowanie klucza publicznego i jest szeroko stosowany do zabezpieczania poufnych danych, szczególnie gdy są wysyłane przez niezabezpieczoną sieć, taką jak internet.,

RSA został po raz pierwszy publicznie opisany w 1977 roku przez Rona Rivesta, Adi Shamira i Leonarda Adlemana z Massachusetts Institute of Technology, chociaż stworzenie algorytmu klucza publicznego w 1973 roku przez brytyjskiego matematyka Clifforda Cocksa było klasyfikowane przez brytyjski GCHQ do 1997 roku.

Kryptografia klucza publicznego, znana również jako kryptografia asymetryczna, wykorzystuje dwa różne, ale matematycznie powiązane klucze – jeden publiczny i jeden prywatny. Klucz publiczny może być udostępniany wszystkim, podczas gdy klucz prywatny musi być utrzymywany w tajemnicy.,

w kryptografii RSA zarówno klucze publiczne, jak i prywatne mogą zaszyfrować wiadomość; do jej odszyfrowania używany jest klucz przeciwny do klucza używanego do szyfrowania wiadomości. Ten atrybut jest jednym z powodów, dla których RSA stał się najczęściej stosowanym algorytmem asymetrycznym: zapewnia metodę zapewniającą poufność, integralność, autentyczność i brak odrzucenia łączności elektronicznej i przechowywania danych.

wiele protokołów, takich jak secure shell, OpenPGP, S/MIME i SSL/TLS, opiera się na RSA do szyfrowania i funkcji podpisu cyfrowego., Jest również używany w programach-przeglądarki są oczywistym przykładem, ponieważ muszą ustanowić bezpieczne połączenie przez niebezpieczną sieć, taką jak internet, lub zweryfikować podpis cyfrowy. Weryfikacja podpisu RSA jest jedną z najczęściej wykonywanych operacji w systemach podłączonych do sieci.

dlaczego algorytm RSA jest używany

RSA czerpie swoje bezpieczeństwo z trudności faktorowania dużych liczb całkowitych, które są iloczynem dwóch dużych liczb pierwszych., Mnożenie tych dwóch liczb jest łatwe, ale określenie oryginalnych liczb pierwszych z sumy-lub faktoringu-jest uważane za niewykonalne ze względu na czas, który zajęłby przy użyciu nawet dzisiejszych superkomputerów.

algorytm generowania kluczy publicznych i prywatnych jest najbardziej złożoną częścią kryptografii RSA. Dwie duże liczby pierwsze, p i q, są generowane za pomocą algorytmu testu pierwszeństwa Rabina-Millera. Moduł n jest obliczany przez pomnożenie p i Q. liczba ta jest używana zarówno przez klucze publiczne, jak i prywatne i zapewnia połączenie między nimi., Jego długość, zwykle wyrażana w bitach, nazywana jest długością klucza.

klucz publiczny składa się z modułu n i wykładnika publicznego e, który jest zwykle ustawiony na 65537, ponieważ jest liczbą pierwszą, która nie jest zbyt duża. Cyfra e nie musi być potajemnie wybraną liczbą pierwszą, ponieważ klucz publiczny jest udostępniany wszystkim.

klucz prywatny składa się z modułu n i wykładnika prywatnego d, który jest obliczany za pomocą rozszerzonego algorytmu Euklidesowego, aby znaleźć mnożnik odwrotności w odniesieniu do tient N.,

Przeczytaj lub obejrzyj poniższy film, aby uzyskać bardziej szczegółowe wyjaśnienie działania algorytmu RSA.

Jak działa algorytm RSA?

Alicja generuje klucze RSA wybierając dwie liczby pierwsze: p=11 i q=13. Moduł wynosi n = P×q = 143. N ϕ (n)=(p−1)x (q-1)=120. Wybiera 7 dla swojego klucza publicznego RSA e i oblicza swój klucz prywatny RSA za pomocą rozszerzonego algorytmu Euklidesowego, który daje jej 103.

Bob chce wysłać Alice zaszyfrowaną wiadomość, M, więc otrzymuje jej klucz publiczny RSA (n, e), który w tym przykładzie jest (143, 7)., Jego wiadomość tekstowa jest tylko liczbą 9 i jest zaszyfrowana do szyfrogramu, C, w następujący sposób:

Me mod N = 97 mod 143 = 48 = c

Kiedy Alicja otrzyma wiadomość Boba, odszyfruje ją za pomocą klucza prywatnego RSA (d, n) w następujący sposób:

Cd mod N = 48103 Mod 143 = 9 = m

aby użyć kluczy RSA do cyfrowego podpisywania wiadomości, Alice musi utworzyć hash-skrót wiadomości do Boba-zaszyfrować wartość hash za pomocą klucza prywatnego RSA i dodać klucz do wiadomości., Bob może następnie sprawdzić, czy wiadomość została wysłana przez Alice i nie została zmieniona przez odszyfrowanie wartości skrótu jej kluczem publicznym. Jeśli ta wartość odpowiada hashowi oryginalnej wiadomości, to tylko Alice mogła ją wysłać — uwierzytelnienie i nie odrzucenie — a wiadomość jest dokładnie taka, jak napisała — integralność.

Alicja mogła oczywiście zaszyfrować swoją wiadomość za pomocą klucza publicznego RSA Boba-poufność-przed wysłaniem jej do Boba. Certyfikat cyfrowy zawiera informacje identyfikujące właściciela certyfikatu, a także klucz publiczny właściciela., Certyfikaty są podpisywane przez urząd certyfikacji, który je wydaje, i mogą uprościć proces uzyskiwania kluczy publicznych i weryfikacji właściciela.

bezpieczeństwo RSA

bezpieczeństwo RSA opiera się na trudności obliczeniowej faktoringu dużych liczb całkowitych. Wraz ze wzrostem mocy obliczeniowej i odkrywaniem bardziej wydajnych algorytmów faktoringowych wzrasta również zdolność do uwzględniania coraz większych liczb.

siła szyfrowania jest bezpośrednio powiązana z rozmiarem klucza, a podwojenie długości klucza może zapewnić wykładniczy wzrost siły, chociaż pogarsza wydajność., Klucze RSA mają zazwyczaj długość 1024 lub 2048 bitów, ale eksperci uważają, że klucze 1024-bitowe nie są już w pełni zabezpieczone przed wszystkimi atakami. Dlatego rząd i niektóre branże przenoszą się do minimalnej długości klucza 2048-bitów.

poza nieprzewidzianym przełomem w informatyce kwantowej minie wiele lat, zanim potrzebne będą dłuższe klucze, ale kryptografia krzywej eliptycznej (ECC) zyskuje przychylność wielu ekspertów ds. bezpieczeństwa jako alternatywa dla RSA do implementacji kryptografii klucza publicznego. Może tworzyć szybsze, mniejsze i wydajniejsze klucze kryptograficzne.,

nowoczesny sprzęt i oprogramowanie są gotowe do ECC, a jego popularność prawdopodobnie wzrośnie, ponieważ może zapewnić równoważne bezpieczeństwo przy mniejszej mocy obliczeniowej i zużyciu zasobów baterii, dzięki czemu jest bardziej odpowiedni dla aplikacji mobilnych niż RSA. Wreszcie zespół naukowców, w skład którego wchodzi Adi Shamir, współtwórca RSA, z powodzeniem stworzył 4096-bitowy klucz RSA przy użyciu kryptoanalizy akustycznej; jednak każdy algorytm szyfrowania jest podatny na ataki.