Algoritmul RSA

Algoritmul RSA

The RSA algorithm was publicly described in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames, listed in the same order as on the paper.

RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key.

Descriere

Pentru siguranta metodei numerele p si q trebuie sa fie foarte mari (cel putin 100 cifre)

EXEMPLU

Generarea cheilor

1) Generarea (alegerea) numerelor  p si q (numere prime si fff mari)

Pentru usurinta calculelor in acest exemplu numereor vor fi de valori mici.:

p = 7
q = 19

2) Fie n = pq

n = 7 * 19
  = 133

3) Fie m = (p - 1)(q - 1)

m = (7 - 1)(19 - 1)
  = 6 * 18
  = 108

4) Cautam numarul e - intreg cel mai mic, ai e si m sa fie prime intre ele

e = 2 => gcd(e, 108) = 2 (no)
e = 3 => gcd(e, 108) = 3 (no)
e = 4 => gcd(e, 108) = 4 (no)
e = 5 => gcd(e, 108) = 1 (yes!)

5) Gasim d, astfel ca de % m = 1

Aceasta este echivalent cu a gasi d astfel ca de = 1 + nm unde n este integer. Rescriem astfel: d = (1 + nm) / e. Acum cautam succesiv pe n astfel ca d sa fie intreg:

n = 0 => d = 1 / 5 (no)
n = 1 => d = 109 / 5 (no)
n = 2 => d = 217 / 5 (no)
n = 3 => d = 325 / 5
           = 65 (yes!)

Comunicarea

Criptare

Pentru exemplificare se cripteaza valoarea '6' (mesajul ce trebuie trimis; trebuie sa fie mai mica decat minimul dintre p si q).

C = P^e % n
  = 6⁵ % 133
  = 7776 % 133
  = 62

Decriptarea

P = C^d % n
  = 62⁶⁵ % 133
  = 62 * 62⁶⁴ % 133
  = 62 * (62²)³² % 133
  = 62 * 3844³² % 133
  = 62 * (3844 % 133)³² % 133
  = 62 * 120³² % 133

Se repeta secventa de operatii care a redus 62⁶⁵ la pana cand se reduce exponentul la .