Firma Digitale RSA

Gli algoritmi di firma digitale che utilizzano chiavi crittografiche di tipo RSA sono specificati in una serie di standard chiamati Public-Key Cryptography Standards (PKCS) e sviluppati da RSA Laboratory.

Masked Generation Function

Una Masked Generation Function è una funzione che riceve in ingresso una stringa di byte e produce una stringa di byte in output. Come parametri sono indicati la stringa di ingresso e un intero che indica la lunghezza desiderata dell'output.

output = MGF(input, lunghezza)

L'output viene generato in modo deterministico (ad uno stesso input corrisponde lo stesso output), ma per essere impiegata in ambito crittografico è necessario che:

  • sia difficile ricavare la stringa di input a partire da quella di output
  • senza conoscere la stringa di input, quella di output appare come una sequenza pseudocasuale

In genere le funzioni di questo tipo impiegano delle funzioni di Hash.

RSASSA-PKCS1-V1_5-SIGN

Dato un messaggio M, la chiave privata del mittente, una funzione di hash, e una lunghezza desiderata della firma emLen, la firma avviene tramite la seguente codifica.

Sia T una stringa formata dal codice hash H del messaggio M, e da un identificativo che indica la funzione hash utilizzata: T = (HashID | H)
Sia tLen la lunghezza di T.

Si crea un blocco di dati codificato EB nel modo seguente:

EB = 0x00|0x01|PS|0x00|T

dove PS è una stringa di dati di lunghezza pari a emLen – tLen – 3 formata da byte di valore 0xFF.

La firma è costituita dalla cifratura tramite chiave privata del mittente della stringa EB.

Gli identificativi sono definiti in questo modo (stringhe di bit in formato esadecimale):

MD2 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04 10
MD5 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10
SHA-1 30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14
SHA-256 30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20
SHA-384 30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30
SHA-512 30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40

La verifica della firma consiste nella decifrazione della stringa EB tramite la chiave pubblica del mittente. Ottenuta EB, si ricava la stringa T. Tramite HashID si determina la funzione Hash utilizzata e la si impiega per calcolare il codice hash del messaggio. Si confronta quest'ultimo con la stringa H.

Esempio firma RSASSA-PKCS1-V1_5-SIGN

Sia M il messaggio di valore "prova". Si sceglie SHA-1 come algoritmo di Hash, quindi hLen = 20 byte. La chiave pubblica ha lunghezza 1024 bit, quindi k = 128 byte.

H = SHA-1(M) = 6279886fde090b3038f267098bcca771a6efa946

Si vuole una lunghezza di firma pari a 256 byte, quindi emLen = 256.

Allora
T = (HashID | H) = (30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 | 62 79 88 6f de 09 0b 30 38 f2 67 09 8b cc a7 71 a6 ef a9 46)

tLen = 15 + 20 = 35 byte

La stringa PS ha lunghezza pari a: 256 - 35 - 3 = 218 byte

Il blocco dati EB è:

00 01 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 00 30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 62 79 88 6f de 09 0b 30 38 f2 67 09 8b cc a7 71 a6 ef a9 46

La firma è data dalla cifratura di EB con la chiave privata del mittente.

RSASSA-PSS

Dato un messaggio M, una funzione di Hash e una chiave privata (n, d), si costruisce la seguente stringa di byte codificata.

Sia mHash il codice Hash del messaggio M, di lunghezza hLen. Si genera una stringa di byte detta salt di lunghezza sLen, che può essere anche nulla. Si pone

M' = 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 | mHash | salt

Sia H l'hash della stringa M':
H = HASH(M)

Si genera una stringa PS di lunghezza emLen - sLen - hLen - 2 di byte con valore 0x00, che può anche avere lunghezza nulla.

Sia DB una stringa di lunghezza emLen - hLen - 1 composta dalla seguente concatenazione:
DB = PS | 0x01 | salt

Si calcola:
dbmask = MGF(H, emLen - hLen - 1)
maskedDB = DB xor dbmask

si pongono gli 8emLen - emBits bit del byte più a sinistra a 0.

Sia
EM = maskedDB | H | 0xBC

La firma è costituita dalla cifratura con la propria chiave privata della stringa EM

Il destinatario che riceve una firma effettua la decifratura con la chiave pubblica del mittente, ottenendo la stringa EM

I primi emLen – hLen – 1 byte di EM rappresentano il valore di maskedDB, e i successivi hLen il valore di H. L'ultimo byte (più a destra) deve avere valore 0xBC. Si verifica che gli 8emLen – emBits bit più a sinistra del byte più a sinistra di maskedDB devono essere nulli.

Si calcola
mHash = HASH(M)
dbMask = MGF (H, emLen – hLen – 1)
DB = maskedDB xor dbMask

Si pongono i 8emLen – emBits bit più a sinistra del byte più a sinistra di DB a zero. Si verifica che gli emLen – hLen – sLen – 2 byte più a sinistra di DB siano nulli e che l'ottetto nella posizione emLen – hLen – sLen – 1 abbia il valore 0x01

Gli ultimi sLen byte di DB sono la stringa salt. Si costruisce la stringa M':
M' = 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 | mHash | salt

e si calcola
H' = HASH(M')

La firma è valida se H' = H.

Esempio firma RSASSA-PSS

Si considera un messaggio M = "prova", la funzione di Hash SHA-1 e la chiave privata.

mHash = SHA-1(M) = 62 79 88 6f de 09 0b 30 38 f2 67 09 8b cc a7 71 a6 ef a9 46
hLen = 20

Consideriamo come stringa salt la seguente stringa casuale: 89 74 AC 91 15 D6 0B 32
sLen = 16

allora, la stringa M' è:

M' = 00 00 00 00 00 00 00 00 62 79 88 6f de 09 0b 30 38 f2 67 09 8b cc a7 71 a6 ef a9 46 89 74 AC 91 15 D6 0B 32

e il valore di H è:

H = SHA-1(M') = 5d 58 fd 77 bf ef 10 bb 4c de 73 70 f8 04 ad 0b 0a 14 c3 74

Si vuole una lunghezza di firma pari a 256 byte, quindi emLen = 256.

La lunghezza della stringa PS è: 256 - 16 - 20 - 2 = 218 byte di valore 0x00

Sia DB una stringa di lunghezza pari a 256 - 20 - 1 = 235 byte seguente:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 89 74 ac 91 15 d6 0b 32

la stringa dbmask ha lunghezza 235 byte, come DB e riceve in input il valore di H. Successivamente viene effettuata l'operazione di xor tra DB e dbmask per ottenere maskedDB, anch'essa di 235 byte. Infine si concatena maskedDB, H (di lunghezza 20) e un byte finale di valore 0xbc, per ottenere una stringa di lunghezza pari a 256 byte, come desiderato. Questa stringa viene cifrata con la chiave privata.

Algoritmi

Fattorizzazione Interi Logaritmo Discreto Curve Ellittiche
Firma RSA, Rabin-Williams, ESIGN DSA, Nyberg-Rueppel ECDSA, Nyberg-Rueppel su Curve Elittiche

Vedi anche

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License