Firma di Schnorr

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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,[1] uno dei primi la cui sicurezza è basata sulla presunta difficoltà computazionale del calcolo di logaritmi discreti.[1] L'algoritmo è efficiente e le firme generate hanno dimensioni ridotte.[1] Il suo brevetto[2] è scaduto a febbraio 2008.

Algoritmo[modifica | modifica wikitesto]

Scelta dei parametri[modifica | modifica wikitesto]

  • Tutti gli utenti dello schema di firma scelgono in accordo un determinato gruppo, , il cui ordine è un numero primo, , con generatore 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 .

Notazione[modifica | modifica wikitesto]

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;
  • , dove l'insieme delle stringhe di bit finiti;
  • , dove è l'insieme di classi di equivalenza modulo
  • , dove è il gruppo moltiplicativo di interi modulo (se è primo, )
  • .

Generazione della chiave[modifica | modifica wikitesto]

  • Scegliere una chiave privata , appartenente all'insieme di cui sopra.
  • La chiave pubblica è .

Firma[modifica | modifica wikitesto]

Per firmare un messaggio :

  • Scegliere un numero casuale appartenente all'insieme di cui sopra.
  • Sia .
  • Sia , dove denota la concatenazione e è rappresentato come una stringa di bit.
  • Sia .

La firma del messaggio è costituita dalla coppia.

Nota che ; se , allora la dimensione della firma non supera i 40 byte.

Verifica[modifica | modifica wikitesto]

  • Sia
  • Sia

Se allora la firma è verificata.

Dimostrazione di correttezza[modifica | modifica wikitesto]

È relativamente semplice notare dimostrare se il messaggio firmato è uguale al messaggio verificato:

, quindi .

Informazioni pubbliche: , , , , , , . Informazioni private: , .

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

Sicurezza[modifica | modifica wikitesto]

Lo schema di firma digitale applica la trasformazione di Fiat–Shamir[3] al protocollo di identificazione di Schnorr.[4] Pertanto (come per gli argomenti di Fiat e Shamir) è sicuro se è modellato come un oracolo random.

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

Nel 2012, Seurin[1] 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 nel suo coefficiente tempo-successo, è una funzione che rimane vicino a 1 fino a quando " non diventa più piccolo di 1", è la probabilità di falsificare un errore al massimo domandando all'oracolo random.

Riutilizzo del nonce[modifica | modifica wikitesto]

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

.

Per isolare il valore di è infatti sufficiente che :

.

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

Firme brevi di Schnorr[modifica | modifica wikitesto]

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.[5] 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.

Note[modifica | modifica wikitesto]

  1. ^ a b c d (EN) Yannick Seurin, On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model (PDF), su Cryptology ePrint Archive, International Association for Cryptologic Research, 12 gennaio 2012. URL consultato l'11 agosto 2014.
  2. ^ (EN) US4995082, United States Patent and Trademark Office, Stati Uniti d'America.
  3. ^ (EN) Fiat e Shamir, How To Prove Yourself: Practical Solutions to Identification and Signature Problems (PDF) [collegamento interrotto], in Proceedings of CRYPTO '86, 1986.
  4. ^ (EN) Schnorr, Efficient Identification and Signatures for Smart Cards (PDF) [collegamento interrotto], in Proceedings of CRYPTO '89, 1989.
  5. ^ a b Hash function requirements for Schnorr signatures, su www.neven.org. URL consultato il 5 settembre 2020.
  6. ^ a b (EN) Mehdi Tibouchi, Attacks on Schnorr signatures with biased nonces (PDF), in 21st Workshop on Elliptic Curve Cryptography, Radboud University - Institute for Computing and Information Sciences, 13 novembre 2017. URL consultato il 3 ottobre 2018 (archiviato il 3 ottobre 2018).

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Crittografia Portale Crittografia: accedi alle voci di Wikipedia che trattano di crittografia