Crittografia

Moltiplicare è facile fattorizzare è difficile

L'algoritmo RSA si basa su una constatazione facile da verificare con un computer e un software di matematica:

• L'operazione di moltiplicazione fra due numeri primi p e q molto grandi si esegue in pochi secondi con un computer.

• L'operazione inversa la fattorizzazione del prodotto dei due numeri primi molto grandi (p⋅q) richiede un tempo che non è ragionevole anche con un computer.

Ad esempio, è semplice fattorizzare il numero 91 controllando se è divisibile per 3 oppure per 5 oppure per 7 e verificare che è uguale al prodotto 7⋅13, diventa un pò più complicato se il numero è 32712247 perchè prima di stabilire che è divisibile per il numero primo 4817 bisogna controllare che non è divisibile per tutti i numeri primi minori di 4817 che sono 643, se poi il numero da fattorizzare ha diverse centinaia di cifre diventa umanamente impossibile.

Il cifrario RSA utilizza proprio il prodotto di due numeri primi molto grandi come chiave pubblica. Attualmente l'algoritmo RSA utilizza numeri primi di 300 cifre e il loro prodotto è un numero con 600 cifre e per operare con numeri cosí grandi è necessario utilizzare computer e particolari programmi. Per dimostrare l'affidabilità di questo sistema di scrittura segreta nel 1994 gli autori dell'algoritmo RSA offrirono un compenso di 100 dollari alla prima persona in grado di decifrare un messaggio cifrato ottenuto con una chiave pubblica di 129 cifre derivante dal prodotto di due numeri primi di 64 e 65 cifre. La sfida fu accettata da un gruppo internazionale costituito da 600 persone che lavorarono con 1600 computer connessi in rete utilizzando il miglior algoritmo di fattorizzazione a disposizione in quel momento. La sfida fu vinta dopo 8 mesi di intenso lavoro. Ora riflettiamo. E' opportuno affidare informazioni segrete importantissime a un metodo di cifratura che si basa solo sulla attuale lentezza dei computer? Bisogna tener presente che la capacità dei computer di eseguire un numero elevato di calcoli aumenta di anno in anno e che si possono scoprire algoritmi di fattorizzazione più efficiente tali da ridurre notevolmente il tempo necessario per scomporre il prodotto p⋅q. E' stato accertato che i tempi di fattorizzazione crescono esponenzialmente rispetto alla lunghezza di p⋅q e quindi aumentando il numero delle cifre della chiave pubblica aumenta esponenzialmente anche il livello di sicurezza del sistema in grado di garantire una elevata protezione. I numeri primi sono infiniti e fortunatamente per il sistema RSA, costruire un numero primo molto grande è facile perchè esistono algoritmi molto efficaci in grado sia di generare numeri primi molto grandi sia di riconoscere se un numero con miglia di cifre è primo o composto in pochi secondi. Il più grande numero primo che si conosce (21 dicembre 2018) ha più di 24 milioni di cifre decimali.

Per questo motivo il cifrario RSA è il sistema più usato al mondo.

Gli oggetti matematici che vengono utilizzati nell'algoritmo RSA sono due: l'aritmetica modulare spesso detta l'aritmetica dell'orologio e il piccolo teorema di Fermat. Nel prossimo paragrafo vedremo brevemente questi due argomenti.