RIVEST–SHAMIR–ADLEMAN (RSA)

cifrario asimmetrico che sfrutta il problema della fattorizzazione di un numero primo in cui La chiave pubblica e formata da due numeri $n,e$ (noti) e la privata da $n,d$ (privati)

Generazione delle chiavi

$n$ viene scelto essere: $p\ast q$ con $p$ e $q$ numeri primi molto grandim si calcola poi un numero coprimo di $n$ come segue $\Phi (n)=(p-1)\ast (q-1)$ a questo punto $e$ viene scelto fra i coprimi di $\Phi (n)$: $gen(\Phi (n),e)=1$ infine viene calcolato $d$: $d=e^{-1}\mathrm{mod}n$ Le chiavi finali risultano essere:

$$\begin{gathered} \text{displaylines}{k}_{priv}=[d,n] \\ {k}_{pub}=[e,n] \end{gathered}$$

La cifratura e la decifratura sono implementate come esponenziazioni modulari

$$E_{rsa}(x)=x^e\mathrm{mod}n$$ $$D_{rsa}(c)=x^d\mathrm{mod}n$$

E molto importante che nel caso $x>n$ questo venga frammentato per garantire una cifratura corretta

Ricerca numeri primi

Per implementare correttamente queste soluzioni e necessario trovare un’ implementazione efficiente per la ricerca di numeri primi

una possibile soluzione può essere

# numero random grande
int x = random.gen()
while(! primo(x)){ // test di primalita
x= x+2
}
return x

questa soluzione ha un tempo di esecuzione $o(ln(x))$

Test di primalità

Per ricercare un numero primo per la generazione dei segreti previsti per RSA e necessario definire un metodo per determinare se un dato numero e primo o meno, ci sono 2 metodologie per eseguire un test di primalità:

• deterministico più oneroso ma garantisce di trovare un numero primo
• probabilistico meno oneroso ma non c’e certezza di trovare un numero primo

Attacchi a RSA

L’algoritmo RSA e vulnerabile a diverse tipologie di attacco:

• Forza bruta: attacchi che sfruttano il numero n, la fattorizzazione del numeri primi, per evitare dobbiamo dividere in modo corretto la chiave.
• Attacchi matematici
• Attacchi a tempo: difficilissima da fare ma è stata dimostrata, esistono contromisure che possono essere adottate (es tecniche di padding)
• Attacchi a testo cifrato scelto: posso evitare se utilizzo il padding oaet (probabilistico)

Firma con RSA

RSA e un algoritmo di cifratura con recupero (e.g. che necessita di frammentare il messaggio e firmare i singoli pezzi), questo lo rende meno adatto a eseguire la firma di testi in quanto essa può essere trasportata da un file ad un altro se i blocchi sono identici.

Perché firmare con rsa: autenticazione a occhi chiusi

grazie alla proprietà moltiplicativa di RSA e vero che:

$$\begin{gathered} c=(m^{dU}\mathrm{mod}nU)=((m_1\ast m_2{)}^{dU}\mathrm{mod}nU)= \\ ((m_1^{dU}\mathrm{mod}nU)\ast (m_2^{dU}\mathrm{mod}nU){)}^{dU}\mathrm{mod}nU \end{gathered}$$

questo consente di implementare la cosiddetta autenticazione ad occhi chiusi, dove un nodo e in grado di firmare un messaggio senza conoscerne il contenuto

• X sceglie a caso un numero $r$ coprimo con $nT$
• Invia a T il testo cifrato $c_1=m{r}^{eT}\mathrm{mod}nT$
• T firma $c1$ e restituisce a X $c2=m^{dT}{r}^{eTdT}\mathrm{mod}nT=(m^{dT}r)\mathrm{mod}nT$
• X moltiplica $c2$ per $r^{-1}$: $c3=(m^{dT}r{r}^{-1})\mathrm{mod}nT=d^{dT}\mathrm{mod}nU$
• Il destinatario di $m$ può verificare che è autenticato da T: $(c3{)}^{eT}\mathrm{mod}nT=m$

questa proprietà può essere sfruttata da un attaccante per far firmare messaggi a una destinazione che altrimenti non li firmerebbe

PREVIOUS NEXT