Numeri primi e crittografia

Verrà presentato lo sviluppo storico della Crittografia, introducendo via via le nozioni matematiche (numeri primi, aritmetica modulare, algoritmi della Teoria dei Numeri) necessarie per la Crittografia moderna a chiave pubblica (in particolare del Sistema RSA). Si mostra come la sicurezza dell’RSA sia basata sulla difficoltà della fattorizzazione in primi di un dato intero. A questo punto si parla di numeri primi, di distribuzione dei numeri primi, di test di primalità e di algoritmi per la fattorizzazione in primi e si vede come l’aumento della potenza dei calcolatori non costituisce una minaccia per il sistema, ma piuttosto il contrario. Si trae spunto da questi problemi per fare qualche accenno sulla complessità degli algoritmi. Si assegnano ai ragazzi interessati esercizi di aritmetica modulare, ma anche esercizi di implementazione di un mini-sistema crittografico RSA, con generazione delle chiavi pubblica e privata, cifratura di un messaggio da trasmettere ad altri, decifrazione di un crittogramma ricevuto da altri, firma digitale. Il laboratorio ha una forte valenza interdisciplinare, in quanto si presta ad essere sviluppato in collaborazione tra insegnanti di matematica e di informatica, ma può anche fornire spunti di collaborazione con gli insegnati di storia, in particolare per quel che riguarda il ruolo avuto dalla crittografia nella seconda guerra mondiale.