il sistema RSA

Il primo algoritmo di codificazione a chiave pubblica (codificazione assimetrica) è stato sviluppato da R.Merckle e M.Hellman nel 1977. Divenne rapidamente obsoleto grazie ai lavori di Shamir, Zippel e Herlestman, famosi criptanalisti.

Nel 1978, l'algoritmo a chiave pubblica di Rivest, Shamir, e Adelman (da cui il nome RSA) appare per la prima volta. Questo algoritmo serviva ancora nel 2002 per proteggere i codici nucleari dell'esercito americano e russo.

funzionamento de RSA

Il funzionamento del criptosistema RSA è basato sulla difficoltà di fattorizzare dei grandi interi.

Siano due numeri primi p e q, e d un intero tale ched sia primo con(p-1)*(q-1)). La tripletta (p,q,d) costituisce così la chiave privata.

La chiave pubblica è allora la doppietta (n,e) creata attraverso la chiave privata dalle trasformazioni seguenti :

n = p * q
e = 1/d mod((p-1)(q-1))

Sia M , il messaggio da inviare. Bisogna che il messaggio M sia primo con la chiave n. In effetti, la docodificazione si basa sul teorema d'Euler che dice che se M en sono primi fra loro, allora :

Mphi(n) = 1 mod(n)

E' quindi necessario che M non sia un multiplo di p, di q , o di n. Una soluzione consiste nel ritagliare il messaggio M in pezzi M_i facendo in modo che il numero di cifre di ogni M_isia strettamente inferiore a quello di p e di q. Questo suppone quindi che p e q siano grandi, cosa che succede in pratica visto che il principio di RSA risiede nella difficoltà di trovare in tempi ragionevoli p e q conoscendo n, cosa che suppone p e q grandi.

In pratica…

Supponiamo che un utente (chiamato Bob) desideri inviare un messaggio Ma una persona (chiamamiola Alice), gli basterà procurarsi la chiave pubblica (n,e) di quest'ultima e poi calcolare il messaggio cifrato c :

c = Me mod(n)

Bob invia in seguito il messaggio cifrato c à Alice, che è capace di decifrarlo attraverso la sua chiave privata (p,q,d) :

M =  Me*d mod(n) = cd mod(n)