La crittografia a chiave pubblica è così strutturata: Vi sono gli utenti: A, B, C,… Ogni utente dispone di una funzione di codifica EA, EB, EC,…che è resa pubblica. Ogni utente ha una funzione segreta di decodifica DA, DB, DC,… Un testo in chiaro T è diviso in blocchi; ogni blocco viene trasformato in un numero M che lo rappresenta esattamente. Il problema si riduce dunque a quello di inviare i numeri M. Le funzioni EA, EB, EC,… e le funzioni DA, DB, DC,…sono calcolate in modo da soddisfare la relazione DB(EB(M)) = M per ogni possibile M; in altre parole la funzione di decodifica D è la inversa della funzione di codifica E. Chi desidera inviare un messaggio M all'utente B, utilizza la funzione pubblica EB e invia a B il numero EB(M). L'utente B usa la sua funzione segreta DB e calcola DB(EB(M)) = M. Le funzioni EA, EB, EC,…sono molto particolari: vengono dette funzioni trappola a molla segreta. Come una trappola esse agiscono in una sola direzione: nessuno può calcolare M conoscendo EB(M), non si può tornare indietro, non si può calcolare la funzione inversa DB. Non servirebbero a nulla però se le DB fossero incomputabili in maniera assoluta; è qui che interviene la molla segreta: l'utente possiede una informazione segreta che gli permette di calcolare la DB. Esistono funzioni così strane? Oggi se ne conoscono molte. Un esempio assai importante per la crittografia odierna è dato dal metodo RSA. Il metodo RSA (Rivest, Shamir, Adleman) L'utente A sceglie n = pq con p e q primi grandi distinti, p < q. L'aggettivo grande dipende dalla potenza di calcolo dell'avversario. Oggi p e q devono avere un centinaio di cifre. Poi A sceglie e in C(j (n)) = C((p-1)(q-1)) e calcola il suo inverso d; sappiamo che d soddisfa alla: ed = 1 mod j (n). I numeri p, q, j (n) vengono cancellati. I numeri e, n sono resi pubblici. Il numero d è tenuto segreto. I messaggi sono rappresentati da numeri M < p. Sotto scriviamo la funzione trappola a molla segreta EA e la sua inversa DB. EA(M) = Me mod n DA(M) = Md mod n La conoscenza segreta è data dai primi p e q senza i quali non è possibile calcolare d (l'inverso di e modulo j (n)). Infatti j (n) non si può calcolare senza conoscere i fattori di n. Si noti che questa conoscenza segreta è cancellata per sempre e non può essere recuperata. Verifichiamo infine che vale davvero la relazione necessaria DB(EB(M)) = M per ogni possibile M. Per definizione DA(EA(M)) = DA(Me mod n) = Med mod n. Dal fatto che ed = 1 mod n segue che j (n) divide ed – 1. Quindi ed - 1 = kj (n), e infine possiamo dire che ed = kj (n) + 1 per un certo intero k. Allora: Med mod n = Mkj (n)+1 mod n = (per le usuali proprietà delle potenze) (Mj(n))k × M mod n = 1k × M mod n = M mod n = M Nell'ultima riga abbiamo usato il teorema di Eulero: Mj(n) = 1 mod n. La sicurezza del sistema RSA (uno dei più sicuri attualmente) si fonda sulla differenza enorme esistente tra due tempi di calcolo. Mentre esistono algoritmi che permettono in pochi secondi di trovare numeri primi di centinaia di cifre, e quindi è facile e veloce costruire la funzione trappola E, occorrerebbero secoli di calcolo su migliaia di computers ultraveloci per fattorizzare un intero grande. Del resto se il malintenzionato non riesce a trovare i fattori di n, non può trovare il numero segreto d che è l'unico che permette di costruire la funzione di decodifica D.