Sicurezza di RSA

di Raspanti Davide

Insegnamento: Tecnologie per la sicurezza L-S
Docente: Laschi Roberto
Anno Accademico: 2002-2003

Lo schema di cifratura

Generazione di numeri primi

Il soddisfacimento dei requisiti di robustezza imposti dal sistema RSA (Appendice A) è stato ottenuto generando i relativi numeri primi attraverso un algoritmo che prevede innanzitutto di scegliere un numero casuale di dimensioni simili a quelle del numero (grande) desiderato e, successivamente, di cercare il numero primo immediatamente successivo a quest'ultimo (Capitolo 3).

A tal fine è stato utilizzato il generatore di numeri pseudocasuali fornito da Mathematica:

r = Random[Integer, {(10^10), (10^11)}]

Nell'esempio sopra riportato è stato specificato che il numero intero desiderato deve appartenere all'intervallo compreso fra (10^10) e (10^11).

Il passo successivo prevede, come sottolineato inizialmente, di ricercare il numero primo immediatamente successivo al numero ricavato (cioè ad r):

primoSuccessivo[num_] := 
      Module[{n}, 
If[EvenQ[num], n = num + 1, 
          n = num]; 
While[! PrimeQ[n], 
          n = n + 2]; 
n]

primoSuccessivo[r]

PrimeQ[%]

L'algoritmo, quindi, controlla innanzitutto se il numero attualmente in esame risulta pari e quindi, in caso affermativo, provvede a sommare ad esso 1 per renderlo dispari; il procedimento viene ripetuto per tutti i numeri dispari successivi fino all'identificazione di un primo.

Sulla base di quanto esposto, dunque, si potrebbe definire una funzione che richieda come unico parametro di ingresso un numero intero corrispondente all'ordine di grandezza (potenza del 10) del primo casuale richiesto:

generaPrimoCasuale[n_] := 
      primoSuccessivo[Random[Integer, {(10^(n - 1)), (10^n)}]]

Generazione delle chiavi

Indicando con p e q i numeri primi (casuali) generati allo scopo di rendere computazionalmente impossibile la fattorizzazione di n=p*q, il valore dell'esponente e deve risultare primo con (p-1)*(q-1) (Appendice A). Una possibile scelta sarebbe dunque quella di adottare, come esponente pubblico, un numero primo casuale tale da consentire di calcolare l'esponente di decifrazione d mediante la funzione

getChiave[e_, p_, q_] := 
      Module[{d, f, m, 
          z}, 
f = (p - 1)*(q - 
                1); 
{m, {d, z}} = 
          ExtendedGCD[e, f]; 
{e, d, p*q}]

Si noti l'uso dell'algoritmo esteso di Euclide (Appendice A).
Si può quindi definire la seguente funzione (funzione che, assegnata la dimensione approssimata dei primi casuali richiesti, produce p, q ed e e calcola d):

generaChiave[ord_] := 
      Module[{e, p, q}, 
p = 
          generaPrimoCasuale[ord]; 
q = 
          generaPrimoCasuale[ord]; 
e = 
          generaPrimoCasuale[Floor[2/3*ord]]; 
getChiave[e, 
          p, q]]

generaChiave[60]

Si osservi il legame fra la scelta del valore assegnato all'ordine di grandezza dell'esponente di cifratura e le considerazioni fatte in merito alla sua influenza sulla sicurezza del sistema (Capitolo 2 ed Appendice A).
Considerando i casi di impiego presentati di seguito è conveniente ricorrere ad un'opportuna struttura di gestione delle chiavi così generate:

generaChiaveRSA[ord_] := 
      Module[{e, d, n}, 
{e, d, n} = 
          generaChiave[ord]; 
chiaveRSA[e, d, 
          n]]

generaChiaveRSA[60]

Specifica dell'esponente

Numerose applicazioni richiedono esplicitamente un ridotto esponente di cifratura: ciò è dovuto principalmente al fatto che un tale esponente permette di raggiungere elevate velocità di calcolo (in fase di cifratura) grazie al minor numero di moltiplicazioni modulari da eseguire (Appendice A). Le smart cards, ad esempio, rappresentano un contesto tipico in questo senso dal momento che, prevedendo di memorizzare la chiave di decifrazione direttamente sulla carta, impongono il ricorso ad esponenti segreti di dimensioni limitate (con tutti i rischi relativi a siffatta scelta).

Una funzione che consente di specificare l'esponente e presenta la seguente architettura:

specificaEsponente[ord_, e_] := 
      Module[{p, q, d, n}, 
p = 
          e + 1; 
q = e + 1; 
While[
          GCD[p - 1, e] > 1, 
          p = generaPrimoCasuale[ord]]; 
While[
          GCD[q - 1, e] > 1, 
          q = generaPrimoCasuale[ord]]; 
n = 
          p*q; 
d = 
          PowerMod[e, -1, n]; 
chiaveRSA[e, d, 
          n]]

Si noti che i cicli While introdotti hanno il compito cruciale di assicurare una scelta accurata del valore di p e di q (e, infatti, non deve avere alcun fattore in comune con p-1 o q-1); la struttura sopra riportata, quindi, richiede inevitabilmente un incremento del tempo di calcolo necessario per generare la chiave in quanto, come è possibile osservare, è molto probabile che prima di giungere al risultato voluto si debba produrre e verificare un numero considerevole di primi.

Gestione delle chiavi

Strutture

Nella creazione della chiave pubblica e privata si è deciso di scegliere i seguenti modelli di rappresentazione (il modello strutturale di riferimento è quello della lista):

chiaveRSA[e,d,n] - per la combinazione chiave pubblica/chiave privata
chiavePubblica[e,n] - per la chiave pubblica
chiavePrivata[d,n] - per la chiave privata
{chiavePubblica[e,n],chiavePrivata[d,n]} - per la coppia chiave pubblica/chiave privata

Funzioni

Sulla base delle strutture adottate ed in previsione di quelle che saranno le tipologie di impiego trattate risulta utile e necessario definire alcune funzioni che consentano di manipolare le chiavi prodotte.

Una prima funzione fornisce una coppia chiave pubblica/chiave privata a partire dal risultato dei processi di generazione descritti sopra:

getCoppia[chiave_] := 
      chiave /. chiaveRSA[e_, d_, n_] -> {chiavePubblica[e, n], 
            chiavePrivata[d, n]}

Altre importanti funzioni sono quelle attraverso le quali è possibile estrarre singolarmente la chiave pubblica o quella privata:

getPubblica[chiaveRSA[e_, d_, n_]] := 
        chiavePubblica[e, n];
getPubblica[{chiavePubblica[e_, n_], chiavePrivata[d_, n_]}] := 
      chiavePubblica[e, n]

getPrivata[chiaveRSA[e_, d_, n_]] := 
        chiavePrivata[d, n];
getPrivata[{chiavePubblica[e_, n_], chiavePrivata[d_, n_]}] := 
      chiavePrivata[d, n]

Il procedimento di generazione della chiave può dunque essere delegato ad una sola funzione (l'unica accessibile a chi intenda ottenere una chiave RSA):

generaCoppia[ord_] := getCoppia[generaChiaveRSA[ord]]

Ad esempio:

coppia = generaCoppia[50]

getPubblica[coppia]

getPrivata[coppia]

Ulteriori funzioni a cui fare riferimento sono:

getModulo[chiavePubblica[e_, n_]] := n;
getModulo[chiaveRSA[e_, d_, n_]] := n

esponentePubblico[chiaveRSA[e_, d_, n_]] := e

esponentePrivato[chiaveRSA[e_, d_, n_]] := d

Codifica del messaggio

Come è già stato sottolineato (Appendice A), la dimensione dei blocchi in cui viene suddiviso il messaggio da cifrare dipende dalla dimensione del modulo.

Ipotizziamo che i messaggi considerati contengano esclusivamente caratteri relativi allo standard ASCII (quindi caratteri lunghi 8 bits).
Una stringa di caratteri può essere convertita in una lista di numeri appartenenti all'insieme ASCII nel seguente modo:

lista = ToCharacterCode["Stringa di prova"]

Supponiamo che si intenda ridurre una lista di codici ASCII (come quella ottenuta sopra) ad un singolo numero: non si può certamente pensare di risolvere  il problema semplicemente concatenando le lettere (in quanto alcune presentano due caratteri, altre invece tre). Si sa tuttavia che ogni lettera risulta composta da 8 cifre binarie e, dunque, la concatenazione può essere effettuata eseguendo uno shift a sinistra di 8 posizioni e, successivamente, sommando.
Questo processo può essere schematizzato come indicato di seguito:

concatena[l_] := concatena[l, 0];
concatena[l_, num_] := 
      If[Length[l] == 0, num, 
        concatena[Rest[l], (num*256) + First[l]]]

Si noti la natura tail ricorsiva della funzione.
Ad esempio:

num = concatena[lista]

IntegerDigits[num, 256]

% == lista

La tecnica di codifica presentata si presta ora ad essere utilizzata come meccanismo interno di un'opportuna funzione che, a partire da una stringa di ingresso, generi una lista di blocchi corrispondenti alla rappresentazione del messaggio in esame:

raggruppa[l_, blcLun_]:=Module[{s = l},
While[Mod[Length[s], blcLun] ≠ 0, 
              s = Join[s, {32}]] (*Padding*);
Table[
              Take[s, {i, i + blcLun - 1}], {i, 1, Length[s] - 1, 
                blcLun}]]

raggruppa[lista, 5]

L'intrinseca dipendenza della dimensione dei blocchi dalla dimensione del modulo conduce quindi alla specifica della seguente funzione di codifica:

codifica[mess_, n_] := 
      Module[{blcLun, bitLun, l, blocchi}, 
bitLun = 
          Length[IntegerDigits[n, 2]] - 1; 
blcLun = 
          Quotient[bitLun, 8]; 
l = 
          ToCharacterCode[mess]; 
blocchi = 
          raggruppa[l, blcLun]; 
Map[concatena[#] &, 
          blocchi]]

Ad esempio:

messCod = codifica["Stringa di prova", 89657832121]

La corrispondente funzione di decodifica è pertanto:

decodifica[l_] := 
      FromCharacterCode[Flatten[Map[IntegerDigits[#, 256] &, l]]]

Quindi:

decodifica[messCod]

Cifratura e decifrazione

Cifratura di un blocco

Il processo di cifratura, come già evidenziato (Appendice A), provvede innanzitutto a suddividere in blocchi (di numeri molto grandi) il messaggio da cifrare e, successivamente, calcola la potenza e-esima (modulo n) di ciascun blocco così ottenuto:

cifraBlocco[blc_, chiavePubblica[e_, n_]] := 
      PowerMod[blc, e, n]

Ad esempio:

{pub, priv} = generaCoppia[20]

m = generaPrimoCasuale[16]

c = cifraBlocco[m, pub]

Per quanto concerne il processo di decifrazione:

decifraBlocco[blc_, chiavePrivata[d_, n_]] := 
      PowerMod[blc, d, n]

Ad esempio:

p = decifraBlocco[c, priv]

m == p

Cifratura di un messaggio

I meccanismi di codifica/decodifica e di cifratura/decifrazione finora discussi si prestano ora ad essere sintetizzati in due funzioni di base: la prima, una volta ricevuti in ingresso il messaggio e la chiave, ha il compito di eseguire l'operazione di cifratura restituendo, alla fine, una lista di blocchi numerici; la seconda, invece, ricevendo in ingresso tali blocchi insieme alla chiave segreta, gestisce la fase di decifrazione:

cifraMessaggio[mess_, chiavePubblica[e_, n_]] := 
      Module[{c1, c2}, 
c1 = 
          codifica[mess, n]; 
c2 = 
          Map[(cifraBlocco[#, chiavePubblica[e, n]]) &, c1]]

decifraMessaggio[c_, chiavePrivata[d_, n_]] := 
      Module[{dec}, 
dec = 
          Map[(decifraBlocco[#, chiavePrivata[d, n]]) &, 
            c]; 
decodifica[dec]]

Ad esempio:

messaggio = "I meccanismi di codifica/decodifica e di cifratura \
finora discussi si prestano ora ad essere sintetizzati in due funzioni di \
base: la prima, una volta ricevuti in ingresso il messaggio e la chiave, ha \
il compito di eseguire l'operazione di cifratura restituendo, alla fine, una \
lista di blocchi numerici; la seconda, invece, ricevendo in ingresso tali \
blocchi insieme alla chiave segreta, gestisce la fase di \
decifrazione.";

{pubblica, privata} = getCoppia[generaChiaveRSA[10]]

messaggioCifrato = cifraMessaggio[messaggio, pubblica]

decifraMessaggio[messaggioCifrato, privata]

Attacco con esponente di cifratura piccolo

Come già precisato (Capitolo 2), questa tipologia di attacco può essere impiegata ogniqualvolta lo stesso messaggio (o parte di esso) sia cifrato numerose volte secondo distinti moduli ma con lo stesso (ridotto) valore per l'esponente pubblico. L'attacco in esame risulta pertanto particolarmente efficace nel caso in cui, allo scopo di incrementare la velocità del processo di cifratura, venga usato come esponente pubblico e=3 (Appendice A): in tale circostanza, infatti, il crittoanalista necessita di soli 3 messaggi.

L'attacco prevede di ricorrere al teorema cinese del resto per ricavare un'unica soluzione x al sistema di congruenze relative ai 3 messaggi cifrati (Appendice B): la funzione che segue impiega l'algoritmo di Gauss (Appendice B) per risolvere le equazioni costituenti tale sistema e, di conseguenza, per calcolarne la soluzione cercata.

inverso[u_, n_] := 
      Module[{k, i, m}, 
{m, {i, k}} = 
          ExtendedGCD[u, n]; 
i]

Gauss[as_, ns_] := 
      Module[{n, nS, mS, i, k, x}, 
n = 
          Fold[Times, 1, ns]; 
k = 
          Length[ns]; 
nS = 
          Map[(n/#) &, ns]; 
mS = 
          Table[inverso[nS[[i]], 
              ns[[i]]], {i, 1, 
              k}]; 
x = (∑_(i = 1)^k) Mod[
              as[[i]]*
                nS[[i]]*
                mS[[i]], 
              n]; 
Mod[x, n]]

Si noti che i valori forniti in ingresso alla funzione definita sopra rappresentano rispettivamente i messaggi cifrati ed i diversi moduli usati. Il valore restituito, inoltre, corrisponde al messaggio (o al blocco di messaggio) elevato all'esponente pubblico scelto.

Una possibile realizzazione dell'attacco in esame è la seguente.
Si generino innanzitutto 3 chiavi secondo le modalità esposte (Capitolo 3 e Appendice A):

chiave1 = specificaEsponente[20, 3]

chiave2 = specificaEsponente[20, 3]

chiave3 = specificaEsponente[20, 3]

Supponiamo ora di impiegare come messaggio un numero casuale (numero che, chiaramente, dovrà risultare minore del minimo fra i moduli utilizzati):

messaggio = 
      Random[Integer, {1, 
          Min[getModulo[chiave1], getModulo[chiave2], 
            getModulo[chiave3]]}]

A questo punto si procede cifrando il messaggio con ciascuna delle chiavi prodotte (ottenendo così 3 messaggi cifrati):

c1 = cifraBlocco[messaggio, getPubblica[chiave1]]

c2 = cifraBlocco[messaggio, getPubblica[chiave2]]

c3 = cifraBlocco[messaggio, getPubblica[chiave3]]

Estraendo il modulo da ogni chiave

ns = {getModulo[chiave1], getModulo[chiave2], 
        getModulo[chiave3]}

ed organizzando i messaggi cifrati in una lista

as = {c1, c2, c3}

si può usare l'algoritmo di Gauss per ottenere il valore cercato x:

x = Gauss[as, ns]

Infine, calcolando la radice e-esima (cubica in questo caso) si verifica l'equivalenza fra il risultato ottenuto ed il messaggio iniziale:

p = (x^(1/3))

p == messaggio

Chiavi più grandi

Verifichiamo l'efficacia dell'attacco nel caso in cui vengano utilizzate chiavi di dimensioni maggiori:

chiave4 = specificaEsponente[150, 3]

chiave5 = specificaEsponente[150, 3]

chiave6 = specificaEsponente[150, 3]

{n4, n5, n6} = 
      Map[getModulo[#] &, {chiave4, chiave5, chiave6}]

m1 = Random[Integer, {1, Min[n4, n5, n6]}]

cs1 = 
      Map[cifraBlocco[m1, getPubblica[#]] &, {chiave4, chiave5, 
          chiave6}]

x1 = Gauss[cs1, {n4, n5, n6}]

p1 = (x1^(1/3))

p1 == m1

Esponenti di cifratura più grandi

Nel caso in cui vengano usati esponenti di cifratura più grandi, l'efficacia dell'attacco presentato è garantita solo se viene assicurata la disponibilità di un numero maggiore di messaggi cifrati (Capitolo 2).
Un esponente frequentemente impiegato nella pratica è (2^16) + 1: il motivo di ciò deriva dal fondamentale contributo da esso offerto alla velocizzazione del procedimento di cifratura (Appendice A) e dalla sua robustezza ad attacchi analoghi a quello in esame (è infatti altamente improbabile che uno stesso messaggio sia inviato a (2^16)+1 destinatari).

kps = Table[specificaEsponente[20, 5], {i, 1, 5}]

ns1 = Map[getModulo[#] &, kps]

m2 = Random[Integer, {1, Min[ns1]}]

cs2 = Map[cifraBlocco[m2, getPubblica[#]] &, kps]

x2 = Gauss[cs2, ns1]

p2 = (x2^(1/5))

p2 == m2