Passa al contenuto principale

2. Notazioni DSA ed ECDSA

In questa sezione, descriviamo succintamente DSA ed ECDSA e definiamo le nostre notazioni. Le specifiche complete per DSA ed ECDSA possono essere trovate in [FIPS-186-4] e [X9.62], rispettivamente.

2.1. Parametri della Chiave​

DSA ed ECDSA operano su un grande gruppo di dimensione prima, in cui l'operazione di gruppo è facile da calcolare, ma il logaritmo discreto è computazionalmente impraticabile con la tecnologia esistente e prevedibile. La definizione del gruppo è chiamata "parametri della chiave". I parametri della chiave possono essere condivisi tra diverse coppie di chiavi senza alcun effetto negativo sulla sicurezza; questo è il caso abituale con ECDSA in particolare.

DSA utilizza i seguenti parametri della chiave:

p: un grande numero primo (almeno 1024 bit)

q: un numero primo sufficientemente grande (almeno 160 bit) che è anche un divisore di p-1

g: un generatore per il sottogruppo moltiplicativo di ordine q degli interi modulo p

Il gruppo su cui sarà calcolato DSA consiste dei valori g^j mod p, dove ^ denota l'esponenziazione e j varia da 0 a q-1 (inclusi). La dimensione del gruppo è q.

ECDSA utilizza i seguenti parametri della chiave:

E: una curva ellittica, definita su un dato campo finito

q: un numero primo sufficientemente grande (almeno 160 bit) che è un divisore dell'ordine della curva

G: un punto di E, di ordine q

Il gruppo su cui sarà calcolato ECDSA consiste dei punti della curva jG (moltiplicazione del punto G per l'intero j) dove j varia da 0 a q-1. G è tale che qG = 0 (il "punto all'infinito" sulla curva E). La dimensione del gruppo è q. Si noti che queste notazioni differiscono leggermente da quelle descritte in [X9.62]; le usiamo al fine di corrispondere a quelle utilizzate per DSA.

2.2. Coppie di Chiavi​

Una chiave privata DSA o ECDSA è un intero x preso modulo q. Gli standard pertinenti prescrivono che x NON DOVRÀ essere 0; quindi, x è un intero nell'intervallo [1, q-1].

Una chiave pubblica DSA o ECDSA è calcolata dalla chiave privata x e dai parametri della chiave:

  • Per DSA, la chiave pubblica è l'intero: y = g^x mod p

  • Per ECDSA, la chiave pubblica è il punto della curva: U = xG

2.3. Conversioni di Interi​

Sia qlen la lunghezza binaria di q. qlen è il più piccolo intero tale che q è minore di 2^qlen. Questa è la dimensione della rappresentazione binaria di q senza un bit di segno (si noti che q, essendo un grande numero primo, è dispari, evitando così qualsiasi ambiguità sulla lunghezza di qualsiasi intero uguale a una potenza di 2). Definiamo cinque funzioni di conversione, che operano su stringhe di bit, ottetti e interi modulo q. qlen è il parametro principale per queste conversioni.

Nelle seguenti sottosezioni, utilizziamo altre due lunghezze, chiamate blen e rlen. rlen è uguale a qlen, arrotondato per eccesso al successivo multiplo di 8 (se qlen è già un multiplo di 8, allora rlen è uguale a qlen; altrimenti, rlen è leggermente più grande, fino a qlen+7). Si noti che rlen non è correlato al valore r, la prima metà di una firma generata. blen è la lunghezza (in bit) di una sequenza di input di bit e può variare tra le chiamate. blen può essere inferiore, uguale o maggiore di qlen.

2.3.1. Bit e Ottetti​

Formalmente, tutte le operazioni sono definite su sequenze di bit. Una sequenza è ordinata; il primo bit si dice essere il più a sinistra, mentre l'ultimo bit è il più a destra.

Sulla maggior parte dei sistemi software, i bit sono raggruppati in ottetti (sequenze di otto bit). I dati binari, ad esempio, l'output di una funzione hash, sono disponibili come sequenza di ottetti. Quando applicabile, consideriamo che i bit all'interno di un ottetto siano ordinati dal più significativo al meno significativo: il primo bit (più a sinistra) all'interno di un ottetto ha valore numerico 128, mentre l'ultimo (più a destra) ha valore numerico 1.

2.3.2. Stringa di Bit a Intero​

La trasformazione bits2int prende come input una sequenza di blen bit e restituisce un intero non negativo che è minore di 2^qlen. Consiste dei seguenti passaggi:

  1. La sequenza viene prima troncata o espansa alla lunghezza qlen:

    • se qlen < blen, allora vengono mantenuti i qlen bit più a sinistra, e i bit successivi vengono scartati;

    • altrimenti, vengono aggiunti blen-qlen bit (di valore zero) alla sinistra della sequenza (cioè, prima dei bit di input nell'ordine della sequenza).

  2. La sequenza risultante viene quindi convertita in un valore intero utilizzando la convenzione big-endian: se i bit di input sono chiamati b_0 (più a sinistra) a b_(qlen-1) (più a destra), allora il valore risultante è:

    b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0

La trasformazione bits2int può anche essere descritta nel modo seguente: la sequenza di bit di input (di lunghezza blen) viene trasformata in un intero utilizzando la convenzione big-endian. Quindi, se blen è maggiore di qlen, l'intero risultante viene diviso per due elevato alla potenza blen-qlen (divisione euclidea: il resto viene scartato); in molte implementazioni software di aritmetica su grandi interi, quella divisione è equivalente a uno "shift a destra" di blen-qlen bit.

2.3.3. Intero a Stringa di Ottetti​

Un valore intero x minore di q (e, in particolare, un valore che è stato preso modulo q) può essere convertito in una sequenza di rlen bit, dove rlen = 8*ceil(qlen/8). Questa è la sequenza di bit ottenuta mediante codifica big-endian. In altre parole, i bit della sequenza x_i (per i che varia da 0 a rlen-1) sono tali che:

x = x_0*2^(rlen-1) + x_1*2^(rlen-2) + ... + x_(rlen-1)

Chiamiamo questa trasformazione int2octets. Poiché rlen è un multiplo di 8 (il più piccolo multiplo di 8 che non è inferiore a qlen), allora la sequenza di bit risultante è anche una sequenza di ottetti, da cui il nome.

2.3.4. Stringa di Bit a Stringa di Ottetti​

La trasformazione bits2octets prende come input una sequenza di blen bit e restituisce una sequenza di rlen bit. Consiste dei seguenti passaggi:

  1. La sequenza di input b viene convertita in un valore intero z1 attraverso la trasformazione bits2int:

    z1 = bits2int(b)

  2. z1 viene ridotto modulo q, producendo z2 (un intero tra 0 e q-1, inclusi):

    z2 = z1 mod q

    Si noti che poiché z1 è minore di 2^qlen, quella riduzione modulare può essere implementata con una semplice sottrazione condizionale: z2 = z1-q se quel valore è non negativo; altrimenti, z2 = z1.

  3. z2 viene trasformato in una sequenza di ottetti (una sequenza di rlen bit) applicando int2octets.

2.3.5. Utilizzo​

Vale la pena notare che int2octets non è l'inverso di bits2int, nemmeno per sequenze di input di lunghezza qlen: int2octets aggiungerà alcuni bit a sinistra, mentre bits2int scarterà alcuni bit a destra. int2octets è l'inverso di bits2int solo quando qlen è un multiplo di 8 e le sequenze di bit hanno già lunghezza qlen.

bits2int viene utilizzato durante la generazione e la verifica della firma in DSA ed ECDSA standard per trasformare un valore hash (calcolato sul messaggio di input) in un intero modulo q. Cioè, l'intero ottenuto attraverso bits2int viene ulteriormente ridotto modulo q; poiché quell'intero è minore di 2^qlen, quella riduzione può essere eseguita con al massimo una sottrazione.

int2octets è definito con il nome "Integer-to-OctetString" nella Sezione 2.3.7 di SEC 1 [SEC1]. Viene utilizzato nella specifica della codifica di una chiave privata ECDSA (x) all'interno di una struttura basata su ASN.1.

bits2octets non viene utilizzato in DSA o ECDSA standard. Lo useremo nella specifica di (EC)DSA deterministico.

2.4. Generazione della Firma​

La generazione della firma utilizza una funzione hash crittografica H e un messaggio di input m. Il messaggio viene prima elaborato da H, producendo il valore H(m), che è una sequenza di bit di lunghezza hlen. Normalmente, H viene scelta in modo tale che la sua lunghezza di output hlen sia approssimativamente uguale a qlen, poiché la sicurezza complessiva dello schema di firma dipenderà dal più piccolo tra hlen e qlen; tuttavia, gli standard pertinenti supportano tutte le combinazioni di hlen e qlen.

Vengono quindi applicati i seguenti passaggi:

  1. H(m) viene trasformato in un intero modulo q utilizzando la trasformazione bits2int e una riduzione modulare aggiuntiva:

    h = bits2int(H(m)) mod q

    Come è stato notato nella descrizione di bits2octets, la riduzione modulare aggiuntiva non è più di una sottrazione condizionale.

  2. Viene generato un valore casuale modulo q, denominato k. Quel valore NON DOVRÀ essere 0; quindi, si trova nell'intervallo [1, q-1]. La maggior parte del resto di questo documento ruoterà intorno al processo utilizzato per generare k. In DSA o ECDSA standard, k DOVREBBE essere selezionato attraverso una selezione casuale che sceglie un valore tra i q-1 valori possibili con probabilità uniforme.

  3. Un valore r (modulo q) viene calcolato da k e dai parametri della chiave:

    • Per DSA:

      r = g^k mod p mod q

      (L'esponenziazione viene eseguita modulo p, producendo un numero tra 0 e p-1, che viene quindi ulteriormente ridotto modulo q.)

    • Per ECDSA: viene calcolato il punto kG; la sua coordinata X (un membro del campo su cui E è definito) viene convertita in un intero, che viene ridotto modulo q, producendo r.

    Se r risulta essere zero, DOVREBBE essere selezionato un nuovo k e r calcolato nuovamente (questo è un evento assolutamente improbabile).

  4. Il valore s (modulo q) viene calcolato:

    s = (h+x*r)/k mod q

    La coppia (r, s) è la firma. Come una firma debba essere codificata non è coperto dagli standard DSA ed ECDSA stessi; un modo comune è utilizzare una struttura ASN.1 codificata in DER (una SEQUENCE di due INTEGER, per r e s, in quell'ordine).