Gli algoritmi di crittografia a chiave pubblica, noti anche come algoritmi asimmetrici, servono a risolvere uno specifico problema nella comunicazione sicura di messaggi su Internet.
Infatti, nonostante la loro proverbiale lentezza di esecuzione, se sono utilizzati dentro protocolli idonei, permettono a due entità che non hanno mai interagito prima di arrivare a possedere una medesima quantità segreta, solitamente chiamata chiave simmetrica, tramite la quale la crittazione e la decrittazione dei messaggi successivi può avvenire in modo efficiente.
Indice degli argomenti
Gli algoritmi asimmetrici
Gli algoritmi asimmetrici sono suddivisi in categorie distinte, a seconda del problema matematico su cui si basa la loro garanzia di sicurezza.
Le tre categorie più famose e più implementate in pratica sono:
- la categoria resa sicura dal problema matematico detto “fattorizzazione” che comprende il famoso algoritmo RSA;
- quella resa sicura dal problema detto “logaritmo discreto” che comprende algoritmi quali ElGamal e DSA (Digital Signature Algorithm);
- quella che sfrutta l’imprevedibilità delle operazioni in spazi matematici detti curve ellittiche e che spesso viene soprannominata ECC (Elliptic Curve Cryptography).
Chiavi private e chiavi pubbliche: terminologia di base
Per impostare correttamente l’esecuzione di un certo algoritmo asimmetrico, dobbiamo immaginare che ogni entità (come per esempio il proprio telefono o il browser su cui stiamo leggendo questo articolo) sia dotata di due informazioni, strettamente correlate tra loro tramite una certa regola.
Una di queste informazioni, in gergo, viene chiamata “chiave privata”, mentre l’altra è detta “chiave pubblica” (da qui il nome della categoria di algoritmi che le usano).
La regola che lega la chiave privata a quella pubblica si declina in una maniera specifica a seconda dell’algoritmo asimmetrico utilizzato.
È assolutamente cruciale che la chiave privata, come suggerisce il suo nome, sia tenuta segreta e al sicuro dall’entità che la possiede. Questa proprietà è assunta come regola inviolabile.
Se una entità terza riuscisse a risalire a tale chiave segreta, riuscirebbe a compromettere la garanzia di sicurezza di qualunque algoritmo asimmetrico che utilizza tale chiave.
La chiave pubblica, al contrario, può essere visionabile da chiunque, e in pratica è spesso necessario che la seconda entità con cui vogliamo scambiare informazioni ne sia a conoscenza.
Chiaramente, la chiave pubblica è collegata con la chiave privata in una maniera tale che dalla chiave pubblica sia difficile trovare la privata.
Inoltre, su Internet, esiste un complesso sistema composto da enti validatori fidati che specificano a quale entità debba essere assegnata una data chiave pubblica.
Tre casi d’uso degli algoritmi asimmetrici
Gli algoritmi asimmetrici hanno tre cruciali applicazioni. La prima consiste nella creazione di una firma digitale.
Se il tuo medico di famiglia vuole dimostrare che il tuo referto è stato effettivamente inviato e prodotto da lui, allora può utilizzare un algoritmo asimmetrico, la sua chiave privata e il referto stesso per produrre una firma digitale.
Questa firma è la crittazione con chiave privata di qualche informazione strettamente dipendente dal referto stesso. Per crittazione, in questo contesto, si intende l’operazione eseguita da un algoritmo asimmetrico volta a ottenere un risultato che, senza la conoscenza della chiave privata del mittente, risulta intrattabile da analizzare o ricreare.
Una volta che si riceve la firma digitale, è possibile utilizzare la chiave pubblica del proprio medico per decrittare la firma e ottenere l’informazione in entrata che l’aveva generata. Con questa informazione è anche possibile verificare la correttezza della firma stessa.
La seconda applicazione
La seconda applicazione consiste nel volersi mettere in contatto con un nuovo collega di lavoro su un’app di messaggi.
Se i due colleghi intendono scambiarsi numerosi messaggi in un breve lasso di tempo, conviene loro utilizzare algoritmi simmetrici, quali AES, visto che sono costruiti per essere i più veloci ed efficienti per crittare e decrittare messaggi (ovvero “mascherare” e “togliere la maschera” a messaggi) in casistiche come questa.
Però, gli algoritmi simmetrici funzionano solo se entrambi i colleghi possiedono la stessa chiave simmetrica da inserire dentro l’algoritmo simmetrico.
Gli scambi di chiave (simmetrica) (key agreement schema o key exchange) permettono a due entità di scambiarsi un’informazione online con un algoritmo asimmetrico senza che altre entità malevoli riescano a carpire tale informazione.
Infatti, seguendo una specifica procedura, è possibile combinare in maniera furba la propria chiave privata con quella pubblica del proprio collega per giungere a una certa quantità che il proprio collega calcola, combinando la sua chiave privata con la nostra pubblica. Questa quantità comune può essere poi utilizzata come chiave simmetrica.
La procedura che permette di combinare le chiavi è più complicata di quella che si può immaginare inizialmente, prevedendo messaggi intermedi per completare correttamente la combinazione di chiavi. Ma questi messaggi non rilasciano alcuna informazione riguardo alle proprie chiavi private o alla chiave simmetrica finale.
La terza applicazione
La terza applicazione imita la funzionalità di crittazione e decrittazione di un algoritmo simmetrico.
Un conoscente potrebbe utilizzare la nostra chiave pubblica per crittare un
messaggio. Il messaggio così crittato può viaggiare in sicurezza su Internet, visto che solo il possessore della chiave privata correlata a quella pubblica usata nella crittazione è in grado di decrittarlo e di risalire al messaggio originale.
Può sembrare strano che gli algoritmi asimmetrici siano utilizzati in questa modalità. Dopotutto, sono quelli simmetrici e non quelli asimmetrici ad essere i più efficienti in questo senso.
Nonostante ciò, questa terza applicazione degli algoritmi asimmetrici trova comunque successo perché permette di:
- eseguire ulteriori verifiche dell’integrità dei messaggi ricevuti;
- creare un ulteriore strato di crittazione di un messaggio oltre quello fornito da un algoritmo simmetrico;
- trasportare una chiave simmetrica.
Il trasporto di chiave simmetrica
Con il trasporto di chiave simmetrica (key transport scheme) si intende una procedura che consiste nel far generare una chiave simmetrica da un mittente, nel crittare questa chiave simmetrica con la chiave pubblica di un destinatario e, appunto, nel trasportare tale chiave simmetrica crittata al destinatario, cosicché possa essere decrittata.
A seconda dei contesti, una procedura di trasporto di chiave potrebbe essere preferibile a una di scambio di chiave. Per esempio, se il destinatario è un dispositivo elettronico poco potente come un microonde, allora risulta più opportuno generare la chiave simmetrica altrove e poi trasportarla nel microonde invece di eseguire uno scambio di chiave.
Le tre categorie di algoritmi asimmetrici: le funzioni botole
Le tre categorie principali di algoritmi asimmetrici sono distinguibili l’una dall’altra in base al problema matematico che le rende sicure. Una maniera analoga per giungere alla medesima distinzione consiste nell’interpretare il problema matematico alla base come una funzione botola.
Per funzione botola (trapdoor function) si intende una particolare operazione matematica che un computer è in grado di calcolare banalmente e la cui operazione inversa risulta sostanzialmente infattibile da calcolare in tempo utile tramite computer, a meno che non si conoscano informazioni aggiuntive dette botole.
Ecco le tre categorie di algoritmi asimmetrici.
La delicatezza di RSA
RSA è l’acronimo dei cognomi degli studiosi Ron Rivest, Adi Shamir e Leonard Adleman che furono i primi a descriverlo pubblicamente alla fine degli anni ‘settanta’70.
Praticamente usato in ogni meandro di Internet, perché è stato studiato a fondo nel corso degli anni, è facile da comprendere ad alto livello ed è molto flessibile. Infatti, con piccoli aggiustamenti specificati negli standard quali il FIPS 186-5 e lo SP800-56B pubblicati dal NIST e il RFC 8017 pubblicato da IETF, RSA può essere usato per firme digitali, scambi di chiave o trasporti di chiave.
La funzione botola di RSA è una moltiplicazione di numeri primi per ottenere una quantità detta modulo. La funzione inversa, che coincide con il problema matematico su cui si basa la sua sicurezza, è la fattorizzazione, ovvero, l’operazione che in entrata prende un numero e in uscita scrive tale numero come prodotto di uno o più numeri primi.
Per precisare, un numero intero positivo è detto primo se è maggiore di 1 e se è divisibile solo per sé stesso e per 1, mentre un numero intero è detto composto se è maggiore di 1 e non è primo. Il problema della fattorizzazione di enormi numeri, in effetti, risulta ancora relativamente intrattabile per un computer moderno.
Infine, la botola consiste nel conoscere la chiave privata, che infatti è composta anche dai numeri primi che compongono il modulo.
Il modulo di RSA nella crittazione e decrittazione
Il modulo di RSA viene utilizzato nell’operazione di crittazione e decrittazione. Infatti, nella sua specifica, RSA prevede a un certo punto di moltiplicare per sé stesso numerose volte un messaggio in entrata (interpretato come numero). Questa operazione è chiamata in gergo elevamento a potenza.
Il modulo viene utilizzato per limitare la dimensione del risultato di questa moltiplicazione per due motivi:
- il primo è per inviare più facilmente su Internet tale risultato troncato;
- il secondo è per complicare la situazione e rendere più arduo risalire alla quantità di volte che il messaggio-numero è stato moltiplicato per sé stesso.
Questa quantità, solitamente chiamata esponente, fa parte anche della chiave privata di RSA insieme ai numeri primi, quindi è importante rendere infattibile per un attaccante risalire a questo esponente. L’intera idea di questo elevamento a potenza modulare, che può essere interpretato come prendere il resto della divisione intera tra un elevamento a potenza e un certo modulo, torna anche nei logaritmi discreti.
Vantaggi e svantaggi
Il fatto che RSA è stato creato tempo fa è contemporaneamente il suo punto di forza e il suo tallone di Achille.
Dalla data della sua ideazione fino ad oggi, nuovi metodi più performanti su computer per fattorizzare numeri sono stati trovati, e i computer stessi sono diventati mostruosamente più veloci.
Ciò significa che la lunghezza del modulo è dovuta piano piano aumentare con il tempo, e più è grande il modulo, più sono le informazioni da inviare su Internet e più è lenta la computazione in sé, anche se migliora la sicurezza.
La lunghezza del modulo oramai viaggia tra i 2048 e i 4096 bits, ovvero, numeri maggiori di 2 moltiplicato per sé stesso 2048 volte.
Inoltre, detta in parole povere, RSA è alquanto delicato e precario, nel senso che numerosi attacchi sono spuntati fuori nel corso degli anni della vita di questo algoritmo, e un’implementazione di RSA deve tenerne conto per evitare che la sua sicurezza sia facilmente violata.
Forniamo qui una rapida carrellata di alcuni fattori da tenere a mente per tenere sicuro RSA.
I messaggi interpretati come numeri piccoli producono una crittazione debole, dunque bisogna trasformare il messaggio in entrata in un numero più grande prima di eseguire RSA.
Per via dell’attacco di Weiner, non possiamo scegliere l’esponente della chiave privata troppo piccolo.
A causa del metodo di fattorizzazione di Fermat e dell’algoritmo di Pollard p-1, se RSA usa solo due numeri primi nel modulo, questi primi non devono essere troppo vicini tra loro e devono avere ulteriori proprietà specifiche. Selezionare erroneamente un numero composto al posto di uno dei primi della chiave privata di RSA potrebbe far risalire alla fattorizzazione del modulo in maniera imprevedibilmente facile.
E, come se non bastasse, un’implementazione potrebbe comunque essere esposta ad attacchi che controllano il tempo di esecuzione dell’intero algoritmo, o che controllano la scheda su cui viene eseguito il calcolo, o che sfruttano semplificazioni ottenibili tramite il Teorema cinese del resto.
Insomma, RSA può essere implementato in maniera sicura. Ma arrivare ad avere un’implementazione che evita o mitiga tutti gli attacchi instaurabili su RSA è sicuramente complicato.
L’inefficienza dei logaritmi discreti
Il problema dei logaritmi discreti viene utilizzato da celebri algoritmi asimmetrici quali ElGamal, la firma digitale di Schnorr e il DSA (o Digital Signature Algorithm).
ElGamal è comparso per la prima volta intorno alla metà degli anni Ottanta, la firma di Schnorr è stata brevettata all’inizio degli anni Novanta e Dsa è stato standardizzato dall’ente statunitense NIST a metà degli anni Novanta.
DSA può in realtà essere visto come una variante dei due algoritmi precedenti, con alcune accortezze in più descritte in un apposito standard del NIST. La versione dello standard più recente in cui compare DSA si chiama FIPS 186-5.
La funzione botola utilizzata da questa categoria di algoritmi asimmetrici è un elevamento a potenza modulare, ovvero, come dicevamo in RSA, una moltiplicazione di un elemento per sé stesso un numero “esponente” di volte.
La botola di questa categoria è la conoscenza dell’esponente dell’elevamento a potenza, che funge da chiave privata. La funzione inversa, intrattabile per un computer tradizionale, è invece chiamata logaritmo discreto.
Con il termine logaritmo si intende quell’operazione che prova a estrarre l’esponente da un risultato di un elevamento a potenza. In questo contesto, l’aggettivo discreto, che solitamente in matematica è utilizzato per indicare un numero intero e senza virgola, serve invece a sottolineare quanto sia peculiare e complicato il luogo in cui il problema del logaritmo risulta arduo.
Difatti, ElGamal, Schnorr e DSA svolgono operazioni di elevamento a potenza modulari che però possono assumere solo alcuni tra tutti i possibili valori interi positivi minori del modulo fissato.
Al contrario, RSA permette alle sue operazioni di toccare qualsiasi valore positivo minore del modulo.
I 3 algoritmi asimmetrici meno attaccabili di RSA
Aggiungendo questa restrizione dei possibili risultati ottenibili, questi tre algoritmi asimmetrici risultano molto meno attaccabili di RSA, dunque la loro implementazione risulta più lineare nella maggioranza dei casi. Sono comunque largamente utilizzati su Internet, e sono stati studiati a sufficienza sia in teoria che in pratica.
Nonostante questo, anche questa tipologia di algoritmi ha considerevoli svantaggi. Infatti, il tempo effettivo di esecuzione di tali algoritmi è paragonabile a quello di RSA, cioè nell’ordine di alcuni secondi, e hanno anche un grande costo computazionale, visto che i messaggi che producono e le chiavi di utilizzano sono parecchio lunghi.
Le operazioni svolte sulle curve ellittiche
Gli algoritmi asimmetrici che si basano su curve ellittiche presentano per costruzione vantaggi molto interessanti.
Innanzitutto, esse sono prive di attacchi travolgenti come quelli che affliggono RSA. Inoltre, essi producono dati in uscita che sono molto più corti e maneggiabili rispetto ai dati prodotti dagli algoritmi delle altre due categorie, visto che i primi tirano fuori sequenze considerate sicure usando solo sequenze di un centinaio di zeri e uni, mentre i secondi trattano sequenze lunghe nell’ordine di alcune migliaia di elementi.
Infine, gli algoritmi con curve ellittiche sono efficienti, perché lavorano con piccole quantità e producono il loro risultato molto più in fretta delle altre alternative.
La funzione botola di questa tipologia di algoritmi asimmetrici è la moltiplicazione tra un numero intero e un punto di una curva ellittica. La maniera più intuitiva con cui possiamo presentare il concetto di curva ellittica è la seguente.
I punti di una curva ellittica possono essere visti come tanti tulipani sporadici sparsi in un prato principalmente erboso. Essi crescono in una maniera che appare disordinata, e non esistono tecniche facili per intuire se una certa zona contenga o meno un tulipano.
Moltiplicare un numero per un punto di una curva ellittica consiste nel selezionare un certo tulipano di partenza e spostarsi in un tulipano finale, passando in maniera imprevedibile in tanti tulipani intermedi quanti specificati dal numero in entrata.
Un attaccante che conosce solo il tulipano di partenza e quello di arrivo non riesce a predire quanti tulipani intermedi si toccano.
La botola nelle curve ellittiche
Come è intuibile, la botola nelle curve ellittiche è il numero intero usato nella moltiplicazione per un punto, e tale numero svolge la funzione di chiave privata. La funzione inversa, che consiste nel dover in qualche modo estrarre il numero moltiplicato dal punto finale conoscendo il numero iniziale, è sostanzialmente intrattabile in un computer tradizionale attuale.
Gli algoritmi asimmetrici basati su curve ellittiche hanno iniziato a prendere piede all’inizio di questo millennio, subito dopo che il NIST li ha standardizzati, e da anni i grandi browser come Chrome, Safari ed Edge lo supportano nativamente.
La ECC (Elliptic Curve Cryptography) prende particolarmente piede in quelle situazioni in cui la velocità e la facilità di computazione sono importanti. Quindi, automobili e dispositivi elettronici delle case hanno l’importante libertà di utilizzare ECC al posto di RSA ed ElGamal.
Addirittura, le curve ellittiche sono anche utilizzate in alcune criptovalute, quali bitcoin.
La scelta delle curve ellittiche
Ma esistono anche contesti in cui ECC potrebbe non essere la scelta ottimale. Spesso, se si deve parlare con banche di dati o siti Internet di moltissimi anni fa, conviene utilizzare direttamente solo algoritmi precedenti all’avvento dell’ECC.
Inoltre, per massimizzare il guadagno di efficienza ottenibile, le operazioni sulle curve ellittiche devono essere implementate e ottimizzate, e chiaramente questo lavoro risulta in media più complesso di quello richiesto da RSA o ElGamal.
Detto questo, è comunque facilmente intuibile il perché le curve ellittiche siano state una aggiunta ben accetta allo scenario degli algoritmi asimmetrici.
Il futuro degli algoritmi asimmetrici
Gli algoritmi asimmetrici si usano costantemente su Internet per far iniziare una comunicazione sicura tra due entità e per produrre firme digitali. A meno di avere particolarmente cura a mitigare tutti i vari attacchi, la difficoltà della fattorizzazione di un modulo RSA permette sia di scambiare chiavi con un vecchio sito, sia di firmare digitalmente un nostro referto.
Il logaritmo discreto, come declinato in ElGamal, Schnorr e DSA, offre una robusta alternativa a RSA, rendendo più difficile montare attacchi, ma rimanendo ancora un po’ lento.
Le curve ellittiche utilizzate nella ECC fanno ottenere prestazioni eccellenti a meno di impegnarsi maggiormente nella fase iniziale di scrittura della loro implementazione, e sono sostanzialmente il fiore all’occhiello degli algoritmi asimmetrici nei computer tradizionali moderni.
È proprio qui la criticità. Anche se i computer quantistici sono ancora in fase di studio, è estremamente probabile che la vendita di computer quantistici a persone comuni sia dietro l’angolo.
Dal punto di vista crittografico, con un minimo aggiustamento, AES e gli algoritmi simmetrici resisteranno bene a questa novità. Invece, l’algoritmo di Shor, efficiente solo su computer quantistico, trivializza le funzioni inverse di ognuna delle tre categorie di algoritmi asimmetrici analizzate.
Realizzando l’importanza di prevenire la minaccia quantistica e di iniziare la lunga fase di aggiornamento dei sistemi, il NIST ha già indetto una competizione pubblica per standardizzare nuovi algoritmi asimmetrici in grado di sostituire quelli attuali e di resistere ad attacchi quantistici.
Sarà proprio la crittografia post-quantistica a mitigare questa imminente minaccia.
