Kryptografia – RSA

Wstęp


Zgodnie z tym co obiecałem kolejnym artykułem z dziedziny kryptografii będzie RSA, czyli jeden z najpopularniejszych systemów szyfrowania z jakich korzystamy każdego dnia (chociaż w sposób nieświadomy). Jednak na początku warto poznać nieco poznać jego historię.

Nazwa RSA pochodzi od pierwszych liter nazwisk jego drugich odkrywców (pierwsza implementacja została utajniona zaraz po opatentowaniu tego algorytmu):  Rona Rivesta, Adi Shamira oraz Leonarda Adlemana, którzy go także spopularyzowali.

RSA jest algorytmem niesymetrycznym co oznacza, że do szyfrowania i deszyfrowania potrzebne są różne klucze, jak wspominałem we wcześniejszym artykule o protokole Diffiego-Hellmana RSA jest jego ulepszoną wersją, ponieważ także i tu siła algorytmu opiera się na problematyczności faktoryzacji dużych liczb pierwszych.

 

RSA


Jak wspominałem (może w sposób nieco niejawny) RSA posiada pewną przewagę nad protokołem Diffiego-Hellmana teraz nieco im się przyjrzymy.

  • Jedną z pierwszych zalet jest fakt, że ten sposób szyfrowania nie wymaga komunikacji pomiędzy dwoma stronami w celu uzgodnienia wspólnego klucza.
  • Kolejnym ważnym faktem jest to że RSA jest szyfrem niesymetrycznym co oznacza, że do procesu szyfrowania i deszyfrowania używa się innych kluczy, z których 1 jest powszechnie znany.
  • Ostatnią ciekawą cechą jest to, że jeżeli chcemy aby wiele osób mogło nam wysłać jakąś wiadomość (zaszyfrować ją) to nie musimy z każdą tych osób uzgadniać specjalnych kluczy, lecz wystarczy tylko 1 – wspólny (publiczny).

 

Przykład na kolorach

Działanie RSA znowu pokażemy sobie na przykładzie kolorów, co powinno nam nieco ułatwić zrozumienie tego mechanizmu zanim ten proces sobie sformalizujemy.

  1. Pierwsza osoba (niech to będzie Alicja) generuje swój klucz prywatny poprzez wybranie losowo koloru i niech to będzie czerwony. Następnie Alicja używając urządzenia, które generuje kolor dopełniający do jej czerwonego (czyli taki kolor, który po połączeniu  czerwonym utworzy biały kolor).
  2. Dostała cyjan, który wysyła Bobowi i to jest jej klucz publiczny, załóżmy że Bob chce wysłać jej tajny odcień żółtego w następujący sposób: miesza swój żółty z jej kluczem publicznym i wysyła jej nowo powstały kolor.
  3. Alicja gdy wymiesza swój klucz prywatny z odebranym kolorem od Boba otrzyma tajny kolor Boba.

Widzimy tutaj znaną nam z protokołu Hellmana zależność: łatwość wykonania w jedną stronę (zaszyfrowania) i problem odszyfrowania wiadomości gdy nie znamy klucza prywatnego, jeżeli żyjemy dalej na przykładzie z kolorami (i zakładamy że kolory są w systemie RGB) to samych kluczy prywatnych istnieje 256^3 (wartości 0-255).

 

Matematyczny punkt widzenia

Tutaj znowu posłużymy się działaniem modulo, które jak widzimy jest dość przydatne z oczywistego powodu: łatwe do wykonania trudne do odwrócenia szczególnie przy dużych liczbach (no do czasu aż ktoś znajdzie wzór liczący liczby pierwsze).

W dalszej części będziemy korzystali z funkcji Eulera, zdaję sobie sprawę, że nie każdy wie czym to jest więc pobieżnie o tym sobie opowiemy. φ(n) wypisuje ilość liczb, różnych od n i nie mających z nią wspólnych dzielników. W przypadku liczb pierwszych zachodzi taka zależność: φ(n) = n-1.

Z racji, że ta funkcja jest multiplikatywna [ φ(A*B) = φ(A) * φ(B) ], to możemy zauważyć że to daje nam funkcję, która jest łatwa do wykonania w 1 stronę, a w drugą jest za bardzo złożona obliczeniowo (mnożenie liczb jest szybsze niż rozkładanie liczby na czynniki pierwsze). Więc zachodzi coś takiego:

φ(n) = φ(p1-1) * φ(p2-1)

 

Więc jeśli mamy jakąś liczbę pierwszą i znamy jej rozkład na liczby pierwsze, np. 65 = 5 * 13, to wiemy, że φ(65) = 4*12 = 48.

Zróbmy to od razu na przykładzie, załóżmy, że Bob ma wiadomość m, którą przekształcił w liczbę (m=89), Alicja generuje liczby pierwsze p1 = 53, p2 = 59. Po czym tworzy liczbę n poprzez przemnożenie p1 i p2 (n=3127) i łatwo oblicza φ(n) = 3016. Następnie wybiera mały wykładnik publiczny e = 3, taki że jest to liczba nieparzysta i nie mająca wspólnego dzielnika z φ(n). Kolejnym krokiem znalezienie prywatnego wykładnika d = (k * φ(n) + 1)/e = (2*3016 + 1)/3 = 2011.

Następnie chowamy wszystkie liczby poza wartościami n i e, które tworzą klucz publiczny.

Bob szyfruje swoją wiadomość poprzez policzenie c = m^e mod n = 1394 i wysyła to do Alicji, która deszyfruje ją: c^d =

 

Algorytm

  1. Generujemy 2 liczby pierwsze p1 i p2; następnie tworzymy liczbę n = p1*p2 (pozbywamy się liczb p1 i p2).
  2. Wybieramy losowo liczbę e, taką że eφ(n) są względnie pierwsze.
  3. Za pomocą algorytmu Euklidesa tworzymy liczbę d = (1 mod φ(n))/e.
  4. Klucz publiczny to (e,n), klucz prywatny to (d,n).
  5. Szyfrowanie liczby m < n, odbywa się w następujący sposób:
    E(m) = m^e mod n
  6. Deszyfrowanie liczby c, odbywa się w następujący sposób:
    D(c) = c^d mod n

 

Posłowie


Użyteczność (czy też trudność złamania) RSA niewątpliwie zwiększają bardzo duże liczby, a o sposobach jak takie duże liczby sobie wygenerować opowiemy sobie w przyszłości.

Implementacja RSA chyba nie będzie konieczna, przynajmniej na razie ponieważ powyżej pokazany algorytm powinien być dość prosty w zrozumieniu.

Jak zwykle zachęcam do komentowania, wyszukiwania ewentualnych błędów, które mogły się pojawić z racji że ten artykuł był pisany o różnych porach, zapraszam także na twittera.