INŻYNIERIA BEZPIECZEŃSTWA – LABORATORIUM

Algorytm RSA

Algorytm RSA – zagadnienia teoretyczne

W roku 1977 trzej profesorowie z MIT w USA, Ronald L. Rivest, Adi Shamir i Leonard Adleman,

opublikowali nowy rodzaj szyfrowania danych, który nazwano od pierwszych liter ich nazwisk

systemem RSA. Jest to niesymetryczny

algorytm

szyfrujący, którego zasadniczą cechą są dwa klucze:

publiczny do kodowania informacji oraz prywatny do jej odczytywania. Klucz publiczny (można go

udostępniad wszystkim zainteresowanym) umożliwia jedynie zaszyfrowanie danych i w żaden sposób

nie ułatwia ich odczytania, nie musi więc byd chroniony. Dzięki temu firmy dokonujące transakcji

poprzez sied Internet mogą zapewnid swoim klientom poufnośd i bezpieczeostwo. Drugi

klucz (prywatny, przechowywany pod nadzorem) służy do odczytywania informacji zakodowanych

przy pomocy pierwszego klucza. Klucz ten nie jest udostępniany publicznie. System RSA umożliwia

bezpieczne przesyłanie danych w środowisku, w którym może dochodzid do różnych nadużyd.

Bezpieczeostwo oparte jest na trudności rozkładu dużych liczb na czynniki pierwsze.

Załóżmy, iż dysponujemy superszybkim komputerem, który jest w stanie sprawdzid podzielnośd

miliarda dużych liczb w ciągu jednej sekundy. Aby złamad szyfr RSA należy rozbid klucz publiczny na

dwie liczby pierwsze będące jego dzielnikami. Znajomośd tych liczb pozwala rozszyfrowad każdą

informację zakodowaną kluczem prywatnym i publicznym.

Brzmi dosyd prosto. Jednakże nie ma prostej metody rozbijania dużych liczb na czynniki pierwsze. Nie

istnieje żaden wzór, do którego podstawiamy daną liczbę i w wyniku otrzymujemy wartości jej

czynników pierwszych. Należy je znaleźd testując podzielnośd kolejnych liczb.

Z rozważao o liczbach pierwszych wynika, iż w przypadku dwóch różnych dzielników pierwszych

jeden musi leżed poniżej wartości pierwiastka z danej liczby, a drugi powyżej (dlaczego?). Zatem, aby

go znaleźd musimy wyliczyd pierwiastek z rozkładanej liczby, a następnie testowad podzielnośd przez

liczby nieparzyste leżące poniżej tego pierwiastka.

Statystycznie poszukiwany czynnik pierwszy powinien znajdowad się w górnej połówce zakresu od 2

do pierwiastka z n. Ile działao musimy wykonad? Policzmy.

Klucz 128 bitowy. Pierwiastek jest liczbą 64 bitową. W zakresie od 2 do 2

64

co druga liczba jest

nieparzysta, zatem jest ich około 2

64

/ 2 = 2

63

. Ponieważ interesuje nas tylko górna połówka, to ilośd

liczb do sprawdzenia jest dwa razy mniejsza, czyli wynosi 2

63

/ 2 = 2

62

. Ile czasu zajmie naszemu

superkomputerowi sprawdzenie podzielności przez około 2

62

liczb, jeśli w ciągu 1 sekundy wykonuje

on miliard sprawdzeo? Odpowiedź brzmi:

zajmie to około 2

62

/ 10

9

= 4611686018 sekund =

= 76861433 minut = 1281023 godzin = 53375 dni = 146 lat

Czy sądzisz, że ktoś będzie czekał przez prawie dwa życia na złamanie szyfru? Zatem można podad do

publicznej wiadomości liczbę będącą iloczynem dwóch dużych liczb pierwszych i mied prawie

pewnośd, iż nikt jej nie rozbije na czynniki pierwsze w rozsądnym czasie. Ostatecznie zamiast 128

bitów możemy zwiększyd klucz do np. 1024 bitów, a wtedy czas łamania szyfru liczy się miliardami

miliardów... miliardów lat.

Fazy algorytmu RSA:

1. Generacja klucza publicznego i tajnego. Klucz publiczny jest przekazywany wszystkim

zainteresowanym i umożliwia zaszyfrowanie danych. Klucz tajny umożliwia rozszyfrowanie

danych zakodowanych kluczem publicznym. Jest trzymany w ścisłej tajemnicy.

2. Użytkownik po otrzymaniu klucza publicznego, np. poprzez sied Internet, koduje za jego

pomocą swoje dane i przesyła je w postaci szyfru RSA do adresata dysponującego kluczem

tajnym, np. do banku, firmy komercyjnej, tajnych służb. Klucz publiczny nie musi byd

chroniony, ponieważ nie umożliwia on rozszyfrowania informacji - proces szyfrowania nie jest

odwracalny przy pomocy tego klucza. Zatem nie ma potrzeby jego ochrony i może on byd

powierzany wszystkim zainteresowanym bez ryzyka złamania kodu.

3. Adresat po otrzymaniu zaszyfrowanej wiadomości odczytuje ją za pomocą klucza tajnego.

Tworzenie kluczy dla systemu RSA:

1. Znajdź dwie duże liczby pierwsze (mające np. po 1024 bity). Oznacz je jako p i q. Istnieją

specjalne algorytmy generujące duże liczby pierwsze.

2.

Oblicz:

Ø = (p - 1) (q - 1)

oraz

n = p q

Wygenerowane liczby pierwsze usuo, aby nie wpadły w niepowołane ręce. Ø to tzw.
funkcja Eulera, n jest modułem.

3. Wykorzystując odpowiednio algorytm Euklidesa znajdź liczbę e, która jest względnie pierwsza

z wyliczoną wartością funkcji Eulera Ø (tzn. NWD(e, Ø) = 1) Liczba ta powinna również

spełniad nierównośd 1 < e < n . Nie musi ona byd pierwsza lecz nieparzysta.

4. Oblicz liczbę odwrotną modulo Ø do liczby e, czyli spełniającą równanie d e mod Ø = 1.

Można to zrobid przy pomocy rozszerzonego algorytmu Euklidesa, który umieściliśmy w

naszym opracowaniu

5. Klucz publiczny jest parą liczb (e, n), gdzie e nazywa się publicznym wykładnikiem. Możesz go

przekazywad wszystkim zainteresowanym.

6. Klucz tajny to (d, n), gdzie d nazywa się prywatnym wykładnikiem. Klucz ten należy

przechowywad pod ścisłym nadzorem.

Szyfrowanie danych kluczem publicznym RSA

1. Otrzymujesz od adresata klucz publiczny w postaci pary liczb (e, n).

2. Wiadomośd do zaszyfrowania zamieniasz na liczby naturalne t, które muszą spełniad

nierównośd 0 < t < n

Można tutaj skorzystad np. z łączenia kodów znaków. Oczywiście adresat musi znad użyty

przez ciebie sposób przekształcenia tekstu w liczbę, aby mógł on później odtworzyd

otrzymaną wiadomośd. Zwykle nie ma z tym problemu, ponieważ nadawca i odbiorca stosują

wspólne oprogramowanie, które troszczy się za ciebie o takie szczegóły techniczne.

3. Na tak otrzymanych liczbach wykonujesz operację szyfrowania i otrzymujesz liczby

c =

t e

mod n.

4. Liczby c są zaszyfrowaną postacią liczb t i przekazuje się je adresatowi wiadomości. Klucz (e,

n) umożliwił ich zaszyfrowanie, lecz nie pozwala ich rozszyfrowad.

Rozszyfrowanie danych kluczem prywatnym RSA

1. Jesteś adresatem zaszyfrowanych wiadomości. Wcześniej wszystkim korespondentom

przesłałeś wygenerowany klucz publiczny (e,n), za pomocą którego mogą oni szyfrowad i

przesyład ci swoje dane. Otrzymujesz więc zaszyfrowaną wiadomośd w postaci liczb

naturalnych c, które muszą spełniad warunek: 0 < c < n

2. Liczbę c przekształcasz na pierwotną wartośd t stosując wzór: t =

c d

mod n

3. Z otrzymanej liczby t odtwarzasz wg ustalonego systemu znaki tekstu. Teraz możesz odczytad

przesłaną wiadomośd.

Demonstracja z wykorzystaniem programu CrypTool 1.4.30

1. Tworzenie liczb pierwszych

Na poniższym zdjęcie obrazuje sposób wyszukiwania liczb pierwszych p i q:

- jakim algorytmem będziemy poszukiwad liczb,

- z jakiego zakresu wartości,

- liczba p,

- liczba q.

2. Automatycznie po wylosowaniu w 1. Punkcie uzyskujemy liczby pierwsze p i q.

3. Analogicznie do 2. Punktu uzyskujemy klucz prywatny.

4. Opcje wprowadzania wiadomości do zaszyfrowania. Tutaj mamy do wyboru opcje dla

alfabetu i systemu liczbowego:

- wybór znaków,

- wariant RSA,

- metoda kodowania,

- długośd bloków,

- system liczbowy.

5. Wprowadzanie wiadomości.

6. Wyświetlenie wiadomości. Każdy znak zostaje oddzielony separatorem # w celu

uwidocznienia szyfrowania.

7. Automatyczne wprowadzenie liczb.

8. Szyfrowanie: c[i] = m[i]^e (mod N)

Lub

Deszyfrowanie do tekstu jawnego: m[i] = c[i]^d (mod N)

Ostatecznie szyfrowanie wygląda tak:

Zadania do samodzielnego wykonania:

1. Zaimplementowad algorytm wyznaczający liczby pierwsze.

2. Za pomocą programu CrypTool wyznaczyd swój własny podpis cyfrowy i zaszyfrowad dowolny

tekst za pomocą algorytmu RSA.

3. Zaimplementowad szyfrowanie algorytmem RSA w dowolnym środowisku.