La fattorizzazione usando la “phi” di Eulero

Oggi torniamo a parlare di fattorizzazione. Scopriremo infatti come fattorizzare il prodotto di due numeri primi conoscendo la “phi” di Eulero del loro prodotto.

Partiamo subito con un esempio. Supponiamo che un hacker di nome Oscar sia talmente bravo da riuscire a calcolare la “phi” di Eulero di un numero senza conoscere i suoi fattori primi.(Noi non sappiamo come faccia perché il metodo che usa Oscar è segreto e lo conosce solo lui). Supponiamo anche che Bob usi il cifrario RSA e che la sua chiave pubblica sia N = 2813 ed E = 5. Ecco come fa Oscar a calcolare i fattori primi di N = 2813:

• Oscar sa che il numero N che compare nella chiave pubblica dell’ RSA è il prodotto di due numeri primi. Detto in altre parole, l’obiettivo di Oscar è trovare due numeri primi P e Q tali che 2813 = P x Q
• Oscar usa il suo metodo segreto per calcolare la “phi” di Eulero di 2813. Il risultato è Phi(2813) = 2688.
• Siccome 2813 = P x Q, la “phi” di Eulero di 2813 è anche uguale a Phi(2813) = (P x Q) – P – Q + 1 = 2813 – P – Q + 1. (Qui Oscar ha usato la formula per calcolare la “phi” di Eulero del prodotto di due numeri primi)
• Mettendo insieme le formule dei due punti precedenti, Oscar scopre che 2688 = 2813 – P – Q + 1.
• Dopo alcuni conti (che non svolgiamo ma che risultano abbastanza semplici), Oscar scopre che P² – (126 x P) + 2813 = 0
• Siccome P² – (126 x P) + 2813 = 0 è un’ equazione di secondo grado ad una incognita (la P):
  • Oscar calcola il “delta” della sua equazione di secondo grado. Il risultato è Delta = sqrt(126² – (4 x 2813)) = sqrt(15876 – 11252) = sqrt(4624) = 68
  • Oscar calcola P = (126 – 68)/2 = 58/2 = 29
• Oscar calcola Q = N/P. Il risultato è Q = 97, e questo significa che 2813 = 29 x 97.

Il nostro articolo termina qui. Ovviamente scrivete nei commenti se avete dubbi o domande a riguardo. Buona crittografia! xD