PDF de programación - Multiplicación Escalar en Curvas de Koblitz: Arquitectura en Hardware Reconfigurable

Centro de Investigaci´on y de Estudios

Avanzados

del Instituto Polit´ecnico Nacional

Departamento de Ingenier´ıa El´ectrica

Secci´on Computaci´on

Multiplicaci´on Escalar en Curvas de Koblitz:

Arquitectura en Hardware Reconfigurable

Tesis que presenta

Juan Manuel Cruz Alcaraz

para obtener el Grado de

Maestro en Ciencias

en la Especialidad de

Ingenier´ıa El´ectrica

Director de la Tesis

Dr. Francisco Rodr´ıguez Henr´ıquez

M´exico, D. F.

Noviembre 2005

ii

Resumen

En 1985, Victor Miller y N. Koblitz propusieron un criptosistema de llave
p´ublica an´alogo al esquema de El Gamal en el cual el campo GF(2m) es
substituido por el grupo de puntos en una curva el´ıptica definida en un campo
finito. La operaci´on b´asica es la multiplicaci´on escalar, la cual est´a definida
como el m´ultiplo entero de un punto dado sobre la curva.

Koblitz introdujo una familia de curvas que admiten multiplicaciones es-
calares especialmente veloces. En 1998 Jerome A. Solinas presenta versiones
mejoradas de los algoritmos existentes para multiplicaci´on escalar sobre cur-
vas Koblitz donde es posible generar una expansi´on del factor escalar cono-
cida como τ NAF la cual reemplaza las operaciones de doblado de puntos por
exponenciaciones cuadr´aticas.

En esta tesis se presenta una implementaci´on en hardware reconfigurable
de los algoritmos propuestos por Solinas en la cual, bas´andose en las venta-
jas presentadas proporcionadas por las curvas Koblitz, se logran desempe˜nos
competitivos en comparaci´on con resultados previamente reportados con
otras t´ecnicas para el c´alculo de multiplicaci´on escalar en ECC.

Se propone una arquitectura de multiplicaci´on compuesta por dos unidades
aritm´eticas independientes (campos finitos y aritm´etica entera). Un bloque
de memoria compartida es usado para comunicar resultados intermedios. Se
presentan su implementaci´on en VHDL y su respectiva s´ıntesis sobre un dis-
positivo FPGA Xilinx XC2V4000 as´ı como resultados en tiempos de ejecuci´on
de una multiplicaci´on escalar y recursos utilizados del dispositivo.

iii

iv

Abstract

In 1985, Victor Miller and N. Koblitz proposed a public key cryptosystem
analogous to ElGamal scheme, where the finite field GF(2m) is replaced by
the group of points in an elliptic curve defined over a finite field. The basic
operation is scalar multiplication, defined as an integer multiple of a point in
the curve.

Koblitz introduced a familiy of curves which admit especially fast elliptic
scalar multiplication. In 1998 Jerome A. Solinas presented improved versions
of the available algorithms for computing the scalar multiplication in Koblitz
curves. These algorithms represent the scalar factor as an expansion known
as τ NAF. This expansion allows to replace doubling point operations with
quadratic exponentiations.

This thesis presents a reconfigurable hardware implementation based in
the algorithms proposed by Solinas. This arquitecture takes advantage of the
Koblitz curves features obtaining a competitive performance against previous
reported implementations using different techniques for the scalar multipli-
cation on ECC.

The multiplication arquitecture proposed here is composed by two in-
dependent arithmetic units (finite fields and integer arithmetic). A shared
memory block provides basic communication. The thesis presents a VHDL
implementation and its respective synthesis using for a Xilinx XC2V4000
FPGA device. FPGA resources requirements and time needed to compute a
scalar multiplication is also presented.

v

vi

Agradecimientos

A mis padres Pedro y Magdalena. Gracias por nunca perder la f´e en mi,
ni en la realizaci´on de mis metas. Gracias por forjar en mi sus principios y
su filosof´ıa de la vida, por todos los sacrificios y desvelos.

A mis hermanos Jacobo y Alba. Gracias por toda la alegr´ıa que com-
parten y me contagian d´ıa con d´ıa, por recordarme con ella el verdadero
valor y prop´osito de la vida. Gracias por acompa˜narme en mi ni˜nez y com-
partir la suya conmigo, s´e que nuestros caminos se dividen, pero de alg´un
modo siempre est´an y estar´an conmigo.

A mi familia, gracias por el apoyo incondicional, por el consejo que nunca

me falt´o.

A mis amigos Abigail, Claudia, Francisco, Grettel, M´onica, Nancy, Paty,
Roc´ıo y Ulises. Gracias por todos los recuerdos que ahora compartimos, por
su compa˜nia durante estos a˜nos, por esa felicidad que irradian y que me hizo
posible sobrevivir tantas presiones y desvelos.

A mis profesores, por compartir sus consejos y conocimientos tanto acad´emi-

cos como de la vida diaria.

A Sofia Reza, por su apoyo y confianza, por hacer de la secci´on un mejor

lugar de trabajo para todos sus integrantes.

Al CINVESTAV por proveer los recursos necesarios para el desarrollo de

esta tesis.

vii

viii

Al Dr. Julio L´opez Hern´andez de la Universidad de Campinas de Brasil

por sus valiosas observaciones durante el desarrollo de esta t´esis.

A Manuel Iv´an Tostado Ram´ırez de la Universidad Aut´onoma de Sinaloa
por sus aportaciones en la realizaci´on de las estad´ısticas presentadas en el
Ap´endice B.

Al proyecto de CONACyt No.45306 el cual financi´o parcialmente el de-

sarrollo de esta tesis.

Introducci´on

El avance de la tecnolog´ıa ha permitido la implementaci´on de algoritmos
dedicados a resolver problemas criptogr´aficos b´asicos como el problema de
factorizaci´on entera y el problema del logaritmo discreto de una manera
bastante eficiente. Los mejores algoritmos conocidos hasta hoy para resolver
los problemas de factorizaci´on entera y el problema del logaritmo discreto,
como lo son el algoritmo de la Criba en Campos Num´ericos (Number Field
Sieve) y el algoritmo de la Rho de Pollard (Pollard’s rho) respectivamente,
tiene un tiempo de c´omputo subexponencial.

Las criptograf´ıa de curvas el´ıpticas, desde que fu´e desarrollada en 1985
por Neal Koblitz y Victor Miller, ha demostrado ser capaz de proveer la
misma funcionalidad que esquemas tradicionales y ampliamente usados en
aplicaciones comerciales como RSA. M´as a´un, ECC es capaz de proveer los
mismos niveles de seguridad que RSA pero con llaves significativamente m´as
peque˜nas. Por ejemplo, se acepta por lo general que una llave de curva el´ıptica
de 160 bits provee el mismo nivel de seguridad que una llave RSA de 1024
bits [1].

El contraste entre los desempe˜nos relativos entre ambos esquemas crip-
togr´aficos ha motivado a diversos grupos de trabajo para desarrollar al-
goritmos eficientes. De la misma manera, se han publicado implementa-
ciones de dichos algoritmos en una gran diversidad de plataformas y dise˜nos
especializados. Pueden encontrarse implementaciones en software para di-
versos procesadores comerciales y dise˜nos de microprocesadores dedicados al
c´alculo de las operaciones b´asicas para la ley de grupo en curvas el´ıpticas
optimizados para diversos algoritmos.

De aqu´ı el inter´es de presentar una arquitectura en hardware reconfi-
gurable que presente buen desempe˜no en tiempos de c´omputo y/o recursos
de hardware utilizados.

En la presente tesis, se presenta un dise˜no en hardware reconfigurable de

ix

x

los algoritmos propuestos por Solinas en [2] y [3]. Los algoritmos propuestos
por Solinas son algoritmos an´alogos a m´etodos tradicionales de expansi´on
NAF con la caracter´ıstica del reemplazo de doblados de puntos el´ıpticos por
exponenciaciones cuadr´aticas sobre campos finitos.

Las plataformas de hardware presentan excelentes desempe˜nos debido a
que la aritm´etica GF(2m) es posible implementarla eficientemente. Debido
a la dependencia que la eficiencia de la multiplicaci´on escalar tiene con los
algoritmos de aritm´etica modular GF (2m) , es parte del problema a resolver
presentar dise˜nos en hardware reconfigurable de algoritmos para aritm´etica
de campos finitos GF (2m) eficientes en recursos y tiempo de c´omputo. Los
algoritmos presentados originalmente son analizados y especializados para la
plataforma de hardware propuesta para optimizar el rendimiento del sistema.
El contenido de la tesis ha sido organizado en 6 Cap´ıtulos. El Cap´ıtulo 1
presenta una introducci´on a criptograf´ıa de llave p´ublica y diversos esquemas
de firma digital para enfocarse finalmente a criptograf´ıa de curvas el´ıpticas.
El Cap´ıtulo 2 provee las bases matem´aticas necesarias para la definici´on for-
mal de criptograf´ıa de curvas el´ıpticas. Define formalmente la operaci´on de
multiplicaci´on escalar el´ıptica y diversos m´etodos existentes para el c´alculo
eficiente de dicha operaci´on. Finalmente define y expone las caracter´ısticas
principales de las curvas Koblitz y su aplicaci´on en el desarrollo del m´etodo
de multiplicaci´on propuesto por Solinas. El Cap´ıtulo 3 presenta un an´alisis
de los algoritmos propuestos por Solinas para la multiplicaci´on escalar y su
adaptaci´on y optimizaci´on para una plataforma de hardware. El Cap´ıtulo 4
describe en detalle la arquitectura propuesta y sintetizada sobre el dispositivo
FPGA Xilinx XC2V4000 y el dise˜no de m´odulos de aritm´etica de campo finito
eficientes. El Cap´ıtulo 5 presenta la evaluaci´on de los resultados obtenidos en
la etapa de s´ıntesis del dise˜no propuesto en cuanto a unidades b´asicas del dis-
positivo FPGA utilizadas y tiempos de c´omputo necesarios para el c´omputo
de una multiplicaci´on escalar. Este ´ultimo se presenta en microsegundos y
cantidad de ciclos de reloj. Finalmente se presenta un estudio comparativo
con diversos trabajos considerados similares a nuestra implementaci´on. El
Cap´ıtulo 6 presenta las conclusiones obtenidas durante el proceso de dise˜no
y durante las comparaciones de los resultados finales. Diversos puntos con-
siderados como posibles extenciones futuras del trabajo son comentados.

´Indice general

´Indice de Figuras

´Indice de Tablas

XIII

XVI

1. Criptograf´ıa de Curvas El´ıpticas
1.1. Servicios B´asicos en Criptograf´ıa
. . . . . . . . . . . . . . . .
1.2. Criptograf´ıa de Llave P´ublica . . . . . . . . . . . . . . . . . .
1.3. Firma Digital RSA . . .