RSA (kryptografia)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[1].

Opis algorytmu[1][edytuj | edytuj kod]

Generowanie kluczy[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.

Własności operacji szyfrowania i deszyfrowania[edytuj | edytuj kod]

Niech C_{K_1},D_{K_1},C_{K_2},D_{K_2} będą kolejno szyfrowaniem i deszyfrowaniem kluczami K1 i K2. Wtedy zachodzi:

  • C_{K_1} \left (C_{K_2}(M) \right ) = C_{K_2} \left (C_{K_1}(M) \right) - przemienność operacji szyfrowania
  • 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[edytuj | edytuj kod]

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 jest w stanie zdeszyfrować wartość funkcji skrótu oraz porównać ją z wyliczoną wartością tejże funkcji z otrzymanej wiadomości. Jeśli obie wartości się zgadzają, to przyjmuje się, że wiadomość została podpisana poprawnie.

Próby złamania[edytuj | edytuj kod]

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

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[3]. 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[4][5]. 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[edytuj | edytuj kod]

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

Przypisy

  1. 1,0 1,1 Bruce Schneier: Kryptografia dla praktyków: protokoły, algorytmy i programy źródłowe w języku C. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 572-581. ISBN 83-204-2678-2.
  2. The RSA Factoring Challenge (ang.). [dostęp 2010-03-02]., kiedy odtworzono liczby użyte do stworzenia 140-bitowych kluczy
  3. Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Joppe W. Bos, Pierrick Gaudry, Alexander Kruppa, Peter L. Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev and Paul Zimmermann, Factorization of a 768-bit RSA modulus
  4. Andrea Pellegrini, Valeria Bertacco, Todd Austin: [http://www.eecs.umich.edu/~valeria/research/publications/DATE10RSA.pdf FaultBased Attack of RSA Authentication]. 2010.
  5. Daniel Bleichenbacher: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. 1998.
  6. Steven Levy: Rewolucja w kryptografii. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 143. ISBN 83-204-2757-6.

Bibliografia[edytuj | edytuj kod]

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

Linki zewnętrzne[edytuj | edytuj kod]