Le chiavi pubbliche e l'RSA

Il sistema ideato da Diffie e Hellman, nonostante garantisse un elevato livello di sicurezza, non raggiunse mai il livello di diffusione che meritava, a causa dell'elevato dispendio di tempo necessario a concordare periodicamente la chiave con cui poi cifrare il messaggio. Fortunatamente questa non fu l'unica grande intuizione dei due crittografi: essi avevano immaginato anche un altro sistema per risolvere il problema della diffusione delle chiavi, molto più efficace e pratico.

Vediamo in pratica, tornando ad Alice e Bob, l'ulteriore sistema teorizzato da Diffie e Hellman.
Supponiamo che Bob voglia mandare un messaggio ad Alice utilizzando un servizio pubblico facilmente accessibile: quello postale. Purtroppo nella loro città il servizio postale è estremamente inaffidabile, e i postini si divertono a curiosare nella posta indirizzata ad Alice. Allora Alice decide di dare a ogni ufficio postale un gran numero di lucchetti aperti tutti uguali, con la stessa serratura, ma di cui solo lei ha l'unica chiave in grado di aprirli. Così Bob, posto il suo messaggio da inviare ad Alice in una scatola di metallo, deve solo andare all'ufficio postale e chiedere "un lucchetto di Alice". Per lui sarà banale usare il lucchetto per chiudere la scatola, ma in questo modo nessuno riuscirà più a riaprirla per vedere il messaggio, tranne Alice, che è l'unica che possiede la chiave.

Hellman e Diffie

Generalizzando il caso di Bob e Alice, immaginiamo che esista una sorta di elenco telefonico, consultabile da chiunque, dove a ogni persona sia associata una chiave "pubblica", con cui Bob, Carlo, Andrea o chiunque altro possa criptare il proprio messaggio e soltanto la persona a cui è indirizzato abbia la chiave "privata", diversa da quella pubblica, con cui decrittare il messaggio. Con questo sistema esisteranno due chiavi "asimmetriche", diverse fra loro, di cui una, quella per criptare, diffondibile pubblicamente, e l'altra, per decrittare, privata e segreta.

Chiavi RSA

Questa idea, semplice ma al tempo stesso geniale, rimase tuttavia solo un'idea nelle menti di Diffie e Hellman, poiché, nonostante i loro studi, non riuscirono a trovare una funzione che soddisfacesse le loro esigenze. Diffusa tra la comunità scientifica questa idea rimase incompiuta fino a quando, nell'aprile del 1977 tre matematici, Rivest, Shamir e Adleman trovarono la funzione che tanto a lungo era stata cercata, inventando così l'RSA, dalle iniziali dei loro cognomi. Attualmente l'RSA è considerato il più inviolabile dei sistemi di sicurezza al mondo ed è comunemente usato da grandi agenzie governative segrete e di spionaggio, ma anche quando semplicemente paghiamo un gelato con il bancomat.

Vediamo adesso, in modo approfondito, i criteri matematici alla base del funzionamento della crittografia RSA.

Si scelgono due numeri primi P e Q, e si calcola il loro prodotto M, con la codizione M>X dove X è il messaggio da crittare in forma numerica (ad esempio se trascritto atraverso il sistema binario dove ogni carattere è associato a una sequenza di 0 e 1).

Successivamente si calcola φ(M), detta funzione di Eulero, che è il numero degli interi minori di M che sono primi con M.  Dunque, se P e Q sono primi, φ(P) e φ(Q) sono rispettivamente P-1 e Q-1.  E' inoltre possibile dimostrare che φ(M)=φ(P·Q)=(P-1)(Q-1).

Si sceglie poi un numero A tale che esso sia primo con φ(M). In linguaggio matematico (A,φ(M))=1

Dopodiché si calcola un numero B tale che A·B+nφ(M)=1 dove n è un numero intero negativo qualsiasi. Questo tipo di equazione ha un numero infinito di coppie (B,n) come risultati ma, grazie a un algoritmo tipico dell'aritmetica dei moduli, è possibile calcolare la coppia con B il più piccolo possibile. Bisogna innanzitutto calcolare il resto della divisione fra A e φ(M), dunque φ(M)=nA+r1. Dopodiché calcoliamo il resto della divisione fra A e r1

A=nr1+r2    e così via finche non otterremo un resto uguale a 0

r1=nr2+r3

r2=r3+r4 

rn=rn+1+0

Questo algoritmo, detto algoritmo di Euclide, è anche utilizzato per calcolare il massimo comune divisore fra due numeri, che sarà esattamente l'ultimo resto della divisione diverso da 0, ma dato che in questo caso abbiamo scelto A e φ(M) affinché siano primi fra loro l'ultimo resto diverso da 0 sarà 1.

A questo punto, risalendo i passaggi all'indietro e lasciando sempre in evidenza il resto finale 1, ricaviamo i fattori moltiplicativi di A e φ(M).

Per esempio, se dobbiamo calcolare: 260X+231Y=1

Calcoliamo i resti delle divisioni
nei vari passaggi

260=23·11+29

231=29·7+28

29=28·1+1

mettiamo in evidenza il resto
in ciascun passaggio

29=260-231

28=231-29·7

1=29-28

Adesso sostituiamo i numeri 28 e 29 dell'ultima equazione
con le espressioni delle altre due

1=(260-231)-[231-(260-231)·7]

se risolviamo otteniamo che 

1=260·8-231·

abbiamo dunque ottenuto X=8 e Y=-9

Una volta determinati i nostri risultati, possiamo diffondere la chiave pubblica, che sarà composta dalla coppia di numeri M e A. Questi due valori possono tranquillamente essere divulgati e saranno usati per criptare il messaggio da spedire.

Chi vuole mandare il suo messaggi X dovrà calcolare [XA]M, che, come già detto, è per lui un'operazione relativamente semplice.

Fatto ciò questa persona può spedire, senza problemi di sicurezza, il messaggio Y. Questo non corre il rischio di essere decrittato perché, come già spiegato, è ottenuto attraverso una funzione univoca. Ma come faremo noi destinatari allora a decrittarlo?

Ricevuto il messaggio Y a noi basterà calcolare [YB]M. Per alcune proprietà dell'elevamento a potenza nell'aritmetica dei moduli e per il modo particolare con cui sono stati scelti i vari numeri, soprattutto B, a seguito del calcolo finale il risultato sarà uguale al messaggio originale X.

Facciamo un esempio: prendiamo come P e Q i numeri primi 7 e 11. Dunque M=77 e φ(M)=6x10=60. Scegliamo A che sia primo con 60, A=13. Calcoliamo B tale che 13B+60n=1 e troviamo B=37.

Ottenuti tutti i nostri dati diffondiamo apertamente la chiave pubblica M=77 e A=13

Bob, per mandarci il suo messaggio lo trasforma in un numero secondo un metodo universalmente stabilito (generalmente si usa il codice binario): supponiamo che voglia scrivere la parola DIECI, assegnando ogni lettera dell'alfabeto a un numero da 0 a 20 (A=0 B=1 C=2...) allora DIECI diventa l'insieme di numeri [3, 8, 4, 2, 8]. Criptando una lettera per volta otterremo ciò:

D3⇒[313]77=38

I8⇒[813]77=50

E⇒4⇒[413]77=53

C⇒2⇒[213]77=30

I⇒8⇒[813]77=50

Una volta criptato il suo messaggio, Bob può spedire i numeri 38, 50, 53, 30, 50, e il destinatario eleva ogni numero alla sua chiave B e calcola [X37]77 per riottenere il messaggio iniziale, che tramuterà poi in forma letterale.

38⇒[3837]77=3⇒D

50⇒[5037]77=8⇒I

53⇒[5337]77=4⇒E

30⇒[5337]77=2⇒C

50⇒[5037]77=8⇒I

In questo modo possiamo riottenere il messaggio iniziale.

Come può dunque questo sistema di crittografia essere inviolabile?

La difficoltà nel cercare di decodificare un messaggio così protetto sta nel fatto che, una volta crittato con la chiave pubblica A e M, il messaggio necessita della chiave privata B per essere decrittato. Per calcolare la chiave B è necessario conoscere φ(M), che di per sé è impossibile da calcolare conoscendo solo M, ma se si conoscono i due fattori P e Q che lo compongono, allora basta calcolare (P-1)·(Q-1). E' di fatto impossibile conoscere i due numeri primi che moltiplicati forniscono come risultato M, se è noto solo M. L'unico modo sarebbe dunque fattorizzare M per ottenere P e Q, fatto sta che la fattorizzazione di un numero è uno dei più grandi problemi della storia della matematica, poiché non esiste un algoritmo semplice per svolgerlo. Dunque, anche se M è pubblicamente divulgato, questo sistema si basa sul fatto che nessuno riuscirà, in un arco di tempo ragionevole, a trovare P e Q per riuscire a decrittare i messaggi.

Appena scoperto l'RSA, i tre crittografi lanciarono una sfida alla comunità mondiale dei matematici, cifrando un testo e fornendo come chiave pubblica:

M=114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541

Chiedevano di fattorizzare il numero nei due numeri primi P e Q che lo componevano per riuscire a decrittare il messaggio, e il premio era di 100$.

Tale sfida fu risolta 17 anni dopo il 26 Aprile 1994, da un gruppo di 600 volontari di tutto il mondo. I fattori erano:

  • P = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577
  • Q = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533

Anche tenendo conto dell'enorme sforzo simultaneo si potrebbe rimanere sorpresi del fatto che il codice sia stato violato in un tempo relativamente "breve", ma c'è da tenere conto che, come nel caso del sistema di Diffie e Hellman, è sufficiente aumentare la grandezza dei numeri in questione per rendere impossibile la fattorizzazione di M. La chiave pubblica fornita dagli inventori dell'RSA era dell'ordine di 10129, mentre le chiavi comunemente usate oggi sono dell'ordine almeno di 10300.

Shamir, Rivest e Adleman

Come è possibile notare, però, nell'esempio esposto con la parola DIECI, i due numeri risultanti dalla crittazione delle due lettere I sono identici. Tale ricorrenza potrebbe costituire un aiuto per coloro che cercano di trovare falle in questo sistema, poiché, se si ha a disposizione una grande quantità di materiale crittografato è possibile intuire delle ricorrenze alfabetiche, come nei cruciverba. Tale problema implicherebbe la modifica continua delle chiavi pubbliche, ma fortunatamente, dato che sarebbe macchinoso trovare un nuovo numero M e i suoi due numeri primi P e Q, è sufficiente modificare la chiave pubblica A, e di conseguenza anche quella privata B.

Chiavetta RSA

Attualmente, per operazioni delicate quali la protezione di transazioni bancarie via Internet, vengono forniti generatori casuali del numero A sotto forma di chiavette elettroniche, consegnate dalle banche ai rispettivi utenti. Queste chiavette elettroniche permettono di determinare, simultaneamente al sistema centrale della banca, il numero A. L'utente introduce nella schermata di Interner-banking le disposizioni da inoltrare alla banca, che vengono criptate dall'apposito software con la chiave pubblica M della banca e quella individuale A della chiavetta. Il sistema informatico della banca calcola la chiave per decrittare B in base alla chiave usata A e la chiave segreta φ(M). Naturalmente la banca dispone del numero apparso sulla chiavetta RSA consegnata al cliente, dal momento che questa produce una sequenza continua di valori in perfetta sincronia temporale con il sistema centralizzato della banca stessa.

Inoltre questo sistema di crittografia permette anche una "garanzia di ricevuta": infatti il destinatario del messaggio codificato può criptare a sua volta un messaggio di risposta X. Questo messaggio, per essere decrittato necessita della chiave pubblica M e A: in questo modo, anche se il messaggio è comprensibile da chiunque, in quanto tutti conoscono la chiave pubblica, il destinatario ha la certezza di chi è il mittente, il solo a conoscere φ(M), da cui si ricava B.

Il procedimento è il seguente:

X⇒[XB]M=Y

Y⇒[YA]M=X