Algoritmo di firma DSA

Calcolo parametri condivisi

L'algoritmo richiede i parametri condivisi [p, q, g]
q è un numero primo di 160 bit
Viene calcolato con la funzione RandomPrime che calcola un numero primo con un numero fissato di bit

RandomPrime[n_Integer?NonNegative] := 
      Module[{x}, 
        x = Random[Integer, {2^(n - 1), 2^n - 1}]; 
If[
          EvenQ[x], x = x + 1]; 
While[! PrimeQ[x], 
          x = x + 2; 
If[x ≥ 2^n, 
            x = Random[
                Integer, {2^(n - 1), 2^n - 1}]; 
If[
              EvenQ[x], x = x + 1]]]; x]

q  =  RandomPrime[160]

Verifica della dimensione di q e del fatto che sia un numero primo

NumBit[num_Integer?NonNegative]  :=  
      Length[IntegerDigits[num, 2]]

NumBit[q]

PrimeQ[q]

p è un numero primo tale che (2^512) < p < (2^1024)
Il numero di bit che costituiscono p deve essere inoltre divisibile per 64 e p deve essere scelto in modo che q sia un divisore primo di p-1

CalculateP[n_Integer?NonNegative, 
        q_Integer?NonNegative]  := 
Module[{x, 
          z}, 
x = 0; 
        z  =  Floor[
            2^(n - 1)/
              q]; 
While[! ((x > 
                    2^(n - 1)) && (x < 2^n - 1) && 
                PrimeQ[x]), 
x  =  
            z*q + 1; 
z++]; 
If[! PrimeQ[x], x = 0]; 
x]

p viene scelto di 1024 bit

p  =  CalculateP[1024, q]

Verifica che p sia un primo di 1024 bit e che q sia divisore primo di p-1

NumBit[p]

PrimeQ[p]

Mod[p - 1, q]

Infine deve essere scelto il parametro g in modo che g = h\(TraditionalForm\`\^\(\(p - 1\)\/q\)\)mod p > 1 con 1 < h < p-1 scelto a caso

CalcG[p_Integer?NonNegative, 
        q_Integer?NonNegative]  := 
Module[{h, z, 
          g}, 
z = (p - 1)/q; 
g = 
          0; 
While[! (g > 
                1), 
h = 
            Random[Integer, {2, p - 2}]; 
g = 
            PowerMod[h, z, p]]; 
g]

g  =  CalcG[p, q]

Generazione coppia di chiavi

Si passa al calcolo di una coppia di chiavi
La chiave privata a è scelta casualmente in modo che risulti 0 < a < q
La chiave pubblica viene invece ricavata mediante l'operazione y  = (g^a) mod p

GenKey[g_Integer?NonNegative, q_Integer?NonNegative,  
        p_Integer?NonNegative] := 
Module[{a, 
          y}, 
a  =  
          Random[Integer, {1, q - 1}]; 
y  =  
          PowerMod[g, a, p]; 
{a, y}]

{a, y} = GenKey[g, q, p]

Firma

La firma viene calcolata basandosi sull'hash SHA-1 del messaggio. Questo hash ha una dimensione di 160 bit e verrà scelto casualmente nell'esempio realizzato. La firma viene poi ottenuta ricavando le 2 etichette r ed s che sono entrambe di 160 bit

sha = Random[Integer, {1, 2^160 - 1}]

Per il calcolo delle etichette il firmatario deve generare casualmente la grandezza k in modo che risulti 0 < k < q

k = Random[Integer, {1, q - 1}]

L'etichetta r viene calcolata come  r  = ((g^k) mod p) mod q

r = Mod[PowerMod[g, k, p], q]

Mentre l'etichetta s è calcolata come s  =  ((k^(-1))(
              H(m) + a*r) mod q

s = Mod[PowerMod[k, -1, q]*(sha + a*r), q]

La firma è data dalla coppia (r,s) che deve essere inviata assieme al messaggio m

Verifica

La verifica viene effettuata utilizzando (m,r,s) e la chiave pubblica y del firmatario
La verifica parte dall'equazione congruenziale s*k  =  H(m) + a*r (mod q)
si calcola quindi w = (s^(-1)) mod q

w = PowerMod[s, -1, q]

e si calcolano le grandezze (Subscript[u, 1])  =  H (m)*w mod qe (Subscript[u, 2])  =  r*w mod q

u1 = Mod[sha*w, q]

u2 = Mod[r*w, q]

è quindi possibile effettuare la verifica calcolando v  =  ((g^u1) (y^u2) mod p) mod qe controllando se v = r perchè r  =  (g^k)  =  (g^u1) 
            (y^u2) (mod p mod q)

v = Mod[Mod[PowerMod[g, u1, p]*PowerMod[y, u2, p], p], q]

v == r

La robustezza dell'algoritmo si basa sul fatto che calcolare il logaritmo discreto è un problema difficile e quindi un intruso non può risalire alla chiave segreta a dalla chiave pubblica y o al valore k dall'etichetta r