Crittografia #2: gli algoritmi asimmetrici

Abstract
Come abbiamo visto nello scorso articolo per ovviare al problema dello scambio di chiave (k) tra due persone (A e B) si sono sviluppati, in contemporanea ai sistemi crittografici simmetrici, i sistemi crittografici asimmetrici o a chiave pubblica.

La crittografia asimmetrica.

Il principio di funzionamento dei sistemi crittografici asimmetrici è molto semplice:

• una chiave detta pubblica (public key) viene usata per le operazioni di cifratura (encryption)
• una chiave detta privata (private key) viene invece usata per le operazioni di decifratura (decryption)

Sostanzialmente tutti posso cifrare un qualunque messaggio usando la chiave pubblica di A ma solo A è in grado di decifrarlo usando la sua chiave privata.

Vediamo un semplice esempio per chiarici meglio le idee.

Il nostro solito amico A ha la necessità di mandare a B un messaggio segretissimo tramite un canale non sicuro (ad esempio email):

1. B genera due chiavi: una pubblica (K_puB che serve per cifrare) ed una privata (K_prB che serve per decifrare)
2. B manda ad A solo la sua chiave pubblica (la può spedire via email, la può pubblicare in internet)
3. A codifica il messaggio da inviare usando la K_puB e spedisce il messaggio così ottenuto a B
4. B una volta ricevuto il messaggio da A lo decifra usando la sua chiave privata K_prB

A questo punto sorge sicuramente una domanda: dal momento che la chiave privata è legata, in qualche modo, alla chiave pubblica di una persona è possibile ricavare la chiave privata da quella pubblica?

Il principio di generazione della coppia di chiavi K_pu e K_pr si basa su teorie matematiche certe: dal prodotto di numeri primi (numeri primi con 200 o 300 cifre) ai logaritmi discreti, curve ellittiche e meccanica quantistica ... e su funzioni matematiche ritenute one-way; è facile quindi intuire che pur avendo a disposizione una K_pu è molto difficile risalire alla relativa K_pr.

Potrebbe sorgerci un'altra domanda: ma le chiavi pubbliche dei miei destinatari dove le trovo?

Per ovviare a questo problema sono nate degli archivi di chiavi pubbliche: i public key servers ... ma se mi collego ad un public key server chi mi garantisce che la chiave pubblica del mio amico B sia la sua o non sia quella di C che finge di essere B?

Per fare fronte a questo problema sono nate le Certification Authority (CA): sono organizzazioni che garantiscono l'autenticità delle chiavi pubbliche pubblicate sui public key servers.

Analizziamo ora uno degli algoritmi più famosi ed usati in un cifrario asimmetrico: l'algoritmo RSA.

RSA: la crittografia asimmetrica secondo Rivest, Shamir ed Adlemann

Questo sistema fu inventato nel lontano 1978 da Rivest, Shamir ed Adlemann.

Il suo funzionamento si basa sul concetto di fattorizzazione dei numeri primi che, come dimostrò Euclide, sono infiniti.

Prima di esaminare nel dettaglio l'algoritmo RSA è bene ripassare qualche concetto di aritmetica modulare.

Immaginiamo di avere a disposizione solo un numero n di cifre (per esempio 12) e proviamo ad applicare i concetti di addizione e moltiplicazione tenendo presente che al superamento del numero 11 dovremmo ricominciare a contare dall'inizio.

Immaginiamo di sommare i due numeri 7 ed 8, otterremo:

La stessa cosa vale per la moltiplicazione e l'elevazione a potenza.

Vediamo ora come funziona la generazione di chiavi con il sistema RSA:

1. scegliamo p e q in modo che siano numeri primi molto grandi (200 o 300 cifre)
2. definiamo m in modo che m = (p-1)(q-1)
3. definiamo n in modo che n = pq
4. troviamo un numero e che sia primo rispetto ad n e non eccessivamente grande (teorema di Euclide esteso)
5. definiamo d in modo che de = 1 (mod n)
6. la chiave pubblica è identificata dalla coppia di numeri e ed n
7. la chiave privata è identificata dalla coppia di numeri d ed n

La cifratura del messaggio da parte di A usando la chiave pubblica di B appena generata sarà:

C(M) = M^e (mod n)

La decifratura del messaggio inviato da A sarà:

M(C) = C^d (mod n)

Chiariamoci meglio le idee con un esempio numerico (attenzione: i numeri scelti sono apposta ``piccoli'' per facilitare i calcoli)

1. p = 2357, q = 2551
2. m = (p-1)(q-1) = (2357-1)(2551-1) = 6007800
3. n = pq = 2357*2551 = 6012707
4. e = 3674911
5. d = 422191
6. Kpu corrisponde a: e (3674911) ed n (6012707)
7. Kpr corrisponde a: d (422191) ed ovviamente n (6012707)

Di conseguenza, posto M = 5234673, la cifratura sarà:

C(M) = 5234673^3674911 (mod 6012707) = 3650502

E la conseguente decifratura sarà:

M(C) = 3650502⁴²²¹⁹¹ (mod 6012707) = 5234673

Come abbiamo visto la teoria matematica che sta dietro allo RSA è piuttosto semplice e, come abbiamo già detto, si basa sul problema della fattorizzazione di numeri primi molto grandi.

Ma anche gli algoritmi asimmetrici hanno un grosso difetto: sono molto lenti; se paragonati agli algoritmi simmetrici possiamo avere un ritardo di cifratura superiore alle 100 volte!!

Solo nel 1990 l'algoritmo RSA è stato reso pubblico ed è usato da molti programmi come: PGP, SSH ...

Nel prossimo articolo andremo ad analizzare le PKI (Public Key Infrastructure) che sfruttano le caratteristiche delle due grosse famiglie di algoritmi che abbiamo analizzato (simmetrici ed asimmetrici).

Informazioni sull'autore

horobi, diplomato, lavora da circa 10 anni nel campo dell'informatica e si è occupato di sistemi operativi (sia Win che *nix) e reti. Da alcuni anni si occupa di principalmente di sicurezza ed Ethical Hacking.

È possibile consultare l'elenco degli articoli scritti da horobi.

Altri articoli sul tema Crittografia.

Risorse

1. Parte 1: le origini e gli algoritmi simmetrici
   http://www.siforge.org/articles/2003/11/24-crypto_cap1.html