(Classe 5a) - Sistemi e Reti

Si basa sulla scelta di una terna di numeri interi (N, D ed E) con proprietà speciali.

N è il prodotto di due numeri primi molto grandi P e Q (N = P*Q), e deve essere superiore al massimo valore binario dei blocchi di testo da cifrare.

D ed E sono, insieme a N, le due chiavi di cifratura e di decifratura (è uguale usare una come privata e l’altra come pubblica, o viceversa). D ed E vengono ottenuti da P e Q così:

• D deve essere minore di (P-1)*(Q-1) e primo rispetto allo stesso numero (P-1)*(Q-1)
• E deve essere l’inverso moltiplicativo di D mod (P-1)*(Q-1), cioè deve valere che:         
  (D*E) mod (P-1)*(Q-1) = 1 (il loro prodotto, modulo (P-1)*(Q-1), deve dare resto = 1).

Data quindi la terna indicata N, D ed E, valgono le seguenti formule per cifrare e decifrare (sono molto semplici ma anche, per la notevole lunghezza delle chiavi, fino a 1000 più lente da eseguire di quelle analoghe basate su chiave simmetrica):

• blocco-cifrato             = blocco-in-chiaro^D mod N
• blocco-in-chiaro         = blocco-cifrato^E mod N.

La forza di RSA sta nel fatto che ricavare P e Q da N, ossia la fattorizzazione di N (che è come ricavare E da D o viceversa), è un’operazione molto complessa se N ha, ad esempio, da 512 a 1024 bit. Per 512 bit, nel 1999, ci sono voluti 35 anni di CPU per farlo, in 7 mesi solari.