RSA

Zaprezentowany w 1978r. algorytm RSA jest tym dla algorytmów asymetrycznych czym DES dla algorytmów symetrycznych. Nazwa pochodzi od pierwszych liter nazwisk jego twórców a mianowicie Rivesta, Shamira oraz Adlemana. W odróżnieniu od np. algorytmu DES, RSA może operować na dowolnie ustalanej przez użytkownika długości klucza. Z uwagi na swą konstrukcję RSA wymaga wielu operacji arytmetycznych co wydatnie wydłuża czas operacji szyfrowania i deszyfrowania. W stosunku np. do DES`a jest to 100-1000 krotnie mniejsza szybkość. Cecha charakterystyczną dla RSA jest przemienność kluczy stosowanych do szyfrowania i deszyfrowania co wynika z faktu, iż funkcje szyfrująca i deszyfrująca są identyczne.

Algorytm RSA opiera swą siłę na trudności rozkładu liczb na czynniki pierwsze. W pierwszej kolejności dokonywany jest wybór kluczy. Polega on na tym, że wybieramy losowo dwie duże liczby pierwsze p i q. Jest to nieco kłopotliwe ze względu na wielkość liczb. Dokonanie rozkładu na czynniki pierwsze wylosowanych liczb dałoby jednoznaczną odpowiedź czy mamy do czynienia z liczba pierwszą czy też nie, jednak przy tej wielkości liczb jest to praktycznie niemożliwe. Stosuje się zatem testy pierwszości losowanych liczb, które to test nie korzystają z rozkładu na czynniki pierwsze. Test taki mówi tylko o tym, czy mamy do czynienia z liczba złożoną jednak bez 100% pewności czy rzeczywiści tak jest. Wszystkie znane testy są testami probabilistycznymi czyli wynik ich działania jest obarczony pewnym, niewielkim błędem, na przykład test Fermata.

Test Fermata nie daje niestety jednoznacznej odpowiedzi co do liczb pseudopierwszych (zwane liczbami Carmichaela), które to liczby w tym teście dają wynik pozytywny, natomiast liczbami pierwszymi nie są, chociażby liczba 561. Na szczęście nie ma tych liczb zbyt wiele, co zadecydowało o tym iż test Fermata jest wykorzystywany praktycznie, chociażby w popularnym pakiecie PGP. Pewne modyfikacje testu Fermata czynią z niego prawdziwy test probabilistyczny. Najpopularniejszymi odmianami są testy Solovay`a-Strassena czy Millera-Rabina, które dają jednoznaczną odpowiedź na temat pierwszości badanej liczby.

Mając już wylosowane dwie duże liczby pierwsze p i q wybieramy losowo liczbę e taką, aby e oraz (p-1)(q-1) były liczbami względnie pierwszymi. Wykonuje się to w ten sposób, że obliczamy największy wspólny dzielnik da e oraz (p-1)(q-1) aż do momentu wylosowania właściwej liczby e. Kolejnym etapem jest znalezienie przy pomocy algorytmu Euklidesa liczby d takiej, że e*d = 1 mod (p-1)(q-1). Obliczamy liczbę n, która jest iloczynem liczb p i q i kasujemy znalezione wcześniej liczby p i q tak, by nie pozostał po nich żaden ślad. Należy dodać, że (p-1)(q-1) jest wartością funkcji Eulera j (n).Teraz mamy już wszystkie składniki naszych kluczy, bo [e,n] jest naszym kluczem publicznym, natomiast [d,n] jest kluczem prywatnym.

Szyfrowanie przy pomocy RSA odbywa się w sposób matematyczny, oznacza to, iż nasz tekst jawny taktowany jest jako liczba zapisana w postaci binarnej. Ograniczeniem jest to, że liczba ta musi być mniejsza od naszej liczby n, przypomnijmy, iloczynu naszych dwóch dużych liczb pierwszych. Załóżmy że nasz tekst jawny w postaci binarnej oznaczymy jako t.

Szyfrowanie tekstu jawnego t ma postać: t^e mod n = k

Uzyskany wynik tej funkcji jest naszym kryptogramem k.

Deszyfrowanie kryptogramu k ma postać: k^d mod n = t

Jak widać obie funkcje są identyczne o czym wspominałem na początku. Oznacza to zamienność kluczy w zastosowaniach algorytmu RSA.

Algorytm ElGamala

Algorytm ElGamala bazuje na trudności obliczenia tzw. dyskretnych logarytmów. Szyfrowanie za każdym razem wykorzystuje losowo wybraną liczbę, co powoduje, że ten sam tekst jawny może być w różny sposób zaszyfrowana. Ten algorytm określa jednoznacznie który z pary kluczy do czego ma służyć. Klucz publiczny służy do szyfrowania, natomiast prywatny do deszyfrowania danych. Nie istnieje tu zamienność kluczy tak jak było to w przypadku algorytmu RSA. Cechą charakterystyczną i niekiedy wadą jest to, że kryptogramy uzyskiwane w wyniku algorytmu ElGamala są dwukrotnie dłuższe od tekstu jawnego.

Na początek przyda się wyjaśnienie pojęcia dyskretnego logarytmu, a więc w zasadzie najważniejszego elementu całego algorytmu.

Przeprowadźmy następujące założenia:

Niech p będzie liczbą pierwszą, natomiast a generatorem Z _p ( dla każdej liczby x większej od 0 i mniejszej od p istnieje taka liczba i dla której zachodzi zależność x = a ⁱ mod p ). Trudność dyskretnego logarytmu polega na znalezieniu dla danego b większego od 0 i mniejszego od p liczby itakiej, że a ⁱ = b mod p.

Musi być spełniony dodatkowy warunek, mianowicie liczba p musi być wystarczająco duża, w praktyce co najmniej 150 cyfrowa oraz to aby liczba p-1 miała co najmniej jeden duży czynnik pierwszy.

Elementami algorytmu ElGamala są liczba pierwsza p przy czym liczba ta obostrzona jest warunkami wymienionymi powyżej a obliczenie dla niej logarytmu modulo p jest praktycznie niemożliwe, następnie generator a dla Z _p oraz liczby t i b, przy czym t musi być mniejsze od p-1, natomiast b = a ^t. Na klucz publiczny składają się liczby p, a oraz b . Kluczem prywatnym jest liczba t.

Szyfrowanie algorytmem ELGamala odbywa się w oparciu o powyższe dane. Powiedzmy, że chcemy zaszyfrować tekst jawny T. Długość tego tekstu musi być mniejsza od liczby p. Wybieramy losowo liczbę k<p, następnie obliczamy c₁=a ^k mod p oraz c₂=T*b ^k mod p. otrzymana para c₁, c₂ jest naszym kryptogramem tekstu jawnego T.

Deszyfrowanie odbywa się w następujący sposób: zwróćmy uwagę na zależność:

c₂ * (c₁^t)^-1 = T * b ^k * (a ^kt)^-1 = T * a ^kt * (a ^kt) = T mod p. Oczywiście osoba, która deszyfruje dane zna liczbę t i jest w związku z tym w stanie wyznaczyć liczę c₂ * (c₁^t)^-1 mod p a tym samym liczę T, czyli nasz tekst jawny.