262080411

20

A. PAWEŁ WOJDA

8. Wykład 8 - 5.V.2010

8.1. Metoda RS A. O ile metoda Rabina wykorzystuje Małe Twierdzenie Fermata, to metoda RS A¹⁴ opiera się na twierdzeniu Eulera.

Opis metody RSA.

(1)    Bob:

(a)    Znajduje 2 duże liczby pierwsze p, q, liczy n = pq oraz ip(n) = (p —

(b)    Wybiera (dowolne) e € Z* ^ (a więc e jest względnie pierwsze z <p(n)).

(c)    Oblicza d = e^-1 w Z*(_np

(2)    Ewa: Widzi! Widzi zarówno n jak i e. Wie także jaka jest funkcja szyfrująca.

(3)    Alicja:

(a)    Liczy l = m^e (mod n)

(b)    Wysyła l Bobowi.

Bob: Liczy

(6)    l^d = (m^e)^d = m

Prawdziwość wzoru 6 wymaga uzasadnienia. Oto one.

(a)    Przypadek: m _L n. Skoro ed = 1 (mod <p(n)) mamy: ed = 1 + k<p(n) (gdzie n jest pewną liczbą całkowitą. Wówczas

m^ed = _77l¹+^fc,p(n) _    = _m( _mod n)

(b)    Przypadek: m i n nie są względnie pierwsze. Wtedy albo p|m albo q\m (gdyby p|m i q\m to mielibyśmy sprzeczność z założeniem, źem < n¹⁵). Załóżmy, że p\m oraz q J(m.

Mamy teraz: m^ed =    = _m(m⁹-¹)^fc(p-¹⁾. Ale g X m (bo

q jest liczbą pierwszą i q nie dzieli m). Wiemy że, <p(q) — q — 1. A więc m^ed = m ■ 1 ^fc(p^-1) = m (mod q).

Ostatecznie otrzymaliśmy

m^ed = m (mod q)

Mamy także

m^e = m (mod p)

(bo m = 0 (mod p). Z chińskiego twierdzenia o resztach m jest jedynym rozwiązaniem układu równań

m = l^d (mod q)

m = 0 (mod p)

(tak czy inaczej mamy m = l^d (mod n), niezależnie od tego, czy m X n, czy też nie).

¹⁴Nazwa metody od pierwszych liter nazwisk jej twórców: Rivest, Shamir i Adleman. ^Zakładamy, że liczby szyfrowane są mniejsze od n, w przeciwnym przypadku ulegałyby obcięciu modulo n, a więc zniekształceniu. Takie szyfrowanie byłoby bez sensu!