Autentificazione della firma in RSA

Nel sistema RSA l'utente che scrive il messaggio (mittente) può utilizzare la sua chiave segreta per firmare il messaggio, mentre l'utente che lo riceve (destinatario) può verificare la firma usando la chiave pubblica del mittente.

Quando un utente vuole inviare un messaggio firmato a un altro utente, può apporre una firma sul messaggio. Una volta ricevuto il messaggio, il destinatario potrà verificare che la firma sia effettivamente del mittente.

Il sistema di crittografia RSA può essere utilizzato per autenticare le firme elettroniche.

Come funziona?
Un esempio pratico
La funzione di hash

Come funziona?

Nel sistema RSA ogni utente ha una chiave pubblica, nota a tutti, e una chiave privata che è conosciuta solo dall'utente.

Ad esempio, considero due utenti A e B con le seguenti chiavi pubbliche: $K_A$ e $K_B$

$K_A = (n_A,e_A)$

$K_B = (n_B,e_B)$

Dove ogni chiave pubblica è una coppia di valori numerici $(n,e)$ . Le chiavi pubbliche degli utenti sono conosciute da tutti.

Ogni utente ha, inoltre, una chiave privata (segreta) che solo lui conosce: $d_A$ e $d_B$

L'utente che scrive il messaggio (mittente) usa la sua chiave segreta per firmare il messaggio, mentre l'utente che lo riceve utilizza la chiave pubblica del mittente per verificare la firma.

1] Scrittura del messaggio con firma

L'utente A (mittente) scrive il messaggio $M$ .

Poi genera una firma elettronica $F$ .

La firma $F$ è un valore numerico che rappresenta $M$ , di solito si usa una funzione hash calcolata sul messaggio $M_1$ per generarla.

$F = \text{hash}( M )$

Nota. La firma viene generata dalla funzione di hash a partire dal messaggio. In questo modo, se qualcuno alterasse il contenuto del messaggio durante la spedizione, la firma generata sul messaggio originale non risulterebbe più valida.

A questo punto l'utente A cripta la firma usando la sua chiave segreta $d_A$ che solo lui conosce:

$F_c = F^{d_A} \mod n_A$

Quindi, invia il messaggio all'utente B.

2] Ricezione del messaggio firmato

L'utente B (destinatario) riceve il messaggio $M_1$ e la firma criptata $F_c$ del mittente.

Per verificare e decriptare la firma $F_c$ , l'utente B utilizza la chiave pubblica del mittente $e_A$

$F_c^{e_A} \mod n_A = (F^{d_A})^{e_A} \mod n_A$

Poiché in RSA vale $d_A \cdot e_A \equiv 1 \mod \phi(n_A)$ , si ottiene:

$F_c^{e_A} \mod n_A = F$

L'utente B ha recuperato la firma $F$ dell'utente A.

A questo punto, per verificare la validità della firma rispetto al messaggio, il destinatario applica la stessa funzione di hash al messaggio $M$ ricevuto per ottenere un valore $H$ :

$H = \text{hash}(P_1)$

Poi confronta $F$ e $H$ :

Se il valore $F$ ottenuto dalla firma decifrata corrisponde a $H$ , l'hash calcolato dal messaggio ricevuto), allora la firma è valida e il messaggio non è stato alterato.
Se $F \neq H$ , il destinatario sa che il messaggio è stato modificato da terzi e/o la firma non è autentica.

In altre parole, la funzione di hash agisce come un "impronta digitale" del messaggio.

La firma criptata $F_c$ garantisce che questa impronta sia autentica e collegata al mittente.

Nota. Quando il destinatario decripta $F_c$ e confronta il risultato con l'hash calcolato localmente, verifica sia l'integrità che l'autenticità del messaggio. Questo garantisce al destinatario la certezza che il messaggio proviene realmente dal mittente e non ha subito alterazioni.

Un esempio pratico

Ecco un esempio pratico di firma digitale RSA con invio di un messaggio da A a B

L'utente ha le seguenti chiavi:

La chiave pubblica di A è $(n_A = 77, e_A = 13)$
La ciave privata di A è $d_A = 37$

Nota. La chiave pubblica l'ho generata usando due numeri primi: $p = 7$ e $q = 11$ . $n_A = p \cdot q = 7 \cdot 11 = 77$ A cui corrisponde la funzione di Eulero $\phi(n_A)$ $\phi(n_A) = (p-1) \cdot (q-1) = 6 \cdot 10 = 60$ Poi ho scelto un valore $e_A$ coprimo con $\phi(n_A)$ : $e_A = 13$ . La chiave segreta è un valore tale che $d_A \cdot e_A \equiv 1 \mod \phi(n_A)$ Utilizzando l'algoritmo euclideo esteso ho ottenuto $d_A = 37$

1] L'utente A scrive il messaggio con una firma digitale

L'utente A scrive un messaggio.

$M = 5$

Poi utilizza la funzione hash per generare la firma.

Per semplicità, in questo esempio la funzione hash restituisce un valore identico al valore del messaggio stesso (in casi reali, si usa una funzione hash come SHA-256).

$F = \text{hash}(M) = 5$

Quindi, utilizza la sua chiave privata $d_A = 37$ per calcolare la firma criptata $F_c$ :

$F_c = F^{d_A} \mod n_A$

$F_c = 5^{37} \mod 77$

$F_c = 47$

Infine, invia all'utente B il messaggio $M = 5$ e la firma criptata $F_c = 47$ .

Nota. Per risolvere la congruenza $5^{37} \mod 77$ il metodo delle potenze successive:

   - $5^1 \mod 77 = 5$
   - $5^2 \mod 77 = 25$
   - $5^4 = (5^2)^2 \mod 77 = 25^2 \mod 77 = 625 \mod 77 = 9$
   - $5^8 = (5^4)^2 \mod 77 = 9^2 \mod 77 = 81 \mod 77 = 4$
   - $5^{16} = (5^8)^2 \mod 77 = 4^2 \mod 77 = 16$
   - $5^{32} = (5^{16})^2 \mod 77 = 16^2 \mod 77 = 256 \mod 77 = 25$

Per la proprietà delle potenze

$5^{37} = 5^{32} \cdot 5^4 \cdot 5^1$

In questo modo, invece di calcolare direttamente $5^{37}$ , posso applicare il principio di riduzione modulare in ogni passo.

$5^{37} \mod 77 = (5^{32} \cdot 5^4 \cdot 5^1) \mod 77$

Sostituisco i valori modulo 77 delle rispettive potenze.

Ad esempio, $5^{32} \mod 77 = 25$ , $5^4 \mod 77=9$ e $5^1 \mod 77= 5$ .

$5^{37} \mod 77 = (25 \cdot 9 \cdot 5) \mod 77$

$5^{37} \mod 77 = 1125 \mod 77$

$5^{37} \mod 77 = 47$

Così facendo i calcoli per risolvere la congruenza diventano molto più semplici: $1125 : 77 = 14$ con resto $r=47$

2] L'utente B riceve il messaggio e verifica la firma

L'utente B (destinatario) B riceve il messaggio $M$ e la firma $F_c$ .

Deve verificare se la firma apposta sul messaggio è valida.

Utilizza la chiave pubblica di A $(n_A = 77, e_A = 13)$ per decifrare $F_c$ :

$F = F_c^{e_A} \mod n_A$

$F = 47^{13} \mod 77$

$F = 5$

Poi verifica la firma usando la funzione di hash sul messaggio ricevuto.

$H = \text{hash}(M) = 5$

Infine, confronta il valore $F$ ottenuto dalla firma decifrata con l'hash calcolato.

Poiché $F=H$ capisce che la firma è valida.

In questo esempio, i numeri sono semplici per motivi didattici. Nella realtà, si usano numeri molto più grandi per garantire sicurezza.

Nota. Per calcolare $47^{13} \mod 77$ passo dopo passo, utilizzo l'esponenziazione modulare e le proprietà delle potenze modulari. Calcolo le potenze successive di $47 \mod 77$ :

- $47^1 \mod 77 = 47$
   - $47^2 \mod 77 = (47 \cdot 47) \mod 77 = 2209 \mod 77 = 34$
   - $47^4 \mod 77 = (34 \cdot 34) \mod 77 = 1156 \mod 77 = 4$
   - $47^8 \mod 77 = (4 \cdot 4) \mod 77 = 16$

Per la proprietà delle potenze

$47^{13} = 47^{8} \cdot 47^{5}$

$47^{13} = 47^{8} \cdot 47^{4} \cdot 47^{1}$

Combino le potenze necessarie secondo la forma binaria dell'esponente:

$47^{13} \mod 77 = ( 47^{8} \cdot 47^{4} \cdot 47^{1} ) \mod 77$

Sostituisco i valori modulo 77 delle rispettive potenze.

Ad esempio, $47^8 \mod 77 = 16$ mentre $47^4 \mod 77=4$ .

$47^{13} \mod 77 = ( 16 \cdot 4 \cdot 47 ) \mod 77$

$47^{13} \mod 77 = 3008 \mod 77$

$47^{13} \mod 77 = 5$

Quindi, il risultato della congruenza è 5 perché $3008 : 77 = 39$ con resto $r=5$

La funzione di hash

Una funzione hash prende in ingresso un messaggio (di qualsiasi lunghezza) e restituisce un valore a lunghezza fissa, detto digest.

Una buona funzione hash deve avere le seguenti proprietà:

Deterministica: lo stesso input produce sempre lo stesso hash.
Impossibilità di inversione: dato un digest, non si può risalire al messaggio originale.
Resistenza alle collisioni: è difficile trovare due messaggi diversi che producono lo stesso hash.
Diffusione: una minima modifica all'input cambia drasticamente il digest.

Un esempio di funzione hash comunemente utilizzata in crittografia è SHA-256 (Secure Hash Algorithm 256-bit) che appartiene alla famiglia di SHA-2.

A partire da un messaggio ( $M$ ) genera un valore numerico esadecimale $F$ .

$F = \text{SHA-256}(M)$

Ad esempio, se considero il messaggio seguente:

M="Questo è un esempio."

Utilizzando la funzione **SHA-256**, il digest in esadecimale $F$ sarà:

7a580dd696f5b5b6324a350b4a4cf3a6e4b43e672dc5f1b9dd84af7f3d9964c0

Se cambio anche un solo carattere cambia nel messaggio, ad esempio:

M="Questo è un esempio?"

Il nuovo hash $F$ sarà completamente diverso dal precedente.

30c916eec612587b60b0d770c9312a67d73d7efab39456970d03e4faaddbfb79

Ogni digest $F$ rappresenta in modo univoco il messaggio $M$ che l'ha generato.

Inoltre, ogni piccola variazione del messaggio originale genera un digest molto diverso.

Altre funzioni hash utilizzate oltre a SHA-256, sono le seguenti:

MD5 ormai obsoleta per applicazioni crittografiche, poiché non è resistente alle collisioni.
SHA-1 anche questa non è più considerata sicura per usi crittografici.
SHA-3 è la versione più recente della famiglia SHA.

Queste funzioni sono ampiamente utilizzate in crittografia, per firme digitali, autenticazione e checksum dei file.

E così via.