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)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)Generazione delle chiavi
La creazione delle chiavi avviene attraverso le seguenti operazioni:
- Generazione di due numeri primi p e q diversi tra loro.
- Si calcola il loro prodotto n = p q e il valore di $\varphi(n) = (p-1)(q-1)$
- 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$
- Si calcola un numero d detto esponente segreto o privato tale che $ed mod\:\varphi(n) = 1$
- 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)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)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)Si può esprimere anche in questo modo: dato un numero primo p e un numero a coprimo con p, allora
(6)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)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
Siccome
$ed\:mod\:\varphi(n) = 1$ allora per definizione $ed = k\:\varphi(n) + 1 = k(p-1)(q-1) + 1$
sostituendo
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:
Quindi
(11)Per il teorema Cinese del Resto allora
(13)ovvero $m^{k(p-1)(q-1)} mod\:n = 1$
Sostituendo si ha:
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 |