Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Istota szyfru RSA

i parę niezbędnych aparatów

matematycznych

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

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.

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

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

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Funkcja Eulera

»

Funkcja Eulera φ wyznacza ilość liczb względnie 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)

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Twierdzenie Eulera

»

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

a

φ(n)

mod n=1

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Algorytm

czyli szyfrujemy i deszyfrujemy -

- krok po kroku

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

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

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Szyfrowanie wiadomości

»

Szyfrowana jest wiadomość LICZBOWA m

»

m<n

»

Otrzymujemy zaszyfrowaną wiadomość c

m

e

mod n=c

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Deszyfrowanie wiadomości

»

Zaszyfrowana wiadomość c jest z powrotem zamienianana wiadomość

m

c

d

mod n=m

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Potęgowanie modulo

c

d

mod n=m

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Kryptologia

Monika Sztobryn

Dowód poprawności

Twierdzenie: 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

(φ(n)

)

k

mod n =

= m(1)

k

mod n =

m mod n=m.

Odwiedź matematyczną stronę Batorego: www.matbatory.xt.pl

Koło Naukowe

MiR

Koniec

Dziękuję za uwagę :)