Chiavi L'automazione della sicurezza

I passaggi matematici dell’RSA

Ignora collegamenti di navigazioneHome > Schede approfondimento > I passaggi matematici dell'RSA venerdì 14 dicembre 2018
Ignora collegamenti di navigazione
I passaggi matematici dell’RSA
L’epifania di Diffie
I passaggi matematici dell’RSA Top
1. Alice sceglie due numeri primi molto grandi p e q e li tiene segreti (per brevità, p=17 e q=11);

2. N=p*q (N=187). Alice sceglie il numero y tale che y, p-1 e q-1 siano primi tra loro (y=7);
3. Alice pubblica y e N, cioè le chiavi pubbliche;
4. il messaggio M è cifrato in modo da originare il crittogramma C secondo la formula C=M^y(mod N); (in realtà ogni lettera di M viene tradotta nel relativo codice ASCII)
5. Se Bob vuole inviare semplicemente il messaggio M=’X’ (bacio): M=88=Ascii('X'); C=88^7 (mod 187)=11
6. Alice può decifrare il messaggio perché conosce le chiavi private p e q che le permettono di calcolare il numero d nel seguente modo: y*d=1 (mod (p-1)*(q-1))--> d=23
7. Alice riceve il messaggio C=11 e procede nel seguente modo: M=C^d (mod N)=11^23(mod 187)=88 cioè X
Nella realtà i numeri p e q sono scelti ciascuno di grandezza pari a circa 10^306 e al momento attuale non esiste una funzione per scomporre un numero nei suoi fattori primi.

Con il metodo esaustivo la decrittografia da parte di un computer odierno di un solo codice, impiegherebbe circa 10 anni.
L’epifania di Diffie Top
Tra il 1975 e il 1976 il matematico americano Diffie Whitfield pose le basi per l’algoritmo di crittografia che è condizione necessaria per le odierne comunicazioni, denominato RSA.
Diffie Hellman_merkle Il racconto che l’hippie Diffie, ha fatto dell’illuminazione che sta alla base di questa scoperta assomiglia molto ad uno dei racconti di Joyce, eccettuato il finale.
Nel 1975 passavo lunghi periodi di meditazione apparentemente improduttiva e una volta provai un tale senso di frustrazione che arrivai a dire a mia moglie che ero solo uno scienziato fallito, destinato a non concludere mai niente. Le consigliai anche di trovarsi un partner migliore.
Mary mi rispose di avere piena fiducia in me e dopo due sole settimane mi si presentò di colpo un’idea brillante che però subito svanì.
Scesi da basso con l’intenzione di bere una coca e d’un tratto temetti di aver scordato tutto. Mi era venuto in mente qualcosa di interessante, ne ero certo, ma non ricordavo cosa fosse.
Poi lo ritrovai e subito tornai ad emozionarmi; sentivo l’adrenalina scorrermi nelle vene. Per la prima volta da quando mi occupavo di crittografia capivo di aver fatto una scoperta veramente importante. Ebbi come l’impressione che il mondo si fosse fermato.
Diffie aveva architettato un tipo di cifratura basata su una chiave asimmetrica.
Contrariamente alla gente di Dublino la fuga di Diffie ha avuto buon esito.
Simone Testa - www.monci.it