crittografia a chiave pubblica: RSA

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)

validità di RSA

• 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
• RSA soddisfa i tre criteri di validità per sistemi di crittografia commerciale, ma non è esente da minacce:
  • 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

confronto fra crittografia simmetrica e asimmetrica

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

riferimenti

• Rivest, Shamir, Adelman (1978) :
     A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,
     Comm. ACM 21, 120-126, 1978.   http://theory.csail.mit.edu/~rivest/publications.html
• Diffie & Hellman (1976) : New Directions in Cryptography,
     IEEE Trans. on Info. Theory, IT-22(6), 644-654, 1976.
     http://www-ee.stanford.edu/~hellman/publications.html
• Merkle & Hellman (1978) : Hiding Information and Signatures in Trapdoor Knapsacks,
     IEEE Trans. on Info. Theory, IT-24(5),525-536, 1978.
     http://www-ee.stanford.edu/~hellman/publications.html
• 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
• Agrawal, Kayal & Saxena (2002) : PRIMES is in P, Annals of Mathematics, 160(2): 781-793, 2004.
     http://www.cse.iitk.ac.in/users/manindra/publications.html
• AKS Primality Test : http://mathworld.wolfram.com/AKSPrimalityTest.html
• RSA Factoring Challenge : http://www.rsa.com/rsalabs/node.asp?id=2092
• 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