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ę (deszyfrowanie).

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

• funkcja Eulera

• twierdzenie Eulera

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(Z_n)|

Z_n={0,1,2,…,n-1} (|Z_n|=n)

U(Z_n)=Z_n - {m₁,m₂,m₃,…,m_n}

gdzie: NWD(n,m_n)>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 Z_n 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=1
  czyli: ed=kt+1 k=2,d=2427

podstawiamy za k kolejne liczby naturalne
i 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:

m^e mod n=c

Deszyfrowanie wiadomości

• wiadomość c wstawiamy do wzoru i otrzymujemy z powrotem wiadomość m

c^d 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

Kryptologia Kod RSA

4

Koło Naukowe MiR ©2007