RSA,
dalle iniziali dei nomi degli inventori:
Rivest, Shamir, Adelman (1978)
come funziona (essenzialmente):
una coppia di chiavi associate è costituita da due coppie
(n, e),
(n, d),
tali che, per qualsiasi testo in chiaro M,
considerato come numero binario naturale:
(M e) d =
(M d) e = M (mod n)
si scelgono n, e, d tali da soddisfare
le seguenti proprietà:
n = pq, con
p, q primi molto grandi (256 bit o più),
dunque φ(n) = (p-1)(q-1)
e primo relativo con
φ(n), cioè
gcd(e,φ(n)) = 1
d inverso di e
(mod φ(n)), cioè
ed = 1 mod(φ(n))
(*)
Teorema di Eulero:
M φ(n) = 1 (mod n)
, se M, n primi relativi
se M, n sono primi relativi,
lo sono sia M, p
che M, q, dunque:
M p-1 = 1 (mod p) ,
M q-1 = 1 (mod q)
, e per k tale che
ed = kφ(n) + 1
(tale k esiste per la proprietà
(*)),
elevando entrambi i membri della prima equazione a
k(q-1)
e quelli della seconda equazione a k(p-1),
si ottiene:
M kφ(n)
= 1 (mod p) ,
M kφ(n)
= 1 (mod q) ,
donde
M kφ(n)
= 1 (mod n)
e quindi, moltiplicando ambo i membri per M :
M ed
= M (mod n)
come altri algoritmi di crittografia a chiave pubblica
(Diffie-Hellman (1976), Merkle-Hellman (1978), Elgamal (1985)),
RSA è basato su un problema computazionalmente
difficile, in questo caso:
determinazione dei fattori primi
di un dato numero (abbastanza grande)
la complessità del problema del
test di primalità
è stata recentemente provata essere
polinomiale, con
l'AKS Primality Test (Agrawal, Kayal & Saxena, 2002)
...
tuttavia ciò non invalida la crittografia RSA perché nessun
algoritmo polinomiale è noto per il problema della
fattorizzazione in primi
si è già rivelata fattibile la fattorizzazione del numero
RSA-200; rimane aperta quella
dei numeri più grandi della
RSA Factoring Challenge
algoritmi quantistici (probabilistici)
per il problema della fattorizzazione, e per altri di simile difficoltà,
hanno complessità polinomiale, v.
(Shor, 1995):
ciò potrebbe minacciare la validità di RSA con tecnologie future
le radicalmente differenti caratteristiche di
riservatezza delle chiavi e
la notevolmente diversa
velocità degli algoritmi
di cifratura e decifrazione comportano usi diversi, ma spesso
complementari,
della crittografia simmetrica e di quella asimmetrica
caratteristica
crittografia simmetrica
crittografia asimmetrica
numero di chiavi
1
2
riservatezza delle chiavi
segreta, condivisa
una chiave pubblica, l'altra segreta (locale)
velocità dell'algoritmo
rapida
più lenta,
per un fattore ∼ 104
distribuzione della chiave
singolarmente per ciascun canale
si può usare la chiave pubblica
per distribuire altre chiavi
usi migliori
uso estensivo della crittografia,
riservatezza e integrità dei dati
crittografia una tantum, scambio delle chiavi, autenticazione
Elgamal (1984) :
A public key cryptosystem and a signature scheme based on discrete
logarithms,
in: Advances in Cryptology: Proc. CRYPTO 84,
LNCS 196(4), 10-19, Springer, 1985. http://www.springerlink.com/content/cemajg0qmeev
Shor (1995) :
Polynomial-Time Algorithms for Prime Factorization and Discrete
Logarithms on a Quantum Computer, SIAM J. Computing,
26 1484-1509, 1997.
http://www.arxiv.org/abs/quant-ph/9508027
