Index calculus sul gruppo dei punti di una curva ellittica

Abstract

Il problema del logaritmo discreto su una curva ellittica (ECDLP) garantisce la sicurezza di diversi crittosistemi utilizzati in crittografia. Uno dei possibili attacchi all’ECDLP è l’Index Calculus, una famiglia di algoritmi che opera in due passi principali: uno di collezione di relazioni e uno di algebra lineare. Dall’introduzione da parte di Igor Semaev di quelli che sono noti come polinomi di sommazione o di Semaev, strumento utile nella ricerca delle relazioni, sono state proposte diverse varianti di Index Calculus. Lo scopo di questa tesi è lo studio di alcune di queste varianti. Nell’ultimo capitolo sono presentate due implementazioni in linguaggio C++ di algoritmi di Index Calculus per curve definite su campi di cardinalità prima, proposti rispettivamente da Petit, Kosters e Messeng e da Amadori, Pintore e Sala. Per arrivare a ciò, ho realizzato un programma che svolge le operazioni di base su una curva ellittica e mi sono avvalsa degli strumenti algebrici disponibili nella libreria di CoCoA. I primi due capitoli espongono i preliminari necessari riguardanti le curve ellittiche e la risoluzione di sistemi polinomiali, mentre il terzo capitolo è riservato all’ECDLP, le sue applicazioni e alcuni possibili attacchi. Gli ultimi tre capitoli sono la parte centrale della tesi, con lo studio degli algoritmi di Index Calculus, l’analisi dei risultati ottenuti dai test effettuati e la spiegazione delle implementazioni.

Several cryptographic shemes base their security upon the hardness of the elliptic curve discrete logarithm problem (ECDLP). An Index Calculus algorithm is an attack on ECDLP that consists in two main steps: a relation collection step and a linear algebra step. Since the introduction by Igor Semaev of summation polynomials, a useful tool in finding relations, several variants of Index Calculus have been proposed. The purpose of this thesis is to study some of these variants. In the last chapter, two C++ implementations of Index Calculus algorithms for curves defined over prime fields are presented, respectively proposed by Petit, Kosters and Messeng, and by Amadori, Pintore and Sala. To achieve this, I have developed a program that performs basic operations on an elliptic curve and I have taken advantage of the algebraic tools available in the CoCoA library. The first two chapters provide the necessary prerequisites concerning elliptic curves and the resolution of polynomial systems, while the third one is dedicated to ECDLP, its applications and some possible attacks. The last three chapters are the core of the thesis, covering the study of the Index Calculus algorithms, the analysis of the results obtained from the conducted tests and the explanation of the implementations.