RSA (kryptografia)

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).

Szyfrowanie wiadomości

Alice przekazuje swój klucz publiczny ( n {displaystyle n } $n\,$ & e {displaystyle e } ) $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} mniejszą od n {styl n} za pomocą uzgodnionego odwracalnego protokołu znanego jako schemat paddingu. Następnie oblicza szyfrogram c {displaystyle c} $c\,$ odpowiadający:

c = m e mod n {{displaystyle c=m^{e}}mod {n}} $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} $c\,$ do Alice.

Odszyfrowanie wiadomości

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

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

Biorąc pod uwagę m, można odzyskać pierwotne liczby pierwsze, a zastosowanie $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}} $m^{ed}\equiv m{\bmod {pq}}$ .

Tak więc,

c d ≡ m mod n {displaystyle c^{d}}equiv m{mod {n}}} $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.

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

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

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

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

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

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

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

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

m = 855 2753 mod 3 233 = 123 {przykład m=855^{2753}{mod {3}}233=123}. $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)}}} $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}}}} $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}}}. $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)}} $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} $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}}} ${\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}} }} $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}} $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.