Sistema RSA (1977)
Sia f(n) la funzione di Eulero (# interi primi con n);
Si considerino due numeri primi p e q di 150 cifre;
I parametri del sistema RSA sono settati come segue:
- K[priv] = (p, q, d) dove n = p*q, mcd(d, f(n))=1;
- K[pub] = (e,n) dove e * d = 1 mod f(n);
Test primalità --> polinomiale randomizzato;
Fattorizzazione --> forse nemmeno in RP;
Sicurezza <--> contrasto tra “test primalità” e “fattorizzazione”;
Problema: Dato y=x^e mod n, trovare x è facile se n è primo (Rabin, 80), altrimenti risulta difficile quanto la fattorizzazione di n.
La chance che due utenti calcolino gli stessi (p,q) è molto bassa.
Dato un messaggio M, si procede come segue:
- M viene diviso in blocchi M[1],..., M[h] di log n bit ciascuno.
- Cifrare un blocco M[i] significa calcolare C[i] = M[i]^e mod n ;
- Decifrare un blocco C[i] significa calcolare C[i]^d mod n ;
Veloce fattorizzazione --> RSA forzato.
Approcci suggeriti sono falliti oppure hanno portato ad un algoritmo veloce per la fattorizzazione (non è nota l’equivalenza).