PDF de programación - Multiplicadores de arquitectura segmentada y su aplicación al cómputo de emparejamientos bilineales

Centro de Investigaci´on y de Estudios Avanzados

del Instituto Polit´ecnico Nacional

Unidad Zacatenco

Departamento de Computaci´on

Multiplicadores de arquitectura segmentada

y su aplicaci´on al c´omputo de
emparejamientos bilineales

Tesis que presenta

Nidia Asunci´on Cortez Duarte

para obtener el Grado de

Maestra en Ciencias en Computaci´on

Director de la Tesis

Dr. Francisco Rodr´ıguez Henr´ıquez

M´exico, D.F.

Agosto 2009

ii

Resumen

Las aplicaciones criptogr´aficas requieren de implementaciones eficientes de aritm´etica
b´asica sobre campos finitos tales como suma, resta, multiplicaci´on, divisi´on, exponen-
ciaci´on y c´alculo de ra´ıces, por mencionar algunas, siendo la multiplicaci´on, la operaci´on
que requiere mayor atenci´on debido a su costo en recursos y tiempo de ejecuci´on, adem´as
de que es la operaci´on m´as utilizada en la mayor´ıa de los algoritmos criptogr´aficos.

En esta tesis centramos nuestro inter´es en los algoritmos de multiplicaci´on; par-
tiendo del algoritmo original de Karatsuba-Ofman, analizamos algunas de sus variantes
y describimos las estrategias que consideramos para dise˜nar una arquitectura la cual
esta basada en una estructura segmentada de k-estados. Implementamos nuestras ar-
quitecturas en dispositivos de hardware reconfigurable en el campo finito binario F2239
con k = 1, . . . , 3, donde cada estado est´a compuesto por un multiplicador de 120-bits.
Asimismo, se dise˜n´o un multiplicador para el campo finito ternario F397 con k = 1, . . . , 4,
donde cada estado esta compuesto por un multiplicador de 49-trits. Nuestras arquitecturas
son capaces de c´alcular en promedio k multiplicaciones cada 3 ciclos de reloj. En el campo
F397 mediante una arquitectura segmentada de 4 estados fue posible calcular m´as de una
multiplicaci´on polinomial por cada ciclo de reloj.

Debido a que una de las aplicaciones m´as relevantes para este tipo de multiplica-
ciones es el c´alculo de emparejamientos bilineales decidimos estudiarlos en esta tesis.
Un emparejamiento necesita el c´omputo eficiente de un ciclo principal junto con una
operaci´on adicional denominada exponenciaci´on final. En ambos m´odulos se requiere
evaluar muchas multiplicaciones. En este trabajo se decidi´o utilizar como caso de estudio
el dise˜no del m´odulo de exponenciaci´on final en caracter´ıstica dos.

Todos los dise˜nos se implementaron utilizando el lenguaje de descripci´on de hardware
VHDL y se sintetizaron para dispositivos Virtex II-Pro y Virtex 5 de Xilinx. Se ocuparon
las herramientas de Xilinx para descripci´on y simulaci´on. De acuerdo a nuestros resultados
de la simulaci´on post-place and route en las FPGAs de Xilinx, nuestros multiplicadores
son los m´as eficientes y nuestra implementaci´on de la exponenciaci´on final resulta ser
competitiva con respecto a otros dise˜nos reportados.

iii

iv

Abstract

Cryptographic applications require efficient implementation of the basic arithmetic
finite field operations such as field addition, subtraction, multiplication, division, ex-
ponentiation, squaring, square root, cubing and cube root computation. Among the
aforementioned arithmetic operations, multiplication is by far the one that has received
more attention, mostly because of its crucial role in the aforementioned cryptographic
schemes besides the cost of area and time calculation.

In this thesis, we focus our attention in parallel subquadratic multiplication algorithms.
From the original Karatsuba-Ofman algorithm, we studied some variants recently pub-
lished and we also describe the strategies that were considered to design our reconfigurable
hardware architecture. We decided to use a k-stage pipeline structure. We implemented our
architectures in reconfigurable hardware in the binary finite field F2239 with k = 1, . . . , 3,
where each stage is composed of a 120 bit polynomial multiplier unit and over the ternary
finite field F397 with k = 1, . . . , 4, where each stage is composed of a 49 trit polynomial
multiplier unit. Our architectures can compute in average k field multiplications every
three clock cycles. In the field F397, our four-stage pipeline design can compute in average
more than one field multiplication per clock cycle.

Since the most relevant applications of this kind of multipliers lie on bilinear pairing
computation, where several field multiplications need to be computed at once, we decided
to study it. A bilinear pairing needs the efficient computation of a main cycle and one
additional operation called final exponentiation which is required to obtain a unique
value. Both modules imply the computation of many multiplications. Therefore, the final
exponentiation was considered as a good case of study for our multipliers in characteristic
two.

All the designs were implemented utilizing the hardware description language VHDL
and were also sintetized for Virtex II-Pro and Virtex 5 FPGA devices. The Xilinx tools were
utilized for description and simulation. According to our post-place and route results on
Xilins FPGAs, our multipliers are the most efficient and our design of final exponentiation
is competitive compared to previously published works.

v

vi

Agradecimientos

A mi madre Lidia
Por su apoyo incondicional, por su atenci´on, mi educaci´on
y su comprensi´on. Gracias por ser mi ejemplo de vida.

A mi padre Jes´us
Por el amor que d´ıa a d´ıa me ha demostrado. Gracias por
ense˜narme distintas maneras de vivir la vida.

A mi hermano Daniel
Por sus palabras de aliento y su constante apoyo.

A Alejandro Gonz´alez
Por escucharme en todo momento, principalmente por su
cari˜no y motivaci´on en la ´etapa final de esta tesis.

A toda mi familia y amigos
Por sus buenos deseos y su agradable compa˜nia.

A mis amigos
Daniel, Luis, J´esus y Lul´u
por sus valiosos consejos y ense˜nanzas as´ı como su
paciencia en aquellas jornadas de trabajo arduo.

Miriam, Adriana
por los grandes momentos que compartimos y su infinita
confianza.

Gaby y Amilcar
por toda su ayuda y comprensi´on.

A Raymundo y Joselyn
Por brindar una opci´on para darle un respiro a la vida as´ı
como sus palabras de aliento.

vii

viii

A las se˜noras
Flor C´ordova, Sof´ıa Reza y Felipa Rosas
por su apoyo, cari˜no y su infinita paciencia.

A mi director de tesis
El Dr. Francisco Rodr´ıguez Henr´ıquez por
el apoyo brindado durante el desarrollo de esta tesis.

A los doctores
Arturo D´ıaz P´erez y Luis Gerardo de la Fraga
por sus valiosos comentarios en la revisi´on y correcci´on
para el enriquecimiento de este documento.

Al Dr. Jean Luc Beuchat
Un agradecimiento especial por sus consejos que fueron de
suma importancia para obtener los resultados de esta tesis.

CINVESTAV-IPN
Por permitirme ser parte de esta instituci´on por brindarme
la formaci´on y las herramientas suficientes durante mis
estudios de maestr´ıa.

CONACYT
Por el apoyo econ´omico que me fue otorgado a partir de su
programa de becas y del proyecto n´umero 60240 para
llevar realizar mis estudios de maestr´ıa.

COMECYT
Por el apoyo econ´omico que me fue otorgado a partir de su
programa de becas para posgrado para as´ı llevar a buen
t´ermino mis estudios de maestr´ıa.

´Indice general

´Indice general
´Indice de figuras
´Indice de cuadros

1. Nociones b´asicas de seguridad

1.1.
1.2. Criptograf´ıa . .

Introducci´on a la seguridad y criptograf´ıa . . .
.

. .

. .

. .

. .

.

.

.

.

.

.

.

.

.
.

.
.

.
.

.
.

. .
.
.

.
.

1.2.1. Sistemas criptogr´aficos sim´etricos o de llave privada .
1.2.2. Sistemas criptogr´aficos asim´etricos o de llave p´ublica .
1.2.3. Nivel de seguridad . . .
. .

. .

. .

. .

.

.

.

.

.

.

.

.

ix

xiii

xv

3
3
5
5
6
9

.
. .
. .
.
.
.
.
.
.
.
. .
.

. .
.
.
. .
. .
.
.
.
.
. .

.
.
. .
. .
. .

. .

.
.
.
.
.

.
.
.
.
.

.
.
. .
. .
. .

.
.
. .
. .
. .

. .
. .
. .
. .
.
.

.
.
.
. .

.
.
. .
. .
.

. .
.
.
.
.

.
. .
. .
. .
. .

2.1. Conceptos .

. .
.
.
.
.
.
.
.
.
.
.
. .
. .
.
.
.
. .
.
.
.
. .
.
.
.
.
.
.
.
.
. .
. .

2. Preliminares matem´aticos
. .
.
.
.
.
. .

. .
.
.
.
2.1.1. Grupo . .
.
.
2.1.2. Anillo . .
.
2.1.3. Campos .
.
2.1.4. Campos finitos . . .
.

.
.
.
.
.
.
.
.
. .
2.1.4.1. Campos finitos binarios . . .
2.1.4.2. Campos finitos ternarios . . .
.
.
. .
. .
.
.
. .
. .
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
. .
.
.
.
.
.
.
.
.
.
. .
. .
.
.
.
.
.
.
. .
. .
. .
.
. .
. .
. .
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
.
. . .
. .
. .
.
.
2.2.8.1. Algoritmo Karatsuba-Ofman . . .
.
.
. .
.
.
2.2.8.2. Algoritmo Karatsuba-Ofman no redundante . . .
2.2.8.3. Algoritmo Karatsuba-Ofman libre de traslape
.

2.2. Aritm´etica en campos F2m y F3m .
.
.
2.2.1. Suma y resta .
.
2.2.2. Multiplicaci´on . . .
.
.
.
2.2.3. Elevar al cuadrado . . .
2.2.4. Ra´ız cuadrada .
.
.
.
2.2.5. Elevar al cubo .
.
2.2.6. Ra´ız c´ubica: .
.
.
.
Inversi´on . . .
2.2.7.
. .
2.2.8. Multiplicaci´on polinomial

. .
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.

.
. .
. .
.
. .
. .
.
.
.

.
.
.
. .
.
.
. .
. .
. .

. .
. .
. .
.
.
.
.
. .

.
.
. .
.
.

. .
. .
.
.

11
. 11
.
.
. 11
.
.
. 11
.
.
. 12
. .
. 12
.
. .
. 13
. .
.
. 14
. .
.
.
.
. 14
.
. . 14
. .
. .
.
. 15
. 16
. .
. . 17
. . 18
. 19
.
.
. 19
. . 20
. 22
. 24
. 27

. .
. .
.
.
.
.
. .
.
.
.

. .
.
.
. .

. .
.
.

. .
.

.
.
.
.

.

.

.

ix

x

´INDICEGENERAL

2.3. Curvas el´ıpticas .

. .
2.3.1. Curvas el´ıpticas sobre campos finitos
2.3.2. Curvas el´ıpticas supersingulares .
.

. .

. .

. .

. .

.

.

.

.

.

.

. .
.
.
. .

. .
.
. .

. .
. .
.
.
.
. .
.

. .
.

. .
.
. .

.
. .
.

.
.
. .

.
.
. .

.
.
. .

. 28
. 31
. 31

3. Multiplicadores Karatsuba-Ofman para Fpm con arquitectura segmentada en

hardware reconfigurable
3.1. Consideraciones de dise˜no e implementaci´on .
.
.
. .
.
.

.
. .
3.2.1. Arquitectura segmentada . . .

3.1.1. Rendimiento en FPGA .
.

3.2. Multiplicadores en F2239

. .
.
.

. .

.
.
.

.
.

.

.
.
.

.
.
. .
.
. .

. .
.
. .
.

.
.
.
. .
.
.
.
.
. .
3.2.1.1. Arquitectura segmentada de una etapa
.
3.2.1.2. Arquitectura s