Sistemi crittografici post-quantum su curve ellittiche = Post quantum cryptography over elliptic curves

Negli ultimi decenni la potenza di calcolo dei computer è raddoppiata ogni 18 mesi grazie ad una miniaturizzazione dei circuiti elettronici. Tuttavia essa si sta arrestando a causa del raggiungimento della soglia della meccanica quantistica. Per questo motivo molte università e aziende private stanno investendo nella ricerca riguardante il computer quantistico: IBM ha presentato nel 2019 il primo computer quantistico commerciale, e Google ha dichiarato di essere vicino alla costruzione del computer quantistico. Dalla nascita dei computer quantistici sorge anche un grande problema, cioè quellodella sicurezza informatica. I computer quantistici, infatti, sarebbero in grado di superare tutte le barriere della crittografia contemporanea, il che giustifica la grande attenzione verso lo sviluppo di nuovi protocolli crittografici resistenti ad attacchi da computer quantistici: la crittografia post quantum. L'interesse per i computer quantistici nell'ambito di questa tesi deriva dall'algoritmo pubblicato nel 1994 dall'informatico teorico statunitense Peter Shor in grado di fattorizzare gli interi in tempo polinomiale tramite l'utilizzo di un computer quantistico. Questo risulta essere un problema poiché molte crittografie tutt'ora utilizzate, come ad esempio RSA, basano la loro sicurezza sulla presunta difficoltà nella fattorizzazione di interi. Per questo motivo nel 2016 il NIST ha indetto una competizione per la determinazione di nuovi protocolli crittograficiche siano sicuri anche rispetto ad attacchi da computer quantistici. Una delle proposte in gara usa la crittografia sui grafi di isogenie di curve ellittiche, che saranno l’argomento principale di questa tesi. Nel lavoro svolto siamo quindi partiti dalla geometria proiettiva per definire le curve ellittiche, che sono curve molto utilizzate nel campo della crittografia per la struttura di gruppo che è possibile definire sui loro punti. Abbiamo analizzato due diverse forme in cui possono essere scritte tali curve: la forma di Weierstrass più classica e quella di Montgomery, particolarmente utile dal punto di vista computazionale. Successivamente si sono analizzate nel dettaglio le curve ellittiche su campi finiti, utili negli algoritmi utilizzati al giorno d’oggi, e le curve ellittiche sul campo dei numeri complessi, che permettono di ricavare importanti proprietà. Abbiamo inoltre presentato il classico protocollo di scambio chiavi di Diffie-Helmann su curve ellittiche e la sua implementazione Python. Nella seconda parte della tesi l’attenzione si è spostata sull’obiettivo di partenza, ossia la costruzione di algoritmi crittografici post quantum. A questo scopo si sono definite le isogenie e le loro proprietà, definendo anche le isogenie duali che permettono i cosiddetti grafi di isogenie, cioè particolari grafi i cui i nodi sono composti dalle curve ellittiche a meno di isomorfismi e gli archi sono le isogenie tradi esse. Tale struttura permette di definire nuovi protocolli crittografici post quantum; nella tesi ci siamo occupati del SIDH (Supersingular Isogeny Diffie Hellmann), che è un protocollo di scambio di chiavi su tali grafi. Anche di tale protocollo abbiamo implementato un rudimentale codice Phyton che lo esegue e che mostra passo per passo i cammini che i Alice e Bob devono compiere sul grafo applicando diverse isogenie per arrivare alla chiave condivisa.