Rompere la codifica RSA

Partiamo dal fatto che l’algoritmo RSA genera una chiave pubblica ed una chiave privata partendo da due numeri primi: p e q. La chiave pubblica è composta dalla coppia di numeri (E, N), dove N = p * q.

F è il toziente di N, che per le proprietà moltiplicativa è dato dal toziente di p moltiplicato il toziente di q. Per un numero primo a, il toziente è a-1, quindi F = (p-1)(q-1).

E è un numero coprimo di F, coprimo significa che E ed F non hanno divisori comuni, eccetto il valore 1, quindi il Massimo Comun Divisore MCD(E, F) = 1.

Dato che la chiave è pubblica, il valore N è conosciuto da chiunque e lo si può utilizzare per ricavare i due fattori p e q di partenza. Fattorizzare un numero primo di grandi dimensioni è computazionalmente difficile, ma se i due numeri di partenza sono vicini, ci può aiutare il “piccolo teorema di Eurelo-Fermat”.

Notiamo prima una cosa: se p e q sono vicini, allora posso approssimare entrambi al valore M e dire che N = M * M, la cui la soluzione è M (radice di N). Il valore M è stato approssimato, ma possiamo dire che il valore preciso si trova nelle vicinanze.

Secondo il Metodo di Fermat, se riesco a scrivere il numero N come differenza di due quadrati, cioè N = A^2 - B^2, allora ho trovato una fattorizzazione di |N| = (|A-B|)(|A+B|). Fattorizzare N significa trovare i due valori A e B.

Secondo il Metodo di Fermat, se N è fattorizzabile come p * q, allora N = A^2 - B^2 = (A-B)(A+B) con A = 1/2(p+q) e B = 1/2(|p-q|).

Per rompere RSA quando p e q sono vicini, posso scrivere l’equazione di Fermat come B^2 = A^2 - N e prendere il valore N dalla chiave pubblica. A questo punto, partendo da K = radice di N e proseguendo, incrementando di volta in volta il valore di K, posso calcolare il valore B^2 = K^2 - N. Se la radice di A è un valore intero, ho trovato sia A che B e quindi posso scrivere N = (A-B)(A+B).

B	B^2	A^2 = B^2 - N	sqrt(A^2)	A