RSA - szyfrowanie asymetryczne
anubis
Algorytm RSA
RSA (Rivest, Shamir, Adelman) ? najpopularniejszy asymetryczny, wykładniczy algorytm szyfrowania danych. Asymetryczność szyfru polega na stosowaniu dwóch kluczy:
- publiczny ? udostępniony każdemu, w większości przypadków służący do szyfrowania informacji
- prywatny ? tajny klucz, znany jedynie właścicielowi, służący do odszyfrowania informacji zaszyfrowanej kluczem publicznym.
RSA został opracowany w 1977 roku przez Rona Rivesta, Adi Shamira i Leonarda Adlemana (od nazwisk twórców powstała nazwa algorytmu, a później nazwa firmy RSA Data Security Inc.). Algorytm do 20 września 2000 roku chroniony był patentem numer 4405892 ? obecnie może być dowolnie wykorzystywany.
Siła algorytmu RSA polega na skomplikowanym matematycznym problemie faktoryzacji wielkich liczb (rozkładzie na czynniki pierwsze).
Opis algorytmu:
- wybierane są dwie duże liczby pierwsze p i q ? np. o długości 512 bitów
- obliczana jest liczba n będąca iloczynem p i q.
n=p*q - 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)
- klucz prywatny d obliczamy z równania d=inv(e,f(n)), czyli jako odwrotność e modulo f(n), tj. (ed) mod (p-1)(q-1)=1
- Szyfrowanie polega na C=M^e mod n
- 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=Me mod n = 4897 mod 187 = 82
Natomiast deszyfrowanie:
M=Cd mod n = 8233 mod 187 = 48
do punktu 3. klucz publicznyc nie jest wybierany ze zbioru [max(p,q)+1, n-1] jak juz to ze zbioru [2, (p-1)*(q-1)-1] - a w praktyce najbardziej popularnym kluczem publiczny jest 2^16 + 1 = 65537
dzieki za zwrocenie uwagi na bledy - juz poprawilem, a odnosnie znaku ^ oznacza to potegowanie (no coz male niedopowiedzenie)...
3 sprawy :)
n ? f(n)=(p1)(q-1)
ten myślnik na początku może mylić, iż to jest minus ;)
może coś takiego?
n => f(n)=(p1)(q-1)
f(n)=(p1)*(q-1)
małe niedopatrzenie: p-1
M^e
znak karetki to w tym przypadku potęgowanie czy operacja xor? Nie każdy to wie :)
a mam to otulic w futerko aby bylo cieplej???
jakby to powiedziec - hmm, troszke za sucho, no ale zawsze cos :))