Czym jest szyfr RSA?

Już wiesz

W wypadku szyfrowania asymetrycznego korzysta się z dwóch kluczy: publicznego do szyfrowania wiadomości oraz prywatnego – do odszyfrowania.

Nazwa szyfru RSA to skrót od nazwisk trzech profesorów z Massachusetts Institute of Technology w USA, którzy w 1977 r. opublikowali ten algorytm. Byli to Ronald L. Rivest, Adi Shamir i Leonard Adleman.

Szyfr RSA to asymetryczny algorytm kryptograficzny. Posiada parę kluczy – publiczny (e, n) oraz prywatny (d, n).
Postępowanie z użyciem asymetrycznego szyfrowania można sprowadzić do następujących kroków:

  • Każda osoba, która chce otrzymać zaszyfrowaną wiadomość, „wystawia” na publiczny widok swój klucz publiczny.

  • Osoba chcąca wysłać wiadomość szyfruje ją wykorzystując klucz publiczny osoby, do której chce ją wysłać.

  • Osoba, która odbiera wiadomość, odszyfrowuje ją z użyciem swojego klucza prywatnego. Nikt, kto nie posiada klucza prywatnego, nie jest w stanie odszyfrować wiadomości.

Jak wyznaczyć klucz prywatny i publiczny?

  1. Wybieramy dwie dowolne liczby pierwsze i oznaczamy je jako pq. Liczby te powinny być możliwie jak największe.

  2. Obliczamy wartość n = p • q. Wartość n jest elementem klucza publicznego i prywatnego, określa również największą możliwą wielkość liczbową wysyłanej przez nas wiadomości.

  3. Wyliczamy wartość funkcji Eulera dla n i wybieramy dowolną liczbę e spełniającą warunek (1 < e < phi(n)), która będzie względnie pierwsza do wartości phi(n).
    Liczba e jest elementem klucza publicznego.

  4. Obliczamy odwrotność modulo phi(n) liczby e i otrzymujemy liczbę d, która jest elementem klucza prywatnego.

Po zrealizowaniu wszystkich czterech kroków możemy szyfrować i deszyfrować wiadomości zgodnie z następującymi funkcjami:

f(W)=Wemod n

oraz:

f1(S)=Sd mod n

– gdzie  to wiadomość w postaci liczbowej, będąca mniejsza od , a  to szyfrogram wiadomości, którą chcemy odszyfrować.

Ważne!

Jeżeli zależy ci na prywatności, nikomu nie podawaj choćby jednej spośród liczb pierwszych p oraz q ani wartości funkcji Eulera. Wykładnik publiczny jest powszechnie znany, więc gdy ktoś pozna również wartość phi(n), może poznać klucz prywatny i złamać szyfr.

Dlaczego p i q muszą być liczbami pierwszymi?

Bezpieczeństwo szyfrowania RSA opiera się na trudności faktoryzacji liczbfaktoryzacja liczbfaktoryzacji liczb. Faktoryzacja liczby będącej iloczynem liczb pierwszychliczba pierwszaliczb pierwszych, jest bardziej złożona niż faktoryzacja liczb będących iloczynem liczb złożonych. Stąd też p i q muszą być pierwsze.

funkcja Eulera
Definicja: funkcja Eulera

Funkcja Eulera phi(n) to funkcja przypisująca każdej liczbie naturalnej liczbę liczb względnie pierwszych z nią i nie większych od niej.

Drugim powodem tego stanu rzeczy, jest to, że dla liczb pierwszych funkcja Eulera przyjmie następującą postać:

φ(n) = φ(pq)  = φ(p)  φ(q)   = (p1 )(q1)

Korzystamy tu z następującej właściwości funkcji Eulera:

Jeśli x jest liczbą pierwszą to:

φ(xk)  = xk1  (x1)

– gdzie p i q to liczby pierwsze o wykładniku równym 1.
Gdyby p i q nie byłyby liczbami pierwszymi, to funkcja Eulera przyjęłaby dużo bardziej złożoną postać, przez co obliczenie jej stałoby się obiektywnie trudniejsze, co w praktycznych zastosowaniach byłoby niekorzystne. Jest to jednak powód drugorzędny.

Załóżmy, że chcemy poznać czyjś klucz prywatny. Klucz publiczny tej osoby jest znany i przyjmuje np. takie wartości: e = 3n = 33. Z racji tego, że n jest niewielkie, możemy bez większego problemu – przy użyciu tzw. metody brutalnej (siłowej) – ustalić, że p = 11q = 3. Tutaj należy zwrócić uwagę, że nie istnieje inna niż 11 i 3 kombinacja liczb, która po pomnożeniu dałaby wynik 33.

Przyjmijmy, że n = 2501. Istnieje tylko jedna kombinacja liczb, których iloczyn wynosi dokładnie tyle, ponieważ zmienne p i q są liczbami pierwszymi. Próba odnalezienia czynników pierwszych metodą brutalną w przypadku n = 2501 jest już bardziej złożona obliczeniowo. Korzystając z niej, musielibyśmy wykonać 40 razy operację dzielenia, zanim odnaleźlibyśmy pierwszy czynnik pierwszy, czyli w tym przypadku p równego 41. W tym przykładzie q jest równe 61.

Ważne!

Odnalezienie wartości p i q powinno być w miarę możliwości trudne, dlatego też muszą być one podobnego rzędu, ponieważ nawet jeżeli n=11485, to korzystając z metody brutalnej, bardzo szybko otrzymamy czynnik pierwszy p=5, a wtedy obliczenie drugiego czynniku nie stanowi już problemu, ponieważ wystarczy podzielić liczbę n przez 5.

Dla porównania załóżmy teraz, że n = 6840. Liczbę 6840 możemy otrzymać poprzez pomnożenie np. 3420 przez 2, 1710 przez 4, czy też 684 przez 10. Istnieje wiele kombinacji liczb złożonych, dzięki której otrzymalibyśmy wartość takiego n.
Reasumując: jeśli p i q nie są pierwsze, to jesteśmy w stanie rozbić liczbę n na wiele czynników pierwszych. Wtedy, pomimo tego, że obliczenie funkcji Eulera staje się potencjalnie dużo bardziej złożone obliczeniowo, to odnalezienie wszystkich czynników pierwszych jest prostsze, a bezpieczeństwo samego szyfrowania opiera się właśnie na trudności rozkładu liczby n na czynniki pierwsze. Gdy p i q nie są pierwsze, to możemy skorzystać z innego wzoru na obliczanie funkcji Eulera, a mianowicie:

φ(n)  =n(11p1)(11p2)....(11pk)

- gdzie pIndeks dolny 1, pIndeks dolny 2, ..., pIndeks dolny k są czynnikami pierwszymi bez powtórzeń.
Przykładowo, dla liczby 32 jedynym czynnikiem pierwszym byłoby 2, podobnie jak dla liczby 1024 lub 8192. Wtedy:

φ ( 8192 )     = 8192 ( 1 1 2 )   =   4096

Jeżeli próbowalibyśmy metodą brutalną odnaleźć wszystkie czynniki pierwsze liczby 8192, to odnaleźlibyśmy je bardzo szybko, ponieważ mimo tego, że liczba ta jest większa niż 2501, dużo prościej się rozkłada.

W przypadku liczb będących iloczynem liczb złożonych jesteśmy w stanie dużo szybciej znaleźć wszystkie czynniki pierwsze metodą brutalną. Aby odnaleźć czynnik pierwszy liczby będącej iloczynem dwóch liczb pierwszych metodą brutalną, musimy w praktyce przeszukać dużo więcej liczb, ponieważ w jej przypadku są tylko dwa czynniki pierwsze.

Jeśli wejdziemy w posiadanie czynników pierwszych, będziemy mogli obliczyć funkcję Eulera, a następnie na tej podstawie będziemy w stanie obliczyć odwrotność modulo e liczby phi(n). Wtedy też nasz klucz zostałby złamany.

Ważne!

Bezpieczeństwo RSA opiera się na trudności faktoryzacji liczb. Dlatego też, jak zostało wyjaśnione, p i q muszą być liczbami pierwszymi podobnego (i możliwie dużego) rzędu, aby trudność ta była jak największa.

Aby obliczyć odwrotność modulo, również należy posługiwać się liczbami pierwszymi.

Odwrotność modulo

odwrotność modularna
Definicja: odwrotność modularna

Odwrotność modularna to operacja polegająca na odnalezieniu dla dowolnej pary a mod b takiego , że a  x mod b = 1.

Alternatywnie możemy to zapisać jako x   =   a 1   m o d   b.

Obliczenie odwrotności modulo można przeprowadzić na wiele sposobów, ale żaden z nich nie ma złożoności wielomianowej. Najprostszą metodą jest metoda naiwna polegająca na podstawianiu pod x kolejnych wartości, dopóki nie uzyska się poprawnego wyniku.

Dobrym wyborem jest skorzystanie z rozszerzonego algorytmu Euklidesa.

Ważne!

Rozszerzona wersja algorytmu Euklidesa pozwala odnaleźć kombinację liniową liczb, zgodnie z następującym wzorem:

a  x + b  y = NWD(a,b)

- gdzie liczba x jest odwrotnością modulo b liczby a, pod warunkiem, że liczby a i b są względnie pierwsze. Jest to wspomniana wcześniej zależność mówiąca o tym, że aby obliczyć odwrotność modulo, należy operować na liczbach względnie pierwszych, ponieważ tylko liczby względnie pierwsze mają odwrotność modularną.

Załóżmy, że chcemy obliczyć odwrotność modulo 5 liczby 2. W tym celu musimy więc rozwiązać następujące działanie:

2  x mod 5 = 1

Następnie należy odnaleźć x.

Przeprowadzimy to przy użyciu metody brutalnej:
2 ∙ 1, czyli 2 modulo 5 = 2
2 ∙ 2, czyli 4  modulo 5 = 4
2 ∙ 3, czyli 6 modulo 5 = 1

Zatem pod x możemy wstawić 3.

Nie jest to jednak jedyne rozwiązanie – próbując dalej, będziemy odnajdywać kolejne możliwe wartości x:
2 ∙ 4, czyli 8 modulo 5 = 3
2 ∙ 5, czyli 10 modulo 5 = 0
2 ∙ 6, czyli 12 modulo 5 = 2
2 ∙ 7, czyli 14 modulo 5 = 4
2 ∙ 8, czyli 16 modulo 5 = 1

Zatem pod x można również podstawić 8.

Czy wybór składnika d w kluczu prywatnym ma znaczenie?

Udowodniliśmy, że modulo 5 liczby 2 ma co najmniej dwa rozwiązania – prawda jest jednak taka, że rozwiązań tych jest nieskończenie wiele. Czy istnieje jednak najlepszy wybór wyniku dla klucza prywatnego?

Zaprezentowane wyżej szyfrowanie ma następującą postać:

f(W)=Wemod n

a z kolei deszyfrowanie będzie miało taką postać:

f1(S)=Sd mod n
Przykład 1

Przyjmijmy następujące dwie liczby pierwsze:
p = 3
q = 5
Zatem:
n = 3 • 5 = 15

φ(n)=φ(15)=φ(35)=(31)(51) = 2  4 = 8

Wybieramy liczbę względnie pierwszą z przedziału (1, 8).
Może to być chociażby liczba 3, więc przyjmijmy e = 3.
Następnie obliczamy odwrotność modulo phi(n) liczby e, czyli:
e • x mod phi(n) = 1, co z kolei po podstawieniu wartości liczbowej daje nam:
3 • x mod 8 = 1.

Z racji tego, że liczby są małe, możemy skorzystać z metody brutalnej:
(3 • 1) mod 8 = 3
(3 • 2) mod 8 = 6
(3 • 3) mod 8 = 1
(3 • 4) mod 8 = 4
(3 • 5) mod 8 = 7
(3 • 6) mod 8 = 2
(3 • 7) mod 8 = 5
(3 • 8) mod 8 = 0
(3 • 9) mod 8 = 3
(3 • 10) mod 8 = 6
(3 • 11) mod 8  = 1

Odwrotnością modulo 8 liczby 3 będzie więc m.in. 3 i 11.
Wartość 3 lub 11 jest też naszą wartością d w kluczu prywatnym.

Liczba, którą chcemy zaszyfrować, musi być mniejsza od n, które w naszym wypadku wynosi 15. Wybierzmy więc liczbę 13.

f(13)=133mod 15 = 2197 mod 15 = 7

Teraz odszyfrujmy wiadomość, korzystając po kolei z 3 i 11 jako wartości d.

f 1 ( 7 ) = 7 3   m o d   15   = 343   m o d   15   =   13
f 1 ( 7 ) = 7 11   m o d   15   = 1977326743   m o d   15   =   13

Na zaprezentowanym powyżej przykładzie widać, że dla poprawności algorytmu nie ma znaczenia, jaką liczbę wybierzemy jako d, dopóki będzie ona odwrotnością modulo phi(n) liczby e. Z obliczeniowego punktu widzenia najkorzystniejszą decyzją jest wybranie mniejszego d, jednakże d nie powinno być równe e. Należy unikać sytuacji, w których klucz prywatny i klucz publiczny posiada takie same wartości, ponieważ byłaby to słabość, która mogłaby zostać wykorzystana przez naszego potencjalnego przeciwnika. W tym przypadku najlepszym wyborem, ze względu na bezpieczeństwo, byłoby więc wybranie d równego 11.

Dlaczego szyfrowanie i deszyfrowanie działa?

Poniższa funkcja:

f(W)=Wemod n

oraz funkcja odwrotna:

f1(S)=Sd mod n

służą kolejno do szyfrowania i deszyfrowania, a zasada ich działania opiera się na arytmetyce modularnej, którą można wyjaśnić na przykładzie zegara.

RSuZwsnNvl2rd
Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Zegar wskazuje godzinę trzecią – dla przykładu załóżmy, że interesuje nas jedynie zachowanie wskazówki godzinowej. Mija 12 godzin – zegar ponownie wskazuje godzinę trzecią. Czy czas stanął w miejscu? Czy jest to ta sama godzina trzecia, co 12 godzin temu? Oczywiście, że nie.

Stwierdzenie więc, że 3 + 12 = 3 jest niepoprawne, ponieważ godziny te nie są sobie równe, lecz są do siebie przystające. W matematyce operację przystawania zapisujemy tak:

Możemy też zapisać tę relację w nastepujący sposób:

[ a ] n = [ b ] n
przystawanie
Definicja: przystawanie

Przystawanie (inaczej: kongruencja) modulo n to sytuacja, w której reszty z dzielenia przez są równe (wówczas zachodzi równanie: a % n = b % n, co można zapisać też jako [a]Indeks dolny n = [b]Indeks dolny n).

Przedstawiona wcześniej reguła z zegarem matematycznie prezentowałaby się więc tak:

[ 3 + 12 ] 12 = [ 3 ] 12

Operacja szyfrowania i deszyfrowania opiera się na następującej zasadzie:

[ a e ] n   =   [ ( [ a e ] n ) d ] n

Dlatego też wysyłana przez nas wiadomość w postaci liczbowej musi być mniejsza od n, ponieważ wtedy nawet dla e = 1d = 1 wiadomość, którą chcemy wysłać, byłaby różna od tej, którą finalnie otrzymamy.

Dla zainteresowanych

Jeśli interesuje cię temat nietypowej arytmetyki, w której 12 + 3 może być równe 3, warto zapoznać się z pojęciem struktury algebraicznej, a przede wszystkim grupy oraz pierścienia.

Teoria a praktyka

Im większe liczby pierwsze p i q, tym trudniej jest odgadnąć choćby jedną z nich. Można tu sobie zadać zasadne pytanie: skoro atakujący wie, że korzystamy jedynie z liczb pierwszych, to czemu nie odnajdzie wszystkich liczb pierwszych i nie sprawdzi po prostu wszystkich kombinacji?

Głównym problemem takiej strategii jest fakt, że liczb pierwszych jest nieskończenie wiele, zatem chcąc przeciwdziałać metodzie brutalnej, powinniśmy za nasze p i q przyjąć możliwie jak największe liczby pierwsze, które są podobnych rzędów wielkości. Właśnie dlatego w praktycznych zastosowaniach używa się kluczy mających po kilkaset bitów (dla przypomnienia: liczba mająca 64 bity może mieć maksymalnie wartość 18 446 744 073 709 551 615).

Jak już powiedzieliśmy, liczb pierwszych jest nieskończenie wiele. Największą znaną i potwierdzoną liczbą pierwszą na dzień 21.06.2020 jest liczba składająca się z 22 338 618 cyfr.

Wzór na oszacowanie liczby liczb pierwszych pomiędzy 0 a x to:

x ln   x

Błąd dla x = 50000 wynosi jedynie 0,6% i dla większych wartości tylko się zmniejsza.
Czyli liczb pierwszych do liczby 50000 jest około 4621 +/- 0,6%.

Słownik

liczba pierwsza
liczba pierwsza

liczba naturalna większa od 1, mająca tylko dwa dzielniki: 1 oraz siebie samą (przykładowo: 2, 3, 5, 7, 11)

liczba złożona
liczba złożona

liczby złożone to liczby naturalne, które posiadają więcej niż dwa dzielniki. (przykładowo: 6, 9, 12, 14)

szyfrogram
szyfrogram

zaszyfrowana wiadomość

faktoryzacja liczb
faktoryzacja liczb

inaczej rozkład na czynniki pierwsze