Chiave pubblica (n,e) = (9017,251),
Messaggio cifrato c = 6543.
Eva vuole decrittare il messaggio senza conoscere la chiave privata. Per prima cosa scompone n:
n = 71·127.
Di conseguenza può calcolare φ(n) = 70·126 = 8820.
Grazie a φ(n) può dare inizio alla procedura per calcolare d, che deve essere tale per cui ed ≡ 1 mod 8820. L'equazione diofantea da risolvere è la seguente:
251d - 8820k = 1.
Si esegue la divisione con resto 8820/251:
8820 = 251·35 + 35.
Si sostituisce 8820 e si raccoglie:
251d - (251·35 + 35)k = 1,
251(d - 35k) - 35k = 1.
Indichiamo con A l'espressione tra parentesi d-35k:
251A - 35k = 1
Ora si può ripetere il procedimento. Si esegue la divisione con resto 251/35:
251 = 35·7 + 6.
Si sostituisce 251 e si raccoglie:
(35·7 + 6)A - 35k = 1,
35(7A - k) + 6A = 1.
Indichiamo con B l'espressione tra parentesi 7A - k, e ricominciamo (anche se si vede già il risultato: B = -1, A = 6).
35B + 6A = 1.
Si esegue la divisione con resto 35/6:
35 = 6·5 + 5.
Si sostituisce 35 e si raccoglie:
(6·5 + 5)B + 6A = 1,
6(5B + A) + 5B = 1.
Indichiamo con C l'espressione tra parentesi 5B + A, e ricominciamo (anche se si vede già il risultato: C = 1, B = -1).
6C + 5B = 1.
Si esegue la divisione con resto 6/5:
6 = 5·1 + 1.
Si sostituisce 6 e si raccoglie:
(5·1 + 1)C + 5B = 1,
5(C + B) + C = 1.
A questo punto C ha coefficiente 1 e tutti (compresi i calcolatori) vedono la soluzione: C + B = 0, C = 1.
Ora si eseguono le sostituzioni all'indietro:
C = 1,
C + B = 0, B = -C, B = -1,
5B + A = C, A = C - 5B, A = 1 + 5, A=6,
7A - k = B, k = 7A - B, k = 42 + 1, k = 43,
d - 35k = A, d = 35k + A, d = 35·43 + 6, d = 1511.
Finalmente è stato trovato d, ora si può decrittare il messaggio:
m ≡ cd mod n = 65431511 mod 9017 = 102.
“Quanti calcoli!”.
“Bè, ma li fanno i calcolatori, mica si fanno a mano”.
“E non è facile per Eva, con calcolatore alla mano, decrittare il messaggio? Perché in questo esempio ci siamo riusciti, mentre nella realtà non ci si riesce?”.
“Ti rispondo con una domanda: hai notato su cosa si basa la ricerca di d?”.
“Sulla definizione di d, suppongo: d è tale per cui ed è congruente a 1 modulo φ(n)”.
“Quindi, dato che e è pubblico, riesci a calcolare il valore di d se conosci φ(n)”.
“Giusto”.
“Supponi allora che esista un metodo veloce per calcolare φ(n) a partire da n. Sapendo che n è il prodotto di due numeri primi p e q (che Eva non conosce), si possono fare i calcoli seguenti:”.
φ(n) = (p - 1)(q - 1) = pq - (p + q) + 1 = n - (p + q) + 1.
“Ok, ma a cosa mi serve?”.
“Ricordati che le incognite sono p e q. Dall'equazione che abbiamo appena scritto possiamo ricavare p + q:”.
p + q = n - φ(n) + 1.
“E quindi?”.
“Dato che già conosciamo il prodotto pq = n, ora siamo in possesso di due dati: la somma di due numeri e il loro prodotto. Un problema che sanno risolvere gli studenti di seconda superiore è proprio quello della ricerca di due numeri conoscendone la somma e il prodotto”.
“Ah, è vero, basta risolvere un'equazione di secondo grado. Se indichiamo con S la somma e con P il prodotto dei due numeri da trovare, l'equazione da risolvere è x2 - Sx + P = 0”.
“Esatto. Quindi potremmo trovare facilmente p e q, cioè potremmo fattorizzare n. Riassumendo: se Eva fosse in grado di calcolare in modo veloce φ(n), allora sarebbe anche in grado di fattorizzare velocemente n. Dato che ad oggi non è noto un metodo veloce per fattorizzare, allora non è noto nemmeno un metodo veloce per trovare φ(n)”.
“Mh, una specie di dimostrazione per assurdo”.
“Sì, una specie, perché non è un teorema. Il fatto che ad oggi non sia noto un metodo per fattorizzare, o per trovare φ(n), non significa che in futuro non lo si possa trovare”.
“O che qualche organizzazione di controspionaggio non lo conosca già, ma lo tenga segreto”.
“Se è così, è un segreto molto ben custodito”.
Nessun commento:
Posta un commento