RSA (kryptografia)

Algorytm Rivesta-Shamira-Adlemana (RSA) – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adiego Shamira oraz Leonarda Adlemana. Pierwszy algorytm, który może być stosowany zarówno do szyfrowania, jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych^[1]. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców^[2].

Opis algorytmu^[2]

Generowanie kluczy

W celu wygenerowania pary kluczy (prywatnego i publicznego) należy posłużyć się algorytmem:

• Wybieramy losowo dwie duże liczby pierwsze p i q (najlepiej w taki sposób, aby obie miały zbliżoną długość w bitach, ale jednocześnie były od siebie odległe wartościami – istnieją lepsze mechanizmy faktoryzacji, jeżeli liczba ma dzielnik o wartości bliskiej ${\displaystyle {\sqrt {n}}}$).
• Obliczamy wartość n = pq.
• Obliczamy wartość funkcji Eulera dla n: ${\displaystyle \varphi (n)=(p-1)(q-1).}$
• Wybieramy liczbę e (1 < e < φ(n)) względnie pierwszą z φ(n).
• Znajdujemy liczbę d, gdzie jej różnica z odwrotnością modularną liczby e jest podzielna przez φ(n):

d ≡ e⁻¹ (mod φ(n)).
Ta liczba może być też prościej określona wzorem:
d⋅e ≡ 1 (mod φ(n)).

Klucz publiczny jest definiowany jako para liczb (n, e), natomiast kluczem prywatnym jest para (n, d).

Szyfrowanie i deszyfrowanie

Zanim zaszyfrujemy wiadomość, dzielimy ją na bloki ${\displaystyle m}$ o wartości liczbowej nie większej niż n, a następnie każdy z bloków szyfrujemy według poniższego wzoru:

${\displaystyle c\equiv m^{e}{\pmod {n}}.}$

Zaszyfrowana wiadomość będzie się składać z kolejnych bloków ${\displaystyle c.}$ Tak stworzony szyfrogram przekształcamy na tekst jawny, odszyfrowując kolejne bloki ${\displaystyle c}$ według wzoru:

${\displaystyle m\equiv c^{d}{\pmod {n}}.}$

Własności operacji szyfrowania i deszyfrowania

Niech ${\displaystyle C_{K_{1}},D_{K_{1}},C_{K_{2}},D_{K_{2}}}$ będą kolejno szyfrowaniem i deszyfrowaniem kluczami K₁ i K₂. Wtedy zachodzi:

• ${\displaystyle C_{K_{1}}\left(C_{K_{2}}(M)\right)=C_{K_{2}}\left(C_{K_{1}}(M)\right)}$ – przemienność operacji szyfrowania,
• ${\displaystyle D_{K_{1}}\left(D_{K_{2}}(M)\right)=D_{K_{2}}\left(D_{K_{1}}(M)\right)}$ – przemienność operacji deszyfrowania.

Ze względów bezpieczeństwa nie powinno się stosować więcej niż 2 zagnieżdżone szyfrowania ze względu na ataki oparte na chińskim twierdzeniu o resztach.

Podpisywanie i weryfikacja podpisu

Analogicznie, RSA może zostać użyte do przeprowadzenia operacji podpisu. W takim przypadku szyfruje się zazwyczaj skrót wiadomości za pomocą klucza prywatnego i propaguje taki szyfrogram wraz z oryginalną wiadomością. Odbiorca posiadający klucz publiczny deszyfruje - otrzymaną z wiadomością - zaszyfrowaną wartość funkcji skrótu, następnie oblicza wartość tejże funkcji z otrzymanej wiadomości. Jeśli obie wartości się zgadzają, przyjmuje się, że wiadomość została podpisana poprawnie.

Próby złamania

Pierwszą udaną faktoryzację RSA zakończono 2 grudnia 1999 roku w ramach konkursu The RSA Factoring Challenge^[3].

Dotychczas największym kluczem RSA, jaki rozłożono na czynniki pierwsze, jest klucz 768-bitowy. Liczby pierwsze zostały znalezione 12 grudnia 2009, a informacje o przeprowadzonej faktoryzacji opublikowano 7 stycznia 2010 roku^[4]. Wykorzystano do tego klaster komputerów; czas zużyty na obliczenia był o 2 rzędy wielkości krótszy od prognozowanego.

Istnieje także szereg ataków na implementacje RSA^[5][6]. Ochrona przed nimi polega na stosowaniu probabilistycznych trybów szyfrowania (OAEP) oraz konstruowania implementacji sprzętowych i programowych w taki sposób, by nie były podatne na ataki czasowe lub manipulacje zasilaniem (sprzętowe).

Potencjalnym zagrożeniem dla RSA jest skonstruowanie komputera kwantowego.

Claus Peter Schnorr w opublikowanym 1 marca 2021^[7] (i poprawionym 9 lipca 2021^[8]) opisie wykorzystania szybkiej faktoryzacji liczb całkowitych za pomocą algorytmów SVP twierdzi, że takie podejście łamie całkowicie kryptografię RSA.

Kwestie patentowe

W Stanach Zjednoczonych algorytm RSA był opatentowany. Patent o numerze 4.405.829 został przyznany Massachusetts Institute of Technology (które było w tym czasie pracodawcą autorów) we wrześniu 1983 roku, następnie wszystkie prawa do tego patentu zostały odsprzedane firmie RSA Data Security (za kwotę 150 000 USD)^[9]. Patent wygasł 21 września 2000 roku.

Przypisy

Bibliografia

• Thomas H. Cormen, Rozdział 31: Algorytmy teorioliczbowe, w: Wprowadzenie do algorytmów, wyd. VII, WNT, Warszawa 2005, s. 902–909.

Linki zewnętrzne

• Opis RSA (pdf)
• RSA Security