In un precedente articolo abbiamo visto lo scambio di chiavi Diffie-Hellman, e poi in un altro articolo l’algoritmo di Schnorr per l’identificazione, che gli è collegato. In questo articolo vediamo come applicare l’algoritmo di Schnorr al problema di produrre una firma digitale. Rimandiamo all’articolo precedente per una spiegazione più approfondita e per la notazione.
Come abbiamo detto, l’algoritmo di Schnorr permette anche di produrre una firma digitale. Supponiamo ad esempio che Arduino rilasci pubblicamente un certo software o più genericamente un messaggio qualsiasi, e vuole dimostrare di essere stato veramente lui a farlo (ovvero colui che possiede la sua chiave privata $a$ corrispondente alla sua chiave pubblica $A$). Allora adotta una firma digitale, ovvero dei dati che possono essere utilizzati da chiunque per verificarne l’autenticità (utilizzando la chiave pubblica $A$) ma prodotti solo da qualcuno che conosce la chiave privata $a$. L’algoritmo funziona nella maniera seguente:
- Arduino vuole dimostrare di essere stato lui a rilasciare un messaggio $m$ (che in pratica è un numero naturale).
- Come prima Arduino produce una coppia temporanea di chiavi privata e pubblica $(t, T)$.
- Utilizzando una funzione di hash $H$ (di cui avevamo parlato in un articolo precedente) produce un hash $h = H(m, T)$. Ad esempio si può utilizzare una funzione di hash sicura qualsiasi dandogli come input $m$ concatenato con $T$.
- In questo caso $h$ svolge la funzione di “sfida” e quindi calcoliamo la “risposta” $r = a h + t$.
- La firma digitale è data dalla coppia $(T, r)$.
Chiunque voglia verificare la firma digitale produce prima di tutto la sfida/hash $h=H(m,T)$. Poi basta verificare (come prima) che $g^r \equiv A^h T \,\,(\mathrm{mod}\,p)$, dove i vari pezzi sono tutti noti.
Nell’articolo precedente abbiamo spiegato che è cruciale l’interattività dell’algoritmo. Infatti, abbiamo visto che se è possibile scegliere la sfida anticipatamente, allora è possibile generare $T$ ed $r$ senza conoscere $a$. Qui non c’è niente di interattivo: come abbiamo evitato questo problema? L’idea cruciale, che è dovuta a Fiat e Shamir e permette in molti casi di trasformare un protocollo di identificazione in un protocollo di firma digitale, è l’utilizzo della funzione di hash. Avevamo visto prima che conoscendo la sfida (in questo caso $h$) è banale produrre $T$ (scegliendo $r$ a caso). Ma poiché $T$ entra proprio nel calcolo di $h$ (in maniera altamente non predicibile, cioè tramite la funzione di hash), allora è come se non conoscessimo la sfida $h$ prima di dover scegliere $T$. Ciò perché appunto $T$ entra nel calcolo di $h$, e la funzione di hash produce un output essenzialmente caotico (se ben concepita).
Chiaramente questo protocollo verifica soltanto che Arduino sostiene di essere stato lui a rilasciare il messaggio, ma non che sia effettivamente lui: conoscendo $m$, è banale produrre la firma. Ad esempio Arduino può anche firmare un $m$ prodotto da qualcun altro. Tuttavia al contrario sappiamo (almeno con probabilità elevata) che a produrre la firma non può essere stato nessuno se non Arduino.