Pizzirani, Alberto (2014) New experiments for cryptanalysis on elliptic curves. [Tesi di dottorato]

Anteprima

Testo Pizzirani_Alberto_25.pdf Download (1MB) | Anteprima

Abstract

The work of this thesis is focused on improving some tools commonly used for cryptoanalytical applications on elliptic curves, and some of them can be applied also when performing modular arithmetic in a more general context than the cryptological one. In chapter 1 it is given an introduction to the NVidia CUDA programming model and described some problems that can appear while writing code that must run on graphic processing units. In chapter 2 it is described a full implementation for single-instruction multiple-data architectures of a fast modular arithmetic library, with emphasis on the modular inversion. It is presented a variant of the Stein's algorithm that reduces divergence among thread and allows to consider it as a good alternative (for sufficiently big prime fields) to the branch-free algorithm based on Euler-Fermat theorem. In chapter 3 it is discussed the Rho-Pollard implementation for single-instruction multipledata architectures that uses the negation maps. It is presented also a variant of the classical iterating function of the Rho-Pollard algorithm to reduce the overhead to check for fruitless cycles. Chapter 4 contains the description of an experimental work performed on SAGE and aimed to apply the Smart's attack on anomalous elliptic curves (defined on prime fields) to a curve defined over a ring Zn1n2 with n1n2 points. To realize these experiments, the author, implemented into SAGE a complete system of addition laws for elliptic curves over rings, and the functions to perform arithmetic on polyadic numbers.

Downloads

Actions (login required)

Modifica documento