Gli algoritmi di firma digitale: presente e futuro

La firma digitale è, sotto molti aspetti, l’analogo nel mondo digitale della firma autografa che tutti usiamo quotidianamente. La principale differenza tra queste due modalità risiede però nel fatto che, mentre per la seconda l’autenticità della firma è legata alla grafia di chi la appone, nel primo caso è garantita dal possesso di uno strumento crittografico (le chiavi crittografiche) da parte del firmatario. Analogamente alla firma autografa, anche la firma digitale ha come principale obiettivo il non ripudio (il firmatario non può negare di aver apposto la firma su un documento), oltre al garantire l’autenticità e l’integrità del documento firmato.

La firma digitale si sviluppa nell’ambito della crittografia asimmetrica, infatti in uno schema di firma è necessaria una coppia di chiavi crittografiche (sk,pk):

• La chiave privata (o di firma) sk, che solo il firmatario conosce, viene utilizzata per realizzare la firma;
• La chiave pubblica (o di verifica) pk, che è nota a tutti, viene utilizzata per verificare la firma stessa.

Al fine di realizzare la firma è quindi necessario utilizzare un algoritmo che, dati in input il documento D e la chiave privata sk, restituisca come output la firma S. Di seguito in fig. 1 riportiamo una rappresentazione schematica di tale processo.

Qualsiasi utente in possesso della chiave pubblica pk del firmatario può verificare tale firma utilizzando un algoritmo che, presi in input il documento che è stato firmato, la firma e la chiave pubblica pk, restituisca:

• VERO se la firma S è stata effettivamente realizzata dall’utente corrispondente alla chiave pubblica pk considerata e se il documento D non è stato modificato;
• FALSO se il documento D è stato modificato dopo l’apposizione della firma o se la chiave privata utilizzata per firmare non corrisponde alla chiave pubblica usata nella verifica, ovvero se la firma è stata realizzata da qualcun altro rispetto a colui che viene ritenuto il firmatario.

In fig. 2 è rappresentato il processo di verifica della firma digitale.

Possiamo ora considerare un primo esempio di firma digitale basata sullo schema di cifratura asimmetrica RSA. In questo algoritmo di firma, come nel crittosistema RSA, si parte da un parametro N=pq con p e q numeri primi. Il firmatario, qui nominato Samantha, genera una coppia di chiavi RSA (d,e) con d\cdot e = 1 \mod (p-1)(q-1), dove d è la chiave privata ed e la chiave pubblica.

Per firmare un documento D, visto come un intero positivo minore di N, Samantha calcola la firma S come S = D^d \mod N.
Per verificare la firma, qualsiasi utente in possesso della chiave pubblica e di Samantha può controllare se S^e = D \mod N.
In caso affermativo la firma viene giudicata valida, altrimenti viene rifiutata.

Algoritmi più diffusi e paradigmi principali

Lo schema di firma digitale presentato nella sezione precedente, nonostante sia un buon esempio per illustrare il funzionamento di tali algoritmi, non è utilizzabile nella pratica in quanto insicuro. La struttura di fondo dello schema RSA, però, viene utilizzata nello schema di firma RSA PKCS #1 v1.5 (ormai sconsigliato) o nella sua più recente versione RSA-PSS, che rientrano tra gli algoritmi maggiormente diffusi al giorno d’oggi.

Altri schemi largamente impiegati sono sicuramente ECDSA e EdDSA: entrambi questi algoritmi basano la propria sicurezza sul problema del logaritmo discreto sulle curve ellittiche. A seconda delle esigenze legate al contesto di utilizzo di tali algoritmi è poi possibile selezionare una diversa curva ellittica fra quelle annoverate negli standard del NIST o diventate standard industriali de facto: ne è un esempio l’istanza di ECDSA che utilizza la curva Secp256k1, adottata da Bitcoin.

Possiamo identificare, alla base degli schemi di firma digitale usati oggigiorno, due principali paradigmi:

• Hash-then-sign , in cui si calcola l’hash (o digest) del messaggio che vogliamo firmare e si calcola la firma di tale digest;
• Fiat-Shamir , in cui la firma viene costruita applicando la trasformata di Fiat-Shamir che, a partire da un protocollo di identificazione che richiede interazione tra le parti, deriva uno schema di firma non interattivo.

Il paradigma Hash-then-sign è adottato da schemi quali i già citati RSA PCKS #1 v1.5 e RSA-PSS. Con l’utilizzo di tale paradigma si vogliono risolvere alcuni problemi che affliggono gli schemi di firma che non utilizzano funzioni di hash.

Per prima cosa, considerando come oggetto da firmare il digest del documento e non il documento stesso si ha una garanzia sulle dimensioni limitate dell’oggetto firmato: questo consente di avere un algoritmo molto più efficiente e assicura che non sia necessario “spezzare” il documento in più pezzi. Non dovendo ricorrere alla frammentazione del documento da firmare si riduce così la possibilità di “deletion attacks”, ossia attacchi in cui un attore malevolo elimina un pezzo del messaggio con la relativa firma e il ricevente non ha modo di accorgersi che ciò che riceve è una versione “tagliata” del documento originariamente firmato dal mittente.

Un’altra motivazione per il calcolo del digest del documento prima dell’applicazione della firma digitale è che l’utilizzo delle funzioni di hash permette di ridurre il rischio che un attaccante sia in grado di costruire una firma valida anche senza essere in possesso della chiave privata: questo tipo di attacco sarebbe invece estremamente semplice se si utilizzasse la versione “naive” della firma basata su RSA precedentemente introdotta.

Queste considerazioni sulla sicurezza motivano l’utilizzo di una funzione di hash anche nel contesto degli schemi di firma costruiti facendo uso della trasformata Fiat-Shamir. Tra questi è doveroso ricordare EdDSA che, sviluppato nel 2011 da un gruppo di ricercatori guidato da Daniel J. Bernstein, rappresenta ad oggi lo stato dell’arte nell’ambito delle firme digitali. EdDSA è costruito a partire da uno protocollo (identificazione di Schnorr) che viene reso non interattivo grazie alla trasformata Fiat-Shamir. EdDSA viene definito utilizzando le cosiddette curve ellittiche di Edwards, da cui l’acronimo EdDSA che sta per Edwards-curve Digital Signature Algorithm. Possiamo ricordare in particolare due versioni di EdDSA:

• Ed25519, che fa uso della curva ellittica Curve25519 e della funzione di hash SHA512;
• Ed448, che utilizza la curva Curve448 e la funzione di hash SHAKE256.

Anche ECDSA, pur non facendo uso della trasformata di Fiat-Shamir, è costruito a partire da un protocollo che richiederebbe interazione tra le parti e che viene reso non interattivo così da renderne possibile l’utilizzo come schema di firma digitale.

Dal punto di vista tecnico EdDSA è considerato migliore di ECDSA perché caratterizzato da migliori performance, maggiore resistenza ad attacchi di tipo side-channel e maggiore livello di sicurezza. In EdDSA, infatti, la firma è costruita in modo deterministico e non richiede un nonce random, evitando così i rischi derivanti dalla ripetizione del nonce a seguito di errori implementativi con conseguenze devastanti sulla sicurezza dello schema di firma.

Applicazioni della firma digitale

Gli schemi di firma digitale sono utilizzati ogniqualvolta sia necessario garantire le proprietà di autenticazione, integrità e non ripudio. Numerosi sono gli scopi per cui si ricorre agli schemi sopra introdotti, ad esempio per autorizzare pagamenti bancari, per firmare elettronicamente documenti e per autorizzare transazioni di criptovalute all’interno della blockchain.

Tuttavia, il principale utilizzo degli schemi di firma digitale avviene all’interno della cosiddetta Public Key Infastructure (PKI). La PKI può essere definita come l’insieme delle strutture volte, tramite l’utilizzo della crittografia, a garantire l’autenticazione tra le parti durante uno scambio chiave; un esempio è la web PKI che permette di stabilire uno scambio di chiave autenticato tra il browser di un utente e un sito internet.

Nella web PKI l’autenticazione del sito web avviene tramite l’utilizzo di un certificato (spesso definito secondo lo standard X.509) su cui è riportata la chiave pubblica del sito stesso insieme ad altre informazioni. L’autenticità di tale certificato è garantita da una Certification Authority (CA), ossia un ente terzo fidato che ne verifica le informazioni e appone la propria firma digitale come validazione. Il browser dell’utente, utilizzando la chiave pubblica della CA (presente nel codice del browser stesso), verifica il certificato autenticando così il sito web con cui è in comunicazione.

La competizione post-quantum del NIST

Tutti gli schemi di firma citati fino a questo punto basano la propria sicurezza sulla difficoltà della fattorizzazione degli interi (RSA) o del logaritmo discreto (ECDSA, EdDSA). Questi problemi, pur garantendo alti livelli di sicurezza nei confronti di un attaccante classico, non sono sufficienti per resistere agli attacchi di un computer quantistico. Visti i grandi passi in avanti compiuti nel corso degli ultimi anni nello sviluppo di computer quantistici sempre più potenti da parte di enti nazionali ed dall’industria, si rende quindi necessaria l’elaborazione di nuovi schemi di firma digitale che continuino a garantire le proprietà di non ripudio, autenticità e integrità anche di fronte ad attacchi di tipo quantistico.

A tal fine nel 2017 il National Institute of Standards and Technology (NIST) americano ha avviato un processo di standardizzazione che ha tra i suoi obiettivi anche l’individuazione e la standardizzazione di schemi di firma digitale quantum-resistant.

Nel mese di luglio 2022 si è concluso il terzo round di tale competizione, al termine del quale sono stati identificati tre schemi di firma che verranno ora standardizzati: Dilithium, Falcon e SPHINCS+. Questi schemi basano la propria sicurezza su problemi matematici ritenuti “difficili” anche per un computer quantistico: in particolare Dilithium e Falcon si basano su problemi provenienti dalla teoria dei reticoli, mentre SPHINCS+ sulle primitive simmetriche.

Si noti che, considerata la limitata varietà delle assunzioni matematiche alla base degli schemi standardizzati al termine del terzo round, nel settembre 2022 il NIST ha pubblicato un nuovo bando per algoritmi di firma Post-Quantum non basati sui reticoli che andranno ad affiancare Dilithium (schema di riferimento), Falcon e SPHINCS+.

A differenza della negoziazione della chiave, gli schemi di firma selezionati dal NIST condividono la stessa struttura ad alto livello degli schemi attualmente usati e ciò dovrebbe rendere più agevole la transizione verso soluzioni resistenti al computer quantistico. Tuttavia, è necessario rimarcare che gli schemi post-quantum in corso di standardizzazione sono caratterizzati da un’elevata dimensione delle chiavi e della firma che dovrà essere tenuta in considerazione in fase implementativa.

Nel corso dei prossimi articoli di questa serie si approfondirà ciascuna primitiva e si descriverà il funzionamento di tali schemi.

Questo articolo appartiene ad una serie di contributi, a cura del Gruppo di Ricerca in Crittografia di Telsy, dedicata al calcolo quantistico e alle sue implicazioni sulla Crittografia. Per la consultazione di altri articoli si rimanda all’indice della rubrica.

Per altri articoli relativi ai temi Quantum e Crittografia si rimanda alle relative categorie nel blog.

Gli autori

Edoardo Signorini, laureato in Matematica con curriculum in crittografia presso l’Università di Trento, ha svolto nel 2020 la Tesi Magistrale nell’ambito della Post-Quantum Cryptography (PQC) presso Telsy. Attualmente ricopre il ruolo di crittografo all’interno del gruppo di ricerca di Telsy e svolge un Dottorato di ricerca industriale in Matematica Pura e Applicata presso il Politecnico di Torino. La sua attività si concentra sulla ricerca in ambito PQC e sull’analisi e lo sviluppo di protocolli crittografici.

Marco Rinaudo, laureato triennale in Matematica presso l’Università degli Studi di Torino e studente del corso di laurea magistrale in Matematica con specializzazione in Crittografia presso l’Università di Trento, attualmente stagista nel gruppo di ricerca di Telsy.