Problemi di razionalità di tori algebrici e applicazioni alla crittografia

Introduzione Prima dell’avvento di internet, la scienza che si occupava di inviare messaggi al riparo da occhi indiscreti era segregata a meri scopi militari, anzi molto spesso gli stessi scopritori di nuovi sistemi sicuri per comunicare venivano obbligati a mantenere il segreto, con l’inevitabile conseguenza che le scoperte non venivano loro riconosciute. Simile destino e` toccato ad Alan Turing, ideatore dell’informatica moderna, che durante la Seconda Guerra Mondiale e` riuscito a decifrare i messaggi delle forze tedesche, ma del quale non si e` saputo nulla fino agli anni Settanta. Al giorno d’oggi, pero`, gli interessi dietro alla protezione delle comunicazioni sono usciti in modo prepotente dall’ambito militare, grazie alla rapidissima diffusione del World Wide Web, meglio conosciu- to come internet. Attraverso la rete possiamo comunicare, trovare informazioni, conoscere nuovi amici e anche gestire conti bancari o fare acquisti con la nostra carta di credito. In questi ultimi aspetti en- tra in gioco quella scienza che si occupa di nascondere le informazioni private agli occhi indiscreti: la crittografia. La vera rivoluzione in questo ambito si e` avuta nel 1976, quando Diffie e Hellman inventarono la crittografia a chiave pubblica. In pratica i due ricercatori hanno risolto l’annoso problema dello scambio di chiavi: prima di essi, il mittente e il destinatario legittimo del messaggio dovevano accordarsi preventi- vamente sul procedimento utilizzato per cifrare e decifrare. Con la chiave pubblica, invece, il destinatario comunica al mittente la sua chiave pubblica, che il mittente usera` per celare il messaggio, dopo di che nemmeno lui potra` riottenerne il contenuto, perche` per decifrare il testo dovra` essere usata una chiave, differente dalla prima, custodita gelosamente dal destinatario. Come e` possibile ottenere questo risultato nella pratica? Basta trovare un problema matematico appartenente alla categoria NP-completo, ovvero un’operazione facile da compiere in un senso, che risulta pero` molto difficile nell’altro. Ad esempio dati due numeri primi (diciamo 37 e 97)e` molto facile trovare il loro prodotto. Invece dato il loro prodotto (3589)none` per niente facile risalire ai numeri di partenza, nonostante il teorema fondamentale dell’aritmetica ci assicuri che sono unici. In questo caso, per chiarire l’idea, la chiave pubblica e` 3589 e la chiave privata e` uno qualsiasi dei suoi fattori primi (37 o 97), avendo uno dei quali si riesce a ricavare il secondo. Uno dei problemi di questo tipo piu` diffusi e utilizzati per i cifrari moderni e` il logaritmo discreto. Dati tre numeri p, q, r, si tratta di trovare un intero a tale che p a r mod q.