Apr 27, 2015

Semplice spiegazione di RSA

Ho ritrovato un vecchio appunto che m'ero segnato, così a occhio, 18 anni fa. E' un esempio di come funziona la cifratura a chiave pubblica RSA.
Copio-incollo tale e quale.

L'algoritmo RSA
(spiegazione ed esempio tratti dal libro "Network and internetwork security, principles and practice", William Stalligs)

In questo algoritmo, dato un messaggio M, il testo cifrato C e' nella forma:

C = M^e mod n
e il messaggio M viene ottenuto da C nel seguente modo:
M = C^d mod n, quindi M = (M^e)^d mod n = M^(ed) mod n
dove la chiave privata e' quindi (e,n) e quella pubblica e' (d,n).
I numeri d ed e sono ottenuti col seguente procedimento:
il mittente sceglie 2 numeri primi, p e q
il numero n, detto "modulo pubblico", viene calcolato = pq
il mittente calcola il numero e tale che mcd(fi(n),e) = 1 con 1 < e < fi(n)
viene calcolato il numero d '= e^(-1) mod(fi(n)); ovvero ed '= 1 mod(fi(n))

(indichiamo qui con '= il simbolo algebrico dell'"uguale con tre righette", per indicare con ed '= 1 mod (fi(n)) che e*d e' nella forma k * fi(n) + 1)


ESEMPIO del procedimento:

Prendiamo due numeri primi, ad es., p=7 e q=17
Calcoliamo n = pq = 7*17 = 119
Calcoliamo fi(n) che, per una proprieta' matematica della funzione fi, e' uguale a (p-1)*(q-1); fi(119) = 6 * 16 = 96
Scegliamo e in modo che sia relativamente primo a fi(n) e minore di esso: in questo caso prendiamo e = 5
Calcoliamo d tale che de '= 1 mod 96 (ovvero d*e e' uguale a un multiplo di 96  piu' 1) e d < 96; d=77, in quanto 77*5 = 385 che e' uguale a quattro volte 96 piu' 1.
La chiave pubblica e' quindi (5,119) e quella privata e' (77,119).
Dato il messaggio in chiaro con vaore, ad es., 19, il testo cifrato sara' C = 19^5 mod 119 = 66.
Il testo cifrato viene decifrato cosi': M = 66^77 mod 119 = 19

Quindi, piu' grandi sono i numeri primi scelti, maggiore e' la sicurezza.



NOTE:

i) ^ e' l'operatore di elevamento a potenza: 3^2=9
ii) mcd(arg1,arg2) = massimo comun denominatore
iii) mod = resto della divisione intera: 5 mod 2 = 1
iv) fi(arg) = il numero di interi positivi minori di n e relativamente primi a n
v) "relativamente primo" = due numeri interi sono relativamente primi tra loro se non hanno fattori primi in comune (a parte il numero 1), cioe', n e m sono relativamente primi tra loro se mcd(m,n)=1; es.: 8 e 15, 8 si scompone in 2*4 e 15 in 3*5
vi) dato un numero primo p, allora fi(p) = p-1; (ovvero tutti i numeri minori di un numero primo sono relativamente primi ad esso)

vii) dati due numeri primi p1 e p2 e il loro prodotto n, vale la seguente relazione: fi(n) = fi(p1*p2) = fi(p1) * fi(p2) = (p1 - 1)*(p2 -1); (omettiamo la dimostrazione)

No comments: