FIRMA DIGITALE SCHEMI, METODI E CIFRARI

Algoritmo Tipo Determinismo Anno

RSA Recupero Deterministico 1978 Rabin Recupero 1979 ElGamal Appendice Probabilistico 1984 DSA Appendice Probabilistico 1991 Schnorr Appendice 1991 Nyberg-Rueppel Recupero 1993

RSA L’algoritmo di RSA è reversibile, ovvero funziona anche invertendo le chiavi. Perciò RSA a

chiavi invertite è un algoritmo di firma con recupero.

Usare RSA per una firma di un documento è però inefficiente a causa della idispensabile

suddivisione in blocchi. Di dimensione inferiore a n. Qundi è possibile firmale solo l’hash del

documento.

ALGO RIT MO S 1. 𝑐 = (𝐻 𝑚 )𝑃𝑈 𝑚𝑜𝑑 𝑛

2. Trasmette 𝑚 ∥ 𝑐

ALGO RIT MO V

1. Estrae 𝑚′

2. Calcola 𝐻(𝑚′ )

3. Accetta 𝑚′ se e solo se 𝐻 𝑚′ = 𝑐𝑒𝑚𝑜𝑑 𝑛 = 𝐻(𝑚)

F IRMA C I ECA

Dato un messaggio 𝑚 = 𝑚1 × 𝑚2 si ha

𝑐 = 𝑚𝑑 𝑚𝑜𝑑 𝑛 = 𝑚1𝑑𝑚𝑜𝑑 𝑛 × 𝑚2

𝑑𝑚𝑜𝑑 𝑛 𝑚𝑜𝑑 𝑛

Quindi possiamo firmare indipendentemente parti di messagio.

Sia, ora X un ente certificatore che deve firmare il messaggio 𝑚 senza conoscerne il

contenuto. L’utente U può inviare

𝑐1 = 𝑚 × 𝑟𝑒𝑋 𝑚𝑜𝑑 𝑛𝑋

Ora X può firmare applicanto la prorpia chiave privata e inviare

𝑐2 = 𝑚𝑑𝑋 × 𝑟𝑑𝑋 𝑒𝑋 𝑚𝑜𝑑 𝑛𝑋 = 𝑚𝑑𝑋 × 𝑟 𝑚𝑜𝑑 𝑛𝑋

Quindi U avrà

𝑐3 = 𝑚𝑑𝑋 × 𝑟 × 𝑟−1 𝑚𝑜𝑑 𝑛𝑋 = 𝑚𝑑𝑋 𝑚𝑜𝑑 𝑛𝑋

Messaggio firmato senza che l’utente certificatore abbia letto il contenuto.

ELGAMAL L’input è l’impornta ℎ = 𝐻(𝑚)

L’output sono due etichette 𝑅, 𝑆

Si basa sul problema P1

ALGO RI MO G

1. Scelta di un numero primo 𝑝 di un suo generatore 𝑔 un numero a caso 1 ≤ 𝑢 ≤

𝑝 − 2

2. Chiave pubblica : 𝑝, 𝑔, 𝑔𝑢 𝑚𝑜𝑑 𝑝

3. Chiave privata: 𝑢

ALGO RIT MO S

Per ogni messaggio da inviare si ha

1. Scegliere 𝑘 tale che 2 < 𝑘 < 𝑝 − 2 e 𝑀𝐶𝐷 𝑘, 𝑝 − 1 = 1

2. Generare l’etichetta 𝑅 = 𝑔𝑘𝑚𝑜𝑑 𝑝

Questo è vero perchè

𝑔ℎ𝑚𝑜𝑑 𝑝 = 𝑦𝑅𝑅𝑆𝑚𝑜𝑑 𝑝

𝑔ℎ𝑚𝑜𝑑 𝑝 = 𝑔𝑎𝑅𝑔𝑘𝑆𝑚𝑜𝑑 𝑝

𝑔ℎ−𝑎𝑅−𝑘𝑆 ≡ 1(𝑚𝑜𝑑 𝑝)

ℎ − 𝑎𝑅 − 𝑘𝑆 ≡ 𝑝 − 1(𝑚𝑜𝑑 𝑝)

ℎ − 𝑎𝑅 − 𝑘𝑆 ≡ 0(𝑚𝑜𝑑 𝑝 − 1)

𝑆 = 𝑘−1 ℎ − 𝑎𝑅 𝑚𝑜𝑑 (𝑝 − 1)

S è espressione congruenziale di firma.

ALGO RIT MO V

1. Controllare che sia 1 ≤ 𝑅 ≤ 𝑝 − 1 e 𝑆 ≠ 𝑝 − 1

2. Calcolare

𝑣1 = 𝑦𝑅𝑅𝑆𝑚𝑜𝑑 𝑝

𝑣2 = 𝑔ℎ𝑚𝑜𝑑 𝑝

3. Se 𝑣1 = 𝑣2 il messaggio è integro.

DSS Basato su ElGamal

Si basa sul problema P1

La dimensione di p è definita dallo standard: 2512 < 𝑝 < 21024

I calcoli di R e S sono fatti 𝑚𝑜𝑑 𝑞 ove 𝑞 è il più grande fattore primo di 𝑝 − 1 tale

che 2159 < 𝑞 < 2160

𝐻(𝑚) deve essere di 160 bit e calcolata con SHA-1

ALGO RIT MO G

Come ElGamal

ALGO RIT MO S

Per ogni messaggio da firmarel’utente deve scegliere un numero a caso 1 ≤ 𝑘 ≤ 𝑞 − 1 e

calcola due etichette di 160 bit ciascuma:

𝑅 = 𝑔𝑘𝑚𝑜𝑑 𝑝 𝑚𝑜𝑑 𝑞

𝑆 = 𝑘−1 𝐻 𝑚 + 𝑎 × 𝑅 𝑚𝑜𝑑 𝑞

ALGO RIT MO V

1. Verificare che sia 0 < 𝑅 < 𝑞 e 0 < 𝑆 < 𝑞

2. Calcolare:

𝑤 = 𝑆−1𝑚𝑜𝑑 𝑞

𝑢1 = 𝐻 𝑚 × 𝑤 𝑚𝑜𝑑 𝑞

𝑢2 = 𝑅 × 𝑤 𝑚𝑜𝑑 𝑞

𝑣 = 𝑔𝑢1 × 𝑦𝑢2 𝑚𝑜𝑑 𝑝 𝑚𝑜𝑑 𝑞

3. Se 𝑣 = 𝑅 la firma è valida.