opis algorytmu RSA.txt

Opis algorytmu:
1.        wybierane s� dwie du�e liczby pierwsze p i q ? np. o d�ugo�ci 512 bit�w
2.        obliczana jest liczba n b�d�ca iloczynem p i q.
n=p*q
3.        klucz publiczny e wybieramy ze zbioru [max(p,q)+1, n-1] b�d�cy wzgl�dnie pierwsz� liczb� z funkcj� Eulera dla n => f(n)=(p-1)*(q-1)
4.        klucz prywatny d obliczamy z r�wnania d=inv(e,f(n)), czyli jako odwrotno�� e modulo f(n), tj. (e*d) mod (p-1)*(q-1)=1
5.        Szyfrowanie polega na C=M^e mod n
6.        Deszyfrowanie M=C^d mod n

Wspomniany wcze�niej problem faktoryzacji odnosi si� do liczby n. znaj�c jedynie liczb� n (kt�ra jest publiczna) nie jest si� w stanie okre�li� liczb p i q ? b�d�cych podstaw� do oblicze� kluczy szyfrowania (oczywi�cie zak�adaj�c, �e pracujemy na du�ych liczbach).

Przyk�ad szyfrowania i deszyfrowania infromacji:
Niech:
n=187
p=11
q=17

w�wczas:
f(n)=(11-1)*(17-1)=160
wybrano e=97
wi�c d=inv(97,160)=33

Niech tekst jawny M=48, w�wczas kryptogram:
C=M^e mod n = 48^97 mod 187 = 82
Natomiast deszyfrowanie:
M=C^d mod n = 82^33 mod 187 = 48