1 Szyfrowanie i deszyfrowanieKryptologia Szyfrowanie i deszyfrowanie Kod RSA KN MiR Prezentacja Moniki Sztobryn Na podstawie materiałów z MATprojektu 2005

2 Rozdziały: Kod RSA Kryptologia Istota szyfru RSAAlgorytm szyfrowania i deszyfrowania Dowód poprawności

3 Kryptologia Kod RSA Istota szyfru RSA Istota szyfru RSA

4 Kryptologia Kod RSA Kod RSA KryptologiaIstota szyfru RSA Kryptologia Nauka zajmująca się szyfrowaniem – kryptografia oraz deszyfrowaniem - kryptoanaliza Kod RSA Nazwa szyfru pochodzi od nazwisk jego twórców. Aby zaszyfrować wiadomość wystarczy znajomość klucza jawnego, lecz do odszyfrowania niezbędny jest klucz prywatny. Trudność złamania kodu opiera się na trudności rozłożenia bardzo dużych liczb naturalnych na czynniki pierwsze.

5 pojawiające się w algorytmie koduKryptologia Kod RSA Istota szyfru RSA Operacje i funkcje pojawiające się w algorytmie kodu Funkcja modulo Funkcja Eulera Twierdzenie Eulera

6 FUNKCJA MODULO Kod RSA a mod n=x KryptologiaIstota szyfru RSA FUNKCJA MODULO Operacja zwracająca resztę z dzielenia liczby a przez n. a mod n=x np.: 5 mod 2=1 9 mod 3=0 13 mod 5=3 8 mod 10=8

7 FUNKCJA EULERA Kod RSA KryptologiaIstota szyfru RSA FUNKCJA EULERA Funkcja Eulera φ wyznacza ilość liczb wzgęldnie pierwszych z daną liczbą, mniejszych od niej. Rozpatrujemy zbiór liczb naturalnych (wraz z zerem) np.: φ(8)=4 Jeżeli n jest liczbą pierwszą, to φ(n)=n-1 Słaba multiplikatywność φ(an)= φ(a) · φ(n)

8 Jeżeli a jest liczbą całkowitą, a n naturalną, toKryptologia Kod RSA Istota szyfru RSA TWIERDZENIE EULERA Jeżeli a jest liczbą całkowitą, a n naturalną, to aφ(n) mod n=1

9 Algorytm szyfrowania i deszyfrowaniaKryptologia Kod RSA Algorytm szyfrowania i d… Algorytm szyfrowania i deszyfrowania

10 Wybór kluczy Kod RSA KryptologiaAlgorytm szyfrowania i d… Wybór kluczy Wybieramy liczby pierwsze p,q (jak największe i TAJNE!) Obliczamy n=pq Obliczamy t=(p-1)(q-1) Losowo wybieramy e takie, że NWD(e,t)=1 Znajdujemy d takie, że: ed mod t=1 (d zostaje tajne!) ed=kt+1, k – liczba naturalna [e, n] – klucz jawny [d, n] – klucz prywatny

11 me mod n=c Szyfrowanie wiadomości Kod RSA KryptologiaAlgorytm szyfrowania i d… Szyfrowanie wiadomości Szyfrowana jest wiadomość LICZBOWA m m Otrzymujemy zaszyfrowaną wiadomość c me mod n=c

12 cd mod n=m Deszyfrowanie wiadomości Kod RSA KryptologiaAlgorytm szyfrowania i d… Deszyfrowanie wiadomości Zaszyfrowana wiadomość c jest z powrotem zamieniana na wiadomość m cd mod n=m

13 cd mod n=m Potęgowanie modulo Kod RSA KryptologiaAlgorytm szyfrowania i d… Potęgowanie modulo cd mod n=m

14 Kryptologia Kod RSA Dowód poprawności Dowód poprawności

15 Kod RSA Kryptologia Tw.: cd mod n=m (me mod n)d mod n=mDowód poprawnosci Tw.: cd mod n=m (me mod n)d mod n=m (me)d mod n=mkt+1 mod n=m(mk((p-1)(q-1))) mod n= =m(mk(φ(p)φ(q))) mod n=m(mk(φ(pq))) mod n= =m(mk(φ(n))) mod n=m((mφ(n))k)mod n= =m(1k) mod n=m mod n=m C.N.D.

16 Kryptologia Kod RSA KONIEC prezentacji 