Il cifrario RSA

L'RSA è un cifrario a chiave pubblica che permette di cifrare un messaggio attraverso un procedimento che sfrutta le proprietà dei numeri primi.
In termini molto semplici: fissati due numeri h ed n, che costituiscono la chiave pubblica, si considera un terzo numero d che costituisce la chiave privata (i dettagli sul calcolo di questi parametri sono esposti più giù). Sia m il messaggio da cifrare. L'operazione da compiere è la seguente:
c=mh mod n.
La chiave di decifrazione è costituita dal numero intero d, segreto, che permette di recuperare m grazie alla formula:
m=cd mod n.
L'RSA viene considerato oggi uno dei sistemi di crittografia più sicuri perchè, essendo violabile solo mediante attacchi di forza bruta, la rottura del codice richiederebbe tempi e risorse economiche elevatissimi. Ma i supercomputer di cui dispongono i grandi governi e le continue ricerche matematiche non ci garantiscono, chiaramente, la massima sicurezza.

Esporrò adesso, in termini più tecnici, i principi di funzionamento dell'RSA.

  • Si determini la prima chiave n, prodotto di p e q, due numeri primi molto elevati, tali che la fattorizzazione di n sia estremamente difficile;
  • Si calcoli dunque il valore della funzione di Eulero di n: b=phi(n)=(p-1)*(q-1) il cui valore rimane segreto; si scelga ancora un intero d tale che d e phi(n) siano primi tra loro (d non risulterà necessariamente primo, ma deve essere minore di phi(n)). Infine si trovi h che è il più piccolo x (intero) per cui (dx-1)/phi(n) é un numero intero.

In questo modo abbiamo determinato i numeri n, h e d di cui abbiamo già parlato.

Se chiamo k la quantità (dx-1)/phi(n), ottengo dx=dh=kphi(n)+1. Posso allora dimostrare perchè m=cd mod n:

Il codice RSA viene considerato sicuro perchè, essendo la formula di decifrazione basata su phi(n) calcolabile solo se a conoscenza di p e q, non esiste (o perlomeno non è noto) un algoritmo per scomporre n nei suoi fattori primi p e q in tempi accettabili. Bisognerebbe effettuare attacchi di forza bruta, provando cioè tutti i possibili casi. Fattorizzare un numero di 664 bit richiede almeno 1023 passi usando gli algoritmi più efficienti; per cui ipotizzando di avere una rete costituita da un milione di computer con ciascuno di loro che esegue un milione di passi al secondo, il tempo impiegato per fattorizzare n sarebbe dell'ordine dei 4000 anni. Se poi n fosse un numero a 1024 bit la stessa rete impiegherebbe 1010 anni per fattorizzarlo . Potrebbe sorgere il dubbio che esista un modo di calcolare phi(n) senza passare per p e q: questa ipotesi in effetti è verificabile ed è uno dei tanti motivi per non dare massima fiducia a questo algoritmo di cifratura.

Esempio
  • n=p*q=5*7=35
  • b=phi(35)=(5-1)(7-1)=24
  • d=7 (primo con 24)
  • k=(7x-1)/24       da cui:   x=(k*24+1)/7
  • Fisso k=2 in modo da ottenere un numero x intero. Quindi k=2 e x=h=7.

    Ho trovato tutti i parametri che mi servivano e, a questo punto, suppongo che il messaggio da cifrare sia m=3. Procedo e calcolo:

    c=mh mod n=37mod 35=2187 mod 35=17

    Se adesso volessi decifrare il messaggio, essendo a conoscenza della chiave segreta d, procedo in questo modo:

    m=cd mod n=177mod 35=3

    Elevazione a potenza modulare

    L’operazione dell’elevazione a potenza modulare consiste nel calcolare xy mod z dove x, y e z sono interi. Ma, lavorando con numeri estremamente grandi, gli elaboratori non sono in grado di eseguire da soli questi calcoli. E'allora necessario fare uso di algoritmi di calcolo che, benchè laboriosi, ci consentono di raggiungere il nostro scopo. Al momento, per la realizzazione del mio programma di crittografia a chiave pubblica basato sull'RSA, sto utilizzando il metodo naive, sotto illustrato. Ma ritenendolo poco efficiente (richiede un enorme lavoro della CPU) penso che lo sostituirò con un altro più veloce.

    Metodo naive

    Si può schematizzare questo metodo con il seguente algoritmo:

    a=1
    for i=1 to y do
    a=(a*x)mod z
    next

    In pratica si calcola a=(a*x)mod z ripetendo l'operazione y volte. A questo punto il valore finale di a sarà il risultato di xy mod z, che abbiamo ottenuto evitando di lavorare con numeri troppo grandi. Tale algoritmo non è comunque molto efficiente, essendo il numero di cicli da eseguire uguale ad y. I metodi realmente utilizzati sono 2: il metodo "Left to right" e il metodo "Right to left". Ma parlerò in seguito di questi algoritmi, essendo ancora miei attuali argomenti di studio.

    Attacchi RSA

    Osserviamo che per un crittoanalista rompere l'RSA equivale a calcolare f(n). Infatti, se n e f(n) sono conosciuti ed n è il prodotto di due primi p e q, n può essere facilmente fattorizzato risolvendo il seguente sistema di 2 equazioni in 2 incognite: n = p × q e f(n)= (p - 1)(q - 1). Nelle due incognite p e q. Sostituendo q = n / p nella seconda equazione se ne ottiene un’unica di secondo grado nella sola incognita p:

    p2 - (n - f(n) + 1)p + n = 0.

    Le due radici di questa equazione sono i fattori p e q. Quindi se un crittoanalista conosce il valore di f(n) può fattorizzare n e rompere il sistema.

    Esempio Supponiamo che il crittoanalista conosca f(n) = 84754668 e n = 84773093.Queste informazioni gli permettono di scrivere l'equazione: p2 - 18426p + 84773093 = 0. Risolvendo l’equazione si ottengono le due radici 9539 e 8887 che rappresentano i fattori p e q di n.


    www.tonycrypt.com