OPTIMIZED REPRESENTATIONS IN CRYPTOGRAPHIC PRIMITIVES

This work focuses on optimization of cryptographic primitives both in theory and in applications. From a theoretical point of view, it addresses the problem of speeding up the polynomial multiplication used in Post-Quantum cryptosystems such as NTRU and McEliece. In particular, the latter extensively uses Galois fields whose elements can be represented in polynomial form. After presenting the reduction of the number of gates for polynomial multiplication through new techniques, in this work experimental results of such techniques applied to the current implementation of McEliece will be presented. From a practical point of view, this work focuses on the optimization of a SAT solver-based preimage attack against SHA-1 and on its strength. None of the tested representations of SHA-1 seems to be competitive in terms of resolution. On the contrary, an accurate choice of some pre-image bits allows one to reach a better state of art, revealing meanwhile the weakness of some pre-images.

Il lavoro di tesi si focalizza sull'ottimizzazione di primitive crittografiche sia dal punto di vista teorico che da quello pratico. Riguardo il punto di vista teorico sarà analizzato il problema dell'accelerazione degli algoritmi di moltiplicazione polinomiale, ampiamente impiegati in Crittografia Post-Quantum, come, ad esempio, NTRU e McEliece. Quest'ultimo, in particolare, utilizza campi di Galois e loro estensioni, i cui elementi possono essere rappresentati in forma polinomiale. Saranno dunque esposte nuove tecniche che permettono una riduzione del numero di porte logiche e verranno presentati i risultati sperimentali della loro applicazione all'implementazione del cifrario McEliece attualmente candidato come nuovo standard Post-Quantum al NIST. Dal punto di vista pratico, questo lavoro di tesi, si focalizza sull’ottimizzazione di attacchi alla prima pre-immagine dell'algoritmo di hash SHA-1 basati su SAT solvers. Nessuna delle rappresentazioni testate ha mostrato una particolare efficienza in termini di velocità di risoluzione. Al contrario, un'accurata scelta di valori ha permesso di raggiungere un nuovo stato dell'arte, rivelando al contempo la debolezza di alcune pre-immagini.