Funzioni "a senso unico"

Nell'espressione b = m^a (a, b e m interi positivi, m > 1), supponiamo di conoscere b e a, come facciamo a ricavare m?

Per esempio: m⁷ = 2187

In qualche modo m è una radice, non quadrata, ma "settima" di 2187..... Certo m⁸ = 6561 sarebbe stato più facile perchè m⁸ =(m⁴ )², quindi m⁴ è la radice quadrata di 6561 cioè 81, poi m⁴ =(m² )², quindi m² è la radice quadrata di 81, cioè 9 e finalmente m=3.

Teoricamente la risposta è facile. La funzione esponenziale, exp_m , è la funzione che al numero a associa m^a  (exp_m(a)= m^a). La funzione inversa è il logaritmo log_m(exp_m(a))=log_m(m^a) = a . Quindi m è quel numero tale che log_m(2187)=7.

(Questo non ci aiuta molto a calcolare m ma serve a spiegare la terminologia successiva)

Nell'esempio: 3⁷=2187 e se avete una piccola calcolatrice tascabile potete verificare che log₃(2187) = ln(2187)/ln(3) = 7 (qui ln(x) indica il logaritmo "usuale", quello appunto che si trova sulle calcolatrici tascabili e che, forse, conoscete già).

FATTO 1: Il fatto è che conoscendo b e a è comunque difficile (anche con un computer se i numeri sono abbastanza grandi) ricavare m dall'espressione b = m^a (questo si chiama il problema del "logaritmo inverso").

La cosa però non deve essere completamente impossibile, altrimenti il ricevente non riuscirà a decifrare il messaggio...

Infatti c'è una situazione nella quale, con una piccola informazione supplementare (la chiave privata) si riesce a calcolare il logaritmo. Per questo però bisogna usare le congruenze (o "numeri dell'orologio") e i numeri primi. In caso di bisogno potete consultare il link congruenze (o "numeri dell'orologio")e il link  numeri primi.

Siano adesso p e q  due numeri primi molto grandi e poniamo n = pq.

Il problema diventa: sia b = m^a (mod n), conoscendo b e a, determinare m  (possiamo assumere m < n)

C'è una circonstanza in cui questo è fattibile ed è quando a   non ha divisori comuni (tranne 1) con p-1 e con q-1                                             (si indica questa situazione con (a, p-1)=1=(a, q-1) e si dice che a e p-1 (risp. a e q-1) sono primi tra di loro)

In questo caso si procede così:

• Si trova d tale che ad = 1 (mod p-1) e ad = 1 (mod q-1) (questo si fa facilmente)

• Si calcola b^d, viene b^d= m (mod n) e abbiamo trovato m

Chi è curioso di vedere perchè b^d= m (mod n) può cliccare qui.

Adesso abbiamo tutto quello che ci serve...