CRYPTHAT - Cifratura RSA

Cifratura RSA

Nov 27, 2014. | Da: Guglielmetti Kevin

Concetti Generali

RSA (dal nome degli inventori) è una tecnica di crittografia asimmetrica utilizzata per cifrare informazioni.

Ogni utente avrà una chiave pubblica e una chiave privata. La chiave pubblica sarà distribuita ai possibili destinatari delle informazioni mentre la chiave privata sarà tenuta segreta. Il messaggio verrà cifrato con la chiave privata e soltanto chi possiede la chiave pubblica relazionata con quella privata potrà decodificare il messaggio. In questo modo si garantisce l' integrità del mittente o la segretezza del messaggio.
RSA non è adatto alla trasmissione di grandi quantità di dati; per questo servirà solo per codificare la chiave simmetrica (una sola chiave a 128bit) utilizzata per criptare/decriptare il messaggio.

Funzionamento ed Implementazione

RSA è basato sull'elevata complessità computazionale della fattorizzazione in numeri primi.
La generazione delle chiavi avviene seguendo questi passaggi:

Si scelgono a caso due numeri primi, p e q abbastanza grandi da garantire la sicurezza dell'algoritmo (ad esempio di 150 cifre).
Si calcolano il loro prodotto n = pq, chiamato modulo e la PHY(n) ovvero per i numeri primi (p-1)*(q-1).
Si considera che la fattorizzazione di n è segreta e solo chi sceglie i due numeri primi, p e q, la conosce.
Si sceglie poi un numero e (chiamato esponente pubblico), coprimo (primi tra di loro) con PHY(n) e più piccolo di PHY(n).
Si calcola il numero d (chiamato esponente privato) tale che il suo prodotto con e sia congruo ad 1 modulo(PHY(n)) ovvero che e*d è congruente ad 1modulo(PHY(n)).

La forza dell'algoritmo sta nel fatto che per calcolare d da e o viceversa, non basta la conoscenza di n, ma serve il numero PHY(n) e che il suo calcolo richiede tempi molto elevati; infatti fattorizzare in numeri primi (cioè scomporre un numero nei suoi divisori primi) è un'operazione molto lenta.

L'operazione di cifratura, supponendo che il messaggio M sia un numero, corrisponde a C=M^emod(n). Se ne deduce quindi che la chiave pubblica è la combinazione (e,n).
L'operazione di decifratura corrisponde a M = C^dmod(n). Se ne deduce quindi che la chiave privata è composta da (d,n).

In Crypthat la generazione delle chiavi è gestita da RSACipher con il metodo GenerateKeyPair e le chiavi sono memorizzate in un apposito container RSAContainer all'interno di ogni Identity.

Nel progetto è inoltre presente un Servizio, RSACryptoService, che consiste in un thread che, una volta avviato, periodicamente rigenera le chiavi RSA e notifica il gestore logico del cambiamento permettendo così ad ogni host di notificare la nuova chiave pubblica a tutti gli altri utenti collegati (tramite il server).

Annotazioni

Durante lo sviluppo dell'algoritmo il gruppo ha scoperto dell'esistenza della classe System.Numerics.BigInteger che permette di effettuare operazio su numeri interi di INFINITE cifre, ovviamento a discapito della performance.

Per la generazione casuale delle chiavi/numeri abbiamo scoperto che la classe Random di default non è sicura è stata infatti creata una nuova classe apposta per la generazione delle chiavi di cifratura chiamata RNGCryptoServiceProvider che genera gruppi di byte in sicurezza.

Dato che in RSA è necessario generare 2 numeri primi molto elevati, il controllo sui numeri primi diventa impossibile e si entra nel campo degli algoritmi probabilistici. Guardando su GitHub, si può notare un'implementazione dell'algoritmo di Miller–Rabin che determina se un numero è primo con una certa percentuale di probabilità. Questi algoritmi impiegano pochi secondi in C# a determinare con precisione quasi assoluta se un numero di 150 cifre è primo.

Per il calcolo della chiave privata d, è stato necessario effettuare l'operazione inversa del modulo che è risultata essere risolvibile grazie al Teorema Esteso di Euclide.

In RSA non è possibile cifrare messaggi M maggiori di n. Questo ha portato il gruppo a cifrare la chiave AES simmetrica con cui si era cifrato il messaggio. Così facendo si garantiva che M fosse minore di n. E' stato inizialmente implementato anche un algoritmo per la cifratura a blocchi di byte minori di n, ma da una ricerca su internet si è concluso che il cifraggio a blocchi avrebbe reso l'algoritmo vulnerabile a diversi tipi di attacchi.

RSA non può essere utilizzata come firma digitale, questo perchè non è sempre possibile codificare un messaggio con la propria chiave privata e con un'altra chiave pubblica, in alcuni casi, infatti M elevato alla chiave di uno dei 2 host risulterebbe manggiore della seconda chiave, impedendo così una corretta cifratura del messaggio.