Digital Signature Algorithm

L'algoritmo DSA (Digital Signature Algorithm) è stato pubblicato dal NIST nel documento FIPS PUB 186 [1]. Si basa sulla crittografia 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. 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
  • x: numero generato in modo casuale o pseudocasuale, tale che 0 < x < q
  • y: valore calcolato come $y = g^x mod\:p$
  • k: numero segreto per ogni messaggio, generato in modo casuale o pseudocasuale

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

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 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) è l'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à $u1 = (H(M)w) mod\:q$, $u2 = rw\:mod\:q$ e $v = (((g^{u1})(y^{u2}) 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^{u1})(y^{u2})\: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^{u1})(g^{x u2}) 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 è $u1 + x\:u2 = k\:mod\:q$, elevando ambo i membri con base g si ottiene $g^{u1} g^{x\:u2} = g^{k} mod\:q$, ovvero $g^{u1} y^{u2} = g^{k}\:mod\:q$ ovvero $v = r$.

Bibliography
1. NIST, "Digital Signature Standard (DSS)", FIPS PUB 186-3, giugno 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