Algoritmi a chiave pubblica

Il problema principale con gli algoritmi simmetrici non risiede nella loro sicurezza, ma nello scambio della chiave. Una volta che il mittente ed il destinatario si sono scambiati la chiave, quella chiave può essere usata per comunicare in sicurezza. Ma quale canale sicuro è stato utilizzato per comunicare la chiave stessa? In particolare sarebbe probabilmente più semplice per un malintenzionato cercare di intercettare la chiave piuttosto che provare tutte le chiavi possibili dello spazio di chiavi. Un altro problema consiste nel numero di chiavi necessarie. Se ci sono n persone che vogliono comunicare privatamente fra loro, allora servono n(n-1)/2 chiavi per ogni coppia di persone. Ciò può andar bene per una ristretta cerchia di persone, ma il numero diventa rapidamente enorme per un gruppo largo.

Gli algoritmi a chiave pubblica furono inventati per aggirare completamente il problema dello scambio di chiavi. Un algoritmo a chiave pubblica utilizza una coppia di chiavi per spedire messaggi, entrambi appartenenti alla persona che riceve il messaggio. Una chiave è detta chiave pubblica e può essere data a chiunque. L'altra chiave è detta chiave privata e viene mantenuta segreta dal suo possessore. Il mittente cifra un messaggio usando la chiave pubblica e, una volta criptato, il messaggio può essere decifrato solo con la chiave privata.

Questo protocollo risolve il problema dello scambio di chiavi intrinseco agli algoritmi simmetrici. Non c'è bisogno che mittente e destinatario si mettano d'accordo su una chiave comune. Tutto ciò che serve è che, qualche tempo prima della effettiva comunicazione segreta, il mittente entri in possesso di una copia della chiave pubblica del destinatario. Inoltre una sola chiave pubblica può essere utilizzata da chiunque desideri comunicare con il destinatario. Così solo n coppie di chiavi sono sufficienti a permettere ad n persone di comunicare segretamente una con l'altra.

Gli algoritmi a chiave pubblica sono basati sulle funzioni a difficilmente invertibili con trapdoor[1] o, più brevemente, funzioni trapdoor. Una funzione difficilmente invertibile è una funzione facile da computare, ma la cui inversa è di difficile calcolo. Per esempio, è facile moltiplicare assieme due numeri primi per ottenere un numero composto, ma è difficile fattorizzare un numero composto nelle sue componenti prime. Una funzione trapdoor è simile, ma possiede una scappatoia: se si conosce una parte dell'informazione, diventa facile calcolarne l'inversa. Per esempio, se si considera un numero composto da due fattori primi, allora, conoscendo uno dei due fattori, risulta facile calcolare l'altro. Dato un algoritmo a chiave pubblica basato sulla fattorizzazione in numeri primi, la chiave pubblica contiene un numero composto formato da due fattori primi elevati e l'algoritmo di cifratura usa questo numero composto per criptare il messaggio. L'algoritmo per decriptare il messaggio richiede la conoscenza dei due fattori primi. Così, possedendo la chiave privata che contiene uno dei due fattori, è facile decifrare il messaggio, mentre è estremamente difficile se non si conosce la chiave privata.

Così come accade per gli algoritmi simmetrici, anche per gli algoritmi a chiave pubblica tutta la sicurezza risiede nella chiave. Perciò la dimensione della chiave è una misura della sicurezza del sistema, anche se non è possibile paragonare la dimensione della chiave di un algoritmo simmetrico con quella di di un algoritmo a chiave pubblica per misurare il loro grado di sicurezza. In un attacco a forza bruta contro un algoritmo simmetrico con una chiave da 80 bit, un malintenzionato deve contare al massimo 2⁸⁰ chiavi per trovare quella giusta. In un attacco a forza bruta contro un algoritmo a chiave pubblica con una dimensione della chiave pari a 512 bit, lo stesso malintenzionato deve fattorizzare un numero composto codificato in 512 bit (fino a 155 cifre decimali). Il carico di lavoro per il malintenzionato è fondamentalmente differente a seconda dell'algoritmo che viene attaccato. Mentre 128 bit sono sufficienti per un algoritmo simmetrico, data la tecnologia odierna di fattorizzazione, sono raccomandate chiavi da 1024 bit per la maggior parte degli scopi.