Algoritmo DSA

L'algoritmo DSA (Digital Signature Algorithm) è un algoritmo di firma digitale pubblicato dal NIST nel documento FIPS PUB 186 [1], basato sul problema del logaritmo discreto, analogamente all'algoritmo ElGamal.

Una firma digitale DSA viene calcolata attraverso una serie di parametri, tra cui: una chiave privata x e un numero segreto univoco per ogni messaggio. La firma viene verificata attraverso gli stessi parametri, una chiave pubblica associata alla chiave privata utilizzata per creare la firma.

Descrizione

Si definiscono le seguenti quantità:

  • p: numero primo di dimensioni pari a L bit
  • q: numero primo che divide (p-1) di dimensioni pari a N
  • g: generatore di Zp tale che 1 < g < p

Nello standard si indicano i seguenti valori delle dimensioni dei numeri primi; $1024 \leq L \leq 3072$ e $160 \leq N \leq 256$. Le entità federali governative dovrebbero utilizzare le seguenti coppie di valori: (1024, 160); (2048, 224); (2048, 256). Le autorità di certificazione dovrebbero impiegare chiavi con valori di L e N almeno uguali o superiori all'entità che viene certificata.

Generazione delle chiavi

Dati i parametri p, q, g, sono generati i numeri x e y, nel modo seguente:

  • x: numero generato in modo casuale o pseudocasuale, tale che 0 < x < q
  • y: valore calcolato come $y = g^x mod\:p$

La chiave privata è costituita da x, mentre quella pubblica da p, q, g, y

Generazione della firma

Sia N la lunghezza in bit di q. La firma di un messaggio M è costituita dalla coppia di numeri r ed s che viene calcolata nel modo seguente:

  1. Viene generato un numero segreto casuale o pseudocasuale k tale che: $1 \leq k \leq q$
  2. Viene calcolata la quantità $(g^k mod\:p) mod\:q$
  3. Viene calcolato $k^{-1} mod\:q$, dove $k^{-1}$ è l'inverso della moltiplicazione di k modulo q, ovvero $(k^{-1}k) mod\:q = 1$
  4. Si calcola $s = (k^{-1} (H(M) + xr)) mod\:q$, dove H(M) è il codice hash del messaggio, lungo N bit
  5. Si calcola $r = (g^k mod\:p) mod\:q$
  6. La firma è costituita dalla coppia di valori (r, s)

Verifica della firma

Il destinatario riceve il messaggio M e la firma (r, s). La verifica procede nel modo seguente:

  1. Si calcola $w = s^{-1} mod\:q$ e si calcola l'hash del messaggio H(M)
  2. Si calcolano le quantità $u_1 = (H(M)w) mod\:q$, $u_2 = rw\:mod\:q$ e $v = (((g^{u_1})(y^{u_2}) mod\:p) mod\:q$
  3. Se il valore v corrisponde al valore r allora la firma è autentica, ovvero è stata effettuata dalla chiave pubblica corrispondente.

Dimostrazione

Il valore di v viene calcolato come

(1)
\begin{align} v = (((g^{u_1})(y^{u_2}) mod\:p) mod\:q \end{align}

poiché y fa parte della chiave pubblica ed è $y = g^x\:mod\:p$ allora sostituendo si ha:

(2)
\begin{align} v = (((g^{u_1})(g^{xu_2}) mod\:p) mod\:q = ((g^{H(M)w} g^{xwr}) mod\:p) mod\:q = ((g^{[H(M) + xr]w}) mod\:p ) mod\:q \end{align}

Essendo $s = (k^{-1} (H(M) + xr)) mod\:q$ allora $w = s^{-1} mod\:q = (k(H(M) + xr)^{-1}) mod\:q$. Quindi la quantità $w(H(M) + xr) mod\:q$ è pari a $k\:mod\:q$. Sostituendo si ha:

(3)
\begin{align} ((g^{[H(M) + xr]w}) mod\:p ) mod\:q = (g^k mod\:p) mod\:q \end{align}

che è proprio il valore di r calcolato dal mittente. Quindi v = r

In altre parole, essendo $s = (k^{-1} (H(M) + xr)) mod\:q$, allora $ks = H(M) + xr\:mod\:q$, quindi $H(M) = ks - xr\:mod\:q$. Moltiplicando ambo i membri per w si ha $wH(M) + xrw = ks\:mod\:q$.

Sostituendo, l'ultima equazione è $u_1 + xu_2 = k\:mod\:q$, elevando ambo i membri con base g si ottiene $g^{u_1} g^{xu_2} = g^k mod\:q$, ovvero $g^{u_1} y^{u_2} = g^k mod\:q$ ovvero v = r

Bibliography
1. NIST, FIPS PUB 186-3, "Digital Signature Standard (DSS)", 2009, Sito web: http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License