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 