Algoritmo RSA

Introduzione

L'algoritmo di crittografia asimmetrica RSA è stato inventato da Ron Rivest, Adi Shamir e Leonard Adleman nel 1977. Si basa sulla crittografia della fattorizzazione dei numeri interi, ovvero sulla difficoltà di fattorizzare un numero formato dal prodotto di due numeri primi sufficientemente grandi.

Descrizione

Aritmetica modulare

Con l'operatore mod si indica il resto intero della divisione di un numero. In particolare, scrivendo b = a mod n si indica che b è uguale al resto della divisione di a per n, ovvero a = k*n + b
ad esempio:
27 mod 11 = 5 perché 7 = 2 * 11 + 5.
Inoltre, data l'espressione b = a mod n, il valore di b può essere un qualunque numero compreso tra 0 e n-1.

Numeri primi e coprimi

Un numero è detto primo se è divisibile solo per se stesso e per 1. Per convenzione, 1 non è considerato un numero primo. I numeri primi minori di 20 sono: 2, 3, 5, 7, 11, 13, 17, 19. A differenza di 2, tutti i numeri primi sono dispari, poiché quelli pari sono certamente divisibili per 2.
Il teorema fondamentale dell'aritmetica afferma che ogni numero intero positivo n può essere rappresentato univocamente come prodotto di numeri primi.
L'insieme dei numeri il cui prodotto è uguale a n è chiamato fattorizzazione di n. Per ogni numero n ne esistono svariati insiemi, ma la scomposizione in numeri primi è unica.
Due numeri a e b sono coprimi quando non hanno fattori in comune, ovvero il loro massimo comune divisore è 1. Ad esempio: 14 e 9 non sono numeri primi ma sono coprimi tra loro. Naturalmente due numeri primi saranno sempre coprimi tra loro.

Funzione phi di Eulero

Per ogni numero intero positivo n si definisce la funzione $\varphi(n)$ come il numero degli interi positivi minori di n coprimi con n (l'intero 1 è sempre compreso, essendo coprimo di qualunque altro numero)
Esempio: $\varphi(12) = 4$ perché i seguenti numeri sono coprimi: 1; 5; 7; 11

Se p è un numero primo, allora qualunque altro numero minore di p sarà coprimo, quindi se p è un numero primo:

(1)

\begin{align} \varphi(p) = p-1 \end{align}

Dati due numeri n e m coprimi, il valore della funzione phi del loro prodotto è uguale al prodotto del valore della funzione $\varphi$ dei due numeri:

(2)

\begin{align} \varphi(n m) = \varphi(n)\:\varphi(m) \end{align}

Generazione delle chiavi

La creazione delle chiavi avviene attraverso le seguenti operazioni:

1. Generazione di due numeri primi p e q diversi tra loro.
2. Si calcola il loro prodotto n = p q e il valore di $\varphi(n) = (p-1)(q-1)$
3. Si sceglie un numero e detto esponente pubblico compreso tra 1 e $\varphi(n)$ e coprimo con $\varphi(n)$ (quindi tale che $MCD(\varphi(n), e) = 1$
4. Si calcola un numero d detto esponente segreto o privato tale che $ed mod\:\varphi(n) = 1$
5. La chiave pubblica è costituita dalla coppia di numeri (e, n) e la chiave privata dalla coppia (d, n)

Cifratura

Sia m un numero intero inferiore a n che rappresenta il messaggio che il mittente vuole inviare al destinatario. Il mittente ottiene la chiave pubblica del destinatario costituita dai numeri e, n e calcola un numero c in questo modo:

(3)

\begin{align} c = m^e mod\:n \end{align}

Il numero c viene trasmesso al destinatario.

Decifratura

Il destinatario riceve il numero c e attraverso la sua chiave privata costituita dai numeri (d, n) ottiene il messaggio del mittente m in questo modo:

(4)

\begin{align} m = c^d mod\:n \end{align}

Dimostrazione

Piccolo teorema di Fermat e teorema di Eulero

Il piccolo teorema di Fermat afferma che dato un numero primo p, allora per qualunque intero a si ha:

(5)

\begin{align} a^p mod\:p = a \end{align}

Si può esprimere anche in questo modo: dato un numero primo p e un numero a coprimo con p, allora

(6)

\begin{align} a^{(p-1)} mod\:p = 1 \end{align}

Che si ottiene dividendo ambo i membri dell'equazione per a. Il teorema di Eulero è una generalizzazione del piccolo teorema di Fermat e stabilisce che dato un intero a e un intero positivo n coprimo con a, allora

(7)

\begin{align} a^{\varphi(n)} mod\:n = 1 \end{align}

Questo teorema può essere ricondotto alla formulazione di Fermat considerando un numero n primo e quindi con $\varphi(n) = n-1$.

Sia $c = m^e mod\:n$
allora nella decifratura

(8)

\begin{align} c^d mod\:n = (m^e)^d mod\:n = m^{e\:d} mod\:n \end{align}

Siccome
$ed\:mod\:\varphi(n) = 1$ allora per definizione $ed = k\:\varphi(n) + 1 = k(p-1)(q-1) + 1$
sostituendo

(9)

\begin{align} m^{e\:d} mod\:n = m^{k(p-1)(q-1) + 1} mod\:n = m*m^{k(p-1)(q-1)} mod\:n \end{align}

Dal teorema di Eulero-Fermat, la quantità $m^{k(p-1)(q-1)} mod\:p = (m^{(p-1)})^{k(q-1)} mod\:p = 1^{k(q-1)} mod\:p = 1$, essendo $m^{(p-1)} mod\:p = 1$.
Analogamente, si ha:

(10)

\begin{align} m^{k(p-1)(q-1)} mod\:q = (m^{(q-1)})^{k(p-1)} mod\:q = 1^{k(p-1)} = 1 \end{align}

Quindi

(11)

\begin{align} m^{k(p-1)(q-1)} mod\:p = 1 \end{align}

(12)

\begin{align} m^{k(p-1)(q-1)} mod\:q = 1 \end{align}

Per il teorema Cinese del Resto allora

(13)

\begin{align} m^{k(p-1)(q-1)} mod\:(pq) = 1 \end{align}

ovvero $m^{k(p-1)(q-1)} mod\:n = 1$
Sostituendo si ha:

(14)

\begin{align} m^{k(p-1)(q-1) + 1} mod\:n = m\:m^{k(p-1)(q-1)} mod\:n = m \end{align}

Schemi di cifratura

Per aumentare la sicurezza nell'implementazione dell'algoritmo RSA, sono stati sviluppati degli schemi di cifratura, nell'ambito di una serie di standard chiamati Public-Key Cryptography Standards (PKCS) e sviluppati da RSA Laboratories.

Masked Generation Function

Una Masked Generation Function è una funzione che riceve in ingresso una stringa di byte e produce una stringa di byte in output. Come parametri sono indicati la stringa di ingresso e un intero che indica la lunghezza desiderata dell'output.

output = MGF(input, lunghezza)

L'output viene generato in modo deterministico (ad uno stesso input corrisponde lo stesso output), ma per essere impiegata in ambito crittografico è necessario che:

• sia difficile ricavare la stringa di input a partire da quella di output
• senza conoscere la stringa di input, quella di output appare come una sequenza pseudocasuale

In genere le funzioni di questo tipo impiegano delle funzioni di Hash.

RSAES-PKCS1-v1_5

Data la chiave pubblica del destinatario (n, e), dove n è lungo k byte e un messaggio M di lunghezza mLen non superiore a (k-11), si crea un blocco dati codificato EB nel modo seguente:

EB = 0x00|0x02|PS|0x00|M

dove PS è una stringa di dati di lunghezza pari a k - mLen - 3 di byte generati in modo casuale. I byte di PS devono essere diversi da 0.

La lunghezza di EB è pari quindi a k.

Si effettua la cifratura di EB con la chiave pubblica del destinatario.

C = RSA(EB, (n, e))

Decifrando il messaggio C con la chiave privata del destinatario (n, d), si ottiene il blocco dati codificato EB.

EB = RSA(C, (n, d))

Si estrae il messaggio, che segue il byte nullo 0x00.

RSAES-OAEP

Data la chiave pubblica del destinatario, lunga k bit, una funzione di Hash che produce un codice di lunghezza hLen, un messaggio M di lunghezza mLen <= k – 2hLen – 2 e una stringa opzionale L, si crea un blocco dati DB codificato nel modo seguente:

DB = Hash(L)|PS|0x01|M

dove PS è una stringa nulla di lunghezza pari a k - mLen - 2hLen - 2.

Sia seed una stringa dati casuale di lunghezza hLen. Si calcola

dbMask = MGF(seed, k - hLen - 1)
maskedDB = DB xor dbMask
seedMask = MGF(maskedDB, hLen)
maskedSEED = seed xor seedMask

Sia EM una stringa composta dalla concatenazione seguente:

EM = 0x00|maskedSEED|maskedDB

Infine si cifra EM e la si trasmette.

Nell'operazione di decifratura, data la chiave privata del destinatario, lunga k byte, una funzione di Hash che produce un codice di lunghezza hLen, un messaggio cifrato C di lunghezza k >= 2hLen + 2 e una stringa opzionale L, si effettuano le seguenti operazioni.

Si decifra C ottenendo una stringa codificata e composta da

Y|maskedSEED|maskedDB

dove Y è un singolo byte di valore 0x00, maskedSEED ha lunghezza hLen e maskedDB di lunghezza k – hLen – 1

Si calcola:
seedMask = MGF(maskedDB, hLen)
seed = maskedSEED xor seedMask
dbMask = MGF(seed, k - hLen - 1)
DB = maskedDB xor dbMask

ottenuto il blocco DB, esso è codificato come

DB = Hash(L)|PS|0x01|M

I primi hLen byte sono relativi al codice Hash della stringa L opzionale, seguiti da una stringa PS di byte nulli 0x00 e da un byte separatore 0x01. Successivamente è presente il messaggio M.

Sicurezza

La sicurezza dell'algoritmo RSA si basa sulla difficoltà della fattorizzazione di un numero intero sufficientemente grande. che la fattorizzazione di un numero grande sia difficile. La chiave pubblica viene resa disponibile a tutti, anche a potenziali attaccanti, i quali vogliono calcolare l'esponente segreto d avendo a disposizione i valori di n ed e. Per calcolarlo serve il valore $\varphi(n) = (p-1)(q-1)$ quindi si deve scomporre il numero n nei due numeri primi p e q. Se questi sono sufficientemente grandi il problema diventa intrattabile.
Non è stato tuttavia dimostrato che la difficoltà nel rompere l'algoritmo RSA sia equivalente alla difficoltà della fattorizzazione, ma è ritenuto molto probabile.

Tipicamente vengono generate chiavi da 1024, 2048, 4096 bit. La lunghezza delle chiavi si riferisce alla dimensione del numero n = p q. Chiavi di lunghezza inferiore a 1024 bit sono attualmente sconsigliate.

Algoritmi

	Fattorizzazione Interi	Logaritmo Discreto	Curve Ellittiche
Cifratura	RSA, Rabin	ElGamal, DHIES

Vedi anche

• Firma con algoritmo RSA