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:

  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. (ed) 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=Me mod n = 4897 mod 187 = 82
Natomiast deszyfrowanie:
M=Cd mod n = 8233 mod 187 = 48

Anubis
marcin@plastimet.com.pl
www.anubis.prog.prv.pl

5 komentarzy

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

  1. 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)

  2. f(n)=(p1)*(q-1)
    małe niedopatrzenie: p-1

  3. 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 :))