Kryptologia

Szyfrowanie i deszyfrowanie

Kod RSA

 

 

Kryptologia

Kod RSA

Rozdziały:

✗

Istota szyfru RSA

✗

Algorytm szyfrowania i deszyfrowania

✗

Dowód poprawności

 

 

Kryptologia

Kod RSA

Istota szyfru RSA

Istota szyfru RSA

 

 

Kryptologia

Kod RSA

Istota 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.

 

 

Kryptologia

Kod RSA

Istota szyfru RSA

Operacje i funkcje

pojawiające się w algorytmie kodu

✗

Funkcja modulo

✗

Funkcja Eulera 

✗

Twierdzenie Eulera

 

 

Kryptologia

Kod RSA

Istota 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

 

 

Kryptologia

Kod RSA

Istota 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)

 

 

Kryptologia

Kod RSA

Istota szyfru RSA

TWIERDZENIE EULERA

Jeżeli a jest liczbą całkowitą, a n naturalną, to 

a

φ(n) 

mod n=1

 

 

Kryptologia

Kod RSA

Algorytm szyfrowania i d…

Algorytm szyfrowania i 

deszyfrowania

 

 

Kryptologia

Kod RSA

Algorytm 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

 

 

Kryptologia

Kod RSA

Algorytm szyfrowania i d…

Szyfrowanie wiadomości

✗

Szyfrowana jest wiadomość LICZBOWA m

✗

m<n

✗

Otrzymujemy zaszyfrowaną wiadomość c

m

e

 mod n=c

 

 

Kryptologia

Kod RSA

Algorytm szyfrowania i d…

Deszyfrowanie wiadomości

✗

Zaszyfrowana wiadomość c jest z powrotem zamieniana na 

wiadomość m

c

d

 mod n=m

 

 

Kryptologia

Kod RSA

Algorytm szyfrowania i d…

Potęgowanie modulo

c

d

 mod n=m

































d

d

x

n

c

x

x

n

c

x

x

n

c

x

x

 n

c 

d

 

mod

 

 

mod

 

 

mod

 

mod

razy

 

1

3

2

2

1

1



 

 

Kryptologia

Kod RSA

Dowód poprawności

Dowód poprawności

 

 

Kryptologia

Kod RSA

Dowód poprawnosci

Tw.: c

d

 mod n=m

(m

e

 mod n)

d

 mod n=m

(m

e

)

d

 mod n=m

kt+1 

mod n=m(m

k((p-1)(q-1))

) mod n=

=m(m

k(φ(p)φ(q))

) mod n=m(m

k(φ(pq))

) mod n=

=m(m

k(φ(n))

) mod n=m((m

φ(n)

)

k

)mod n=

=m(1

k

) mod n=m mod n=m

C.N.D.

 

 

Kryptologia

Kod RSA

KONIEC

prezentacji 