Wykład 9
Szyfr RSA
Problem: Znalez
ć system kryptograficzny, w którym klucz szyfrujący jest powszechnie
znany (dostępny) i umożliwia zaszyfrowanie wiadomości przez dowolną osobę tak, aby
nikt niepowołany (znający także ten klucz) nie mógł odczytać zaszyfrowanej wiadomości,
a jednocześnie mógł ją odszyfrować adresat.
Rozwiązanie polega na podziale klucza na dwie części: część publiczną (jawną), która
służy tylko do szyfrowania i część prywatną (tajną)  służącą tylko do deszyfrowania.
Taki klucz nazywa siÄ™ kluczem asymetrycznym.
Pierwszy taki asymetryczny system kryptograficzny kryptosystem RSA opublikowany
został w 1977 roku przez Rona Rivesta, Adi Shamira i Leona Adlemana.
9.1 Generowanie klucza
I. Wybieramy dwie duże liczby pierwsze p, q i obliczamy ich iloczyn
n = pq.
II. Znajdujemy liczby e, d " N spełniające następujące warunki:
(1) 1 < e < Õ(n),
(2) eÄ„"Õ(n),
(3) d = e-1 mod Õ(n).
III. Kluczem szyfru RSA jest trójka liczb (n, e, d), przy czym
" para (n, e) jest publiczną częścią klucza.
" liczba d jest prywatną częścią klucza.
Liczbę n nazywamy modułem RSA, liczbę e nazywamy wyładnikiem szyfrującym, zaś
liczbę d  wykładnikiem deszyfryjącym.
26
9.2 Szyfrowanie
Założenia: Nadawca chce zaszyfrować wiadomość i przesłać ją adresatowi. Nadawca
zna część publiczną (n, e) klucza k. Wiadomość jest zapisana za pomocą alfabetu za-
wierającego N znaków; będziemy dalej zakładać, że alfabetem tym jest po prostu ZN.
Niech
l = #logN n# .
Nadawca będzie szyfrować bloki tekstu jawnego złożone z l znaków (de facto liczb). Jeżeli
ostatni blok tekstu jawnego zawiera mniej znaków, to nadawca uzupełnia go dopisując
odpowiednią liczbę dowolnych znaków.
Przebieg szyfrowania:
I. Dla każdego bloku tekstu jawnego
m1m2 . . . ml
nadawca oblicza liczbÄ™
l

m = miNl-i.
i=1
Liczba ta należy do zbioru Zn, gdyż
l l

0 m = miNl-i (N - 1) Nl-i = Nl - 1 < n.
i=1 i=1
II. W celu zaszyfrowania obliczonej liczby m nadawca używa funkcji szyfrującej zdefi-
niowanej wzorem
"x"Z Ek(x) = xe MOD n.
n
III. W wyniku szyfrowania nadawca otrzymuje liczbę c = Ek(m). Ponieważ 0 c < n <
Nl+1, więc c można przedstawić jednoznacznie w postaci
l

c = ciNl-i,
i=0
gdzie ci " ZN dla i = 0, 1, . . . , l. Aby uniknąć przesyłania dużej liczby c, nadawca
wysyła adresatowi blok tekstu c0c1 . . . cl zapisany tym samym alfabetem, co tekst jawny.
27
9.3 Deszyfrowanie
I. Adresat otrzymuje od nadawcy ciąg bloków postaci c0c1 . . . cl. Każdy z nich zamienia
na liczbę c " Zn wykorzystując wzór
l

c = ciNl-i,
i=0
II. Adresat oblicza m = Dk(c), gdzie funkcja Dk jest określona następująco
"y"Z Dk(y) = yd MOD n.
n
III. OtrzymanÄ… liczbÄ™ m adresat zamienia na blok tekstu jawnego m1m2 . . . ml zapisujÄ…c
m w postaci
l

m = miNl-i.
i=1
Twierdzenie 9.1. Dla każdego poprawnie zbudowanego klucza k = (n, e, d) szyfru RSA
zachodzi równość
"x"Z Dk(Ek(x)) = x.
n
9.4 Formalny opis kryptosystemu RSA
System kryptograficzny RSA jest algorytmem zależnym od dwóch parametrów będących
liczbami pierwszymi. Jeżeli p, q są (dużymi) liczbami pierwszymi i n = pq, to
RSA(p, q) = (P, C , K , E, D),
gdzie
P = Zn,
C = Zn,
K = {(n, e, d) : e, d " Zn '" eÄ„"Õ(n) '" ed a" 1 (mod Õ(n))},
E = {E(n, e, d) : E(n, e, d)(x) = xe MOD n dla (n, e, d) " K i x " P},
D = {D(n, e, d) : D(n, e, d)(y) = yd MOD n dla (n, e, d) " K i y " C }.
28
9.5 Bezpieczeństwo
Postulaty bezpieczeństwa konstrukcji klucza RSA:
Liczby pierwsze p, q wykorzystywane do konstrukcji klucza należy wybrać tak, aby
spełnione były następujące warunki
1. obie liczby p i q sÄ… wybrane losowo;
2. obie liczby p i q mają co najmniej po 150 cyfr dziesiętnych;
3. jedna z nich jest o kilka rzędów wielkości mniejsza od drugiej, ale, jednocześnie,
ich różnica jest względnie mała;
4. (p - 1)/2 i (q - 1)/2 sÄ… liczbami pierwszymi;
5. p + 1 oraz q + 1 mają duże czynniki pierwsze p2 i q2 odpowiednio;
6. p2 - 1 oraz q2 - 1 mają duże czynniki pierwsze;
7. NWD(p - 1, q - 1) jest niewielki.
Wybór takich postulatów jest spowodowany analizą znanych (nieefektywnych) algoryt-
mów faktoryzacji i próbą zabezpieczenia przed możliwością efektywnego ich zastosowa-
nia do rozkładu części klucza jawnego n na czynniki. Uważa się, że liczby spełniające
powyższe postulaty są tzw. mocnymi liczbami pierwszymi, czyli liczbami pierwszymi,
których iloczyn jest wyjątkowo trudny do faktoryzacji za pomocą znanych aktualnie
algorytmów.
Szyfr RSA można zaatakować również poprzez próbę wyznaczenia m z zależności
c = me MOD n,
ale okazuje się, że jest to zadanie równie trudne, jak rozkład na czynniki liczby n.
29