Algoritmo RSA: la teoria matematica alla base della crittografia a chiave pubblica

L'algoritmo RSA è uno dei sistemi di crittografia a chiave pubblica più conosciuti e utilizzati al mondo. Viene impiegato in protocolli come HTTPS, firme digitali, scambio sicuro di chiavi e in molti altri contesti di sicurezza informatica.

In questo articolo analizziamo la teoria matematica alla base di RSA, concentrandoci su:

• ruolo dei numeri primi e della fattorizzazione
• aritmetica modulare e congruenze
• funzione phi di Eulero
• generazione delle chiavi pubblica e privata
• motivi teorici della sicurezza dell'algoritmo

❓ Che cosa è in sintesi l'algoritmo RSA

RSA è un algoritmo di crittografia asimmetrica che utilizza una chiave pubblica per cifrare e una chiave privata per decifrare. La teoria alla base di RSA si fonda su tre pilastri matematici:

• la difficoltà di fattorizzare un intero molto grande nei suoi fattori primi
• le proprietà dell'aritmetica modulare
• il teorema di Eulero e la funzione phi di Eulero

L'idea chiave è costruire una trasformazione che sia facile da applicare in un verso, ma estremamente difficile da invertire senza un'informazione segreta, cioè la chiave privata.

📒 Numeri primi e fattorizzazione in RSA

La teoria di RSA parte dalla scelta di due numeri primi grandi, normalmente indicati con p e q.

• si scelgono due primi p e q molto grandi e segreti
• si calcola il loro prodotto n, cioè n = p * q
• questo numero n è chiamato modulo ed è reso pubblico

Conoscendo solo n, senza conoscere p e q, risulta molto difficile risalire ai fattori primi quando n è sufficientemente grande. Questo problema è noto come fattorizzazione di interi.

L'ipotesi di sicurezza di RSA è che, per valori reali usati in pratica, fattorizzare n richieda una quantità di tempo e risorse di calcolo non praticabile.

🔧 Aritmetica modulare e potenze in RSA

L'algoritmo RSA lavora all'interno dell'aritmetica modulare, cioè il calcolo eseguito tenendo conto del resto di una divisione per un numero n.

Se scriviamo a modulo n intendiamo il resto della divisione di a per n. Nel contesto delle congruenze si dice che:

a è congruo a b modulo n quando a e b producono lo stesso resto nella divisione per n.

In RSA si lavora con potenze modulari, cioè espressioni del tipo:

• c = m elevato alla e modulo n, per la cifratura
• m = c elevato alla d modulo n, per la decifratura

dove m è il messaggio in chiaro trasformato in numero, c è il cifrato, e è l'esponente pubblico, d è l'esponente privato, n è il modulo.

📜 Funzione phi di Eulero

Un elemento centrale della teoria di RSA è la funzione phi di Eulero, indicata spesso come phi di n. Per un numero intero positivo n, la funzione phi di Eulero restituisce:

• il numero di interi compresi tra 1 e n che sono coprimi con n, cioè con massimo comune divisore pari a 1

Nel caso di RSA, dove n è il prodotto di due primi distinti p e q, la funzione phi assume una forma molto semplice:

• phi(n) = phi(p * q)
• phi(n) = (p - 1) * (q - 1)

Questa formula è fondamentale perché compare direttamente nella generazione degli esponenti e e d.

💡 Teorema di Eulero e base teorica di RSA

Il teorema di Eulero afferma che, se a e n sono coprimi, cioè il massimo comune divisore tra a e n è uguale a 1, allora:

a elevato alla phi(n), calcolato modulo n, risulta congruo a 1.

Da questo teorema si deduce la possibilità di costruire due esponenti e e d tali che, per ogni numero a coprimo con n:

a elevato alla potenza e * d, calcolato modulo n, restituisca nuovamente a.

In RSA questa proprietà viene sfruttata nel modo seguente:

• si sceglie un esponente pubblico e coprimo con phi(n)
• si calcola un esponente privato d che sia inverso moltiplicativo di e modulo phi(n)

In altre parole, e e d vengono definiti in modo che il loro prodotto, considerato modulo phi(n), sia pari a 1. Questa relazione rende la cifratura e la decifratura operazioni inverse tra loro.

🔑 Generazione delle chiavi RSA

Scelta dei numeri primi e calcolo del modulo

La generazione delle chiavi RSA avviene teoricamente in questi passaggi:

• si scelgono due numeri primi p e q, casuali, grandi e segreti
• si calcola n = p * q
• il valore n viene reso pubblico e viene usato come modulo comune

Calcolo di phi(n)

Una volta determinato n, si calcola la funzione phi di Eulero:

• phi(n) = (p - 1) * (q - 1)

Scelta dell'esponente pubblico e

Si sceglie un numero intero e tale che:

• e sia maggiore di 1 e minore di phi(n)
• e sia coprimo con phi(n), cioè il massimo comune divisore tra e e phi(n) sia uguale a 1

Nella pratica si usano spesso valori standard come 65537, che offrono un buon compromesso tra sicurezza e prestazioni.

Calcolo dell'esponente privato d

L'esponente privato d viene calcolato come inverso moltiplicativo di e modulo phi(n). Significa trovare un numero d tale che:

il prodotto tra e e d, considerato modulo phi(n), dia come risultato 1.

Una volta trovato d, le chiavi sono definite così:

• chiave pubblica formata dalla coppia (n, e)
• chiave privata formata dalla coppia (n, d), che deve restare segreta

🔒 Cifratura e decifratura con RSA

Operazione di cifratura

Per cifrare un messaggio, si parte da un valore numerico m che rappresenta il messaggio in chiaro ed è minore di n. Il mittente calcola:

c = m elevato alla e modulo n.

Il valore c ottenuto è il messaggio cifrato che può essere inviato in modo sicuro.

Operazione di decifratura

Il destinatario, che conosce l'esponente privato d, calcola:

m = c elevato alla d modulo n.

Sostituendo c con m elevato alla e, si ottiene una potenza m elevato alla e * d modulo n. Grazie alla relazione tra e e d e al teorema di Eulero, questo calcolo restituisce il valore iniziale m.

In questo modo, solo chi possiede d può riportare il cifrato c al messaggio originario.

📉 Perché RSA è considerato sicuro dal punto di vista teorico

Dal punto di vista teorico, la sicurezza di RSA si basa soprattutto su due osservazioni:

• se si conosce phi(n), si può ricavare d risolvendo la relazione tra e e d modulo phi(n)
• per calcolare phi(n) a partire da n è necessario conoscere i fattori primi p e q

In pratica, ottenere la chiave privata a partire dalla sola chiave pubblica implica la capacità di fattorizzare n nei suoi fattori primi. Per valori di n sufficientemente grandi, con gli algoritmi di fattorizzazione conosciuti, questa operazione richiede tempi enormi.

Per questo motivo si considera che, con dimensioni di chiave adeguate, l'attacco diretto basato sulla fattorizzazione non sia praticabile.

⚠ Limiti teorici e sviluppi futuri

Nonostante la sua robustezza teorica nell'ambito del calcolo classico, esistono alcuni limiti e considerazioni future legate a RSA.

• algoritmi quantistici, come l'algoritmo di Shor, potrebbero fattorizzare interi grandi in tempi rapidi sfruttando computer quantistici avanzati
• per contrastare questi scenari futuri, la crittografia sta studiando algoritmi detti post-quantistici, basati su problemi matematici diversi dalla fattorizzazione
• anche nel contesto classico, è necessario aggiornare periodicamente dimensioni delle chiavi e implementazioni

Nonostante questi limiti, RSA resta uno degli algoritmi più studiati e compresi e un riferimento fondamentale nella teoria e nella pratica della crittografia.

📌 Conclusioni

L'algoritmo RSA unisce in modo elegante teoria dei numeri e sicurezza informatica. Attraverso numeri primi, aritmetica modulare, funzione phi di Eulero e teorema di Eulero, costruisce un sistema di crittografia a chiave pubblica che permette di:

• proteggere la confidenzialità delle comunicazioni
• realizzare firme digitali e meccanismi di autenticazione
• scambiare chiavi simmetriche in modo sicuro in protocolli più complessi

Comprendere la teoria alla base di RSA significa capire perché la chiave privata non può essere ricavata facilmente dalla chiave pubblica e come concetti matematici profondi possano tradursi in strumenti concreti per la sicurezza dei dati.