La risposta è: BO! Nel senso che non si sa se ciò sia equivalente a fattorizzare n. Comunque non c'è ancora arrivato nessuno.
Ma ci sono anche altri attacchi, che ora vedremo.
Chosen Ciphertext Attack
Sono nello scenario chosen ciphertext, il che vuol dire che l'attaccante può farsi decifrare un testo a sua scelta.
Orbene: se M è il messaggio, l'attaccante si fa cifrare il messaggio C * xe, ed è in grado di ottenere la decifratura di M.
Infatti, decifrando C * xe avrei:
M = (C * xe^)'^d = Med*xed = M * x mod n
Quindi, avendo in mano Mx mod n, divido per x (ovvero moltiplico per x-1, e lo so fare perché conosco x e n) e ottengo M a partire dalla sua cifratura.
Common Modulus Attack
Se ci sono due persone, la cui chiave contiene lo STESSO n, e ad entrambe viene inviato lo STESSO messaggio M, allora un attaccante è in grado di risalire ad M senza avere la chiave, ma avendo solo i due messaggi cifrati C1 e C2.
Quello che ha in mano è:
C1 = Me1 mod n
C2 = Me2 mod n
dove C1 e C2 sono i cifrati mandati al primo e al secondo personaggio, rispettivamente, e e1 ed e2 sono la loro chiave pubblica: {e1, n}, {e2, n}. Abbiamo infatti detto qui sopra che siamo nel caso in cui due persone abbiano la stessa n.
Quindi, tramite l'algoritmo di Euclide esteso (è esteso l'algoritmo, non Euclide!) l'attaccante è in grado di calcolare due numeri r ed s che abbiano la seguente proprietà:
e1*r + e2*s = 1 mod n
Euclide esteso calcola ciò in un botto solo.
Con in mano questi valori, si fa poi:
C1r * C2s= (Me1)r * (Me2)s = Me1r + e2s'^ mod n = M'^1 = M mod n
Infatti, abbiamo detto sopra che e1*r + e2*s = 1 mod n.
Low Exponent Attack
Questo è invece il caso in cui diverse chiavi pubbliche hanno lo stesso valore e, e hanno le rispettive n prime tra di loro. Occorre poi che lo stesso messaggio M venga inviato ai vari utenti.
Utilizzando il teorema cinese del resto è possibile risolvere questo sistema:
x = C1 mod n1
x = C2 mod n2
x = C3 mod n3
x = M3 mod n1n2n3 => poi calcolo M = x1/3
Non sto qui a dimostrare perché funziona, perché dovrei conoscere il teorema cinese del resto, ma si dà il caso che non lo conosca:)
Informazioni parziali
La domanda è: guardando C, sono in grado di dire qualcosa su di M?
Ci sono due cose che sarebbe interessante sapere: se M è più lungo o più corto della metà di n (ricordo che comunque M < n), oppure se è pari o no.
Ebbene, è stato dimostrato che calcolare queste due cose, ovvero rispondere con un SI o con un NO alle domande qui sopra, è equivalente a invertire RSA, cioè fattorizzare n, quindi computazionalmente impossibile.
Attacchi ad implementazioni
Sono due attacchi particolari, che riguardano le implementazioni di RSA in hardware.
Il primo attacco è detto timing attack: se un attaccante è in grado di osservare quanto tempo ci mette un calcolatore di velocità nota a produrre i risultati quando calcola i vari valori di RSA, è in grado di risalire alla chiave privata.
Lo stesso avviene per il power attach: se l'attaccante è in grado di monitorare il consumo di corrente di un processore che calcola RSA (ricordando che per calcoli complessi l'uso di corrente sale), allora può risalire alla chiave privata.
Per proteggersi da ciò basta introdurre dei calcoli casuali qua e là per sbarellare le osservazioni.
