7.Szyfrowanie RSA

Jest to jeden z pierwszych i obecnie najpopularniejszy asymetryczny algorytm kryptograficzny (z kluczem publicznym), zaprojektowany w roku 1977 przez Rona Rivesta, Adi Shamira i Leonarda Adlemana. Bezpieczeństwo tego algorytmu opiera się na trudności rozkładu na czynniki dużych liczb złożonych w rozsądnym czasie. Znajduje on zastosowanie zarówno do szyfrowania wiadomości, jak i do podpisów cyfrowych.

Schemat działania szyfrowania RSA podczas wysyłania wiadomości od nadawcy do odbiorcy:

Generowanie klucza

Wybieramy dwie liczby pierwsze p,q możliwie duże oraz bliskie sobie, przykładowo:

p=11, q=13

Wyznaczamy liczbę n, która jest iloczynem p⋅q i wybieramy dowolną liczbę naturalną e, względnie pierwszą z liczbą ( p − 1) ⋅ (q − 1). W naszym przykładzie:

n = p*q = 143

(p-1)*(q-1) = 10 * 12 = 120

e = 7, ponieważ NWD(7,120)=1

Wyznaczamy liczbę d, taką, że (e*d ) mod (p − 1)*(q − 1) = 1. W naszym przykładzie ma zachodzić, że:

(7 * d) mod 120 = 1

więc d może być równe 103, gdyż 7*103 = 721, a 721 mod 120 wynosi 1,

a więc d=103

Zapominamy o liczbach p i q.

Klucz publiczny to para liczb (n,e), klucz prywatny to para (n,d)

Klucz publiczny: (143,7) Klucz prywatny (143,103)

Szyfrowanie wiadomości

Aby zaszyfrować wiadomość należy przedstawić ją w postaci liczby nie większej od n . W tym celu najczęściej posługujemy się kodami ASCII. Na cele przykładu wybierzmy literę 'a', która ma kod ASCII 97, więc sekretna wiadomość do przesłania to:

W=97.

Wykorzystując klucz publiczny odbiorcy wiadomości, tworzymy zaszyfrowaną wiadomość P ze wzoru:

P = W^e mod n

Aby obliczyć tak dużą potęgę korzystamy z szybkiego potęgowania oraz własności operacji na resztach.

P = 97^7 mod 143

97^7 mod 143 = ( 97^4 * 97^2 * 97 ) mod 143 =

= 97^4 mod 143 * 97^2 mod 143 * 97 mod 143 = (126 * 114 * 97) mod 143 = 59

Liczba 59 jest kryptogramem, który należy przesłać.

Odszyfrowanie wiadomości

Aby odszyfrować wiadomość odbiorca oblicza:

W = P^d mod n

Czyli dla naszego przykładu:

W = 59^103 mod 143

Ponownie korzystamy z szybkiego potęgowania i własności operacji modulo:

59^103 = 59^64 * 59^32 * 59^4 * 59^2 * 59^1

przyp.

ponieważ 103 = (1 1 0 0 1 1 1)₂ //bity odpowiadają za wykładniki będące kolejnymi potęgami dwójki

59^103 mod 143 = 59^64 mod 143 * 59^32 mod 143 * 59^4 mod 143 * 59^2 mod 143 * 59 mod 143 =

= (113 * 16 * 113 * 49 * 59) mod 143 = 97

W = 97

Jest to wiadomość, która została nadana.

Uwierzytelnianie wiadomości

RSA może być zastosowane do podpisywania (uwierzytelniania) wiadomości. Nadawca wylicza wartość skrótu wiadomości, a następnie podnosi ją do potęgi d (modulo n), a więc wykonuje te same operacje jak podczas zwykłego deszyfrowania. Zakodowana w ten sposób wartość skrótu zostaje załączona do wysyłanej wiadomości.

Odbiorca wiadomości podnosi zakodowaną wartość skrótu do potęgi e (modulo n), a następnie porównuje 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.