Fondamenti di sicurezza - RSA

RSA: il sistema di cifratura asimmetrica

RSA è stato definito nel 1977 da Rivest, Shamir e Adleman. È lo schema di cifratura asimmetrica più utilizzato. Esso è basato sull’operazione di elevamento a potenza di interi modulo numeri primi (interi di grandi dimensioni fino a 1024 bit). La sicurezza è garantita dal costo di fattorizzazione di numeri grandi.

Funzionamento RSA

RSA si basa sulla condizione che: presi n, M appartenenti ai numeri naturali, con 0 < M < n dove:

• M è il numero decimale che indica la sequenza di bit da cifrare
• n è un numero (grande, codificato in 1024 o 2048 bit) predefinito

Allora RSA prevede una cifratura a blocchi, con lunghezza limitata dal valore di n.

Come funziona

Se A vuole cifrare il messaggio M, in modo che solo B lo possa leggere, allora:

• A esegue la cifratura C = M^e mod n
• B esegue la decifratura M = C^d mod n

Il mittente A deve conoscere {e,n} = (la coppia di valori {e,n} è la chiave pubblica di B). Il ricevente B deve conoscere {d,n} = (la coppia di valori {d,n} è la chiave privata di B).

• Per cifrare il messaggio M, il mittente A ottiene la chiave pubblica di B, calcola C = M^e mod n, con (0<M<n).
• Per decifrare C, il ricevente B usa la propria chiave privata e calcola M = C^d mod n.

Mod n è come fare diviso n, il resto di questa divisione è C. Es. 9 mod 3 = 0, il resto è zero; 9 mod 2 = 1, il resto è 1; 7 mod 9 = 7. Il 9 non ci sta nel 7 che è quindi il resto.

Spiegazione del teorema di Eulero

Numeri primi

Un numero intero p è primo se gli unici divisori sono 1 e p. Ogni numero intero è prodotto di numeri primi. La funzione di Eulero, indicata con φ (phi), dato un numero intero n, individua la quantità di numeri minori di n e coprimi con n. (es φ(8) = 4, e sono 1, 3, 5, 7).

• Se n è primo, φ(n) = n - 1.
• Se n non è primo, allora è prodotto di numeri primi n = p * q * r, e quindi φ(n) = φ(p - 1) * φ(q - 1) * φ(r - 1).

Teorema di Eulero φ(n): dati due numeri positivi m ed n coprimi tra loro (il massimo comun divisore è 1), allora m^φ(n) mod n ≡ 1.

Es. m = 3, n = 10: φ(10) = 4 (1, 3, 7, 9) quindi 3⁴ mod 10 ≡ 1.

Corollario del teorema di Eulero

Dati due numeri primi p e q, sia n = pq e m compreso tra...