PDF de programación - Esquema de cifrado para la ejecución de consultas en bases de datos cifradas

CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS AVANZADOS

DEL INSTITUTO POLITÉCNICO NACIONAL

DEPARTAMENTO DE COMPUTACIÓN

Esquema de cifrado para la ejecución de consultas en

bases de datos cifradas

Tesis que presenta

Lil María Xibai Rodríguez Henríquez

Para obtener el grado de

Maestra en Ciencias

en Computación

Director de la Tesis: Dr. Debrup Chakraborty

México, D. F.

Diciembre, 2009

.

ii

.

A mi mamita por haberme impulsado desde que era niña a buscar nuevos horizontes,

por mostrarme con su ejemplo que la dedicación es la base del éxito

y por continuar esforzandose por ser el mejor apoyo en mi vida.

iii

.

iv

Agradecimientos

Gracias a don pepe por seguir trabajando arduamente para ayudar y apoyar a su hija.

Gracias a la abuelita Rosita por todas las enseñanzas que me brindó, por que fue y con-
tinua siendo mi compañera mi casi hermana.

A mis hermanos por creer en mi, por compartir conmigo sus experiencias y darme los
más valiosos consejos ante las situaciones que presenta la vida.

A toda la familia por su apoyo incondicional, con especial cariño a mi primo René por
compartir conmigo sus sueños y hacer suyos los mios.

A Raymundo Domínguez Colín por compartir conmigo estos dos años, por brindarme
calma ante los muchos momentos de estrés vividos y ayudar a construir las alegrías.

A todos mis compañeros con los que comparti largas jornadas de trabajo, quienes es-
tuvieron siempre dispuestos a dar su conocimiento, pero sobretodo les agradezco su
amistad.

Gracias al Dr. Debrup Chakraborty, quien con mucho empeño y dedicación me ayudo
hacer una realidad este trabajo de investigación, por estar dispuesto a compartir expe-
riencias y cultura.

A mis lectores Dr. Guillermo Morales, Dr. Francisco Rodríguez; por sus valiosas
aportaciones a mi trabajo.

A Sofia Reza por estar siempre disponible, dispuesta ayudar y pendiente de mi.

Al Cinvestav, por permitirme adquirir los conocimientos necesarios para desenvolverme
en el arte de la Criptografía y en general en las Ciencias de la computación. Gracias
por el apoyo económico que hizo posible la culminación de este trabajo.

A México por crear instituciones como el Cinvestav en las que podemos prepararnos y
estudiar con profesores de alto nivel. Por contar con el Conacyt que me otorgo apoyo
económico para poder realizar esta maestría.

v

.

vi

Contenido

Índice de Figuras

Índice de Tablas

Resumen

Abstract

1 Introducción

1.1 Modelo de bases de datos subcontratadas .

1.2 Planteamiento del problema .

.

.

.

.

.

.

.

.

.

.

1.3 Bases de datos y estructura de las operaciones

1.3.1 Estructura de las operaciones .

.

.

.

1.4 Esquemas existentes

.

. .

. .

. .

. .

. .

. .

1.5 Organización y alcance de la tesis . .

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2 Análisis de los esquemas existentes

2.1 Búsqueda de palabras en documentos cifrados .

2.1.1 Esquema de cifrado .

.

.

2.1.2 Consulta de información .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2.2 Esquema de cifrado para bases relacionales de datos utilizando homo-
.

morfismo .

. . .

. . .

.

.

.

.

.

.

.

.

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2.2.1 Homomorfismo de privacidad .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

vii

xi

xiii

1

3

5

6

7

9

9

12

13

15

15

16

18

19

19

.

.

.

.

.

.

.

.

.

.

.

viii

CONTENIDO

2.2.2 Esquema de cifrado .

. .

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2.3 Esquema que permite consultas básicas en bases de datos relacionales
.

cifradas .

. . .

. . .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. .

. .

. .

. .

.

2.3.1 Esquema de cifrado .

. .

. .

. .

2.3.2 Mejoras al esquema . .

. .

. .

. .

2.4 Comparación de los esquemas existentes

.

.

.

.

.

3 Homomorfismos de privacidad

3.1 Homomorfismo . .

3.2

Isomorfismo .

. . .

.

.

.

.

. .

. .

. .

. .

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3.3 Homomorfismo de privacidad . .

. .

. .

. .

3.4 Criptosistemas homomórficos .

. .

. .

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3.4.1 RSA .

. . .

. . .

.

3.4.2 El Gamal . .

. . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. .

. .

. .

. .

. .

. .

3.5 Esquema de cifrado Paillier .

. .

. .

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3.5.1 El problema de decisión del residuo compuesto .

3.5.2 Esquema de cifrado Paillier .

.

.

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3.6 Homomorfismo de Paillier aplicado a bases de datos cifradas

4 Esquema de cifrado que preserva el orden

4.1 Nociones básicas

.

.

.

. .

. .

. .

. .

. .

. .

4.1.1 Notación y Convenciones . .

. .

.

.

.

.

.

.

.

.

.

.

4.1.2

Función y cifrado que preservan el orden .

4.2 Conexión con la distribución hipergeométrica .

4.2.1 Distribución hipergeométrica . .

.

.

4.3 Esquema de cifrado que preserva el orden .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

4.3.1 Estrategia del algoritmo de preservación de orden .

4.3.2 Ajustes requeridos .

. .

. .

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

19

22

22

23

24

27

27

28

29

29

29

30

31

33

35

37

39

40

40

40

41

42

44

46

46

CONTENIDO

4.4 Cambios realizados sobre el algoritmo de preservación de orden .

4.4.1 Generalización de la estrategia .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

4.5 Cifrado que preserva el orden aplicado a bases de datos cifradas .

ix

47

49

51

.

.

.

.

.

.

.

.

.

.

.

.

5 Esquema de cifrado para la ejecución de consultas en bases de datos cifradas 53

5.1 Recordatorio del modelo de bases de datos subcontratadas .

5.1.1 Operaciones que deben ser soportadas

5.2 Esquema propuesto .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

5.2.1

Justificación de algoritmos elegidos .

. .

5.3 Funcionamiento del esquema propuesto .

5.3.1 Proceso de cifrado . .

. .

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

5.3.2 Proceso de consulta sobre información cifrada .

5.3.3 Proceso de Descifrado . .

. .

. .

.

.

.

.

.

.

.

.

.

6 Implementación del esquema

6.1 Arquitectura y estructura general de la solución .

6.2 Funcionamiento de la solución .

. .

. .

. .

6.2.1 Generación de parámetros iniciales

6.2.2 Organización de la base de datos .

6.2.3

Servicios de la aplicación .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

6.3 Tecnología utilizada y organización del código .

6.4 Resultados experimentales . .

. .

. .

. .

. .

6.4.1 Estructura de la base de datos .

. .

6.4.2 Primera prueba .

.

6.4.3

Segunda prueba . .

7 Conclusiones

7.1 Conclusiones .

. . .

7.2 Trabajo futuro .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

53

54

56

57

58

58

62

65

67

67

69

69

70

70

72

74

74

75

76

79

79

81

x

A Conceptos preliminares

A.1 Grupos . . .

. . .
A.1.1 Grupo Z∗

.

.
N . .

.

.

.

.

. .

B Algoritmos

B.1 AES-128 . .

. . .

.

.

.

.

B.1.1 The State . .

. . .

B.1.2 Cifrado . .

. . .

B.1.3 Descifrado . . .

B.2 base64 . . .

. . .

.

.

.

.

.

.

B.2.1 Codificado .

. . .

.

.

.

.

.

.

B.2.2 Decodificado . . .

C Lenguaje SQL

C.1 Inserción . . .

.

. .

C.2 Consultas .

. . .

.

C.3 Actualizaciones .

C.4 Eliminaciones . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

C.5 Operadores matemáticos .

C.6 Tipos de datos . . .

.

.

.

.

D Manuales

D.1 Manual de instalación .

D.2 Manual del usuario .

D.3 Bibliotecas . . .

.

.

.

D.3.1 gmp . .

. . .

D.3.2 libpq . .

. . .

.

.

.

.

.

.

.

.

.

.

.

.

.

Bibliografía

CONTENIDO

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.