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]
[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 ).
- Obliczamy wartość n = pq.
- Obliczamy φ(n)=(p-1)(q-1)
- Wybieramy liczbę e (1 < e < φ(n)) względnie pierwszą z φ(n).
- Znajdujemy liczbę d, która jest odwrotnością modularną liczby e, tj. iloczyn liczby d przez e dzielony przez φ(n) daje jedynkę:
d⋅e ≡ 1 (mod φ(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 o wartości liczbowej nie większej niż n, a następnie każdy z bloków szyfrujemy według poniższego wzoru:
Zaszyfrowana wiadomość będzie się składać z kolejnych bloków Tak stworzony szyfrogram przekształcamy na tekst jawny, odszyfrowując kolejne bloki według wzoru:
Własności operacji szyfrowania i deszyfrowania
[edytuj | edytuj kod]Niech będą kolejno szyfrowaniem i deszyfrowaniem kluczami K1 i K2. Wtedy zachodzi:
- – przemienność operacji szyfrowania,
- – 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 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
[edytuj | edytuj kod]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
[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)[9]. Patent wygasł 21 września 2000 roku.
Przypisy
[edytuj | edytuj kod]- ↑ RSA, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-10-04] .
- ↑ a b 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.
- ↑ The RSA Factoring Challenge. [dostęp 2010-03-02]. [zarchiwizowane z tego adresu (2013-07-27)]. (ang.)., kiedy odtworzono liczby użyte do stworzenia 140-bitowych kluczy.
- ↑ 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.
- ↑ Andrea Pellegrini, Valeria Bertacco, Todd Austin: FaultBased Attack of RSA Authentication. 2010.
- ↑ Daniel Bleichenbacher: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. 1998.
- ↑ Claus Peter Schnorr , Fast Factoring Integers by SVP Algorithms [online], 2021 [dostęp 2021-03-03] .
- ↑ Claus Peter Schnorr , Fast Factoring Integers by SVP Algorithms, corrected [online], 2021 [dostęp 2022-12-11] .
- ↑ 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, w: Wprowadzenie do algorytmów, wyd. VII, WNT, Warszawa 2005, s. 902–909.