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 nel 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]

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

Note[modifica | modifica wikitesto]

  1. ^ a b c (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) United States Patent 4995082, United States Patent and Trademark Office.
  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 (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]

  • (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 dall'url originale il 9 aprile 2016).

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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