Alice sceglie due primi molto grandi p e q e un numero a che non
abbia divisori in comune con p-1 e q-1 (cioè (a, p-1) = 1 = (a, q-1)). Sia n = pq.
La chiave pubblica di Alice è (n, a). Quindi tutti conoscono (n,
a) (è il nostro fA di prima)
Bob vuole spedire un testo m a Alice. Bob trasmette b con b = ma
(mod n) (cioè fA(m)
= b (mod n))
Quando Alice riceve b, per ricavare m usa il procedimento
precedente, cioè usa d tale che ad = 1 (mod p-1) e ad = 1 (mod q-1). Osservare che per
trovare un tale d bisogna conoscere p e q (d è la chiave privata di Alice, cioè fA*
con le notazioni precedenti)
Se il messaggio b cade nelle mani di Christine, Christine per
decifrarlo deve ricavare un d. Christine conosce b, a e n ma questo non basta !!!!
perchè qui sta il secondo fatto fondamentale:
FATTO 2:
Dato un numero intero n molto grande, è piuttosto difficile (anche usando un computer)
determinare la sua fattorizzazione in numeri primi.
"Piuttosto difficile" non significa impossibile,
significa soltanto che è molto improbabile che uno ci riesca in un tempo ragionevole, ma
non c'è nessuna certezza. Nello stesso modo non c'è nessuna certezza che uno non riesca
a ricavare m da b = ma ma è molto improbabile.
Questo tipo di crittosistema (chiamato RSA) usa i
"numeri dell'orologio" (le congruenze). Abbiamo visto che, tutto sommato, si
può calcolare con i "numeri dell'orologio" (quasi) come con i numeri normali.
I crittosistemi oggi più performanti ("crittosistemi
con curve ellittiche") non usano (solo) i "numeri dell'orologio" ma oggetti
ancora più strani: i punti di una curva...
Vediamo, senza entrare nei dettagli, l'idea di partenza
