Crypto-IT

• Klucz ma zwykle długość od około 1000 do 4000 bitów

RSA jest obecnie jednym z najpopularniejszych algorytmów szyfrowania z kluczem publicznym. Może być stosowany zarówno do szyfrowania wiadomości jak i do podpisów cyfrowych.

RSA został zaprojektowany przez Ron'a Rivest'a, Adi Shamir'a i Leonard'a Adleman'a w roku 1977.

Algorytm RSA umożliwia utworzenie dwóch powiązanych kluczy: publicznego oraz prywatnego, a następnie wykorzystywanie ich w celu ochrony treści przekazywanych wiadomości. Klucz publiczny jest powszechnie znany i każdy może za jego pomocą zaszyfrować dowolną wiadomość. Natomiast jedynie posiadacz klucza prywatnego może odszyfrować otrzymane szyfrogramy.

Analogicznie, posiadacz klucza prywatnego może używać go do szyfrowania danych, pozwalając w ten sposób każdemu posiadaczowi odpowiadającego mu klucza publicznego odszyfrować je.

Bezpieczeństwo szyfrowania RSA opiera się na zagadnieniach faktoryzacji dużych liczb złożonych.

Para powiązanych kluczy algorytmu RSA może być wygenerowana przy użyciu poniższego algorytmu:

1. Wybrać dwie różne liczby pierwsze, zwykle oznaczane jako p oraz q. Liczby powinny być wybrane losowo i składać się z podobnej liczby bitów.
2. Obliczyć:    n = p·q
   Liczba n jest wykorzystywana jako moduł dla kluczy prywatnego i publicznego. Długość n jest długością klucza RSA.
3. Obliczyć wartość funkcji Eulera dla n:
       φ(n) = φ(p)·φ(q) = (p − 1)·(q − 1)
4. Wybrać liczbę całkowitą e, która jest większa od 1 i mniejsza niż poprzednio wyliczona wartość φ(n). Liczby e oraz φ(n) powinny być względnie pierwsze. Liczba e jest używana jako wykładnik klucza publicznego.
5. Wyznaczyć liczbę d taką, że:    d·e = 1  (mod φ(n))
   Liczba d jest używana jako wykładnik klucza prywatnego.

Klucz publiczny składa się z modułu n i publicznego wykładnika e, natomiast klucz prywatny składa się z tego samego modułu n i prywatnego wykładnika d. Wszystkie liczby powiązane z kluczem prywatnym powinny być trzymane w tajemnicy: obie liczby n i d oraz trzy kolejne: p, q i φ(n), które mogą być użyte do wyliczenia d.

Wielu użytkowników może współdzielić wartość e. Zaleca się żeby jej długość była stosunkowo krótka, z racji tego, że od jej długości znacząco zależy złożoność obliczeń podczas szyfrowania wiadomości. Często przyjmowaną wartością liczby e jest liczba pierwsza 2¹⁶+1 (czyli 65537). Możliwe jest użycie również dużo mniejszych liczb (na przykład 3), ale w pewnych okolicznościach powoduje to osłabienie jakości zabezpieczeń.

Każdy użytkownik powinien mieć przypisaną własną liczbę n (która bierze się z iloczynu dwóch liczb pierwszych).

Szyfrowanie odbywa się za pomocą klucza publicznego (n, e). Wiadomość musi zostać podzielona na części, a następnie każda część powinna zostać zmieniona na liczbę (która musi być większa od 0 i mniejsza niż n). W praktyce dzieli się wiadomość na fragmenty, z których każdy składa się z określonej ilości bitów.

Następnie każda liczba wchodząca w skład wiadomości jest podnoszona modulo n do potęgi równej e:
    c_i = m_i^e  (mod n)

Algorytmu RSA można użyć wielokrotnie (przy zastosowaniu różnych kluczy) do zaszyfrowania danej wiadomości, a następnie odszyfrować ją w dowolnej kolejności. Otrzymany wynik będzie zawsze taki sam, bez względu na kolejność operacji. Jednakże, nie należy szyfrować w ten sposób wiadomości więcej niż dwa razy, ponieważ ujawniają się wtedy podatności na ataki oparte na chińskim twierdzeniu o resztach.

Szyfrowanie może zostać przeprowadzone również przy użyciu klucza prywatnego. Cała procedura jest identyczna do opisanej powyżej, z różnicą, że do szyfrowania trzeba będzie użyć klucza prywatnego (n, d). Natomiast odbiorca wiadomości będzie musiał użyć odpowiadającego mu klucza publicznego, w celu odszyfrowania wiadomości.

Deszyfrowanie odbywa się za pomocą klucza prywatnego (n, d).

Szyfrogram składa się z kolejnych liczb, mniejszych niż n. Każda liczba wchodząca w skład szyfrogramu jest podnoszona modulo n do potęgi równej d:
    m_i = c_i^d  (mod n)

Otrzymywane liczby tekstu jawnego należy połączyć w odpowiedniej kolejności, aby utworzyły oryginalną wiadomość.

Jeżeli wiadomość została zaszyfrowana za pomocą klucza prywatnego, to w celu odszyfrowania wiadomości trzeba będzie użyć odpowiadającego mu klucza publicznego. Procedura deszyfrowania jest identyczna do opisanej powyżej, z różnicą, że używany jest klucz publiczny (n, e).

RSA może być zastosowane do podpisywania wiadomości. Nadawca musi wyliczyć wartość skrótu wiadomości, a następnie podnieść ją do potęgi d (modulo n), a więc wykonać te same operacje jak podczas zwykłego dekodowania szyfrogramów. Zakodowana w ten sposób wartość skrótu powinna zostać załączona do wysyłanej wiadomości.

Odbiorca wiadomości powinien podnieść zakodowaną wartość skrótu do potęgi e (modulo n), a następnie porównać wynik z wartością skrótu wyliczoną przez siebie. Jeżeli obie wartości są takie same, to można mieć pewność, że nikt nie zmodyfikował treści wiadomości.

W przypadku użycia małego wykładnika e (przykładowo równego 4) do zaszyfrowania małej wartości m (mniejszej niż n^1/e), otrzymana liczba szyfrogramu będzie miała wartość mniejszą niż wynosi wartość modułu n. Umożliwia to wyznaczenie wartości m przy użyciu zwykłych operacji arytmetycznych, co jest czynnością nieskomplikowaną i szybką.

Żeby wykluczyć zastosowanie algorytmu RSA do szyfrowania zbyt małych liczb tekstu jawnego, zaleca się stosowanie losowych dopełnień (ang. padding), które odpowiednio zwiększają wartość tych liczb. Losowe dopełnienia gwarantują również, że takie same liczby tekstu jawnego będą kodowane przy użyciu zmieniających się liczb szyfrogramu. Istnieje wiele popularnych schematów dopełnień, na przykład OAEP, PKCS#1 lub RSA-PSS.

Algorytm RSA jest deterministyczny, wobec tego szyfr ten jest podatny na ataki z wybranym tekstem jawnym. Można zaszyfrować wiele wiadomości za pomocą znanego klucza publicznego, więc napastnik może odgadnąć zawartość wcześniej przechwyconych zaszyfrowanych wiadomości, przez porównywanie ich z wiadomościami utworzonymi przez siebie.

Inną cechą RSA jest fakt, że szyfrogram iloczynu liczb dwóch tekstów jawnych jest taki sam jak iloczyn dwóch szyfrogramów, które odpowiadają tym tekstom.

RSA jest generalnie uważany za bezpieczny system zabezpieczeń i jest powszechnie stosowany w przeróżnych aplikacjach, protokołach i rodzajach komunikacji.

Wartość funkcji Eulera dla dodatniej liczby całkowitej n, oznaczana jako φ(n), jest określona jako ilość liczb całkowitych dodatnich, mniejszych lub równych n, które są względnie pierwsze z liczbą n.

Jeżeli n jest dodatnią liczbą całkowitą, to φ(n) jest równe liczbie takich liczb całkowitych k, że k jest nie mniejsze niż 1 i nie większe niż n oraz, że liczby n oraz k są względnie pierwsze.

Funkcja Eulera jest funkcją multiplikatywną. Oznacza to, że dla każdych dwóch względnie pierwszych liczb a oraz b zachodzi zależność:
    φ(a·b) = φ(a)·φ(b).

Podnoszenie do potęgi liczby naturalnej modulo liczba naturalna jest jedną z podstawowych operacji w kryptografii. Podlega ono ogólnym prawom rządzącym arytmetyką modulo. Wykładnik, podobnie jak podstawa, jest dodatnią liczbą całkowitą. Dodatnią liczbą całkowitą jest również wynik działania.

Działanie podnoszenia do potęgi modulo można przedstawić jako szereg działań polegających na podnoszeniu do kwadratu i dzieleniu kolejnych wyników przez ustaloną liczbę naturalną.

Przykładowo podniesienie liczby 4 do potęgi 9 modulo 7 można obliczyć w następujący sposób:
    4⁹ mod 7:
    4² mod 7 = 16 mod 7 = 2
    4⁴ mod 7 = 2² mod 7 = 4 mod 7 = 4
    4⁸ mod 7 = 4² mod 7 = 16 mod 7 = 2
    4⁹ mod 7 = (4¹ mod 7 * 4⁸ mod 7) mod 7 = 4 * 2 mod 7 = 1

W przeciwieństwie do zwykłego podnoszenia do potęgi, potęgowanie w arytmetyce modularnej jest działaniem trudnym i nie istnieją wydajne algorytmy przeprowadzania operacji odwrotnej.