Cifratura asimmetrica RSA

Nei cifrari asimmetrici si utilizzano due chiavi una "pubblica" e una "privata", ovviamente la prima è a conoscenza di tutti mentre la seconda è segreta.Il funzionamento di questo sistema prevede che qualsiasi messaggio cifrato con la chiave pubblica possa essere decodificato soltanto con la chiave privata, in questo modo si elimina il problema della distribuzione delle chiavi, tuttavia nelle implementazioni pratiche i cifrari asimmetrici risultano molto più lenti rispetto ai cifrari simmetrici. L' RSA è uno dei più noti algoritmi di cifratura asimmetrici, la sua sicurezza si basa sulla difficoltà di scomporre in fattori numeri grandi. Per l' implementazione si procede innanzitutto con la scelta di due numeri primi P e Q e se ne calcola il prodotto N=P.Q, successivamente si calcola il numero dei numeri compresi fra 1 e (N-1) che sono primi relativamente a N,questa funzione è nota come "toziente di eulero" e solitamente è indicata dalla lettera greca phi Φ.Se N è il prodotto di due numeri primi allora Φ(N)=Φ(P.Q)=(P-1).(Q-1), ciò torna utile perchè Φ dovrà essere calcolato per l'RSA.Occorre poi scegliere una chiave di cifratura casuale "E" che sia relativamente prima rispetto a Φ(N), ed occorre trovare una chiave di decifrazione tale che soddisfi l' equazione :
E.D=S.Φ(N)+1 (S è un qualsiasi numero intero)
Questa equazione può essere risolta mediante "l' algoritmo euclideo esteso" che consente di trovare il massimo comun divisore di due numeri. I valori di N ed E vengono distribuiti attraverso la chiave pubblica mentre D costituisce la chiave privata. La cifratura sarà:
C=(M^E)(mod N)
la decifratura :
M=(C^D)(mod N)
Questa è la sostanza dell' RSA, la sua sicurezza dipende dal fatto che D è segreta, ma dato che E ed N sono pubblici se N dovesse venire fattorializzato nei valori P e Q allora D potrebbe essere determinato con l' aiuto dell' algoritmo euclideo esteso. Quindi è obbligatorio scegliere le lunghezze delle chiavi tenendo presente il miglior algoritmo noto in modo da rendere impraticabile un attacco.Attualmente il miglior algoritmo noto per fattorializzare grandi numeri è il "number field sieve" NFS, ma allo stato attuale, che ovviamente dipende anche dall' hardware,non è sufficientemente veloce per decifrare chiavi RSA da 2048 bit in tempi ragionevoli.