La crittografia dietro a Bitcoin

Analizziamo più in profondità alcuni concetti di crittografia che vengono utilizzati anche per far funzionare il sistema Bitcoin.

IL CIFRARIO DI CESARE

Quasi ogni manuale di crittografia inizia con una breve descrizione del cosiddetto cifrario di Cesare, un metodo di cifratura utilizzato, appunto, da Giulio Cesare che consisteva nel sostituire ciascuna lettera di un testo con quella di tre posizioni più avanti nell’alfabeto.

Questo semplice algoritmo, ben poco sicuro già all’epoca in qui veniva utilizzato, è soggetto a rivelarsi sostanzialmente inutile se al testo cifrato viene applicata quella tecnica crittoanalitica denominata “analisi delle frequenze”, che studia le statistiche relative alla presenza dei singoli simboli o gruppi di simboli nel testo offuscato.

Appare ovvio che algoritmi maggiormente articolati sono anche più complessi da applicare, specie se si può ricorrere solamente a carta e penna.

È per questo motivo che la scienza crittologica ha ottenuto enormi benefici dall’uso degli odierni elaboratori elettronici, ma anche dalla precedente utilizzazione di macchine elettromeccaniche, la più famosa delle quali è sicuramente Enigma, utilizzata dalla forze armate tedesche durante la seconda guerra mondiale e ritenuta, a torto, praticamente indecifrabile.

CRITTOLOGIA E INFORMATICA

Il contributo del matematico inglese Alan Turing alle attività di crittoanalisi della macchina Enigma è ormai noto anche al grande pubblico, mentre è comunemente accettato il fatto che la moderna crittologia nasce successivamente, con la pubblicazione, nel 1949, dell’articolo Communication Theory of Secrecy Systems ad opera del matematico e ingegnere statunitense Claude Shannon.

Shannon, in questo articolo, unisce la teoria dell’informazione, del quale è considerato un po’ il padre, alla crittologia.

Il suo studio è interessante anche perché riesce a dimostrare matematicamente che l’unico metodo crittografico totalmente sicuro è quello che prevede una chiave, non riutilizzabile, lunga quanto il testo da cifrare. Questo algoritmo è detto cifrario di Vernam o anche one-time pad.

Si tratta, ovviamente, di un caso limite, in quanto risulta molto scomodo cifrare testi in chiaro con chiavi di pari lunghezza (senza contare, poi, il problema della trasmissione delle chiavi), ma è una procedura che risulta essere stata realmente adottata anche durante la cosiddetta guerra fredda.

SICUREZZA DEI SISTEMI CRITTOGRAFICI

Posto che «non esiste un modo noto per testare se un sistema [crittografico] è sicuro» (Ferguson/Schneier/Kohono, 2011, Il manuale della crittografia. Applicazioni pratiche dei protocolli crittografici, Apogeo, pag. 11), negli anni sono stati stabiliti dei punti fermi, o comunque delle cosiddette buone pratiche.

Un fatto ormai accettato è che «la sicurezza offerta da un sistema crittografico è affidata esclusivamente alla segretezza della chiave» (Sgarro 1993, Crittografia. Tecniche di protezione dei dati riservati, Muzzio, 10).

Ovvero si accetta il principio formulato da Auguste Kerckhoffs nel 1883 (in La Cryptographie Militaire) secondo il quale un sistema non deve risultare compromesso nel caso in cui il nemico venga a scoprire l’algoritmo di crittazione.

Shannon ribadisce il concetto in maniera ancora più esplicita quando scrive: «il nemico conosce il [tuo] sistema».

Secondo molti studiosi «esistono buone ragioni per rendere pubblici gli algoritmi [di crittazione]» (Ferguson/Schneier/Kohono 2011, pag. 23), soprattutto per consentire una fase di testing che è impossibile attuare con gli algoritmi segreti.

La segretezza, nella crittografia presentata finora, sta quindi tutta nella chiave, che viene utilizzata indifferentemente per cifrare e decifrare il messaggio. Tutto ciò rappresenta, da sempre, un grave problema.

CRITTOGRAFIA A CHIAVE PRIVATA

Poniamo di avere due soggetti che vogliono comunicare segretamente tra loro, che chiameremo Alice e Bob.

Le figure di Alice e Bob sono state probabilmente introdotte per la prima volta nel paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (Rivest/Shamir/Adleman, 1978, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in «Communications of the ACM», 21 (2), pagg. 120–126.) e in seguito utilizzate in molti altri testi per descrivere situazioni simili.

L’algoritmo di cifratura è noto a entrambi i soggetti e può esserlo anche al nemico, senza che questo rappresenti un problema per la sicurezza.

Alice prepara il testo in chiaro e poi lo cifra con una chiave segreta. Manda il messaggio a Bob, il quale ha bisogno della chiave per decifrarlo. Si pone la necessità di avere un canale di comunicazione sicuro per trasmettere la chiave, dato che il canale utilizzato per trasmettere il messaggio viene considerato insicuro.

Se poi Alice deve comunicare non solo con Bob, ma anche con altri soggetti, dovrebbe gestire almeno altrettante chiavi segrete, rendendo molto complesso il suo operato.

INTERCETTAZIONE DELLE COMUNICAZIONI

Introduciamo una terza figura, il nemico, che chiamiamo Eva, e lo piazziamo tra Alice e Bob. Questo tipo di configurazione prende il nome di man in the middle, ovvero una situazione in cui Eva è in grado in intercettare e anche modificare o sostituire i messaggi che Alice invia a Bob.

Eva potrebbe riuscire a rubare la chiave e quindi a leggere tutti i messaggi, oppure riuscire a decriptarli senza chiave provando le varie tecniche note di crittoanalisi.

Se in possesso della chiave segreta (rubata o ricostruita in qualche maniera), Eva sarebbe inoltre in grado di sostituire completamente o modificare i messaggi.

Da tutto ciò emerge un’ulteriore esigenza, quella legata all’autenticazione dei messaggi, ovvero Bob deve essere sicuro che i messaggi che riceve da Alice siano veramente scritti da lei e non siano stati adulterati nella fase di trasmissione dell’informazione. Con l’introduzione delle funzioni di hash (approfondite più in là nel testo) questo esigenza viene soddisfatta.

Quanto esposto fino a qui ricade nel “territorio” nei cosiddetti sistemi crittografici simmetrici, talvolta detti a chiave simmetrica.

Si tratta di situazioni in cui Alice (il mittente) e Bob (il destinatario) condividono la stessa chiave segreta, che viene utilizzata per cifrare il testo in chiaro e successivamente per decifrare il crittogramma.

CRITTOGRAFIA ASIMMETRICA

Negli anni ’70 del XX secolo vengono introdotti i sistemi crittografici asimmetrici, detti anche a chiave pubblica.

Nel 1976 il matematico Whitfield Diffie e l’informatico Martin Hellman pubblicano l’articolo New Directions in Cryptography, nel quale propongono, a livello teorico, un sistema crittografico caratterizzato dall’uso di due chiavi (Diffie/Hellman, 1976, New directions in cryptography, in «IEEE Transactions on Information Theory», 22 (6), pagg. 644–654).

In questa situazione Bob (il destinatario) crea due chiavi. La prima (“privata”) è segreta e la tiene per sé, gli serve per decifrare i messaggi cifrati con seconda chiave, che è pubblica e viene utilizzata, appunto, per cifrare le informazioni. Bob rende nota la chiave pubblica a tutti coloro che vogliono inviargli un messaggio e non ha paura che questa chiave possa venire scoperta dal “nemico”.

Partendo dalla chiave pubblica non è possibile calcolare la chiave privata (è possibile invece il percorso inverso).

Si supera il problema di dover trasmettere la chiave segreta attraverso un canale sicuro e anche quello di dover gestire tante chiavi quanti sono i soggetti ai quali un mittente vuole inviare dei messaggi.

RSA

Il lavoro teorico di Diffie e Hellman offre, dal punto di vista pratico, solo un’applicazione parziale di queste idee innovative, nota come protocollo di scambio di chiavi Diffie-Hellman.

Partendo dagli studi di Diffie e Hellman, i ricercatori Ron Rivest, Adi Shamir e Leonard Adleman elaborano un sistema crittografico a chiave pubblica completamente funzionante, che presentano tra il 1977 e il 1978 e brevettano nel 1983 (assieme al Massachusetts Institute of Technology, del quale sono ricercatori).

Viene anche creata una società ad hoc per gestire i diritti commerciali di questa invenzione, che negli anni ’90 stipula accordi con aziende chiave del mondo dell’informatica e di Internet quali Netscape e Microsoft, ma anche con società di gestione della carte di credito come Visa e Mastercard.

NUMERI PRIMI

Per realizzare in pratica la crittografia asimettrica si parte dalla necessità di trovare funzioni invertibili o la cui invertibilità necessiti di tempi e costi non affrontabili. Scomporre un numero in fattori o testare la primalità di un numero sono operazioni molto onerose dal punto di vista computazionale, soprattutto nel caso di numeri estremamente grandi.

I numeri primi sono, non a caso, uno degli elementi su cui si basa l’algoritmo RSA.

Come noto un numero definito “primo” è quel numero che ha solo due divisori positivi: se stesso e il numero 1.

I numeri primi sono stati studiati fin dall’antichità. Negli Elementi di Euclide è presente una dimostrazione del teorema sull’esistenza di infiniti numeri primi.

Essi sono i ‘mattoni’ su cui vengono costruiti tutti gli altri numeri interi, in quanto «secondo il teorema fondamentale dell’aritmetica ogni intero maggiore di 1 può essere scritto esattamente in un solo modo come prodotto di numeri primi (se non si tiene conto dell’ordine in cui si scrivono i numeri primi)» (Ferguson/Schneier/Kohno, 2011, pag. 151).

Lavorare con in numeri primi non è così semplice. La maggior parte dei linguaggi di programmazione, infatti, non offre il supporto nativo per numeri interi di grandi dimensioni o per numeri in virgola mobile con con centinaia di cifre nella parte decimale: servono librerie software apposite.

FUNZIONAMENTO DI RSA

RSA si basa su una funzione unidirezionale (denominata trapdoor), il cui principio è brevemente riportato di seguito.

Partiamo da p e q che sono due numeri primi di grandi dimensioni quasi uguali tra loro, con p diverso da q. Questi due numeri sono scelti a caso.

Poniamo n come il prodotto tra p e q. Scegliamo infine due esponenti: e e d.

L’esponente e viene scelto tra i valori dispari piccoli, mentre l’esponente d viene calcolato affinché soddisfi la seguente equazione:

ed = 1 (mod t) dove t := mcm(p - 1, q - 1)

La funziona mod (modulo) rappresenta il resto di una divisione.

La funzione mcm rappresenta il calcolo del minimo comune multiplo tra due numeri.

Una volta noti n ed e risulta facile calcolare me (mod n), se si parte da m, ma non è vero il contrario, a meno di non conoscere la fattorizzazione di n.

La coppia (n, e) forma la chiave pubblica.

I valori (p, q, t, d) formano la chiave privata.

Per cifrare un messaggio m, il calcolo avviene così (c è il crittogramma):

c := me (mod n).

Per ritornare al testo in chiaro m partendo da c si calcola cd (mod n).

IMPATTO DELLA CRITTOGRAFIA A CHIAVE PUBBLICA

La crittografia, dopo essere stata usata per secoli, soprattutto in campo politico e militare, diviene un elemento fondamentale per il funzionamento della società.

Un ulteriore conferma dell’impatto polito-sociale che la crittografia comincia ad avere verso la fine del XX secolo si ha quando, nel 1991, Phil Zimmermann, uno dei frequentatori della mailing list Cypherpunk, rilascia il programma Pretty Good Privacy (PGP), che utilizza la crittografia simmetrica e asimmetrica per rendere sicuro lo scambio dei file e soprattutto delle e-mail.

La larga diffusione di PGP complicata l’esistenza di Zimmermann, in quanto nel febbraio 1993 viene indagato dal governo degli Stati Uniti con l’accusa di esportare di armi senza apposita licenza. Tutto ciò in base alle limitazioni imposte dalle leggi statunitensi sull’esportazione dei sistemi crittografici (che verranno in seguito modificate).

Si aggiunge inoltre una disputa sull’utilizzo di tecniche riconducibili al brevetto RSA, all’epoca riconosciuto negli Stati Uniti, ma non nel resto del mondo.

È in parte condivisibile in pensiero secondo cui «[la crittografia] era bollata come traffico d’armi […] ma quando se la sono ritrovata nei browser ed è stata usata per le attività bancarie è nata una lobby abbastanza potente da impedire che fosse proibita» (Assange, 2013, Internet è il nemico, Feltrinelli, pag. 98).

FUNZIONE DI HASH

Tornando al problema dell’autenticazione, va segnalato che i sistemi crittografici a chiave pubblica possono essere utilizzati anche al contrario rispetto all’esempio presentato, ovvero Alice può scrivere un messaggio e cifrarlo con la sua chiave privata. Chiunque, poi, può decifrare il crittogramma utilizzando la chiave pubblica di Alice.

È evidente che questa procedura non garantisce alcuna segretezza, ma non si tratta di un esercizio sterile, in quanto in questa maniera è possibile che il messaggio sia veramente di Bob (in quanto solo con la chiave pubblica di Bob si può rendere comprensibile quanto è stato offuscato con la sua chiave privata).

Si potrebbe quindi ipotizzare uno scenario simile: Alice (mittente) usa la chiave pubblica di Bob per cifrare un messaggio a lui indirizzato. Una volta ottenuto il crittogramma, prima di inviarlo lo cifra usando la propria chiave privata.

Bob, una volta ricevuto il messaggio, applica prima la chiave pubblica di Alice e successivamente la propria chiave privata. Se ottiene un testo in chiaro leggibile, è sicuro della provenienza del messaggio.

La crittografia asimmetrica può essere molto onerosa dal punto di vista computazionale, specie se le informazioni da trasmettere sono di grandi dimensioni.

Il concetto di “leggibilità” del testo in chiaro, poi, è troppo vago, può valere per un messaggio scritto in lingua italiana o in un’altra lingua corrente, ma non certo per un file informatico.

FIRMA DIGITALE

Pertanto, per assicurare l’autenticità dei messaggi è stato introdotto il concetto di firma (o ‘impronta’) digitale, ovvero una stringa di testo che viene allegata al messaggio e cifrata con la chiave privata del mittente.

Dobbiamo quindi accennare al concetto funzione di hash, ovvero una funzione “irreversibile” che «accetta come input una stringa di bit (o byte) di lunghezza arbitraria e produce un risultato di dimensione fissa» (Ferguson/Schneier/Kohno, 2011, pag. 71).

Dato un messaggio m, l’applicazione della funzione di hash viene solitamente rappresentata così: h(m).

Le dimensioni dell’output vanno generalmente dai 128 ai 1024 bit. L’output prodotto viene anche indicato come digest di messaggio.

Con “irreversibile” si intende che dato un valore x «non è possibile individuare un m tale che h(m) = x» (Ferguson/Schneier/Kohno, 2011, pag. 72).

Vengono utilizzati anche i termini equivalenti “funzione unidirezionale” o “resistente alle controimmagini”.

Una possibile modalità di utilizzo della firma digitale è la seguente.

Alice invia a Bob un testo in chiaro. In allegato al messaggio vi è anche la firma digitale del messaggio criptata con la chiave privata di Alice.

Bob usa la chiave pubblica di Alice per ottenere la firma digitale. Conoscendo l’algoritmo con cui tale firma è stata calcolata, Bob può prendere il messaggio in chiaro e calcolare a sua volta l’impronta digitale, che confronterà poi con quella inviatagli da Alice in allegato.

Ovviamente tale procedura garantisce l’autenticità, ma non la riservatezza.

ALGORITMI DI HASH

Le funzioni di hash, per essere utilizzabili a livello pratico, devo avere determinate caratteristiche (oltre alla già citata irreversibilità), ovvero:

• garantire che anche una minima modifica al messaggio originale generi una grande modifica nell’output prodotto (c.d. “effetti valanga”);
• il tempo per il calcolo dell’output sia accettabile;
• la possibilità quasi nulla che messaggi diversi generino lo stesso output (solitamente si parla di “resistenza collisioni”).

Alcuni noti algoritmi di hash sono:

• MD5, creato da Ronald Rivest nel 1991 e molto utilizzato, ma per il quale, nel corso degli anni, sono stati trovati numerosi esempi di collisioni;
• la funzione di Chaum, van Heijst e Pfitzmann, considerata fortemente resistente alla collisioni, ma troppo lenta per essere usata nella pratica (Trappe/Washington, 2009, Crittologia con elementi di teoria dei codici, Pearson, pag. 197);
• SHA, sviluppato dalla National Security Agency (NSA) a partire dal 1993. La versione 3 (SHA-3) è stata rilasciata il 5 agosto 2015.

Alcuni algoritmi che stanno emergendo negli ultimi anni sono:

• scrypt, ideato da Colin Percival, che è stato progettato per avere certo carico computazionale al fine di prevedire i cosiddetti attacchi a forza bruta (ovvero una ricerca esaustiva della chiave provando tutte le combinazioni possibili o utilizzando un dizionario di chiavi già calcolate);
• bcrypt di Niels Provos è basato sul cifrario Blowfish di Bruce Schneier ed è l’algoritmo di default per le password del sistema operativo OpenBSD. È progettato per essere resistente agli attacchi a forza bruta.

Il progetto Bitcoin utilizza, come funzione di hash, l’algoritmo SHA-2 (ma non solo), mentre la moneta matematica Litecoin utilizza una versione semplificata di scrypt.

CURVE ELLITTICHE

Come generare una chiave pubblica partendo da una privata utilizzando una funzione che non sia reversibile? Una delle possibili tecniche coinvolge la matematica delle curve elittiche.

Neal Koblitz e Victor S. Miller introducono l’utilizzo delle curve ellittiche nella crittografia intorno alla metà degli anni ’80.

Una curva ellittica E è un grafico di equazione

E: y2 = x3 + ax2 + bx + c ,

dove a, b e c possono appartenere a un certo insieme di numeri (razionali, reali, interi modulo p, ecc.).

Scegliendo due punti a caso su una curva ellittica, chiamati P1 e P2, si può individuare un terzo punto P3 ancora sulla stessa curva tracciando una retta L che passa per P1 e P2 e interseca E nel punto Q.

Il punto P3 sarà il punto simmetrico a Q rispetto all’asse delle ascisse.

Scegliendo un numero p tra i numeri primi, è possibile lavorare con le curve ellittiche modulo p, come nell’esempio che segue:

y2 mod p = (x3 + 7) mod p .

COMPUTER E NUMERI CAUSALI

Le applicazioni crittografiche fanno largo uso dei numeri casuali, spesso per creare password o chiavi.

Va ricordato che «non esiste alcun modo di produrre numeri realmente casuali utilizzando un elaboratore (o un qualsiasi altro dispositivo deterministico» (Sedgewick, 1993, Algoritmi in C, Addison-Wesley Masson, pag. 528), pertanto si preferisce parlare di numeri pseudocasuali.

Il metodo più noto per la generazione di numeri pseudocasuali è stato ideato attorno agli anni ’50 dal matematico Derrick H. Lehmer e si basa sul metodo della congruenza lineare, ampiamento studiato da Donald E. Knuth nel secondo volume di The Art of Computer Programming.

La casualità viene misurata per mezzo dell’entropia e per generare entropia in un elaboratore elettronico (per sua natura deterministico) spesso vengono utilizzati vari espedienti, come la rilevazione di tasti premuti o di movimenti del mouse, i cui risultati sono poi combinati con i generatori di numeri pseudocasuali.

Capitolo precedente: Bitcoin e monete matematiche https://medium.com/@AndreaFerraresso/bitcoin-e-monete-matematiche-10a2744ef5e6

Capitolo successivo: Bitcoin: uno sguardo sul sitema https://medium.com/@AndreaFerraresso/bitcoin-uno-sguardo-su-sistema-29a63fe33882