lunedì 3 maggio 2010

Alice, Bob e Eva — Perché Eva non riesce a decrittare

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:

mcd 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: