Le funzioni a senso unico
Una funzione a senso unico è una funzione matematica che è facile da calcolare in una direzione, ma difficile da invertire senza informazioni aggiuntive.
In altre parole, se ho una funzione \( f : X \rightarrow Y \), è semplice calcolare \( f(x) \) per un dato \( x \), ma è computazionalmente difficile trovare un \( x \) tale che \( f(x) = y \) per un dato \( y \) tranne quando dispongo di specifiche informazioni, come una chiave segreta.
Queste funzioni sono fondamentali nella crittografia, in particolare nella crittografia a chiave pubblica.
La sicurezza di molti sistemi crittografici dipende dalla difficoltà pratica di invertire queste funzioni senza conoscere la chiave segreta, anche se teoricamente è possibile farlo.
Ad esempio, la moltiplicazione di due grandi numeri primi è facile, ma il problema del factoring, ovvero trovare i fattori primi di un grande numero intero, è molto difficile e richiede un tempo molto lungo con i migliori algoritmi noti su computer classici. Questo è il principio alla base di algoritmi come RSA. Un altro esempi di funzione a senso unico sono i logaritmi discreti.
Un esempio pratico
Un classico esempio di funzione a senso unico è la moltiplicazione di due numeri primi utilizzata nell'algoritmo RSA, un algoritmo di crittografia a chiave pubblica.
La funzione è molto facile da calcolare in una direzione, quella della cifratura.
Scelgo due grandi numeri primi, p e q, e calcolo il loro prodotto n=p⋅q.
$$ n = p \cdot q $$
Il numero n viene utilizzato come parte della chiave pubblica.
Conoscendo la chiave pubblica, chiunque può cifrare un messaggio utilizzando una funzione matematica che include la moltiplicazione modulo n.
D'altra parte, la funzione è molto difficile nella direzione inversa, quella della decifratura.
Senza conoscere i valori di p e q, il tentativo di decifrare un messaggio cifrato richiede di fattorizzare n per recuperare p e q.
Questo è detto problema del factoring, che per numeri molto grandi diventa estremamente difficile.
Solo chi ha la chiave privata, che contiene le informazioni sui valori di p e q, può farlo facilmente.
E così via
