Funzioni e funzioni inverse
Se B vuole mandare un messaggio ad A, non deve prima concordare con A quale chiave usare. Deve semplicemente cercare sull’elenco la chiave pubblica di A, e cifrare il messaggio, mediante un opportuno algoritmo di pubblico dominio, con questa chiave. Una volta cifrato, il messaggio può essere decodificato solo da chi conosce la chiave privata, e dunque solo da A. Perché questo sia possibile, è necessario che la funzione ƒ (che codifica il messaggio) e la funzione ƒ−1 (inversa- che lo decodifica) non siano simmetriche: cioè non deve essere possibile ricavare ƒ−1 direttamente da ƒ. Ma se la funzione ƒ è pubblica, non dovrebbe essere difficile a ricavare ƒ−1, soprattutto nell’era dell’ elettronica. Ci si chiede: è possibile implementare un algoritmo per il quale sia quasi impossibile ricavare ƒ−1 da ƒ? Ebbene non è così scontato!
Esempio dell’elenco telefonico
L’esempio dell’elenco telefonico può farci capire che un algoritmo così fatto, esiste. Trovare il numero di telefono di un utente a partire dal nome è immediato (questa è la funzione ƒ); invece trovare il nome di un utente partendo dal suo numero di telefono (la funzione inversa ƒ−1) è praticamente impossibile, perché richiederebbe una quantità di tempo tale da risultare nei fatti impraticabile. Per impossibile si intende che non è praticabile in tempi ragionevoli. E l’esempio dell’elenco telefonico è molto più facile da effettuare rispetto ai numeri primi enormi che vengono generati nella fase di produzione dell’algoritmo.
Fattorizzazione
Come abbiamo visto nell’ articolo sull’introduzione a RSA, l’algoritmo deve soddisfare la proprietà 2, “facile da calcolare” è la moltiplicazione di due numeri primi n e m molto grandi. Oggi l’ordine di grandezza di una certa sicurezza utilizzato per n e m è circa 10300: noti n e m, il prodotto p = nm si calcola immediatamente. La funzione inversa, quella “impossibile da calcolare”, è la fattorizzazione: se un numero p è il prodotto di due numeri primi “grandi”, la sua fattorizzazione richiede di norma tempi superiori all’età dell’universo. Infatti non si conoscono oggi, algoritmi efficaci di fattorizzazione.
Ricerca
È interessante notare, l’enorme sproporzione degli attuali risultati della ricerca matematica avanzata sui due problemi apparentemente analoghi:
1) stabilire se un numero naturale è primo;
2) fattorizzare un numero naturale.
Il primo problema è “facile”, il secondo è “impossibile”.
Il riconoscimento (e quindi la costruzione) di numeri primi grandi non offre oggi particolari difficoltà computazionali. Esistono algoritmi molto efficienti in grado di riconoscere numeri primi anche di migliaia di cifre in pochi decimi di secondo. I più efficienti di essi, per esempio l’algoritmo di Miller-Rabin, oppure l’algoritmo di Solovay-Strassen, sono di tipo probabilistico.
Il più grande numero primo fino ad oggi conosciuto (almeno nel 2006) è il 43° numero di Mersenne (cioè della forma 2p−1): M43 = 2 30 402 457−1.
Si tratta di un numero che ha quasi 10 milioni di cifre. Per quanto riguarda invece la fattorizzazione del prodotto di due numeri primi ( http://mathworld.wolfram.com/news/2005-11-08/rsa-640/ ), è del maggio 2005 il lavoro di un gruppo di ricerca dell’Università di Bonn che, dopo 5 mesi di attività utilizzando 80 CPU da 2.2 GHz connesse in rete, ha portato a fattorizzare RSA-640, un numero di “soltanto” 193 cifre.