Kryptologia Kod RSA
Kryptologia
Szyfrowanie i deszyfrowanie
Kod RSA
ROZDZIAŁY:
§ Istota szyfru RSA
§ kryptologia, kod RSA
§ funkcja modulo
§ funkcja Eulera
§ twierdzenie Eulera
§ Algorytm szyfrowania i deszyfrowania
§ wybór kluczy
§ szyfrowanie
§ deszyfrowanie
§ potęgowanie modulo
§ Dowód poprawności
§ Bibliografia
§ Załączniki
Istota szyfru RSA
Kryptologia – nauka zajmująca się bezpieczną komunikacją. Dzieli się na kryptografię (szyfrowanie) oraz kryptoanalizę (deszyfrowanmie).
Kod RSA – nazwa szyfru pochodzi od nazwisk jego twórców: Rivesta, Shamira i Adlemana. Jego istotą jest to, że po zaszyfrowaniu wiadomości nie da się jej odszyfrować nie znając klucza prywatnego. Tak więc bez obaw możemy podać do wiadomości publicznej klucz jawny, jednak odczytać wiadomość może tylko posiadacz klucza prywatnego.
Aby zrozumieć zasadę działania kodu, musimy poznać następujące pojęcia:
Funkcja modulo
Jest to operacja zwracająca resztę z dzielenia x naturalnej liczby a przez naturalną liczbę n.
Funkcja Eulera
Funkcja Eulera φ wyznacza ilość liczb względnie pierwszych z daną liczbą, mniejszych od niej. (przykład)
dla n N - {0,1}
φ(n)=|U(Zn)|
Zn={0,1,2,…,n-1} (|Zn|=n)
U(Zn)=Zn - {m1,m2,m3,…,mn}
gdzie: NWD(n,mn)>1
Zauważamy, że jeżeli n jest liczbą pierwszą, to φ(n)=n-1.
Bo wspólny dzielnik większy niż 1 n będzie miała tylko z 0, n oraz kn, gdzie kjest liczbą naturalną. W zborze Zn z w/w wymienionych licz znajduje się tylko 0.
Słaba multiplikatywność:
φ(an)= φ(a) φ(n)
Twierdzenie Eulera
Algorytm szyfrowania i deszyfrowania wiadomości
Wybór kluczy
§ losowo wybieramy dwie bardzo duże liczby pierwsze: p, q p=71, q=53
§ obliczamy n=pq n=3763
§ obliczamy t=(p-1)(q-1) t=3640
§ wybieramy losowo takie e, że NWD(e,t)=1 e=3
§ znajdujemy d takie, że ed mod t=1czyli: ed=kt+1 k=2,d=2427
podstawiamy za k kolejne liczby naturalnei metodą prób i błędów znajdujemy całkowite d
§ klucz jawny: e, n
§ klucz prywatny: d, n
Trudność złamania szyfru opiera się na trudności rozłożenia liczby n na czynniki pierwsze, dlatego tak ważne jest by p i q były jak największe.
Szyfrowanie wiadomości
§ aby zaszyfrować jakikolwiek tekst, musimy zamienić go na liczbę.
§ zamieńmy więc każdą literę zgodnie z prostą zasadą: A to 11, B 12, aż do Z 33. Spację zastąpi 10.
§ Liczba m, którą chcemy zaszyfrować musi być mniejsza niż liczba n.
§ Podzielmy więc tekst na dwuliterowe bloki, co zagwarantuje nam spełnienie tego warunku.
§ Aby zaszyfrować posługujemy się wzorem:
me mod n=c
Deszyfrowanie wiadomości
§ wiadomość c wstawiamy do wzoru i otrzymujemy z powrotem wiadomość m
cd mod n=m
Potęgowanie modulo
§ nasze d jest fest duże, nawet za pomocą komputera nie podnieślibyśmy do takiej potęgi
§ na szczęście potęgowanie modulo ułatwia nam życie
§ jeżeli chcemy podzielić modulo n d-tą potęgę liczby c wystarczy, że modulo tej liczby pomnożymy przez nią, wynik obetniemy modulo n a następnie pomnożymy ponownie przez c, obetniemy modulo n i tak dalej, a operację tą należy wykonywać d razy (przykład)
Dowód poprawności
założenia: m<n
NWD(m,n)=1
Bibliografia
§ B.Schneier; Kryptografia dla praktyków; WNT,
§ M.Kutyłowski, W.B.Strothman; Kryptografia, teoria i praktyka
§ pl.wikipedia.org
§ MATprojekt 2005 autorstwa M. Sztobryn, T. Gawlika
Załączniki
§ prezentacja w programie Microsoft Power Point
§ arkusz kalkulacyjny programu Microsoft Excel
5
Koło Naukowe MiR ©2007
krzysztof0001