CUDA Based Implementation of Parallelized

CUDA based implementation of parallelized

Pollard’s Rho algorithm for ECDLP

M. Chinnicia , S. Cuomob, M. Laportab, S. Migliori c, B. Pennacchiob, A.Pizziranib

a ENEA-FIM, Portici Research Center, Via Vecchio Macello – Loc. Granatello – 80055 Portici (Napoli) , Italy

b UNIVERSITA’ FEDERICO II, Dipartimento di Matematica e Applicazioni”R.Caccioppoli” Via Cinthia –80136 Napoli , Italy

c ENEA- FIM, Enea Sede, Lungotevere Thaon di Revel n. 76 - 00196 Roma, Italy

E-mail:

ABSTRACT

In many applicative contexts such as fluid dynamics, molecular dynamics, computer vision and astrophysics the resolution kernels require intensive use of computational resources. Recent introduction by NVidia of CUDA (Compute Unified Device Architecture) libraries for High Performance Computing (HPC) on Graphic Processing Units (GPUs) has started the trend to use video cards as performance environment. This framework can be introduced also in the cryptanalysis research. In this paper we show how CUDA libraries can be used in cryptography as analysis tool. The increase of data communications made data cryptography a real necessity. In certain cases the private key cryptosystems can suffice; however public key cryptosystems are often needed for communications on insecure channels. Cryptosystems based on elliptic curves offer both schemas (public and private) with a relatively low communication overhead. In elliptic curves cryptography security is strongly based on presumed intractability of DLP (Discrete Logarithm Problem) in group of points of elliptic curve. Thus, testing resistance of ECDLP (Elliptic Curves Discrete Logarithm Problem) means testing their security. In literature various methods (more or less efficient) to solve instances of DLP are known, some of them with deterministic running time, like Shank’s ”Baby step-Giant step”, others with probabilistic running time but with a better trade-off between space and time, like Pollard’s Rho method. We describe, in ENEA-GRID middleware, an implementation of parallelized Pollard’s Rho attack for ECDLP, realized using recent results for optimization of Pollard’s Rho method and some ”ad-hoc” devices for CUDA.