Protocollo Probabilistico
Sia M = M[1] M[2] .... M[h], n = p q (numeri primi) e sia y in PQ[n].
- Per i = 1, 2,..., h esegui
- Estrai un intero casuale r da Z[n];
- Se M[i] = 0, allora genera l’intero C[i] = r^2 mod n;
- Se M[i] = 1, allora genera l’intero C[i] = y r^2 mod n;
Si osservi che:
- se M[i]=0, allora C[i] è un residuo quadrato;
- se M[i]=1, allora C[i] è uno pseudo-quadrato.
r casuale --> no periodicità nella cifratura.
La chiave pubblica é la coppia (n,y).
Notare che 1 bit ---> log n bit nel msg cifrato.
Decifrazione <--> problema dei residui-quadrati
- Se si conosce la fattorizzazione di n, allora la decifrazione richiede tempo polinomale. Altrimenti è difficile decifrare (~ Quadrati VS Pseudo-quadrati).