PDF de programación - Implementación Eficiente de Algoritmos Criptográficos en Dispositivos de Hardware Reconfigurable

Centro de Investigaci´on y de Estudios Avanzados

del Instituto Polit´ecnico Nacional

Unidad Zacatenco

Departamento de Ingenier´ıa El´ectrica

Secci´on de Computaci´on

Implementaci´on Eficiente de Algoritmos Criptogr´aficos

en Dispositivos de Hardware Reconfigurable †

Tesis que presenta:
Nazar Abbas Saqib

Para obtener el grado de:
Doctor en Ciencias

En la especialidad de:
Ingenier´ıa El´ectrica

Opci´on:

Computaci´on

Directores de tesis:

Dr. Arturo D´ıaz-P´erez

Dr. Francisco Rodr´ıguez-Henriquez

Ciudad de M´exico, M´exico.

3 de Septiembre de 2004.

† Este trabajo fue parcialmente financiado mediante el proyecto CONACyT 31892-A: Al-
goritmos y arquitecturas de computadoras con dispositivos reconfigurables.

Centro de Investigaci´on y de Estudios Avanzados

del Instituto Polit´ecnico Nacional

Campus Zacatenco

Computer Science Section

Electrical Engineering Department

Efficient Implementation of Cryptographic Algorithms

on Reconfigurable Hardware Devices †

By

Nazar Abbas Saqib

in partial fulfillment of the
requirements for the degree of

Doctor of Science

Specialization in

Electrical Engineering

Option

Computer Sciences

Advisors:

Dr. Arturo D´ıaz-P´erez

Dr. Francisco Rodr´ıguez-Henriquez

Mexico City, Mexico.

September 3, 2004.

† This work was partially supported by CONACyT, project No. 31892-A: Computer algo-
rithms and architectures with reconfigurable devices.

To my wife, Afshan,
for her devotions, sincerity, and solidarity for me.

To my daughter, Fizza (7 years) and Ahmer (5 years),
whose only presence give me a new sense to my existence.

To my parents, brothers and sister,
for their moral, financial, and everlasting support.

iii

Acknowledgements

I thank to Ministry of Education, Islamabad, Pakistan for the award of Cultural
Scholarship for pursuing doctorate in computer sciences at Mexico, a beautiful coun-
try in North America.

I thank to Mexican Government for a warm welcome and a regular financing
during my doctorate. I would wish to thank all officials of Foreign Office Secretariat,
Ministry of Foreign Affairs for their kind treatment and cooperation during my stay
in Mexico.

I would acknowledge my advisor, Dr. Arturo D´ıaz-P´erez for his knowledge, his
experience, and his guidance for this thesis work. I am thankful to him for arranging
financial support in last months of my studies.

I would acknowledge my advisor, Dr. Francisco Rodr´ıguez-Henriquez for his hard
work and useful ideas for improving this dissertation work. I shall ever remember
long discussions with him during days and nights for the clear conception and pre-
sentation of ideas.

I am personally thankful to my examiners for the revision of my thesis and
for their valuable suggestions. I would like to thank Prof. Dr. C¸ etin Kaya Ko¸c
(Oregon State University, USA), Dr. Claudia Feregrino Uribe (INAOE, Mexcio),
Dr. Guillermo Morales-Luna (CINVESTAV-IPN), Dr. Adriano de Luca Pennacchia
(CINVESTAV-IPN) and my advisors who are also member of my examination com-
mittee.

I would like to thank all professors, officials, and colleagues of my department
for their kind cooperation. I cannot forget Sofia Reza and Flor C´ordova for their
friendly talks and guidance for academic matters. I thank all officials in academic
services and library officials for their nice treatment.

v

RESUMEN

Conforme nos movemos hacia una sociedad de informaci´on, la seguridad se ha
convertido en un asunto crucial en ´areas como la industria, los negocios y la ad-
ministraci´on. Las t´ecnicas b´asicas que se requieren para proteger la informaci´on
pertenecen al campo de la criptograf´ıa. La criptograf´ıa aplicada a la seguridad es
una herramienta importante para asegurar confidencialidad (en la transmisi´on y al-
macenamiento de la informaci´on), integridad (no hay cambio que pueda no ser detec-
tado), identificaci´on de fuente (el que env´ıa puede ser identificado), y no repudiaci´on
(el que env´ıa no puede negar que envi´o un mensaje).

Los algoritmos criptogr´aficos est´an clasificados en dos categor´ıas: algoritmos de
llave secreta y algoritmos de llave p´ublica. Los algoritmos de llave secreta o sim´etrica
utilizan una llave secreta para cifrar o descifrar los mensajes. Algunos ejemplos de
este tipo de algoritmos son: DES, AES, Serpent, MARS y IDEA. En los algorit-
mos de llave p´ublica o asim´etrica, las llaves se organizan en pares: llave p´ublica
y llave privada. Cualquiera puede utilizar la llave p´ublica para cifrar un mensaje,
sin embargo, solo quien posee la llave privada puede descifrar este mensaje. RSA y
Criptograf´ıa de Curvas El´ıpticas (ECC por sus siglas en ingl´es) son esquemas crip-
togr´aficos populares de llave p´ublica. Los algoritmos de llave secreta son r´apidos
y pueden ser usados para cifrar grandes cantidades de datos. Por otra parte, los
algoritmos de llave p´ublica son computacionalmente m´as demandantes que los algo-
ritmos sim´etricos pero evitan la necesidad que exista previamente un secreto entre
dos objetos que quieren comunicarse.

Los algoritmos criptogr´aficos pueden ser implementados en plataformas de soft-
ware y hardware. Las soluciones criptogr´aficas basadas en software, pueden ser
usadas para aplicaciones de seguridad donde el tr´afico no es muy demandante y la
velocidad de encriptaci´on no es muy alta. Por otro lado, los m´etodos por hardware
ofrecen soluciones veloces para aplicaciones donde el tr´afico de datos es m´as intenso
y la gran cantidad de datos requiere una encriptaci´on en tiempo real. Los circuitos
VLSI, y los dispositivos FPGAs (Field Programmable Gate Arrays) son dos alterna-
tivas para implementar algoritmos criptogr´aficos en hardware. Los FPGAs ofrecen

vii

grandes beneficios para la implementaci´on de algoritmos criptogr´aficos al compara-
rlos con las soluciones VLSI por su alta flexibilidad. Debido a que los FPGAs tienen
la propiedad de ser reconfigurables, las llaves se pueden cambiar r´apidamente. M´as
a´un, las primitivas b´asicas de la mayor´ıa de algoritmos criptogr´aficos pueden ser
eficientemente implementadas en FPGAs.

El objetivo principal de esta tesis, es obtener implementaciones de algoritmos
criptogr´aficos basadas en dispositivos reconfigurables como los FPGAs que tengan
un alto desempe˜no sin tener que utilizar altos requerimientos de hardware. Esto
es, el objetivo es encontrar un balance adecuado entre el espacio requerido por los
circuitos y la rapidez con que se pueden realizar las operaciones de ciframiento y
desciframiento. Para cumplir el objetivo de esta tesis se han elegido tres algoritmos
de acuerdo a su importancia en aplicaciones de seguridad: Data Encryption Standard
(DES) y Advanced Encryption Standard (AES) como algoritmos de llave sim´etrica,
y Criptograf´ıa de Curva El´ıptica como algoritmo de llave asim´etrica.

En primer lugar, se presenta la aritm´etica sobre campos finitos GF(2m) dado que
constituye la base te´orica para el desarrollo de los algoritmos criptogr´aficos elegidos
en este trabajo de tesis. M´as adelante, se abordaron metas espec´ıficas para cada
algoritmo.

Se desarrollaron gu´ıas generales para implementar cifradores de bloque de llave
sim´etrica en plataformas reconfigurables. Se presenta la estructura general y los
principios del dise˜no para cifradores de bloque y se identifican las primitivas b´asicas
en este tipo de algoritmos. Se presentan algunas t´ecnicas ´utiles de dise˜no para
obtener implementaciones eficientes en dispositivos reconfigurables. Para aplicar
tales gu´ıas y t´ecnicas se utiliz´o a DES como caso de estudio y se obtuvo una imple-
mentaci´on r´apida y compacta para este algoritmo.

Por otra parte, se exploraron varias alternativas arquitecturales para la im-
plementaci´on de AES en dispositivos reconfigurables. Tales alternativas se pre-
sentan como opciones convenientes para diversas aplicaciones de seguridad. Las
arquitecturas diversas desarrolladas para AES fueron optimizadas para obtener alto
desempe˜no, bajo costo o soluciones altamente portables. La eficiencia de los dise˜nos
se obtuvo mediante la aplicaci´on de t´ecnicas optimizadas de dise˜no y aplicando
algunas transformaciones a los algoritmos originalmente planteados.

Finalmente, se presenta una arquitectura gen´erica para realizar la multiplicaci´on
escalar en curvas el´ıpticas, la operaci´on m´as importante de ECC. Tal arquitectura fue
optimizada para dispositivos reconfigurables (FPGAs) tomando ventaja del m´aximo
nivel de paralelismo que se puede explotar en la multiplicaci´on escalar y mediante
un uso eficiente de loa recursos de hardware. Combinando las operaciones de la
aritm´etica de campos finitos en GF(2m) y de la aritm´etica de curvas el´ıpticas, se
formaron bloques b´asicos para realizar la multiplicaci´on escalar en curvas el´ıpticas.
La caracter´ıstica principal entre todos los dise˜nos desarrollados para hardware
reconfigurable es el uso de t´ecnicas paralelas para realizar las operaciones b´asicas
de los algoritmos y, de esta manera, reducir el retraso de la ruta cr´ıtica del circuito.
El consumo bajo de recursos se obtuvo identificando las operaciones comunes en

diferentes pasos y reutilizando los bloques b´asicos. Por otra parte, se busc´o hacer
un mapeo adecuado a la estructura del dispositivo reconfigurable seleccionado para
obtener dise˜nos optimizados para FPGAs. Los resultados mostraron que se obtu-
vieron dise˜nos para algoritmos criptogr´aficos con un alto desempe˜no mediante un
uso eficiente de los recursos de hardware los cuales son comparables con implementa-
ciones reconfigurables similares que est´an reportadas en la literatura a la fecha.

ABSTRACT

As we move into an information society, information security has become a crucial
issue in industry, business, and administration. The techniques needed to protect
information data belong to the field of cryptography. It is an important tool in
assuring confidentiality (in transmission or storage of information), integrity (no
change can be made undetectably), source identification (the sender can be ident