Crittografia asimmetrica

Cosa è RSA?

Dopo circa due anni dall' uscita dell'innovativo Diffie-Hellman emerse il primo crittosistema a public-key o asimmetrica, RSA. Oltre ad essere il primo crittosistema di questo genere, rimane ancora oggi il sistema public-key più implementato in assoluto. Prende il nome dai suoi inventori: Ron Rivest, Adi Shamir e Leonard Adleman.
Come già detto, essendo un crittosistema asimmetrico, la chiave con cui viene criptato il messaggio è differente da quella con cui viene decriptato in ricezione. Allora la chiave K sarà formata da Kp, pubblica, e Ks, segreta; le due chiavi possono essere ricavate l'una dall'altra, ma il punto di forza su cui si basa RSA è che l'operazione di derivare la chiave segreta da quella pubblica è troppo complessa per venire eseguita in pratica, anche su un calcolatore molto potente.
In questo tipo di cifrari hanno grande importanza le cosidette funzioni unidirezionali: si tratta di funzioni invertibili tali che il calcolo della funzione diretta sia facile, mentre quello della inversa sia difficile per tutti coloro che non sono in possesso della chiave corretta. Un esempio di tale funzione è il logaritmo in base B dove l'inverso è appunto l'esponenziale. Se la base B è un numero ragionevolmente piccolo, il calcolo sia della funzione diretta che della inversa non risulta particolarmente difficile; diversa sarebbe la situazione se il modulo o base fosse un numero primo enorme, poiché la complessità di calcolo sarebbe a dir poco proibitiva.
La funzione unidirezionale che sta alla base di RSA viene costruita sfruttando il fatto che è facile calcolare il prodotto di due numeri primi molto grandi, ma dato il loro prodotto, è oltremodo difficile risalire ai fattori che lo compongono.
Indichiamo i passaggi del cifrario:

R=(C^D)moduloPQ

La chiave pubblica è composta da due parti: il modulo N ed E mentre quella privata da N e D, perciò E è definito l'esponente pubblico e D quello privato.
Si può pubblicare la chiave pubblica liberamente perché non si conoscono metodi per calcolare D, P e Q dati N=PQ ed E.
Mostriamo, di seguito, un esempio chiarificatore, assumendo dapprima dei valori piccoli:

• consideriamo P=5 e Q=3, perciò N=15;
• prendiamo E=5, ottenendo quindi D=5;
• il metodo non funziona perché elevando un numero alla quinta potenza ed eseguendo modulo 15, si ottiene come risultato il numero stesso.

• scelto N=33, avremo Q=11 e P=3;
• prendendo E=3 otteniamo D=7 infatti:
  (P-1)(Q-1)=20 perciò 1modulo20=21=DE;
• eleviamo alla terza potenza i numeri da 0-8 ed eseguiamo modulo 33:

        plain-text     cipher-text
  
          0  _____________   0                                                                      
          1  _____________   1                                                                 
          2  _____________   8
          3  _____________   27
          4  _____________   31  
          5  _____________   26
          6  _____________   18
          7  _____________   13
          8  _____________   17
  
  

  (per esempio: 4^3=64, 64 modulo 33 è uguale a 31)
• per verificare che effettivamente questo cifrario funziona decriptiamo i valori ottenuti al passo precedente: in particolare eleviamo alla settima ed eseguiamo modulo 33.

        cipher-text     plain-text
  
          0   _____________   0                                                                      
          1   _____________   1                                                                 
          8   _____________   2
          27  _____________   3
          31  _____________   4  
          26  _____________   5
          18  _____________   6
          13  _____________   7
          17  _____________   8
  
  

  (per esempio: consideriamo 13^7=62748517, questo valore modulo 33 mi fornisce il valore 7 che volevamo)

Crittografia asimmetrica

Come scegliere la dimensione della chiave in RSA?

Ricordiamo che la chiave in RSA è costituita da un modulo e un esponente, quindi, quando parliamo di dimensione della chiave, intendiamo quella del modulo N.
La scelta della dimensione di N dipende dal bisogno di sicurezza. Più lungo è il modulo, maggiore è la sicurezza ma anche più lente sono le operazioni di cifratura.
Infatti raddoppiando la lunghezza della chiave si incrementa il numero di operazioni necessarie per la cifratura/decifratura con public-key di un fattore 4, e quelle eseguite con secret-key di un fattore 8. La ragione per cui la cifratura/decifratura con public-key richiede meno operazioni è che l'esponente pubblico E puó rimanere fisso anche se aumenta il modulo. Diversamente l'esponente segreto D deve incrementarsi proporzionalmente ad N.
Si dovrà allora trovare un compromesso determinato su considerazioni riguardanti: l'importanza dei dati da proteggere, e quindi la necessità di sicurezza, ed una valutazione di quanto potrebbe essere astuto colui che volesse attaccare il cifrario (hacker).
Rivest stima che un modulo di 512 bits può essere fattorizzato con strumenti sofisticati di un valore circa di 8 milioni di dollari, meno nel futuro. Potrebbe perciò essere consigliabile usare un modulo più lungo per es. di 768 bits o ancora maggiore (1024 bits) se i dati da trasmettere sono di estrema importanza.
Generalmente se la chiave è lunga 512 bits ogni fattore primo P e Q deve essere circa 256 bits.

Crittografia asimmetrica

Privacy

Vediamo come utilizzare questo algoritmo per la "privacy" degli utenti di una rete.
Supponiamo che Alice voglia inviare un messaggio M a Bob. Alice crea il testo cifrato C=(M^E)moduloN dove E ed N costituiscono la chiave pubblica di Bob. Per decifrare, Bob calcola M=(C^D)moduloN con la sua chiave privata <N, D>, ottenendo così il messaggio originale.

Crittografia asimmetrica

Autenticazione

Allo scopo di autenticare un certo messaggio, che verrà trasmesso su una rete di dubbia sicurezza, si può sfruttare tale algoritmo, mostriamo un esempio di tale applicazione. Mettiamo che Alice voglia inviare un documento firmato a Bob, M. Ella crea una firma digitale S con questa operazione: S=(M^D)moduloN dove <N, D> è la sua chiave privata. Bob riceve tale messaggio e vuole verificare se davvero è stata Alice a scriverlo: quindi calcola (S^E)moduloN (con <N, E> chiave pubblica di Alice), se il testo ottenuto è chiaro Bob potrà essere sicuro del mittente.
Ovviamente autenticazione e privacy vengono usate contemporaneamente, cioè una volta verificato che il messaggio è stato inviato da Alice, cosa che tutti potranno fare dal momento che la chiave è pubblica, solo Bob potrà leggere il documento, dato che sarà l'unico a possedere la chiave segreta con cui decifrarlo.

Crittografia asimmetrica

Perché usare RSA rispetto a DES?

RSA non è una alternativa a DES ma un supporto, infatti RSA permette due importanti funzioni a cui non provvede DES:

1. lo scambio sicuro della chiave segreta;
2. la firma digitale.

Crittografia asimmetrica

Quanto è sicuro RSA?

La rottura di RSA si potrebbe verificare nel caso in cui un attacker scopra la chiave privata corrispondente a quella pubblica; questo permetterebbe agli hacker di leggere tutti i messaggi cifrati con la chiave pubblica e contraffare la firma. Ovviamente per determinare la chiave segreta D l' hacker dovrebbe fattorizzare il modulo N nei due termini P e Q e conoscere l'esponente E.
La fattorizzazione è un'operazione estremamente difficile soprattutto se i numeri coinvolti sono molto grandi.
Per valutare quanto sia laborioso trovare una soluzione a tale problema fu lanciata una sfida, nel 1977, ad un gruppo di volontari che avrebbero dovuto scomporre in fattori primi il numero conosciuto come RSA-129 (di 129 cifre). La sfida rimase priva di risposta fino al 1993 quando Graff, Athins, Leyland e Lenstra decisero di prendere la cosa sul serio.
Furono coinvolte 600 persone e 1600 computer in 25 paesi diversi, che sfruttarono l'implementazione detta "Multiple Polynomial Quadratic Sieve". Dopo circa 8 mesi, il gruppo di volontari riuscì a portare a termine il lavoro, determinando i fattori di RSA-129 oltre 390.000 milioni di anni prima del previsto.
Questo esercizio fatto su RSA-129 dimostra che un modulo di 129 cifre può essere scomposto anche se con forze enormi, per cui data la continua crescita tecnologica dei sistemi di computer e il loro calo nel prezzo bisogna pensare ad un modulo di almeno 1024 cifre per essere sicuri di una protezione a lungo termine.
Un'altra tecnica di rottura di RSA è di determinare M direttamente dall'equazione (M^E)moduloN in modo da scoprire il messaggio criptato e contraffare la firma. Nessun attacco di questo tipo è però conosciuto.
Esistono, inoltre, altri metodi che mirano alla scoperta di un singolo messaggio per esempio un semplice messaggio tipo «Attacker at dawn» (attacco all'alba) potrebbe essere decifrato da un hacker anche senza l'aiuto della chiave segreta, oppure, uno stesso testo inviato a più persone ne favorirebbe la decodifica.
Comunque spesso questi attacchi mirano più a rendere insicuro un crittosistema che a violarlo effettivamente.

Crittografia asimmetrica

L'esportazione di RSA

RSA, pubblicato nel 1983, è custodito da PKP (Public Key Patners) e patentato fino al 2000.
In Nord America si deve fare richiesta di licenza per usare o vendere RSA, al di fuori invece non ne è concesso l'utilizzo. Ma se un venditore di software, autorizzato all'uso di critttosistemi a public-key, incorpora RSA in un prodotto commerciale, colui che compra il prodotto finito ha diritto legale di usare RSA. Il governo degli Stati Uniti può usare questo algoritmo senza una licenza dal momento che ha partecipato alla sua creazione.
Comunque PKP permette un libero uso, "non commerciale", di RSA con autorizzazioni scritte per ragioni personali, accademiche o intellettuali.
L'esportazione di RSA rispetta la leggi degli Stati Uniti come tutti gli altri prodotti crittografici. Esportare RSA, per scopi di autenticazione, è permesso indipendentemente dalla lunghezza della chiave benché l'esportatore debba dimostrare che il prodotto non può essere facilmente convertito ad un uso di crittazione. Nel caso che RSA venga usato per la privacy il governo USA non permette l'esportazione se la chiave eccede i 512 bits.
RSA è trovato nelle proposte di Internet come standard PEM e PKCS.

Bibliografia e sorgenti d'informazione

Explore the TELEMAT Site !!!

Ultimo aggiornamento: 24/1/97