S-scatole resistenti alla criptanalisi lineare e differenziale

Introduzione Se il Mondo fosse popolato esclusivamente da persone oneste, non avrebbe al- cun bisogno dei criptografi e dei loro espedienti per mantenere ad un livello di sicurezza accettabile le comunicazioni di dati riservati. Dato che la disonestà è una realtà fin dai tempi più antichi, parallelamente al progredire della civiltà umana sono stati sviluppati metodi sempre più ingegnosi per proteggere le informazioni riservate, come di pari passo sono state sviluppate strategie per infrangere le difese messe in essere dai criptografi. Nata principalmente per soddisfare le esigenze di segretezza nelle comuni- cazioni di piani militari, la criptografia è ormai entrata a far parte della quo- tidianità nella vita civile: carte di credito, bancomat, posta elettronica; un codice numerico od alfanumerico protegge ciò che non deve essere conosciuto od utilizzato da estranei. I criptosistemi di questo tipo sono detti criptosistemi a chiave segreta (o pri- vata, o simmetrica) e nella maggior parte dei casi la loro sicurezza si basa su quel- la delle loro uniche componenti non lineari: le S-scatole, applicazioni costruite in modo da nascondere opportunamente la relazione matematica che intercorre fra i testi veri, la chiave usata per cifrare ed i testi cifrati corrispondenti. Due metodi diffusi e potenti per insidiare la sicurezza di un criptosistema costruito a partire da S-scatole sono la criptanalisi lineare e la criptanalisi diffe- renziale ed i valori di uniformità differenziale ed uniformità non lineare associati ad una data S-scatola sono comunemente impiegati per misurarne la resistenza locale contro la criptanalisi differenziale e lineare, rispettivamente. Di conseguenza è interessante chiedersi quali siano in generale i valori minimi possibili per l'uniformità differenziale e l'uniformità non lineare delle S-scatole: in questa tesi si dimostra che i due valori non possono essere inferiori ad 8 ed esistono S-scatole per cui sono entrambi uguali a 12. Nel progettare S-scatole è inoltre utile disporre di un algoritmo che generi efficientemente applicazioni per cui entrambi questi valori siano piccoli, cioè che generi S-scatole con buona resistenza nei confronti della criptanalisi differenziale e della criptanalisi lineare. Una S-scatola si può rappresentare come una permutazione composta, dove con permutazione composta si intende un'applicazione da r+n bits a n bits, tale che per ogni possibile scelta degli r bits di selezione si ottenga una permutazio- ne da n a n bits. Obiettivo di questa tesi è presentare un metodo iterativo per costruire permutazioni composte con valori di uniformità differenziale e unifor- mità lineare bassi : viene definita una relazione di equivalenza fra permutazioni e vengono calcolati i corrispondenti rappresentanti delle classi di equivalenza, un sottoinsieme di questi si usa come input per l'algoritmo di costruzione. 5