Digital Signature Algorithm

Digital Signature Algorithm (DSA) è uno standard FIPS per la firma digitale proposto dal National Institute of Standards and Technology (NIST) nell'agosto del 1991 per essere impiegato nel Digital Signature Standard (DSS), le sue specifiche sono contenute nel documento FIPS 186^[1], viene definitivamente adottato nel 1993. In seguito è stato riveduto ulteriormente nel 1996 con FIPS 186-1^[2], nel 2000 con FIPS 186-2^[3], nel 2009 con FIPS 186-3^[4], e nel 2013 con FIPS 186-4^[5].

Negli Stati Uniti l'algoritmo DSA è coperto da brevetto^[6] attribuito a David W. Kravitz, un ex-ricercatore della NSA; il NIST ha reso questo brevetto disponibile liberamente per qualsiasi uso^[7].

Descrizione dell'algoritmo

Di seguito vengono descritti i passi fondamentali per l'impiego di DSA, che fa uso di un sistema crittografico a chiave pubblica simile ad ElGamal.

Generazione delle chiavi

Si scelga un numero primo di $d$ -bit $q$ ^[8].
Si scelga un numero primo p lungo L bit, tale che $p=qz+1$ per un qualche numero intero z, con 512≤L≤1024 e divisibile per 64 (nell'ultima revisione dello standard si specifica che L deve corrispondere a 1024).
Si scelga h tale che $1<h<p-1$ e $g=h^{z}{\bmod {p}}>1$
Si generi un numero casuale $x$ tale che $0<x<q$
Calcolare $y=g^{x}{\bmod {p}}$

La chiave pubblica è y, la chiave privata è x.
I parametri (p, q, g) sono pubblici e possono essere condivisi da diversi utenti.

Esistono algoritmi efficienti per il calcolo delle esponenziazioni modulari $h^{z}{\bmod {p}}$ e $g^{x}{\bmod {p}}$ .

Calcolo della firma

Si generi un numero casuale k tale che $0<k<q$
Calcolare $r=(g^{k}{\bmod {p}}){\bmod {q}}$
Calcolare $s=(k^{-1}(H(m)+x*r)){\bmod {q}}$ dove H(m)^[8] è una funzione di hash SHA-d applicata al messaggio m
Nel caso in cui $r=0$ o $s=0$ bisogna ricalcolare la firma
La firma è (r,s)

L'algoritmo esteso di Euclide può essere usato per calcolare l'inverso modulare $k^{-1}{\bmod {q}}$ .

Verifica della firma

Rifiutare firme se non sono soddisfatte le condizioni $0<r<q$ e $0<s<q$
Calcolare $w=s^{-1}{\bmod {q}}$
Calcolare $u_{1}=(H(m)*w){\bmod {q}}$
Calcolare $u_{2}=(r*w){\bmod {q}}$
Calcolare $v=((g^{u_{1}}*y^{u_{2}}){\bmod {p}}){\bmod {q}}$
La firma è verificata se $v=r$

Dimostrazione

L'algoritmo è corretto nel senso che il destinatario verificherà sempre le firme valide.

Da $g=h^{z}{\bmod {p}}\Rightarrow g^{q}\equiv h^{qz}\equiv h^{p-1}\equiv 1{\pmod {p}}$ per il piccolo teorema di Fermat. Dato che $g>1$ e q è primo segue che g è di ordine q.

Il firmatario calcola: $s=k^{-1}(H(m)+xr){\bmod {q}}$

quindi

{\begin{matrix}k&\equiv &H(m)s^{-1}+xrs^{-1}\\&\equiv &H(m)w+xrw{\pmod {q}}\\\end{matrix}}

visto che g è di ordine q

{\begin{matrix}g^{k}&\equiv &g^{H(m)w}g^{xrw}\\&\equiv &g^{H(m)w}y^{rw}\\&\equiv &g^{u_{1}}y^{u_{2}}{\pmod {p}}\\\end{matrix}}

La correttezza di DSA è provata da: $r=(g^{k}{\bmod {p}}){\bmod {q}}=(g^{u_{1}}y^{u_{2}}{\bmod {p}}){\bmod {q}}=v$ .

Sicurezza

Come molti sistemi di crittografia a chiave pubblica, la sicurezza di DSA si basa sull'intrattabilità di un problema matematico, in questo caso sull'inesistenza di un algoritmo efficiente per il calcolo del logaritmo discreto.

Particolare attenzione va posta al calcolo della quantità k: deve essere generata casualmente in modo che non sia possibile risalirvi, nel qual caso sarebbe possibile risalire facilmente ad x (la chiave privata) a partire dalla firma.

Note

^ (EN) FIPS 186, su itl.nist.gov. URL consultato il 19 agosto 2021 (archiviato dall'url originale il 7 aprile 2012).
^ (EN) (PDF)FIPS 186-1
^ (EN) (PDF)FIPS 186-2 Archiviato il 18 maggio 2009 in Internet Archive.
^ FIPS-186-3 (PDF), su csrc.nist.gov.
^ FIPS 186-4 (PDF), su nvlpubs.nist.gov.
^ (EN) US5,231,668, United States Patent and Trademark Office, Stati Uniti d'America.
^ Claus P. Schnorr sostiene che un suo brevetto antecedente ((EN) US4,995,082, United States Patent and Trademark Office, Stati Uniti d'America.) include DSA, questa affermazione è oggetto di disputa.^{[senza fonte]}
^ ^a ^b In origine $d=160$ e $H(m)\equiv {\mbox{SHA-1}}(m)$ , ma con la terza revisione dello standard (FIPS 186-3), chiamato comunemente DSA2 si potrà fare uso delle funzioni di hash SHA-224/256/384/512, con q di dimensione 224, 256, 384, e 512 bit, e L pari a 2048, 3072, 7680, e 15360 rispettivamente.

Voci correlate

Collegamenti esterni

(EN) Denis Howe, Digital Signature Standard, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
(EN) FIPS-186, le specifiche originali di DSA.
(EN) FIPS-186, change notice No.1, il primo aggiornamento alle specifiche.
(EN) FIPS-186-1, prima revisione dello standard.
(EN) FIPS-186-2, seconda revisione dello standard.
(EN) FIPS-186-3, terza revisione dello standard.
(EN) FIPS-186-4, quarta revisione dello standard.

Portale Crittografia

Portale Sicurezza informatica

[1] (EN) FIPS 186, su itl.nist.gov. URL consultato il 19 agosto 2021 (archiviato dall'url originale il 7 aprile 2012).

[2] (EN) (PDF)FIPS 186-1

[3] (EN) (PDF)FIPS 186-2 Archiviato il 18 maggio 2009 in Internet Archive.

[4] FIPS-186-3 (PDF), su csrc.nist.gov.

[5] FIPS 186-4 (PDF), su nvlpubs.nist.gov.

[6] (EN) US5,231,668, United States Patent and Trademark Office, Stati Uniti d'America.

[7] Claus P. Schnorr sostiene che un suo brevetto antecedente ((EN) US4,995,082, United States Patent and Trademark Office, Stati Uniti d'America.) include DSA, questa affermazione è oggetto di disputa.^{[senza fonte]}

[DSA2-8] In origine $d=160$ e $H(m)\equiv {\mbox{SHA-1}}(m)$ , ma con la terza revisione dello standard (FIPS 186-3), chiamato comunemente DSA2 si potrà fare uso delle funzioni di hash SHA-224/256/384/512, con q di dimensione 224, 256, 384, e 512 bit, e L pari a 2048, 3072, 7680, e 15360 rispettivamente.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]