dodany: 12.03.2013 | tagi: , ,

Autor:

Klucz publiczny RSA – jak to działa?

2

Większość kryptografii klucza publicznego oparta jest na trudności matematycznej. Równania matematyczne wykorzystywane do tworzenia kluczy publicznych są tak skomplikowane, że nawet jeśli ktoś z ciekawości spojrzał na strony Wikipedii na temat niektórych sposobów szyfrowania, to z pewnością przewraca mu się oczach, w głowie się kręci i nie do końca wie na co patrzy. Postaramy się wyjaśnić w możliwie przystępny sposób w  jak działają takie algorytmy.

 

Przyjrzyjmy się RSA

Nazwa algorytmu wzięła się od pierwszych liter nazwisk twórców – Rona Rivesta, Adi Shamira i Leonarda Adlemana. Opublikowany został w 1977 roku i jest powszechnie używany do dzisiaj. RSA składa się z trzech części:

  • generowania klucza,
  • szyfrowania,
  • i deszyfrowania.

W pierwszym etapie tworzona jest para kluczy – prywatny i publiczny.

Druga część zajmuje się zwykłą wiadomością – używa klucza publicznego odbiorcy i tworzy zaszyfrowaną treść.

Deszyfrowanie zaczyna się od dostarczenia szyfru, następnie używany jest klucz prywatny odbiorcy i uzyskujemy pierwotną wiadomość. Każdy z tych etapów zawiera w sobie trochę problemów matematycznych.

 

Generowanie klucza

Na potrzeby tego przykładu nasz klucz publiczny będzie zawierał dwie wartości: N i E. Klucz prywatny będzie składał się z liczb: N i D. Zabawa z generowaniem klucza zaczyna się od wybrania dwóch różnych liczb pierwszych. Dla ułatwienia naszych obliczeń weźmiemy małe liczby: P=11 i Q=17. (Siła takich algorytmów opiera się na odpowiednio dużych liczbach pierwszych, których odgadnięcie nie będzie zbyt proste).

Teraz musimy policzyć wartość N. Nic trudnego – wystarczy przemnożyć P i Q:

 

N = P*Q

N = 11*17 = 187

 

Dalej do wyliczenia jest funkcja φ (funkcja Eulera) – przypisuje ona każdej liczbie naturalnej ilość liczb względnie z nią pierwszych, nie większych od niej samej. W naszym przypadku sprowadza się to do wzoru (P-1)*(Q-1).

 

φ(N) = (P − 1)(Q − 1)

φ(N) = (11 − 1)(17 − 1)

φ(N) = 160

 

Jako E musimy wybrać liczbę, która pochodzi z przedziału 1 < E < 160 i jest względnie pierwsza do 160. Czyli – liczba E musi spełniać dwa warunki – być większa od 1, ale mniejsza od naszego φ(N) oraz być względnie pierwsza względem 160. Liczba względnie pierwsza to taka, że największy wspólny dzielnik (NWD) z φ(N) i E musi być równy 1.

Spróbujmy z 23. Spełnia pierwszy warunek – jest większa od 1 i jednocześnie mniejsza od 160. A co z drugim? Jedynym dzielnikiem 23 i 160 jest 1, więc są to liczby względnie pierwsze. W takim razie:

 

E = 23

 

Ostatnią wartością, którą musimy wyliczyć jest D. Do wyliczenia tej liczby musimy znaleźć 23-1 = D(mod 160), co jest tym samym co 23D = 1 mod(160). W takim razie potrzebna nam liczba (D), która po przemnożeniu przez 23 i modulo 160 da resztę 1. Najłatwiejszy sposób to po prostu sprawdzanie od zera póki nie otrzymamy odpowiedniej liczby. Są lepsze sposoby na znajdywanie takich liczb, ale są dużo bardziej skomplikowane. Odpowiednią liczbą u nas jest 7.

 

D*23 (mod 160) = 1

7 * 23 = 161

161 mod 160 = 1

D = 7

 

Koniec pierwszej części – mamy nasz klucz publiczny – liczby N i E, oraz klucz prywatny
– N i D.

 

Szyfrowanie

Zakończyliśmy generowanie kluczy. Teraz mamy wszystkie elementy potrzebne do szyfrowania i deszyfrowania wiadomości. W RSA ten proces opiera się na podniesieniu do potęgi i wykonaniu operacji modulo. Jak to wygląda?

 

C = B^E (mod N)

 

Ta funkcja może wyglądać przerażająco na pierwszy rzut oka, ale nie jest wcale taka trudna. Zaczynamy od liczby B i podnosimy ją do potęgi E, następnie liczymy resztę z dzielenia przez N. Wracając do naszego przykładu – naszą wiadomością do zaszyfrowania będzie 42. W takim razie mamy M=42. Wynikiem tego etapu będzie C – nasz szyfr. Nasza funkcja szyfrująca wygląda tak:

 

C = M^E (mod N)

 

Teraz wystarczy tylko podstawić nasze wartości z przykładu i otrzymamy:

 

C = 42^23 (mod 187)

C=168

 

Deszyfrowanie

Teraz mamy zaszyfrowaną wiadomość. Jak się z nią obchodzić? Dokładnie tak samo, jak w przypadku szyfrowania, tylko używamy innych liczb – teraz potrzeba nam klucza prywatnego:

 

M = C^D (mod n)

 

Po podstawieniu wartości:

 

M = 168^7 (mod 187)

M= 42

 

I mamy naszą oryginalną wiadomość. Całkiem ciekawa, prawda?

 

Jak wspomnieliśmy wcześniej – systemy kryptografii klucza publicznego opierają się na matematycznej trudności w celu zapewnienia bezpieczeństwa. Taką trudnością w przypadku algorytmu RSA jest rozkładanie na czynniki pierwsze dużych liczb. Bierze się to stąd, że dużą liczbą jest N. Ciężko znaleźć czynniki, które przemnożone przez siebie dają ogromną liczbę. A przynajmniej tak długo, jak nie znamy klucza prywatnego odbiorcy. Co jest ważne odnotowania – w praktyce liczby są o wiele większe niż te zastosowane jako przykład w artykule. Przeważnie klucze mają od 1024 do 4096 bitów długości – wtedy obliczenia są dużo trudniejsze i większe niż te pokazane wyżej. Jako przykład trudności złamania takich kluczy można podać, że w 2009 roku po prawie 2 latach przy pomocy setek komputerów otrzymało 232-cyfrową liczbę (768 bitów).

avatar
WebSecurity.pl to największy w Polsce portal o bezpieczeństwie sieciowym.
WebSecurity.pl to codziennie aktualizowane źródło najnowszych informacji i interesujących artykułów z zakresu bezpieczeństwa IT. Na WebSecurity.pl dzielimy się z Wami wiedzą (know-how) i umiejętnościami (how-to), publikując pomocne wskazówki, porady, kursy i tutoriale. Na portalu znajdziecie także prezentacje sprzętu oraz recenzje oprogramowania. WebSecurity.pl to również baza najciekawszych i najważniejszych wydarzeń branżowych w Polsce i na świecie.

2 odpowiedzi na “Klucz publiczny RSA – jak to działa?”

  1. avatar Rocik pisze:

    Przydałoby się, by giganci wprowadzili obsługę rsa w oficjalnych wersjach komunikatorów. O ile się nie mylę, można szyfrować wiadomości w XMPP, jednak gtalk czy Facebook Messanger nie posiadają takich opcji w swoich prawdziwych klientach. Łatwo można się domyślić dlaczego tak jest :)

    • avatar aqqa pisze:

      Pytanie – po co? Ok- powiesz że ktoś zbiera twoje reklamy na potrzeby danych i inne sraty pierdaty- ale spójrz na to z innej strony- poza działającym algorytmem który przegląda dane pod kątem reklamowym, może działać też algorytm podsyłający podejrzane treści np policji, co uważam jest wyżej w hierarchii niż to, że napiszesz koledze czy lubisz colę, chcesz kupić samsunga albo wolisz czerwony kolor. Inna kwestia- większość tych rzeczy jest darmowych- ale to nie to samo co za darmo. Twórcy muszą za coś żyć i mieć możliwość utrzymania tych stron- albo nawet zostania milionerem za świetny sposób- bo czemu nie, jeśli sprzedali swoją usługę setkom milionów ludzi?

Pozostaw odpowiedź aqqa Anuluj pisanie odpowiedzi

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *