Crittografia

Algoritmo RSA

Ora abbiamo tutti gli incredienti matematici per capire la procedura del cifrario RSA. Inizialmente occorrono due numeri primi p e q molto grandi, cioè con 300 cifre decimali e calcolare il prodotto n=p⋅q e φ(n)=(p-1)(q-1). Successivamente si sceglie un qualunque numero k minore di φ(n) e coprimo con φ(n) e si determina il numero l tale che:

k ⋅ l mod φ(n) = 1

I numeri n e k costituiscono la chiave pubblica che verrà resa nota a tutti quelli che sono interessati a inviare dei messaggi segreti, mentre i numeri p, q, l costituiscono la chiave privata e quindi verra tenuta segreta. Chi vuole inviare un messaggio segreto deve trasformare il messaggio in chiaro in un numero m e ciò è possibile utilizzando il codice ASCII che è quello standard dei computer. Ottenuto il numero m (m va diviso in più blocchi se è maggiore di n) si deve calcolare:

m^k mod n

che sarà un numero t. Quest'ultimo è il messaggio segreto che viene inviato al destinatario. Il destinatario calcola:

t^l mod n

e ottiene il numero m e utilizzando il codice ASCII lo trasforma nel messaggio in chiaro. Cerchiamo di capire perchè:

t^l mod n = m

Al posto di t possiamo mettere m^k visto che sono equivalenti rispetto al modulo n per cui si ha:

m^k⋅l mod n

Ora, essendo k ⋅ l mod φ(n) = 1 per la definizione di modulo esiste sicuramente un numero s tale che

k⋅l = s ⋅ φ(n) + 1

e quindi possiamo scrivere:

m^s⋅φ(n)+1 mod n

Cioè

m^s⋅φ(n) ⋅ m mod n

Ora, per il teorema di Eulero

m^φ(n) mod n = 1

e quindi si ottiene:

1^s ⋅ m mod n = m

perchè m è minore di n. Osservazione:

Per decifrare il messaggio cifrato con RSA bisogna conoscere p e q oppure φ(n). Ora, anche la determinazione di φ(n) se n è un numero molto grande non può essere ottenuta in un periodo di tempo ragionevole. L'intervallo di tempo necessario per il calcolo di φ(n) è paragonabile all'intervallo di tempo necessario per la fattorizzazione di n.