Wykład 9

Szyfr RSA

Problem:

Znaleźć 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 Z

N

.

Niech

l = ⌊log

N

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

m

1

m

2

. . . m

l

nadawca oblicza liczbę

m =

l

X

i

=1

m

i

N

l−i

.

Liczba ta należy do zbioru Z

n

, gdyż

0 ¬ m =

l

X

i

=1

m

i

N

l−i

¬ (N − 1)

l

X

i

=1

N

l−i

= N

l

− 1 < n.

II. W celu zaszyfrowania obliczonej liczby m nadawca używa funkcji szyfrującej zdefi-

niowanej wzorem

∀

x∈Z

n

E

k

(x) = x

e

MOD n.

III. W wyniku szyfrowania nadawca otrzymuje liczbę c = E

k

(m). Ponieważ 0 ¬ c < n <

N

l

+1

, więc c można przedstawić jednoznacznie w postaci

c =

l

X

i

=0

c

i

N

l−i

,

gdzie c

i

∈ Z

N

dla i = 0, 1, . . . , l. Aby uniknąć przesyłania dużej liczby c, nadawca

wysyła adresatowi blok tekstu c

0

c

1

. . . c

l

zapisany tym samym alfabetem, co tekst jawny.

27

9.3

Deszyfrowanie

I. Adresat otrzymuje od nadawcy ciąg bloków postaci c

0

c

1

. . . c

l

. Każdy z nich zamienia

na liczbę c ∈ Z

n

wykorzystując wzór

c =

l

X

i

=0

c

i

N

l−i

,

II. Adresat oblicza m = D

k

(c), gdzie funkcja D

k

jest określona następująco

∀

y∈Z

n

D

k

(y) = y

d

MOD n.

III. Otrzymaną liczbę m adresat zamienia na blok tekstu jawnego m

1

m

2

. . . m

l

zapisując

m w postaci

m =

l

X

i

=1

m

i

N

l−i

.

Twierdzenie 9.1.

Dla każdego poprawnie zbudowanego klucza

k = (n, e, d) szyfru RSA

zachodzi równość

∀

x∈Z

n

D

k

(E

k

(x)) = x.

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 = Z

n

,

C

= Z

n

,

K

= {(n, e, d) : e, d ∈ Z

n

∧ e⊥ϕ(n) ∧ ed ≡ 1

(mod ϕ(n))},

E = {E

(n, e, d)

: E

(n, e, d)

(x) = x

e

MOD n dla (n, e, d) ∈ K i x ∈ P},

D = {D

(n, e, d)

: D

(n, e, d)

(y) = y

d

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 p

′

i q

′

odpowiednio;

6. p

′

− 1 oraz q

′

− 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 = m

e

MOD n,

ale okazuje się, że jest to zadanie równie trudne, jak rozkład na czynniki liczby n.

29