RSA — definicja algorytmu szyfrowania z kluczem publicznym

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

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} do Alice.

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

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

Biorąc pod uwagę m, można odzyskać pierwotne liczby pierwsze, a zastosowaniechiń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}} .

Tak więc,

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

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

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

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

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

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

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

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

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

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

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

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}}}}

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

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

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

e d = k × ϕ ( n ) + 1 {displaystyle ed=krotność \i(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}}}

Stosujemy twierdzenie Eulera i otrzymujemy wynik.

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

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

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.