Firma di Schnorr

Claus Peter Schnorr, ideatore dell'algoritmo

In crittografia, la firma di Schnorr è una firma digitale prodotta tramite l'omonimo algoritmo di Schnorr. Si tratta di uno schema per firme digitali di semplice implementazione, uno dei primi la cui sicurezza è basata sulla presunta difficoltà computazionale del calcolo di logaritmi discreti. L'algoritmo è efficiente e le firme generate hanno dimensioni ridotte. Il suo brevetto è scaduto a febbraio 2008.

Algoritmo

Scelta dei parametri

• Tutti gli utenti dello schema di firma scelgono in accordo un determinato gruppo, $G$, il cui ordine è un numero primo, $q$, con generatore $g$ e in cui il problema del logaritmo discreto sia ritenuto complesso. In genere viene usato il gruppo di Schnorr.
• Tutti gli utenti scelgono in accordo una funzione crittografica di hash $H:\{0,1\}^{*}\rightarrow \mathbb {Z} _{q}$.

Notazione

Di seguito:

• l'esponenziazione di un elemento indica la ripetuta applicazione dell'operazione del gruppo su quell'elemento;
• la giustapposizione di due elementi indica una moltiplicazione nell'insieme di classi di equivalenza o l'applicazione dell'operazione del gruppo;
• la sottrazione di due elementi indica una sottrazione nell'insieme di classi di equivalenza;
• $M\in \{0,1\}^{*}$, dove $\{0,1\}^{*}$ l'insieme delle stringhe di bit finiti;
• $s,e,e_{v}\in \mathbb {Z} _{q}$, dove $\mathbb {Z} _{q}$ è l'insieme di classi di equivalenza modulo $q$
• $x,k\in \mathbb {Z} _{q}^{\times }$, dove $\mathbb {Z} _{q}^{\times }$ è il gruppo moltiplicativo di interi modulo $q$ (se $q$ è primo, $\mathbb {Z} _{q}^{\times }=\mathbb {Z} _{q}\setminus {\overline {0}}_{q}$)
• $y,r,r_{v}\in G$.

Generazione della chiave

• Scegliere una chiave privata $x$, appartenente all'insieme di cui sopra.
• La chiave pubblica è $y=g^{x}$.

Firma

Per firmare un messaggio $M$:

• Scegliere un numero casuale $k$ appartenente all'insieme di cui sopra.
• Sia $r=g^{k}$.
• Sia $e=H(r\parallel M)$, dove $\parallel$ denota la concatenazione e $r$ è rappresentato come una stringa di bit.
• Sia $s=k-xe$.

La firma del messaggio è costituita dalla coppia$(s,e)$.

Nota che $s,e\in \mathbb {Z} _{q}$; se $q<2^{160}$, allora la dimensione della firma non supera i 40 byte.

Verifica

• Sia $r_{v}=g^{s}y^{e}$
• Sia $e_{v}=H(r_{v}\parallel M)$

Se $e_{v}=e$ allora la firma è verificata.

Dimostrazione di correttezza

È relativamente semplice notare dimostrare $e_{v}=e$ se il messaggio firmato è uguale al messaggio verificato:

$r_{v}=g^{s}y^{e}=g^{k-xe}g^{xe}=g^{k}=r$, quindi $e_{v}=H(r_{v}\parallel M)=H(r\parallel M)=e$.

Informazioni pubbliche: $G$, $g$, $q$, $y$, $s$, $e$, $r$. Informazioni private: $k$, $x$.

Questo mostra come soltanto un messaggio firmato correttamente sarà verificato correttamente. Tuttavia, questa proprietà da sola non implica che lo schema sia sicuro.

Sicurezza

Lo schema di firma digitale applica la trasformazione di Fiat–Shamir al protocollo di identificazione di Schnorr. Pertanto (come per gli argomenti di Fiat e Shamir) è sicuro se $\mathrm {H}$ è modellato come un oracolo random.

La sua sicurezza può essere contestata in un modello generico di gruppo, ipotizzando che $\mathrm {H}$ sia "resistente alla prima e seconda preimmagine con prefisso casuale". In particolare, $\mathrm {H}$ non occorre che diventi la resistenza alla collisione.

Nel 2012, Seurin fornì una prova esatta dello schema della firma di Schnorr. In particolare, Seurin esegue la prova di sicurezza tramite il lemma forking, dimostrando che esso sia il miglior risultato possibile per qualsiasi sistema di firma digitale, basato su un solo omomorfismo di gruppi incluse le firme come quella di Schnorr o di Guillou–Quisquater. Vale a dire, con l'ipotesi ROMDL, qualsiasi riduzione algebrica deve perdere un fattore $f({\epsilon }_{F})q_{h}$ nel suo coefficiente tempo-successo, $f\leq 1$ è una funzione che rimane vicino a 1 fino a quando "${\epsilon }_{F}$ non diventa più piccolo di 1", ${\epsilon }_{F}$ è la probabilità di falsificare un errore al massimo $q_{h}$ domandando all'oracolo random.

Riutilizzo del nonce

Analogamente ad altri schemi di firma digitale, come DSA, ECDSA e ElGamal, il riutilizzo del nonce segreto $k$ in due distinte firme di Schnorr può permettere ad un osservatore di ricavare la chiave privata. Nel caso della firma di Schnorr, la chiave si può ottenere semplicemente sottraendo i due valori di $s$:

$s'-s=(k'-k)-x(e'-e)$.

Per isolare il valore di $x$ è infatti sufficiente che $e'\neq e$:

$x={\frac {s-s'+k'-k}{e'-e}}$.

L'exploit è applicabile anche per nonce non sufficientemente casuali.

Firme brevi di Schnorr

Il suddetto processo raggiunge un livello di sicurezza t-bit con 4t-bit firme. Ad esempio, un livello di sicurezza di 128 bit richiederebbe un totale di 512 bit (64 byte) in firme digitali. La sicurezza è limitata da attacchi logaritmici discreti sul gruppo, che possiedono una radice quadrata complessa.

Nel documento originale di Schnorr del 1991, è stato suggerito che poiché la resistenza alla collisione nell'hash non è richiesta, le funzioni di hash più brevi possono essere altrettanto sicure, i recenti sviluppi suggeriscono che si può raggiungere un livello di sicurezza t-bit con 3t-bit firme. Di fatto, con le firme brevi un livello di sicurezza di 128 bit richiederebbe soltanto 384 bit (48 byte) in firme digitali, tutto ciò potrebbe essere raggiunto troncando la dimensione di e fino alla metà della lunghezza del bit field di s.

Bibliografia

• (EN) Menezes, Alfred J. et al., Handbook of Applied Cryptography, CRC Press, 1996.
• (EN) Claus-Peter Schnorr, Efficient identification and signatures for smart cards, in Gilles Brassard (a cura di), Advances in Cryptology—Crypto '89, Lecture Notes in Computer Science, n. 435, Springer-Verlag, 1990, pp. 239-252.
• (EN) Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards (ps), in Journal of Cryptology, vol. 4, n. 3, 1991, pp. 161–174. URL consultato il 1º ottobre 2018 (archiviato il 9 aprile 2016).

Voci correlate

• DSA
• EdDSA
• Schema di firma di ElGamal

Collegamenti esterni

• (EN) RFC 8235, su tools.ietf.org, IETF.