PDF de programación - Diseño de un compilador para protocolos criptográficos

Centro de Investigación y de Estudios Avanzados

del Instituto Politécnico Nacional

Unidad Zacatenco

Departamento de Computación

Diseño de un compilador para

protocolos criptográcos

Tesis que presenta:

Rogelio Vargas Márquez

Para obtener el grado de:

Maestro en Ciencias

en Computación

Director de la Tesis:

Dr. Francisco Rodríguez Henríquez

México, D. F.

Diciembre, 2013

© Derechos reservados por

Rogelio Vargas Márquez

2013

Agradecimientos

En primer lugar quiero decir que por falta de espacio no me es posible nombrar a todas
las personas que me apoyaron a lo largo de estos dos años.

Gracias a mi compañera de vida Lucia Rodríguez Cruz y a mi hijo Johann Yael Vargas
Rodríguez, su gran comprensión los ayudo a soportar la distancia y las dicultades que
enfrentamos. Saber que siempre estuvieron ahí en las buenas y en las malas fue el mayor
impulso para concluir mi trabajo.

A mi madre Ma. Mercedes Márquez Arzate, a mi padre Rubén Vargas Blancas y a mi
hermano Rubén Vargas Márquez, quienes me brindaron su apoyo incondicional durante
este tiempo y cuidaron de Lucy y Johann el tiempo que estuve ausente.

A mi director de tesis el Dr. Francisco Rodríguez Henríquez le agradezco por los
conocimientos que me brindo, por el voto de conanza que ha depositado en mí y sobre
todo por la paciencia que tuvo en las ocasiones donde he fallado.

A el Dr. Luis Julian Dominguez Perez le agradezco por todo el apoyo que me dio, por
guiarme durante mi estancia en Tamaulipas y por todo el tiempo que me otorgó para
concluir con éxito este trabajo.

A mis sinodales la Dra. María de Lourdes López García y el Dr. Carlos Artemio Coello
Coello por sus contribuciones a mi trabajo de tesis.

A mis profesores del Departamento de Computación en Zacatenco, a So por todos los
favores que me hizo, a todos mis compañeros en Zacatenco en especial a Eduardo, Marco
y Michel.

A todo el personal de Laboratorio de Tecnologías de Información en Cd. Victoria. A mis
compañeros de aquellos rumbos, en especial a Carlos, Ana, Arturo y Daniel.

A mis amigos de toda la vida y de la UAM Azcapotzalco por su apoyo y preocupación.

Agradezco al Consejo Nacional de Ciencia y Tecnología (CONACyT) por la oportunidad
y la conanza de otorgarme su apoyo económico a través su programa de becas para la
realización de mis estudios de maestría.

Y por
(CINVESTAVIPN) por permitirme ser parte de esta institución.

supuesto al Centro de Investigación y de Estudios Avanzados del

IPN

Índice General

Índice General

Índice de Figuras

Índice de Tablas

Índice de Algoritmos

Resumen

Abstract

1. Introducción

1.1. Nociones básicas de seguridad y criptografía . . . . . . . . . . . . . . . . . . . .
1.2. Esquemas de cifrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1. Criptografía simétrica o de llave privada . . . . . . . . . . . . . . . . . .
1.2.2. Criptografía asimétrica o de llave pública . . . . . . . . . . . . . . . . . .
1.3. Protocolos Criptográcos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Problemas de complejidad en los que se basan los protocolos . . . . . . . . . . .
1.4.1. Problema de logaritmo discreto . . . . . . . . . . . . . . . . . . . . . . .
1.4.2. Problemas de Die-Hellman . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.3. Relación entre los problemas . . . . . . . . . . . . . . . . . . . . . . . . .
1.5. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7. Objetivos
1.8. Organización de la tesis
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Teoría de Compiladores

2.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Tipos de traductores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Estructura de un compilador . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1. Análisis
2.3.2. Síntesis
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3. Tabla de símbolos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.4. Manejador de errores . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4. Expresiones regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5. Gramáticas libres de contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1. BNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.2. Árbol de derivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

v

vii

ix

xi

xiii

1
2
4
5
6
7
8
8
8
9
10
12
13
14

15
15
16
17
18
19
20
20
21
22
23
24

i

2.5.3. Gramáticas ambiguas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3. Primitivas Criptográcas

3.1. Multiplicación escalar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. Método de ventana ω-NAF . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2. Método comb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3. Método GLV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.4. Método GS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. Emparejamiento de Tate . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. Ciclo de Miller
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3. Emparejamiento óptimo ate sobre curvas BN . . . . . . . . . . . . . . . .
3.3. Multiemparejamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Proyección de una cadena a un punto . . . . . . . . . . . . . . . . . . . . . . . .

3.2. Emparejamiento Bilineal

4. Protocolos Criptográcos

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.
4.2. Clasicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Protocolos basados en emparejamientos bilineales
. . . . . . . . . . . . . . . . .
4.4.1. Protocolo de una ronda Die-Hellman tripartito . . . . . . . . . . . . . .
4.4.2. Firma Corta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3. Firma a ciegas de Boldyreva . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.4. Firma agregada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.5. Cifrado basado en la Identidad . . . . . . . . . . . . . . . . . . . . . . .
4.4.6. Cifrado basado en atributos . . . . . . . . . . . . . . . . . . . . . . . . .

5. Compilador COMPROC

5.1. Herramientas del desarrollo

5.2.1. Descripción de protocolos

5.2. Lenguaje para descripción de protocolos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1. Magma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.2. ANTLR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1.1. Descripción literal
. . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1.2. Descripción estándar . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2. Lenguaje LENPROC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.3. Estructura general del lenguaje LENPROC . . . . . . . . . . . . . . . . .
5.2.3.1. Sección para declaración de variables . . . . . . . . . . . . . . .
5.2.3.2. Sección para la descripción del protocolo . . . . . . . . . . . . .
5.3. Arquitectura de COMPROC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4. Generación automática de código . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3.1. Análisis
5.3.2. Síntesis

ii

25
26
27
29
30
31
32
34
35
37
38
40

43
44
45
46
46
49
50
51
52
53
55

59
60
60
60
61
62
62
63
65
65
67
68
70
70
72
74

5.4.1. Descripción del protocolo de rma corta BLS . . . . . . . . . . . . . . .
5.4.2. Descripción del protocolo de rma a ciegas . . . . . . . . . . . . . . . . .
5.4.3. Características de las descripciones
. . . . . . . . . . . . . . . . . . . . .

6. Conclusiones y trabajo futuro

6.1. Resumen de resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Trabajo Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77
79
80

83
83
85

A. Conceptos Básicos

A.1. Grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1.1. Subgrupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1.2. Clase lateral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2. Anillo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.3. Campo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.3.1. Extensión de un campo nito . . . . . . . . . . . . . . . . . . . . . . . .
A.4. Torres de Campo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.5. Grupo ciclotómico
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.6. Morsmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.7. Eigenespacio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.8. Curvas Elípticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.9. Ley de Grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.10.Curvas elípticas sobre campos nitos

87
87
89
90
90
91
92
93
94
95
95
96
97
. . . . . . . . . . . . . . . . .