Criptosistemi asimmetrici

lezione
Criptosistemi asimmetrici
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Sicurezza nelle reti

Introduzione alla crittografia asimmetricaModifica

Il concetto principale che sta dietro alla crittografia asimmetrica è che esistono alcune operazioni che sono estremamente semplici da fare in una direzione, mentre sono estremamente difficili da fare in senso inverso. Per esempio, dati   e   due numeri primi, è semplicissimo calcolare

 

ma è difficilissimo, trovare   e   a partire dal solo  . Tutta la sicurezza degli algoritmi di cifratura asimmetrici si basa proprio sul presupposto che, per risolvere certi problemi, gli algoritmi usati sono estremamente inefficienti; se un giorno uno di questi problemi dovesse essere risolto con un nuovo algoritmo efficiente, probabilmente tutta la sicurezza della crittografia che si basa su quel problema verrebbe meno.

Gli algoritmi di cifratura asimmetrici sono ordini di grandezza meno efficienti degli algoritmi simmetrici, il che è un problema fondamentale per il mondo moderno, dove si richiede ad una smartcard come può essere la carta regionale dei servizi di fare firme, usando crittografia asimmetrica.

Schema generaleModifica

Abbiamo due figure, Alice e Bob, che vogliono comunicare in maniera segreta, in modo tale che Trudy non sia in grado di interferire tra di loro.

L'idea è che Bob deve scrivere ad Alice e, per far questo, userà una chiave detta chiave pubblica,  . Alice possiede una coppia di chiavi  , di cui una,  , deve essere mantenuta segreta.

Quello che accade è che Bob cifra un messaggio con una delle due chiavi di Alice, la chiave pubblica, dopodiché manda il messaggio ad Alice, la quale dovrà usare la sua chiave privata (segreta) per leggere il messaggio di Bob. Chiunque sia in possesso della chiave pubblica sarà anche in grado di mandare messaggi ad Alice, ma se non si ha la chiave privata non si deve essere in grado di ricevere i messaggi destinati ad Alice.

Alice, a sua volta, potrà usare la sua chiave privata per firmare dei messaggi, così chiunque abbia la sua chiave pubblica sarà in grado di verificare che Alice (e soltanto Alice) può aver firmato quel messaggio.

 

Definiamo   la chiave pubblica di Alice,   la chiave privata e l'insieme   il keypair, la coppia di chiavi personale di Alice. Il messaggio in chiaro è  , il messaggio cifrato è  . L'algoritmo di cifratura asimmetrico è rappresentato da  , mentre l'algoritmo per decifrare è  .

Una delle proprietà fondamentali delle chiavi è che deve essere computazionalmente impossibile ricavare la chiave privata a partire dalla chiave pubblica. Uno dei problemi principali che ancora oggi affligge il mondo della crittografia è la distribuzione delle chiavi: in che modo Bob ha la garanzia di possedere la vera chiave pubblica di Alice, e non per esempio la chiave pubblica di Trudy che gliel'ha data facendo finta di essere Alice? infatti, lo scambio delle chiavi avviene nello stesso luogo (internet) in cui avviene lo scambio dei dati.

Come detto, la crittografia asimmetrica si basa su problemi irrisolti della matematica discreta. Si ha:

  • Logaritmi discreti   Diffie-Hellman, ElGamal e DSS;
  • Fattorizzazione discreta   RSA;

La crittografia asimmetrica si propone di risolvere tre diversi aspetti della comunicazione tra le persone:

  • mantenere la confidenzialità tra due persone; l'algoritmo più usato a tal scopo è RSA. Scopi dei possibili attacchi sono:
  • ottenere il messaggio   partendo da   senza conoscere le chiavi;
  • ottenere la chiave privata a partire dalla chiave pubblica.
  • generare firme digitali; le firme sono utili per l'autenticazione, per la protezione dell'integrità dei dati e per il non ripudio dei messaggi. Per questo scopo si possono usare gli algoritmi RSA, ElGamal e DSS. Lo scopo principale degli attacchi, ovviamente, sarà quello di falsificare le firme.
  • derivare delle chiavi effimere da usare per comunicazioni segrete e non recuperabili; per questo obbiettivo si possono usare Diffie-Hellman ed RSA. Scopi degli attacchi possono essere:
  • Calcolare le chiavi;
  • Inserirsi in mezzo ad una comunicazione, man-in-the-middle.

Ad oggi, nessuno dei problemi su cui si basa la crittografia asimmetrica è mai stato risolto, tuttavia negli ultimi anni una gran quantità di studiosi e di fondi è stata dirottata proprio in questa direzione, dal momento che, con l'avvento dei calcolatori, la crittografia è diventata sempre più importante (quasi essenziale) per la comunicazione tra enti e persone. I risultati di questi sforzi ci sono, come per esempio il test di primalità dei numeri del 2002.

La crittografia è una disciplina molto giovane.

Teoria dei numeriModifica

D'ora in avanti, lavoreremo soltanto con numeri interi in  .


Definizione: Numero primo
Si dice numero primo un numero intero divisibile soltanto per se stesso e per  .



Definizione: Massimo comun divisore
Il massimo comun divisore, o greatest common divisor (gcd) è il più grande numero intero positivo che divide entrambi due numeri   e  , con resto  .


Esempio:
Si ha:
  •  
  •  


Per definizione, vale

 



Definizione: Numeri coprimi
Una coppia di numeri   e   è coprima se
 


Esempio:
I numeri   e   sono coprimi tra loro.



Definizione: Relazione di congruenza
Due numeri   e   sono detti congruenti tra loro in modulo  ,
 

quando vale

 


L'operatore  è quella funzione che restituisce il resto della divisione del numero   per il numero  , che è il più piccolo numero non negativo   tale per cui

 

Il valore   è detto resto. Allora, due numero   e   sono congruenti in modulo   se, divisi per  , danno lo stesso resto; in questo caso,   e   sono detti equivalenti in modulo  .


Esempio:
Si ha:
  •  
  •  

da cui risulta che

 


Nota: a volte useremo come notazione   al posto di   per semplicità.


Proprietà: Proprietà dell'operatore modulo
L'operatore modulo gode delle proprietà che ci si aspetta:
  •  
  •  



Definizione: Moltiplicativo inverso  
Nelle congruenze, il moltiplicativo inverso   del numero   è quel valore tale per cui
 

cioè

 


Per definizione, l'inverso moltiplicativo di un numero   esiste se, e solo se, esistono due valori   e   tali per cui

 

In questo caso,   è l'inverso moltiplicativo di  . Più avanti vedremo che l'inverso moltiplicativo di   esiste se, e solo se,

 

cioè, soltanto quando i due numeri sono primi tra loro.


Teorema:
Si ha
 


Dimostrazione:
L'insieme dei numeri che dividono   divide anche  , dove
  (dalla definizione di  )
  • se un numero   divide sia   che  , allora divide anche  ,
 
  • se   divide sia   che  , allora divide anche  .



Definizione: Algoritmo di Euclide
L'algoritmo di Euclide serve per calcolare il massimo comun divisore di due numeri, applicando ricorsivamente il teorema precedente.



Definizione: Algoritmo di Euclide esteso
Questo algoritmo permette di calcolare
  •  
  •  
  •  

Funzionamento:

  •  
  •  
  •  
  •  

Alla fine dell'algoritmo, se si ottiene  , allora

  •  
  •  



Definizione: L'insieme  
L'insieme   è l'insieme di tutti i numeri  .


Per esempio, si ha

  •  
  •  


Definizione: L'insieme  
L'insieme   è l'insieme di tutti i numeri   che sono anche primi con  .


Ad esempio, si ha:

  •  
  •  

È da notare che il numero   non appartiene a  , perché per definizione vale

 

quindi   e   non sono coprimi.


Proprietà:
Il gruppo   è abeliano, cioè:
  1.  , cioè   contiene anche l'inverso moltiplicativo di   (per definizione);
  2. l'operazione associata al gruppo, la moltiplicazione, è sia associativa che commutativa;
  3. esiste l'elemento neutro, che è l' : si ha  ;
  • l'insieme di definizione è chiuso, cioè  



Teorema:
Un insieme   moltiplicato per un elemento di   stesso è ancora l'insieme di partenza  , soltanto che gli elementi sono stati rimescolati.



Teorema: Teorema del resto cinese
Sia
 

con

 

cioè, i valori   e   sono coprimi tra loro. Allora, la relazione tra   e l'insieme   con

 

e con

 

è una biiezione.


Dimostrazione:
Vogliamo dimostrare che la relazione descritta è una biiezione. La relazione tra   e gli   è iniettiva per costruzione, dal momento che vale
 

Dobbiamo dimostrare che anche la relazione   è iniettiva, cioè, partendo dal singolo valore   si deve poter ottenere il valore di  . Si ha

  •   per definizione;
  •  
  1. l'inverso moltiplicativo di   deve esistere, dal momento che   per costruzione;
  2. vale
  •  
  •  
  •  

A questo punto, la dimostrazione è finita se riusciamo a provare che   è definita in modo tale da garantire

 

Questa proprietà deriva da una proprietà appena vista, cioè

  •  


Questo teorema può essere formulato anche in altri modi.

  • Qualsiasi grande numero   può essere rappresentato da un insieme di numeri più piccoli  
  • La relazione che esiste tra   ed il prodotto cartesiano
 
è una biiezione.


Il teorema del resto cinese è molto utile, perché permette di manipolare grandi numeri   semplicemente lavorando su piccoli numeri  .


Esempio:
Si ha
  •  
  •  
  •  
  •  

Sia  , da cui si hanno gli  

  •  
  •  
  •  

Si hanno gli  ,

  •  
  •  
  •  

Si hanno gli  ,

  •  
  •  
  •  

Si è ottenuto

 

dove

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  



Definizione: La funzione di Eulero  
Si definisce la funzione di Eulero   come quella funzione che, dato un numero  , restituisce la cardinalità dell'insieme dei valori inferiori ad   e primi con  , cioè
 



Teorema:
Sia   un numero primo. Allora, vale
 
cioè, per ogni numero   primo, il numero dei numeri minori di   e primi con   è proprio  , cioè nessun numero inferiore ad   divide   (definizione di numero primo).



Teorema:
Siano   e   due numeri primi, e valga  . Allora vale
 


Dimostrazione:
Si ha
 

I numeri

 

non appartengono all'insieme  , così come anche non vi sono i numeri

 

Allora, si ha

 


Questo teorema è valido anche se   e   sono semplici coprimi, anziché essere numeri primi.



Teorema: Teorema di Eulero
Dato un qualsiasi numero  , vale
 


Dimostrazione:
Sia
 

Dal momento che il gruppo   è un gruppo abeliano, allora esiste l'insieme   delle permutazioni di  ,

 

Si definisce la grandezza

 

Si ottiene, quindi, che

 

da cui si ottiene

 



Corollario:
Per qualsiasi  , per qualsiasi  , vale
 

Infatti, vale

 


Un risultato di tutto questo è l'equazione

 

Nel caso in cui valga   con   e   numeri primi, allora per qualunque   e per qualunque   vale

 


Esempio:
Siano
  •  
  •  
  •  

da cui si ottiene

 

Si definisce  , da cui

 

Si impone   e si ottiene

 
 


Il protocollo Diffie-HellmanModifica

Il protocollo Diffie-Hellman è stato pubblicato nel 1976 a firma di Whitfield Diffie e Martin Hellman, ed è il primo protocollo di cifratura asimmetrica delle storia. A dir la verità, pare che l'United Kingdom communications electronic security group avesse già inventato prima lo stesso meccanismo, ma non pubblicarono i risultati dei loro studi.

L'obbiettivo che si propone il protocollo Diffie-Hellman è quello di impostare una chiave temporanea, detta chiave di sessione K, senza alcun parametro di partenza. L'idea è che si vuole scambiare una chiave, attraverso una rete insicura, senza conoscersi e senza essersi messi d'accordo preventivamente.

L'algoritmo Diffie-Hellman poggia le proprie fondamenta sulla difficoltà con cui si riesce a calcolare un logaritmo discreto; infatti, calcolare il valore

 

è facile, ma nessuno è ancora stato in grado di individuare un metodo semplice per ricavare   a partire da  ,   e  .

 

Ipotizzando che sia Alice a iniziare il protocollo, Alice sceglie

  • un numero   primo;
  • un numero   che sia generatore dello spazio  , cioè
 
  •  , un numero casuale compreso in  

Una volta scelti questi tre numeri, trasmette

  •  
  •  
  •  

Bob, ricevuti questi numeri, sceglie a sua volta un numero casuale   e manda ad Alice il numero  . Giunti a questo punto, Alice che Bob saranno in grado di calcolare rispettivamente

  •  
  •  

Questo tipo di protocollo, di per sé, è in grado di proteggere in maniera efficace uno scambio di chiavi  ; anche se un attaccante vede passare i numeri   e  , infatti, non riuscirà ad usarli per calcolare il valore giusto della chiave. Questo protocollo, comunque, diventa molto più sicuro se il numero primo   è anche un primo sicuro, cioè se il numero

 

è a sua volta primo.

Il protocollo Diffie-Hellman diventa completamente insicuro se Trudy diventa, da semplice osservatore, un attaccante attivo: se è in grado di diventare man-in-the-middle, Alice e Bob deriveranno delle chiavi (anche diverse) con Trudy invece che tra di loro, senza aver alcuno strumento per accorgersene. Si deduce che il protocollo Diffie-Hellman non può essere usato se non viene affiancato da altri strumenti di autenticazione.

Infine, bisogna considerare il fatto che calcolare   e   è un compito oneroso.

Il protocollo RSAModifica

Il protocollo RSA è il più vecchio protocollo asimmetrico ancora in funzione, inventato nel 1977 pubblicato l'anno successivo. Come per il protocollo Diffie-Hellman, anche questo fu inventato già nel 1973 dall'United Kingdom communications electronic security group, ma venne tenuto segreto.

Gli scopi di questo protocollo sono la confidenzialità dei dati, le firme digitali e la creazione di chiavi effimere per comunicazioni che non devono essere recuperabili, una volta dimenticate le chiavi.

RSA si basa sul teorema di Eulero, dove:

  •  ,   sono numeri primi da più di 512 bit, generati casualmente
  •  
  •  
  •   è un numero coprimo con  
  •   è il numero moltiplicativo inverso di  , cioè
 
  •   è la chiave privata
  •   è la chiave pubblica

I parametri privati, quindi, saranno  ,  ,  ,   e la chiave privata  , mentre i parametri pubblici saranno   e  , cioè la chiave pubblica  .

ConfidenzialitàModifica

Il testo cifrato si ottiene con l'equazione

 

da cui, attraverso il teorema di Eulero, si può riottenere il messaggio originale facendo

 

Tutto questo, però, è valido soltanto se il messaggio   è più piccolo di  , da cui si evince che è necessario imporre

 

dove   è il numero di bit del blocco del messaggio.

Qui si presenta il fondamentale problema della distribuzione delle chiavi: Alice manda a Bob la sua chiave pubblica, ma come può Bob autenticare la chiave pubblica che ha ricevuto, per esser sicuro che sia davvero la chiave pubblica di Alice? Se la chiave pubblica è sbagliata, Bob cifrerà un messaggio che potrà leggere soltanto Trudy, invece che Alice.

Firma digitaleModifica

È lo stesso principio che porta alla confidenzialità, soltanto che è usato al contrario: Alice usa la sua chiave privata per cifrare un testo (che non può essere più lungo di   bit) e tutti coloro che hanno la possibilità di recuperare la sua chiave pubblica saranno in grado di decifrare il testo, con la garanzia che può esser stata soltanto Alice a cifrare tutto. Quello che accade è che si va a firmare il digest del messaggio, calcolato con un qualche algoritmo MDC; in questo caso, Alice manderà a Bob la coppia

 

In questo caso, il messaggio è firmato, ma non viene mandato cifrato. Si noti l'importanza che assume, a questo punto, l'algoritmo MDC: se trovo un altro messaggio   che abbia lo stesso digest del messaggio originale, potrò affermare che Alice ha firmato il secondo messaggio, oltre al primo.

È importante notare come la firma digitale introduca il concetto di non ripudio del dato: infatti, chi verifica l'autenticità della firma non ha bisogno della chiave privata: si garantisce che soltanto Alice è in possesso dei bit necessari per generare quella particolare firma.

Impostazione di chiavi effimereModifica

Vogliamo generare delle chiavi effimere; sia Alice che Bob hanno, ovviamente, la chiave pubblica di Alice. A questo punto, Bob sceglierà un numero casuale   e manderà ad Alice il valore

 

da cui Alice sarà in grado di ricavare

 

ma l'osservatore esterno, senza conoscere il valore  , non potrà ricavare il valore di   che potrà essere usato, a questo punto, come chiave effimera per cifrare con un qualsiasi algoritmo simmetrico, per esempio DES.

La cifratura delle sessioni viene fatta attraverso chiavi effimere per due motivi fondamentali:

  • una volta che entrambi hanno dimenticato  , tutta la sessione cifrata, anche se registrata, non sarà recuperabile nemmeno entrando in possesso delle chiavi pubblica e privata.
  • la cifratura simmetrica è molto meno impegnativa, dal punto di vista computazionale: i tempi di attesa prima della trasmissione dei dati si accorciano, ed i calcolatori possono essere meno potenti.

Ad oggi, RSA è usato semplicemente per stringhe di bit corte, attorno a 200 bit. Questo perché:

  • è estremamente inefficiente dal punto di vista computazionale;
  • può essere usato soltanto con le modalità ECB e CBC.

I parametri   e  Modifica

Perché RSA sia sicuro,   deve essere il più grande possibile. Una dimensione minima di   può essere compresa tra i 512 e i 1024 bit, che significa un numero attorno alle 150 cifre decimali; questo significa che anche   ed   devono essere adeguatamente grandi.

  e   sono dei numeri primi che devono essere sufficientemente grandi, in modo tale da generare un   grande. Il problema è che devono essere due numeri scelti casualmente: l'algoritmo migliore, ad oggi, è:

  • scegliere un numero sufficientemente grande;
  • verificare se è un numero primo; se no, ricominciare.

Questo meccanismo, che è il migliore, è molto inefficiente: non possiamo far altro che sperare che, prima o poi, il generatore di numeri casuali ci restituisca un numero primo. La probabilità che un numero   sia primo è pari a

 

il che significa che, se   è di 512 bit, la probabilità che   sia primo è attorno a  , cioè lo  .

Test di primalitàModifica

Come detto,   e   devono essere due numeri primi. Per verificarlo, possiamo usare seguente teorema:


Teorema: Piccolo teorema di Fermat
Dato un numero primo  , allora è verificato che, per qualsiasi numero  , vale
 


C'è un problema, però: la stessa equazione è verificata, con   di 100 cifre digitali non primo, con probabilità  : quindi, esiste una probabilità, anche se piccola, che il numero scelto con questo criterio non sia comunque primo. Anche i numeri di Carmichael soddisfano il piccolo teorema di Fermat, senza però essere numeri primi. Esistono altri test di primalità, tutti non deterministici, che permettono di ridurre la probabilità di errore, come il test di Miller-Rabin.

Nel 2002, alcuni ricercatori indiani hanno pubblicato un test deterministico per verificare la primalità dei numeri, ma è di elevata complessità (polinomiale).

La chiave pubblica  Modifica

Il valore di  , di solito, è una costante. Si può scegliere

  •  
  •  
  •  

Scegliere un numero piccolo per   porta con sé dei vantaggi:

  • la cifratura e la validazione delle firme diventa più performante per numeri grandi;
  •   deve essere un numero coprimo con  ; dal momento che già trovare   e   è difficile, è utile avere un numero piccolo per verificare la coprimalità.

Scegliere  , però, comporta due problemi da tenere presente.

  • Se il messaggio da cifrare è
 
allora accadrà che
 
quindi, per ritrovare il testo originale basterà calcolare la radice cubica del testo cifrato,
 
Questo fatto è molto comune per il testo, quindi nelle implementazioni di RSA è fondamentale che venga aggiunto, in automatico, del testo di padding in modo tale da rendere il messaggio adatto alla cifratura.
  • Supponiamo che Alice mandi lo stesso testo   cifrato con tre chiavi pubbliche diverse, cioè mandi i cifrati  ,   e  . Trudy ha la possibilità di intercettare
  •  
  •  
  •  

che sono i tre messaggi cifrati. Usando il teorema del resto cinese, si può calcolare

 
Questo numero sarà esattamente  , se è verificata le ipotesi
  •  
  •  

Generare le chiavi pubblica e privataModifica

Cerchiamo un metodo per generare questo paio di chiavi.

1. scegliere  , per esempio prendendolo  ;
2. generare un numero dispari   casuale, con dimensione maggiore di 512 bit; si impone poi  , in modo tale che   sia coprimo con  .
3. verificare che   è un numero primo
  • controllo che i primi 100 numeri primi non dividano  ;
  • faccio un controllo di primalità non deterministico, oppure deterministico se voglio la sicurezza assoluta della bontà della chiave;
  • se il test di primalità fallisce, si torna al secondo punto.
4. si impone  ;
5. si ripetono i punti dal 2. in avanti, in modo da ricavare anche un numero primo  ;
6. si calcolano i valori derivati da   e  ,
  •  
  •  
7. si usa il teorema di Euclide per calcolare il valore  ;
8. si etichettano
  •  
  •  

Attacchi al protocolloModifica

Nonostante esista da circa 30 anni, all'interno di RSA non sono mai stati trovati dei bug importanti,

Calcolo della chiave privataModifica

Il metodo più semplice è la ricerca esaustiva in tutto lo spazio delle  . Per risolvere i problemi legati a questo attacco, bisogna scegliere un numero   il più grande possibile; il problema è che, scegliendo   grande, la velocità dell'algoritmo diminuisce.

L'attaccante potrebbe cercare di fattorizzare  , ma questo tipo di attacco, ad oggi, è improponibile: con la potenza computazionale moderna, servirebbero migliaia di anni per fattorizzare un numero più grande di 150 cifre decimali. Non è dimostrato, però, che sia necessario fattorizzare   per calcolare il valore corretto di  .

Per semplificare, si potrebbe cercare di calcolare  , ma è matematicamente dimostrato che la difficoltà computazionale è la stessa che serve per fattorizzare  .

Nonostante queste difficoltà, se si prevede di usare una chiave per molto tempo, come accade spesso, conviene portarsi su lunghezze di   di almeno 1024 bit, dal momento che la potenza computazionale aumenta e, come dimostrato dalle recenti tecniche inventate per fattorizzare i numeri, la ricerca è aperta e i risultati, prima o poi, potrebbero arrivare.

Confronto del testoModifica

Una possibile falla nella sicurezza deriva dal messaggio che si sta proteggendo. Se il messaggio   può assumere soltanto pochi valori finito, Trudy potrebbe cifrare le possibili stringhe con la chiave pubblica di Alice e, una volta ottenuto il cifrato, confrontarlo con ciò che transita nel canale. Questo tipo di attacco è possibile con pressoché tutti gli algoritmi, quindi è bene tenerlo sempre in considerazione.

La soluzione più semplice è quella di inserire, in coda al messaggio, un pattern casuale di dati in modo tale da rendere il messaggio più lungo.

Smooth numbersModifica

Gli smooth numbers sono dei numeri prodotto di pochi e piccoli numeri primi. Definiamo la firma RSA di Alice sul messaggio   come la grandezza

 

Allora, a partire dalla firma  , Trudy può calcolare la firma di Alice anche sul messaggio  . Allo stesso modo, con due firme   e  , Trudy può calcolare le firme dei messaggi

  •  
  •  

e tutti i composti di questi messaggi. Se Trudy riesce a collezionare tutta una serie di firme di Alice che, composte tra di loro con moltiplicazioni e divisioni, danno come risultato un numero primo, allora sarà in grado di calcolare la firma corretta di Alice per qualsiasi numero che abbia quel numero primo come fattore. Ovviamente, al crescere delle osservazioni, Trudy sarà in grado di calcolare un numero sempre maggiore di numeri primi con cui comporre i suoi messaggi.

Se ne deduce che, al crescere delle osservazioni, la sicurezza con cui i messaggi vengono firmati decresce, esponendo sempre di più Alice al rischio di falsificazione della firma. Per prevenire questo problema, il PKCS (l'insieme di standard che riguardano la crittografia asimmetrica) prevede che si aggiungano sempre, in coda ai messaggi, delle stringhe casuali, per prevenire la possibilità che venga firmato uno smooth number.

Osservazioni temporali, o timing attackModifica

Si tratta di un attacco che nessuno si aspetterebbe e che nessuno si aspettava, quando fu standardizzato il protocollo. Si tratta, di fatto, di analizzare quanto tempo ci mette un algoritmo a decifrare una firma. Esiste, infatti, una stretta correlazione tra la chiave privata e la difficoltà computazionale richiesta per cifratura e decifratura: basta osservare quanto tempo serve ad un algoritmo per decifrare un messaggio (con la chiave pubblica) per avere alcune informazioni sulla chiave privata.

Per ovviare a questo problema, le implementazioni commerciali di RSA, ad oggi, inseriscono delle attese casuali nel software, in modo da annullare la correlazione tra la firma ed il tempo necessario per decifrare i messaggi.

Attacco attivoModifica

L'unico attacco attivo che si può pensare è il man-in-the-middle, cioè c'è la possibilità che Trudy si inserisca nelle comunicazioni tra Alice e Bob nel momento dello scambio delle chiavi pubbliche: questo accade perché le chiavi, di per sé, non sono autenticate.

Public Key Cryptograpy StandardModifica

Il PKCS è un insieme di regole standard della RSADSI, la RSA Data Security Inc., su come si devono usare gli algoritmi di cifratura asimmetrici, allo scopo di migliorare la loro sicurezza. Vengono definite le modalità con cui si deve:

  • codificare le chiavi pubbliche e private;
  • codificare una firma digitale;
  • inserire del padding per i messaggi corti;
  • cifrare i messaggi.

Lo scopo del PKCS è fornire una serie di regole che massimizzino la sicurezza dell'algoritmo RSA, per minimizzare la probabilità che gli attacchi abbiano successo. La sicurezza dell'algoritmo RSA, che di per sé è ottimo, dipende moltissimo dall'applicazione di queste regole.

Digital Signature StandardModifica

Il DSS è uno standard di cifratura standardizzato dal NIST americano, ed approvato dall'NSA, quindi si presume che possano esistere delle backdoor ignote, esattamente come per l'algoritmo DES.

Il DSS è un protocollo che ha lo scopo di permettere la firma dei documenti; trova le sue fondamenta matematiche su ElGamal, invece che su RSA. Questo tipo di firma digitale, al contrario di RSA, è libera dai brevetti software e, quindi, liberamente utilizzabile in tutto il mondo; al contrario, con RSA, per le aziende che risiedono nelle nazioni che prevedono i brevetti software (come gli USA, ma non l'EU), sarebbe stato necessario acquistare delle licenze. Dal 2000, comunque, il brevetto su RSA è decaduto, quindi si possono usare sia RSA che ElGamal senza dover acquistare licenze di utilizzo.

È dimostrato che, con un calcolatore da 25 milioni di dollari, una firma DSS può essere falsificata in meno di un anno; questo perché la chiave è forzata ad essere di 512 bit, troppo poco. Si tratta, inoltre, di un protocollo molto giovane, quindi molto meno crittanalizzato del suo predecessore RSA.

DSS è stato pensato per le smart card: generare una firma, infatti, è un'operazione che richiede poche risorse; al contrario, la verifica delle firme è più computazionalmente impegnativo.

Elliptic Curve CryptographyModifica

L'algoritmo ECC è un'evoluzione degli algoritmi a chiave asimmetrica.

Gli algoritmi standard, come RSA, DH e DSS, sono basati su una classe di problemi per cui esistono delle soluzioni che prevedono algoritmi di complessità inferiore all'esponenziale; non solo, ma questa complessità, nel tempo, sta scendendo e ci si può aspettare che continui a scendere.

Al contrario, l'algoritmo ECC si basa su problemi le cui soluzioni non prevedono ancora algoritmi con complessità sotto l'esponenziale, quindi ci si può permettere di avere delle chiavi più corte; in particolare, ad oggi, ECC è in grado di fornire la stessa sicurezza di RSA, ma con una chiave 10 volte più piccola.

Utilizzi degli algoritmi asimmetriciModifica

Come già detto per RSA, tutti gli algoritmi asimmetrici possono essere usati soltanto nelle configurazione ECB o CBC, ma non possono essere usati come OFB, CFB o CTR; questo perché i primi due metodi di utilizzo prevedono di usare una funzione diretta   ed una funzione inversa  , mentre per gli altri tre metodi si utilizza sempre la stessa funzione in senso diretto, quindi sarebbe necessario fornire a tutti la chiave privata del mittente dei messaggi.

In generale, è meglio non usare gli algoritmi asimmetrici per cifrare dati che vadano oltre la dimensione  , dal momento che tendono a fornire informazioni utili a Trudy per rompere i protocolli. Infatti, quello che accade di solito è che si usano gli algoritmi asimmetrici per proteggere una chiave simmetrica, eventualmente temporanea, usata per cifrare i dati.

Altri progetti