caratteristiche di una crittografia valida secondo Shannon (1949):

1. la quantità di segretezza necessaria determina la quantità di lavoro necessaria per cifratura e decifrazione
2. insieme di chiavi e algoritmo di cifratura privi di complessità
3. l'implementazione del processo dovrebbe essere la più semplice possibile
4. gli errori di cifratura non dovrebbero propagarsi e danneggiare altre informazioni nel messaggio
5. dimensione del testo cifrato non superiore a quella del testo in chiaro

criteri di validità di sistemi di crittografia commerciale:

• basata sulla matematica
• analizzata e giudicata efficace da esperti competenti
• ha superato la "prova del tempo"

terminologia:

• crittografia simmetrica = a chiave segreta
• crittografia asimmetrica = a chiave pubblica

differenza essenziale:

• crittografia simmetrica: K_d = K_e
  • unica chiave per cifratura e decifrazione
  • segreto condiviso da mittente e destinatario → autenticazione
• crittografia asimmetrica: K_d ≠ K_e
  • chiavi distinte per cifratura e decifrazione
  • solo una delle due va tenuta segreta: segreto locale

problema inerente la crittografia simmetrica: distribuzione delle chiavi

problema inerente entrambi i tipi di crittografia: gestione delle chiavi

in base all'informazione di cui dispone, il criptoanalista può condurre l'attacco a:

• solo testo cifrato
  • il caso presupposto sinora (si usano: frequenze dei simboli nel testo cifrato e nel linguaggio, conoscenze acquisite, etc.)
• testo in chiaro parziale o completo
  • si dispone di un messaggio cifrato e (di una parte) della sua decifrazione
    • attacco al testo in chiaro conosciuto
    • attacco al testo in chiaro probabile
• testo cifrato di qualsiasi testo in chiaro
  • il criptoanalista può inserire testo in chiaro in input al processo di crittografia e osservare l'output: attacco al testo in chiaro scelto
• algoritmo e testo cifrato :    attacco al testo cifrato scelto
• testo cifrato e testo in chiaro :    obiettivo: dedurre la chiave

idea originale: Diffie & Hellman (1976)

• ma anche altri, contemporaneamente in Inghilterra: invenzione coperta dal segreto militare fino agli anni '90, v. Singh (1999)

ogni utente U ha una chiave pubblica K_PU e un'associata chiave privata (segreta) K_SU

• riservatezza: M = D(K_SU, E(K_PU, M))
• autenticità:   M = D(K_PU, E(K_SU, M))

è possibile assicurare simultaneamente riservatezza e autenticità in un sistema di crittografia a chiave pubblica?

sì! mediante doppia cifratura:

• M = D(K_SB, D(K_PA, E(K_SA, E(K_PB, M))))

RSA, dalle iniziali dei nomi degli inventori: Rivest, Shamir, Adelman (1978)

come funziona (in breve): una coppia di chiavi associate consta di 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 (grandi: ≥256 bit), 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 di recente provata 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

le radicalmente differenti caratteristiche di riservatezza delle chiavi e la molto diversa velocità degli algoritmi di cifratura e decifrazione comportano usi diversi, ma spesso complementari, della crittografia simmetrica e di quella asimmetrica