RSA — definicja algorytmu szyfrowania z kluczem publicznym

Poznaj RSA — zasady działania, generowanie kluczy, bezpieczeństwo i zastosowania kryptografii z kluczem publicznym. Proste wyjaśnienie i praktyczne przykłady.

Autor: Leandro Alegsa

RSA (Rivest-Shamir-Adleman) jest algorytmem używanym przez współczesne komputery do szyfrowania i odszyfrowywania wiadomości. Jest to asymetryczny algorytm kryptograficzny. Asymetryczny oznacza, że istnieją dwa różne klucze. Jest to również nazywane kryptografią z kluczem publicznym, ponieważ jeden z kluczy może być podany komukolwiek. Drugi klucz musi być zachowany jako prywatny. Algorytm opiera się na fakcie, że znalezienie czynników dużej liczby złożonej jest trudne: gdy czynniki są liczbami pierwszymi, problem nazywa się faktoryzacją pierwszorzędną. Jest to również generator pary kluczy (klucza publicznego i prywatnego).

Jak działa RSA — opis krok po kroku

  • Generowanie kluczy:
    1. Wybierz dwie duże, losowe liczby pierwsze p i q.
    2. Oblicz n = p · q — moduł, który jest częścią obu kluczy.
    3. Oblicz φ(n) = (p − 1)(q − 1) (funkcja Eulera).
    4. Wybierz liczbę e taką, że 1 < e < φ(n) i gcd(e, φ(n)) = 1 (e jest wykładnikiem publicznym).
    5. Oblicz d, odwrotność mnożenia e modulo φ(n): d · e ≡ 1 (mod φ(n)). d jest wykładnikiem prywatnym.
    6. Klucz publiczny to para (n, e). Klucz prywatny to (n, d) — d i często wartości p, q są przechowywane bezpiecznie, by umożliwić szybsze operacje.
  • Szyfrowanie i odszyfrowywanie:
    • Szyfrowanie wiadomości m (0 ≤ m < n): c = m^e mod n.
    • Odszyfrowanie: m = c^d mod n.
  • Podpisy cyfrowe: podpis s = m^d mod n; weryfikacja: m = s^e mod n. Dzięki temu można potwierdzić autentyczność i integralność wiadomości.

Przykład (dla małych liczb, obrazujący działanie)

Wybierzemy p = 61, q = 53. Wtedy n = 3233, φ(n) = 3120. Niech e = 17 (gcd(17,3120)=1). Obliczamy d = 2753 (ponieważ 17·2753 ≡ 1 mod 3120). Publiczny klucz: (n=3233, e=17). Prywatny: d=2753.

Jeśli m = 65, szyfrogram c = 65^17 mod 3233 = 2790. Odszyfrowanie: 2790^2753 mod 3233 = 65 — odzyskujemy oryginalną wiadomość.

Zastosowania praktyczne

  • Ustanawianie bezpiecznych połączeń (np. w protokole TLS) — często do bezpiecznej wymiany kluczy sesyjnych.
  • Podpisy cyfrowe i certyfikaty (np. X.509, PGP).
  • Szyfrowanie wiadomości i uwierzytelnianie w systemach, gdzie konieczne jest rozdzielenie klucza publicznego i prywatnego.

Bezpieczeństwo i praktyczne uwagi

  • Trudność faktoryzacji: bezpieczeństwo RSA opiera się na praktycznej trudności faktoryzacji dużych liczb złożonych. Obecnie najsilniejszą klasą ataków na klasyczne komputery jest algorytm General Number Field Sieve (GNFS).
  • Rozmiary kluczy: zaleca się co najmniej 2048-bitowy klucz dla krótkoterminowego bezpieczeństwa; 3072-bit lub więcej dla dłuższego bezpieczeństwa. Większe klucze zwiększają bezpieczeństwo, ale pogarszają wydajność.
  • Padding i schematy kodowania: bezpieczne użycie RSA wymaga odpowiednich schematów wypełnienia (padding) — np. OAEP dla szyfrowania i PSS dla podpisów. Stosowanie prostego m^e mod n bez paddingu jest podatne na ataki (np. ataki Bleichenbacher’a przy PKCS#1 v1.5).
  • Wybór e: często stosowany wykładnik publiczny to 65537 (2^16 + 1) — zapewnia równowagę między bezpieczeństwem a wydajnością.
  • Generowanie liczb pierwszych: p i q muszą być losowe i wystarczająco duże; stosuje się testy pierwszości (np. Miller–Rabin) oraz silne źródła losowości.
  • Wydajność: RSA jest znacznie wolniejszy niż algorytmy symetryczne — w praktyce stosuje się go do szyfrowania małych bloków (np. kluczy sesyjnych), a nie dużych strumieni danych.
  • Ataki bocznego kanału i przechowywanie kluczy: implementacje muszą być odporne na ataki bocznego kanału (np. pomiary czasu, zużycia energii) oraz chronić prywatny klucz (HSM, moduły TPM, bezpieczne magazynowanie).
  • Wpływ komputerów kwantowych: algorytm Shora (dla komputerów kwantowych) przełamuje bezpieczeństwo RSA w teorii; dlatego dla długoterminowej komunikacji rozważa się algorytmy post-kwantowe.

Podsumowanie

RSA to fundament współczesnej kryptografii asymetrycznej: umożliwia bezpieczną wymianę kluczy, szyfrowanie krótkich wiadomości i podpisy cyfrowe. Jego bezpieczeństwo zależy od odpowiedniego doboru parametrów (rozmiaru klucza, losowości, paddingu) oraz poprawnych implementacji. Mimo pojawienia się nowych technologii i zagrożeń, RSA wciąż jest powszechnie stosowany tam, gdzie spełnia wymagania bezpieczeństwa i wydajności.

Szyfrowanie wiadomości

Alice przekazuje swój klucz publiczny ( n {displaystyle n } {\displaystyle n\,}& e {displaystyle e } ) {\displaystyle e\,}Bobowi i zachowuje swój klucz prywatny w tajemnicy. Bob chce wysłać wiadomość M do Alicji.

Najpierw zamienia M na liczbę m {styl m} mmniejszą od n {styl n}n za pomocą uzgodnionego odwracalnego protokołu znanego jako schemat paddingu. Następnie oblicza szyfrogram c {displaystyle c} {\displaystyle c\,}odpowiadający:

c = m e mod n {{displaystyle c=m^{e}}mod {n}} {\displaystyle c=m^{e}\mod {n}}

Można to zrobić szybko, stosując metodę wykładania przez podniesienie do kwadratu. Bob następnie wysyła c {w stylu c} {\displaystyle c\,}do Alice.

Odszyfrowanie wiadomości

Alicja może odzyskać m {styl m} {\displaystyle m\,}z c {styl c}{\displaystyle c\,}, używając swojego klucza prywatnego d {styl d} {\displaystyle d\,}w następującej procedurze:

m = c d mod n {{displaystyle m=c^{d}{{bmod {n}}}} {\displaystyle m=c^{d}{\bmod {n}}}

Biorąc pod uwagę m, można odzyskać pierwotne liczby pierwsze, a zastosowanie{\displaystyle m\,}chińskiego twierdzenia o resztach do tych dwóch kongruencji daje wynik

m e d ≡ m mod p q {displaystyle m^{ed}}equiv m{mod {pq}} {\displaystyle m^{ed}\equiv m{\bmod {pq}}}.

Tak więc,

c d ≡ m mod n {displaystyle c^{d}}equiv m{mod {n}}} {\displaystyle c^{d}\equiv m{\bmod {n}}}.

Przykład roboczy

Poniżej znajduje się przykład szyfrowania i deszyfrowania RSA. Parametry użyte tutaj są sztucznie zaniżone, ale możesz również użyć OpenSSL do wygenerowania i zbadania prawdziwej pary kluczy.

  1. Wybierz dwie losowe liczby pierwsze.
  2.  : p = 61 {displaystyle p=61} {\displaystyle p=61}i q = 53 ; {displaystyle q=53;} {\displaystyle q=53;}Oblicz n = p q {displaystyle n=pq}. {\displaystyle n=pq\,}
  3.  : n = 61 ∗ 53 = 3233 {przykład n=61*53=3233} {\displaystyle n=61*53=3233}
  4. Oblicz totient ϕ ( n ) = ( p - 1 ) ( q - 1 ) {displaystyle \i(n)=(p-1)(q-1)\}. {\displaystyle \phi (n)=(p-1)(q-1)\,}
  5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {przykład: ϕ ( n)=(61-1)(53-1)=3120} {\displaystyle \phi (n)=(61-1)(53-1)=3120}
  6. Wybierz e > 1 {współrzędne{\displaystyle e>1} do 3120}.
  7.  : e = 17 {przykład e=17} {\displaystyle e=17}
  8. Wybierz d, {\displaystyle d\,}aby spełnić warunek d e mod ϕ ( n ) ≡ 1 {displaystyle de{mod {phi (n)}}. {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,}
  9.  : d = 2753 {przykład d=2753} {\displaystyle d=2753}
  10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {przykład 17*2753=46801=1+15*3120}{\displaystyle 17*2753=46801=1+15*3120} .

Kluczem publicznym jest ( n = 3233 {displaystyle n=3233} {\displaystyle n=3233}, e = 17 {displaystyle e=17} {\displaystyle e=17}). Dla wyściełanej wiadomości m {{displaystyle m}}{\displaystyle m\,} funkcja szyfrująca c = m e mod n {{displaystyle c=m^{e}{{mod {n}}}} staje się: {\displaystyle c=m^{e}{\bmod {n}}}

c = m 17 mod 3 233 { {displaystyle c=m^{17}{bmod {3}}}233 } {\displaystyle c=m^{17}{\bmod {3}}233\,}

Kluczem prywatnym jest ( n = 3233 {displaystyle n=3233} {\displaystyle n=3233}, d = 2753 {displaystyle d=2753}{\displaystyle d=2753} ). Funkcją deszyfrującą m = c d mod n {displaystyle m=c^{d}{mod {n}}} {\displaystyle m=c^{d}{\bmod {n}}}staje się:

m = c 2753 mod 3 233 {displaystyle m=c^{2753}{bmod {3}}233}. {\displaystyle m=c^{2753}{\bmod {3}}233\,}


Na przykład, aby zaszyfrować m = 123 {displaystyle m=123} . {\displaystyle m=123}, obliczamy

c = 123 17 mod 3 233 = 855 {przykład c=123^{17}{mod {3}}}233=855}. {\displaystyle c=123^{17}{\bmod {3}}233=855}

Aby odszyfrować c = 855 {displaystyle c=855}. {\displaystyle c=855}, obliczamy

m = 855 2753 mod 3 233 = 123 {przykład m=855^{2753}{mod {3}}233=123}. {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Oba te obliczenia mogą być wykonane efektywnie przy użyciu algorytmu kwadrat-i-wielokrotność dla wykładania modularnego [en].

Wyprowadzenie równania RSA z twierdzenia Eulera

RSA można łatwo wyprowadzić wykorzystując twierdzenie Eulera i funkcję totientu Eulera.

Zaczynając od twierdzenia Eulera,

m ϕ ( n ) ≡ 1 ( mod n ) {{displaystyle m^{phi (n)}}} {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

musimy pokazać, że odszyfrowanie zaszyfrowanej wiadomości przy użyciu właściwego klucza da nam oryginalną wiadomość. Biorąc pod uwagę wyściełaną wiadomość m, szyfrogram c jest obliczany przez

c ≡ m e ( mod n ) {{displaystyle c ≡ m^{e}{{mod {n}}}} {\displaystyle c\equiv m^{e}{\pmod {n}}}

Podstawiając do algorytmu deszyfrującego, mamy

c d ≡ ( m e ) d ≡ m e d ( mod n ) {{displaystyle c^{d}\\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}. {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}

Chcemy pokazać, że ta wartość jest również przystająca do m. Wartości e i d zostały dobrane tak, aby nasycić,

e d ≡ 1 ( mod ϕ ( n ) ) {{displaystyle ed}} 1{pmod {{phi (n)}} {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

To znaczy, że istnieje pewna liczba całkowita k, taka że

e d = k × ϕ ( n ) + 1 {displaystyle ed=krotność \i(n)+1} {\displaystyle ed=k\times \phi (n)+1}

Teraz podstawiamy do zaszyfrowanej, a następnie odszyfrowanej wiadomości,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) k ( mod n ) {displaystyle {{begin{aligned}m^{ed}&^equiv m^{kphi (n)+1}} ^{k}{pmod {n}}}end{aligned}}} {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}

Stosujemy twierdzenie Eulera i otrzymujemy wynik.

m × ( 1 ) k ≡ m ( mod n ) {{displaystyle m ≡times (1)^{k}} }} {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

Schematy paddingu

W praktyce, RSA musi być połączona z jakąś formą schematu wypełniania, tak aby żadna z wartości M nie skutkowała niezabezpieczonymi szyfrogramami. RSA używana bez paddingu może mieć pewne problemy:

  • Wartości m = 0 lub m = 1 zawsze dają szyfrogramy równe odpowiednio 0 lub 1, ze względu na właściwości wykładania.
  • Podczas szyfrowania z małymi wykładnikami szyfrowania (np. e = 3) i małymi wartościami m, (niemodularny) wynik m e {{e}} {\displaystyle m^{e}}może być ściśle mniejszy niż modulus n. W tym przypadku szyfrogramy mogą być łatwo odszyfrowane przez wzięcie pierwiastka et z szyfrogramu bez względu na modulus.
  • Szyfrowanie RSA jest deterministycznym algorytmem szyfrowania. Nie ma w nim składnika losowego. Dlatego atakujący może z powodzeniem przeprowadzić atak na kryptosystem za pomocą wybranego tekstu jawnego. Może on stworzyć słownik szyfrując prawdopodobne plaintekty pod kluczem publicznym i przechowując uzyskane w ten sposób szyfrogramy. Atakujący może następnie obserwować kanał komunikacyjny. Gdy tylko zobaczy szyfrogramy, które pasują do tych w jego słowniku, atakujący może użyć tego słownika w celu poznania treści wiadomości.

W praktyce dwa pierwsze problemy mogą pojawić się, gdy wysyłane są krótkie wiadomości ASCII. W takich wiadomościach, m może być konkatenacją jednego lub więcej znaków zakodowanych w ASCII. Wiadomość składająca się z pojedynczego znaku ASCII NUL (którego wartość liczbowa wynosi 0) będzie zakodowana jako m = 0, co daje szyfrogram o wartości 0 bez względu na to, jakie wartości e i N zostaną użyte. Podobnie, pojedynczy znak ASCII SOH (którego wartość liczbowa wynosi 1) zawsze daje szyfrogram o wartości 1. Dla systemów, które konwencjonalnie używają małych wartości e, takich jak 3, wszystkie wiadomości z pojedynczymi znakami ASCII zakodowane za pomocą tego schematu byłyby niezabezpieczone, ponieważ największe m miałoby wartość 255, a 2553 jest mniejsze niż jakikolwiek rozsądny modulus. Taki tekst jawny można by odzyskać po prostu biorąc pierwiastek sześcienny z szyfrogramu.

Aby uniknąć tych problemów, praktyczne implementacje RSA zazwyczaj wstawiają jakąś formę strukturalnego, randomizowanego wypełnienia do wartości m przed jej zaszyfrowaniem. Wypełnienie to zapewnia, że m nie mieści się w zakresie niepewnych tekstów jawnych, oraz że dana wiadomość, po wypełnieniu, zostanie zaszyfrowana do jednego z wielu różnych możliwych szyfrogramów. Ta ostatnia właściwość może zwiększyć koszt ataku słownikowego poza możliwości rozsądnego atakującego.

Standardy takie jak PKCS zostały starannie zaprojektowane do bezpiecznego wypełniania wiadomości przed szyfrowaniem RSA. Ponieważ te schematy wypełniają tekst jawny m pewną liczbą dodatkowych bitów, rozmiar nie wypełnionej wiadomości M musi być nieco mniejszy. Schematy paddingu RSA muszą być starannie zaprojektowane, by zapobiec wyrafinowanym atakom. Może to być ułatwione przez przewidywalną strukturę wiadomości. Wczesne wersje standardu PKCS wykorzystywały konstrukcje ad-hoc, które później okazały się podatne na praktyczny adaptacyjny atak z użyciem wybranego szyfrogramu. Nowoczesne konstrukcje wykorzystują bezpieczne techniki, takie jak Optimal Asymmetric Encryption Padding (OAEP), aby chronić wiadomości, jednocześnie zapobiegając tym atakom. Standard PKCS posiada również schematy przetwarzania zaprojektowane w celu zapewnienia dodatkowego bezpieczeństwa dla podpisów RSA, np. Probabilistyczny Schemat Podpisu dla RSA (RSA-PSS).

Podpisywanie wiadomości

Załóżmy, że Alice używa klucza publicznego Boba do wysłania mu zaszyfrowanej wiadomości. W tej wiadomości może podać się za Alice, ale Bob nie ma możliwości sprawdzenia, czy wiadomość rzeczywiście pochodzi od Alice, ponieważ każdy może użyć klucza publicznego Boba do wysłania mu zaszyfrowanej wiadomości. Tak więc, aby zweryfikować pochodzenie wiadomości, RSA może być również użyta do podpisania wiadomości.

Załóżmy, że Alicja chce wysłać podpisaną wiadomość do Boba. Tworzy wartość hash wiadomości, podnosi ją do potęgi d mod n (tak jak przy odszyfrowywaniu wiadomości) i dołącza jako "podpis" do wiadomości. Kiedy Bob otrzymuje podpisaną wiadomość, podnosi podpis do potęgi e mod n (tak jak w przypadku szyfrowania wiadomości) i porównuje otrzymaną wartość hash z rzeczywistą wartością hash wiadomości. Jeśli obie się zgadzają, wie, że autor wiadomości był w posiadaniu tajnego klucza Alice i że od tego czasu wiadomość nie była modyfikowana.

Należy zauważyć, że bezpieczne schematy paddingu, takie jak RSA-PSS, są tak samo istotne dla bezpieczeństwa podpisywania wiadomości, jak dla ich szyfrowania, oraz że ten sam klucz nigdy nie powinien być używany zarówno do szyfrowania, jak i podpisywania.

Pytania i odpowiedzi

P: Co to jest RSA?


O: RSA (Rivest-Shamir-Adleman) to algorytm używany przez nowoczesne komputery do szyfrowania i odszyfrowywania wiadomości. Jest to asymetryczny algorytm kryptograficzny.

P: Co to znaczy asymetryczny?


O: Asymetryczny oznacza, że istnieją dwa różne klucze - klucz publiczny i klucz prywatny.

P: Na czym opiera się algorytm RSA?


O: Algorytm opiera się na fakcie, że znalezienie czynników dużej liczby złożonej jest trudne - gdy czynniki są liczbami pierwszymi, problem ten nazywa się faktoryzacją pierwszorzędową.

P: Jak działa RSA?


O: RSA obejmuje klucz publiczny i klucz prywatny. Klucz publiczny może być znany wszystkim - jest on używany do szyfrowania wiadomości. Wiadomości zaszyfrowane za pomocą klucza publicznego można odszyfrować tylko za pomocą klucza prywatnego, który musi być utrzymywany w tajemnicy. Obliczenie klucza prywatnego z klucza publicznego jest bardzo trudne.

P: Czy istnieje jakaś inna nazwa dla tego typu kryptografii?


O: Ten typ kryptografii nazywany jest również kryptografią klucza publicznego, ponieważ jeden z kluczy może być podany każdemu, podczas gdy drugi pozostaje prywatny.

P: Czy RSA generuje parę kluczy?


O: Tak, RSA generuje parę kluczy - klucz publiczny i prywatny - które są używane odpowiednio do szyfrowania i deszyfrowania.


Przeszukaj encyklopedię
AlegsaOnline.com - 2020 / 2025 - License CC3