Presentiamo in questo articolo un primo esempio di algoritmo di crittografia a chiave pubblica: RSA. Nel 1978 Ronald Rivest, Adi Shamir e Leonard Adleman, tre giovani professori del MIT, sviluppano la prima applicazione pratica basata sulle tecniche di crittografia a doppia chiave, che prenderà il nome di algoritmo RSA, dalle iniziali dei suoi tre inventori. L’idea di RSA è molto semplice e si basa sulla difficoltà di fattorizzare “grandi” numeri (“large numbers”): mentre è molto facile moltiplicare tra di loro due “grandi” numeri primi, risulta difficile fattorizzare il loro prodotto. In questo modo, il prodotto può essere reso pubblico insieme alla chiave di codifica.
Vediamo ora di presentare l’algoritmo RSA.
Nota: Le formule matematiche presenti saranno espresse in maniera “estesa”, non potendo essere rappresentate per problemi di formattazione del testo.
- Si scelgono, in modo casuale, due “grandi” numeri primi p e q;
- Si calcola n, come prodotto di p e q;
- Si calcola la funziona di Eulero E di n, ossia il prodotto di (p-1) (q-1);
- Si sceglie un numero e tale che il massimo comun divisore di ed ed E sia 1. In formula matematica: M.C.D. (e,E) = 1;
- Si calcola d tale che il prodotto e sia congruo a 1 modulo E.
I numeri n, e, d vengono solitamente chiamati modulo, esponente di codifica (o pubblico) e esponente di decodifica (o privato).
La coppia di numeri (n,e) costituiscono la chiave pubblica, mentre d costituisce la chiave privata. I numeri p e q a questo punto possono essere eliminati.
Va sottolineato comunque che a seconda delle implementazioni dell’algoritmo RSA, la chiave privata può contenere anche altri “elementi”. Quindi è facile trovare in letteratura e nelle varie implementazioni chiavi segrete del tipo (n,d) oppure (p,q, E,d).
La codifica di un messaggio M nel corrispondente testo cifrato C avviene nel seguente modo:
C = (M elevato a e) modulo n
La decodifica invece avviene nel seguente modo:
(C elevato a D) = M modulo n
Consideriamo ora un esempio di come generare le chiavi pubbliche e private. Per semplicità, utilizzeremo dei numeri primi piccoli.
- Siano p = 5, q = 7;
- Quindi, n = p q = 35, E = 4 * 6 = 24;
- Si calcola e in modo tale che: M.C.D. (e, E) = 1. Allora e = 7. La nostra chiave pubblica è la coppia (n,e) = (35,7);
- Si calcola d in modo tale che d sia congruoa (e-1 mod E). Quindi la nostra chiave privata sarà d = 7.
Supponiamo, sempre per semplicità di calcolo, di dover cifrare il nostro messaggio M = 3. Quindi il nostro testo cifrato sarà C = (3 elevato alla 7) modulo 35 = 17
Per decifrare il messaggio, dovrò calcolare (17 elevato a 7) modulo 35, riottenendo M = 3.
Nel corso degli anni, di fatto l’algoritmo RSA ha più volte dimostrato la sua robustezza: di fatto, ancora oggi, a distanza di 30 anni dalla sua nascita, RSA costituisce uno dei sistemi di crittografia più utilizzati, in particolare nella firma digitale.
