RSA (kryptografia)

RSA – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adi 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. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.

Opis algorytmu

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 $\sqrt n$)
• Obliczamy wartość n = pq
• Obliczamy wartość funkcji Eulera dla n: $\varphi(n) = (p - 1)(q - 1)$
• Wybieramy liczbę e (1 < e < φ(n)) względnie pierwszą z φ(n)
• Znajdujemy liczbę d odwrotną do e mod φ(n):
  $d = e^{-1} \mbox{ mod } \varphi(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 $m_{i}$ o wartości liczbowej nie większej niż n, a następnie każdy z bloków szyfrujemy według wzoru:

$c_{i} = m_{i}^e \mod n$

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

$m_{i} = c_{i}^d \mod n$.

Możliwe jest także zaszyfrowanie wiadomości za pomocą klucza tajnego d, a następnie jej odszyfrowanie za pomocą klucza publicznego e. To właśnie ta własność sprawia, że RSA może zostać wykorzystany do cyfrowego podpisywania dokumentów.

Próby złamania

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

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 informację o przeprowadzonej faktoryzacji opublikowano 7 stycznia 2010 roku. 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. 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.

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). Patent wygasł 21 września 2000 roku.

Bibliografia

• Thomas H. Cormen. Rozdział 31. Algorytmy Teorioliczbowe we Wprowadzenie do algorytmów. Wyd. VII. Warszawa, 2005 WNT, s. 902 – 909

Linki zewnętrzne

• Opis RSA (pdf)
• RSA Security