Capitolo 3: Schema di firme DSS

3.1 Digital Signature Standard (DSS)

Nell'agosto del 1991, il National Institute of Standard and Technology (NIST) propose il Digital Signature Algorithm (DSA), per essere usato nel nuovo Digital Signature Standard (DSS).
Questo standard fu rivisto nel 1993 [3], in risposta alle numerose critiche mossegli contro. Questo standard specifica un algoritmo di firme digitali a chiave pubblica (DSA) usato per le applicazioni di firme digitali.
Prima di fare confusione, diamo uno sguardo alla nomenclatura: il DSA è l'algoritmo; il DSS è lo standard. Lo standard esegue l'algoritmo e l'algoritmo è una parte dello standard.
In questa sezione descriveremo il DSS per la generazione e la verifica di firme digitali, e l'algoritmo per la generazione di chiavi pubbliche e private. In entrambi i processi di generazione e firma il messaggio M è compresso dalla funzione hash (SHA) che fornisce come output un messaggio di 160 bit.

3.2 Parametri del DSS

La chiave è K ={ p , q , a , b , s } dove: p è un numero primo la cui lunghezza è compresa tra 512 e 1024 bit, multipla di 64; q è un numero primo di 160 bit che divide p-1; a Î Z_p^* è un elemento di ordine q ( l'ordine di a è il più piccolo intero positivo q tale che a^q=1 mod p); s < q è un numero casuale segreto di 160 bit; b=a^s mod p è un numero di 160 bit. La chiave pubblica è ( p, q, a , b ) mentre quella privata è ( p, q, a , s ). Inoltre P=Z_p^*, A=Z_q x Z_q.

3.3 Generazione della firma

La firma del messaggio M è una coppia di numeri (g,d) calcolati secondo i seguenti passi.

Algortimo di Firma DSS

La firma F di un messaggio M è:

1. Calcola un numero casuale r tale che 1£r£q-1

2. g=(a^r mod p) mod q

3. d=(SHA(M)+sg)r^-1 mod q

sig_K(M,r)=(g,d)

Nel passo 3, l'inverso di r esisterà certamente poichè 1£ r £ q-1 , e gcd(r,q)=1 in quanto q è primo. Il valore di SHA(M) è di 160 bit.

3.4 Procedura di verifica

Per verificare la firma F del messaggio M, Bob deve conoscere la chiave pubblica ( p , q , a , b ) di Alice.

Algortimo di Verifica DSS

La verifica della firma F di un messaggio M è:

1. e'=SHA(M)d^-1 mod q

2. e''=gd^-1 mod q

3.4.1 Correttezza procedura di verifica

Verifichiamo la correttezza della procedura di verifica:

3.5 Critiche al DSS

Quando il DSS è stato proposto dal NIST come standard, ci furono diverse critiche. Sfortunatamente, queste critiche furono più politiche che accademiche. RSA Data Security Inc., autrice dell'algoritmo RSA, condusse la maggior parte delle critiche contro il DSS. Essa voleva RSA, e non un altro algoritmo, usato come standard, questo perchè le licenze d'uso dell'algoritmo RSA avrebbero fornito grossi proventi alla RSADSI, mentre uno standard di firme digitali libero da licenze avrebbe comportato una diminuzione del suo fatturato. Lo standard proposto fu sviluppato dalla National Security Agency (NSA) senza l'ausilio dell'industria statunitense, e molti criticarono questo approccio a "porte chiuse" senza tener conto dei meriti del sistema proposto. Diverse critiche tecniche, invece, furono fatte sul sistema :

DSS non può essere usato per cifrare o per distribuire chiavi.
Questo è vero, ma ciò non è il punto dello standard, poichè esso è stato progettato esclusivamente per le firme digitali.

DSS è stato sviluppato dall'NSA e potrebbe esserci una trap-door nell'algoritmo.

DSS è più lento di RSA.

Nel DSS i tempi di firma sono più veloci dei tempi di verifica. Per contro, se RSA è usato come schema di firme e l'esponente pubblico è molto piccolo (per esempio 3), allora la verifica può essere eseguita molto più velocemente della firma. In definitiva la maggiore critica che viene fatta nei confronti del DSS riguarda la verifica. Infatti, mentre l'operazione di firma viene realizzata una sola volta, la verifica, sulla stessa firma, può essere effettuata più volte nel tempo. Questo suggerisce che uno schema di firme con algoritmo di verifica più veloce sia desiderabile. La risposta del NIST fu che i tempi di verifica del DSS erano tali da poter essere sostenuti.
Le implementazioni reali del DSS possono essere velocizzate attraverso precomputazioni. Notiamo che il parametro g è indipendente dal messaggio; si può quindi creare un insieme di possibili valori del parametro r e per ognuno di loro precomputare il parametro g e il valore r^-1,e porli in un database. Quando un messaggio deve essere firmato è sufficiente prelevare un valore di r e il suo corrispondente g , e poi calcolare il parametro d . Questa precomputazione velocizza considerevolmente il DSS. Riportiamo, qui di seguito, un confronto computazionale tra DSS e RSA per una implementazione su smart-card [1]

	DSS	RSA	DSS con p,q, a comuni
Precomputazioni	14 sec.	--	4 sec.
Firma	0.3 sec.	15 sec.	0.3 sec.
Verifica	16 sec. 1-5 sec. Off Cards	1.5 sec.	10 sec. 1-3 sec. Off Cards

Computazioni Off Card eseguite su 80386 a 33 MHz.

La misura del modulo p è troppo piccola.
La taglia del modulo p fu fissata a 512 bit nel 1991 e molte persone ritenevano che tale modulo dovesse essere di taglia non fissata, allo scopo di garantire una maggiore sicurezza. In risposta a tale critica, il NIST nel 1995 suggerì che una variazione della lunghezza del modulo p era permessa, scegliendo tale misura in modo tale da essere divisibile per 64, e compresa tra 512 e 1024 bit.
La scelta dei parametri p e q deve essere sicura.
Un'ulteriore critica riguardava, infatti, la scelta dei valori p e q. Tale critica nacque dal fatto che esistono dei valori p e q che permettono la falsificazione.
Il NIST ha risolto questo problema fornendo un algoritmo per la determinazione dei parametri p e q.

3.6 Generatori di Z_p^*e loro proprietà

In questa sezione definiamo il concetto di generatore del gruppo moltiplicativo Z_p^* ed alcune sue proprietà che sono utili allo schema di firme DSS. Dalla teoria dei numeri la cardinalità del gruppo moltiplicativo Z_p^*è f(p), dove f(p) è detta funzione di Eulero, in particolare la cardinalità di Z_p^* è f(p)=p-1 se p è un numero primo.
Preso un elemento a qualsiasi in Z_p^*, l'ordine di a è il più piccolo intero positivo r tale che a^r=1 mod p. Se, in particolare, l'ordine di aÎZ_p^* è f(p), ogni elemento di Z_p^* è esprimibile come una potenza di a.

Definizione 3.6.1 Un gruppo G è ciclico se esiste aÎG tale che per ogni bÎG esiste un intero i tale che b=aⁱ. Tale elemento a è chiamato generatore di G.

Data, quindi, la definizione di gruppo ciclico segue che, preso aÎZ_p^*, se l'ordine di a è f(p), allora a è detto generatore o elemento primitivo di Z_p^*. Se Z_p^* ha un generatore, allora Z_p^* è detto ciclico.

Diamo alcune proprietà dei generatori di Z_p^*:

Z_p^* ha un generatore se e solo se n=2,4,p^k,2p^k, dove p è primo e k³1. In particolare, se p è primo, allora Z_p^*ha un generatore.
Se a è un generatore di Z_p^*, allora Z_p^* ={aⁱ mod p tale che 0£ i £ p-1}
Supponiamo che a sia un generatore di Z_p^*. Allora b=aⁱ mod p è ancora un generatore di Z_p^* se e solo se gcd(i,f(p))=1. Poichè Z_p^* è ciclico, allora il numero di generatori è f(f(p)).

3.7 Calcolo di un generatore di Z_p^*

Vediamo come calcolare un generatore di Z_p^*. Una prima idea potrebbe essere quella di scegliere un elemento gÎZ_p^* e vedere, calcolando le potenze g¹,g²,g³,.... se genera tutti i possibili valori di Z_p^*. La complessità di tale algoritmo sarà proporzionale alla cardinalità a di Z_p^* e lavorerà in tempo esponenziale rispetto alla lunghezza di p. Se p è di 512 bit allora la cardinalità di Z_p^* è dell' ordine di 2⁵¹².
L'unico algoritmo conosciuto, in grado di determinare efficientemente un generatore di un gruppo ciclico Z_p^* presuppone la conoscenza della fattorizzazione di p-1, in quanto si basa sul seguente teorema:

Teorema 3.7.1 Sia dato un gruppo ciclico G con |G|=p-1 e sia data la fattorizzazione di p-1=p₁^e1 p₂^{e2
....}p_k^ek.
Allora a è un generatore di G se e solo se a^(p-1)/pi ¹1 mod p "iÎ{1,..,k}

Dimostrazione: Supponiamo che a sia un generatore di G, se esistesse un iÎ{1,..,k} tale che a^(p-1)/pi =1 mod p, l'ordine del sottogruppo generato da a è al più uguale a p₁^e1...p_i-1^ei-1p_i^eip_i+1^ei+1....p_k^ek <p-1. Assurdo.
Viceversa, per il teorema di Lagrange l'ordine di a divide |G|. Ma |G|=p-1 e gli unici elementi che dividono p-1 sono per ipotesi p₁,...,p_k . Se quindi, valgono le equazioni dell'enunciato deve risultare necessariamente che l'ordine di a è uguale a |G|.

Mostriamo l'algoritmo per la generazione di a che si basa sul precedente teorema:

Algortimo per trovare un generatore di un gruppo ciclico

INPUT: Un gruppo ciclico G di ordine p-1, con p primo;
fattorizzazione di p-1 = p₁^e1 p₂^{e2 ....}p_k^ek.

1. Scegli un elemento a caso x ÎG.

2. For i=1 to k do

calcola b= x ^(p-1)/pi mod p

if b=1 then goto passo 1

3. OUTPUT: x come generatore del gruppo ciclico G.

Notiamo che il test al passo 2 dell'algoritmo si basa sul teorema 3.7.1.
Dalla proprietà 3 della sezione 3.6 segue che il numero di generatori modulo un numero primo p è f(f(p))=f(p-1). Inoltre, dalla teoria dei numeri risulta che f(p)>p/(6lnln p) per tutti gli interi p³5.
Segue quindi che f(f(p))=f(p-1)>(p-1)/(6lnln (p-1)).
Pertanto, la probabilità che un elemento scelto a caso in Z_p^* sia un generatore risulta essere maggiore o uguale a 1/(6lnln (p-1)).
In media il numero di iterazioni è minore di 6lnln (p-1).

Esempio:

Per p di 512 bit il numero medio di iterazioni è minore di 6lnln (2⁵¹²)=35,23
Per p di 1024 bit il numero medio di iterazioni è minore di 6lnln (2¹⁰²⁴)=39,38

3.8 Generazione delle chiavi

Ora mostriamo un algoritmo per la generazione delle chiavi:

Algoritmo di generazione delle chiavi

Seleziona un numero primo q tale che 2¹⁵⁹<q<2¹⁶⁰
Scegli t tale che 0£ t £ 8 e seleziona un numero primo p tale che 2^511+64t<q<2^512+64tcon la proprietà che q|(p-1)
Selezione di un generatore a dell'unico gruppo ciclico di ordine q in Z_p^*
3.1 Scegli a caso un elemento gÎZ_p^* e calcola a=g^(p-1)/q mod p
3.2 if a=1 then goto passo 3.1
Seleziona un intero a caso s tale che 1£ s £ q-1
Calcola b=a^s mod p

La lunghezza di q è di 160 bit, la lunghezza di p va da 512 a 1024 bit utilizzando multipli di 64 bit (512, 576,...).
Il passo 3 trova un elemento a che è di ordine q, infatti a^q = ( g^(p-1)/q )^q=1 mod p e, quindi, per definizione a è un elemento di ordine q. Infine, l'algoritmo calcola i valori b e s della chiave.
I passi 1 e 2 richiedono la selezione di numeri primi; vediamo, quindi, di seguito un algortimo che ci permette di generare tali primi.

3.8.1 Algoritmo per la generazione dei primi

Prima di descrivere il funzionamento del seguente algoritmo, osserviamo che un approccio alternativo potrebbe essere quello di scegliere a caso il valore di p, e poi determinare un fattore q di (p - 1) che sia di 160 bit. Naturalmente questo tipo di soluzione risulta essere computazionalmente onerosa, in quanto involve la fattorizzazione di (p-1) per calcolare q. Nell'algoritmo proposto dal NIST viene scelto dapprima il valore q (160 bit) in maniera casuale, e successivamente si determina p; vediamo quali sono i passi attraverso i quali tale algoritmo lavora:

Illustriamo i passi di tale algoritmo.
Il ciclo 3-8 calcola il valore di q utilizzando la funzione one-way SHA che previene la possibilità di invertire i passi della computazione di q. Si noti che per LSB di un numero di intende il bit meno significativo e MSB il bit più significativo.
Nel ciclo 11-16 viene calcolato un valore per p. Se p è primo e la sua lunghezza è esattamente L, il ciclo 2-23 termina con la determinazione dei primi p e q. Altrimenti se p non è primo o la sua lunghezza non è esattamente L, allora il ciclo 11-16 viene ripetuto fino a quando un primo p viene trovato oppure il numero di iterazioni è minore di 4096. Se, dopo tale numero di iterazioni, non è stato ancora determinato un primo p di lunghezza L, allora viene ripetuto il ciclo 2-23 ricalcolando, quindi, il primo q. I parametri S e C rappresentano rispettivamente la sequenza casuale di bit per generare q, e il numero di iterazioni effettuate per generare p. Come tali sono dei testimoni della validità di p e q.
Questo algoritmo potrebbe comunque calcolare dei valori truffa di p e q, ma questo non è un problema per due motivi: innanzitutto i moduli per i quali tale proprietà è vera sono facili da scoprire; inoltre questi moduli sono così rari che la probabilità di calcolarne uno è più piccola della probabilità di generare un numero composto utilizzando una routine probabilistica di generazione di numeri primi.