Renato Betti


IL SISTEMA RSA

Questo sistema, di pochi anni successivo all'idea delle funzioni a trabocchetto, compare in Rivest, Shamir e Adleman [8] e si basa proprio sulla difficoltà a reperire sufficienti risorse di calcolo per la scomposizione in fattori primi di numeri interi che hanno molte cifre.

L'algoritmo proposto per l'implementazione pratica sfrutta in maniera sapiente la complessità computazionale di alcuni processi della Teoria dei numeri, relativi alla Aritmetica modulare (di cui si parla nel box qui accanto, nel quale si illustrano anche i risultati che permettono all'algoritmo di funzionare).
Vale la pena di osservare che questi risultati, tutti riassunti e compiutamente espressi nelle Disquisitiones Arithmeticae di Gauss (1801), erano sostanzialmente già noti ad Eulero e, in qualche caso, anche a Fermat nel corso del `600. A noi sembra che l'applicazione di questi risultati, trovati in un periodo in cui le prospettive del calcolo veloce non erano neppure lontanamente concepibili, sia un esempio straordinario della fecondità del pensiero matematico e della razionalità che è intrinseca alla ricerca di questi grandi personaggi della Matematica.
Cominciamo ad illustrare l'idea che si trova alla base del sistema di Crittografia a chiave pubblica, osservando che alcune operazioni che possono sembrare a prima vista molto onerose rispetto al tempo di calcolo risultano invece facilmente calcolabili: è questo il caso, ad esempio, degli esponenziali e del massimo comune divisore di due numeri -anche molto grandi- così come del calcolo dei resti modulo n. È interessante notare che questa semplicità, pur nelle varianti che sono state elaborate nel tempo, è essenzialmente fornita da un altro risultato classico di grande importanza: l'algoritmo delle divisioni successive o algoritmo euclideo, che affonda le sue radici e la sua ragione d'essere negli Elementi di Euclide e nei problemi dibattuti nel III secolo prima di Cristo (per i problemi di complessità computazionale che riguardano le diverse operazioni si può consultare, ad esempio, Salomaa [9] oppure Ferragine e Luccio [10]).



Euclide
Tutto è pronto per mettere in funzione il sistema: chi intende divenire il destinatario di messaggi riservati - diciamo che sia Bob - fissa e rende pubblica la propria chiave, in modo che chiunque voglia mandargli un messaggio cifrato (non solo Alice, ma anche altri) sappia come comportarsi. A questo scopo, Bob deve compiere alcune scelte ed alcune operazioni preliminari: è superfluo osservare che dalla bontà di queste scelte dipende la sicurezza del cifrario.

Qui non vale però la pena di entrare in questi dettagli, ma piuttosto cercare di chiarire il metodo nei suoi principi (chi sia invece impaziente di conoscere questi particolari consulterà Koeblitz [11], Salomaa [9] o Ferragine e Luccio [10]).
Bob sceglie una coppia di numeri (e, n) con la condizione che e e φ(n) non abbiano fattori primi comuni:
MCD(e, φ(n)) = 1
Abbiamo detto che questa scelta non presenta difficoltà di calcolo anche se i due numeri e ed n saranno piuttosto grandi e, come è stato osservato, è bene che la scelta rispetti opportuni criteri per aumentare la solidità del sistema. Questa coppia (e, n) è la chiave pubblica di Bob, che lui lascia a disposizione di tutti, ma attenzione... Bob non farà nessun accenno al valore di φ(n) -neppure ad Alice- perché questo è il suo segreto, la sua chiave personale che permette di decifrare i messaggi.
Per la verità, per mezzo di φ(n), Bob calcola un numero d che risolva la congruenza di primo grado:

e*x≡1 (mod φ(n))

È questo numero d (mod φ(n)) che utilizza direttamente per decrittare i messaggi. La condizione che e e φ(n) siano primi fra di loro garantisce che la congruenza precedente ammette un'unica soluzione, a meno di congruenze modulo φ(n).
Ora chiunque ha la possibilità di mandare a Bob un messaggio riservato e questi è pronto per decrittarlo. Il procedimento avverrà così: Alice, ad esempio, gli vuole comunicare il messaggio m (che è già opportunamente codificato con un numero). A questo scopo, eleva m all'esponente e e calcola il resto modulo n del numero ottenuto. Ha utilizzato esattamente l'informazione che Bob ha comunicato a tutti - la sua chiave pubblica (e, n) - ottenendo il messaggio cifrato c:

cme (mod n)

Come può Bob ricostruire il messaggio, cioè risalire da c ad m, e perché nessun altro che intercetti c e conosca la chiave pubblica di Bob è in grado di fare altrettanto? Per Bob è facile, perché conosce φ(n) ed ha calcolato d. Gli basta elevare il messaggio cifrato c all'esponente segreto d. Infatti, per come è stato trovato, ed = kφ(n)+1 in corrispondenza a qualche intero k e si ha quindi:

cd≡(me)d ≡med≡mkφ(n)+1≡(mφ(n))k*m ≡m(mod n)

dove si sono usati la proprietà di stabilità della relazione di congruenza rispetto al prodotto ed il teorema di Eulero-Fermat: mφ(n)≡1 (mod n).
Qual è il segreto che permette solo a Bob di decifrare il messaggio? Chiaramente risiede nell'esponente d che usa e che inverte (modulo φ(n)) la chiave cifrante e. E d si ricava conoscendo φ(n): come si è detto, è qui il vero segreto perché il calcolo di φ(n) è tanto complesso quanto la scomposizione di n in fattori. Quando ha scelto la propria chiave pubblica, Bob ha avuto l'accortezza di scegliere n come prodotto di certi numeri primi e dunque, grazie alla proprietà moltiplicativa della φ di Eulero, il calcolo di φ(n) gli risulta estremamente agevole. Si saranno riconosciute, in questo processo, le proprietà fondamentali del calcolo modulare e della φ di Eulero.
La strategia ottimale di Bob è precisamente quella di scegliere n come prodotto di due soli numeri primi, abbastanza grandi e non troppo prossimi fra di loro. In questo modo è n = p*q con p e q primi e si ha:

φ(n)=(p - 1)*(q - 1)

Dunque, tutto si basa sulla scomposizione in fattori primi. Questo fatto indica anche il "punto debole" del sistema crittografico: la sicurezza riposa sulla nostra "ignoranza" di molti fenomeni relativi ai numeri primi. Se e quando la ricerca matematica riuscirà a risolvere i problemi della distribuzione dei numeri primi e troverà un metodo efficiente per la scomposizione in fattori, il metodo perderà immediatamente la sua efficacia... e ci si dovrà rivolgere verso nuove funzioni a trabocchetto.
Ancora una volta, come spesso accade, il progresso tecnico rimane subordinato in maniera diretta alla conoscenza teorica.