Sistema criptográfico basado en curvas hiperelípticas · Verónica González Oquina Sistema criptográfico basado en curvas hiperelípticas Julio Rubio García Facultad de Ciencias,

Verónica González Oquina

Sistema criptográfico basado en curvas hiperelípticas

Julio Rubio García

Facultad de Ciencias, Estudios Agroalimentarios e Informática

Proyecto Fin de Carrera

Matemáticas y Computación

2012-2013

Título

Autor/es

Director/es

Facultad

Titulación

Departamento

PROYECTO FIN DE CARRERA

Curso Académico

© El autor© Universidad de La Rioja, Servicio de Publicaciones, 2013

publicaciones.unirioja.esE-mail: [email protected]

Sistema criptográfico basado en curvas hiperelípticas, proyecto fin de carrerade Verónica González Oquina, dirigido por Julio Rubio García (publicado por la

Universidad de La Rioja), se difunde bajo una LicenciaCreative Commons Reconocimiento-NoComercial-SinObraDerivada 3.0 Unported.

Permisos que vayan más allá de lo cubierto por esta licencia pueden solicitarse a los titulares del copyright.

Ingeniería Técnica en Informática deGestión

Proyecto fin de carrera

Sistema criptográfico basado en curvas hiper-elípticas

Verónica González Oquina

Director: Julio Rubio García

Logroño, abril 2013

Resumen

Este proyecto desarrolla una aplicación que es capaz de crifrar textos usando HECC, o lo que eslo mismo, criptografía con curvas hiperelípticas. Además de la aplicación en sí, se adjuntan tambiénvarios paquetes de Mathematica que nos permiten trabajar y entender mejor como funcionan estetipo de protocolos. Resaltar además que en este trabajo solo se realiza sobre cruvas hiperelípticasde género dos.

Descriptores

Criptografía, HECC, curvas hiperelípticas

iii

Índice general

1 Introducción

2 Documento de Objetivos del Proyecto2.1 Título del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Participantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Motivaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.4 Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.5 Descripción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.6 Herramientas a utilizar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.7 Metodología. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.8 Viabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.9 Riesgos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.10 Costes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.11 Planificación temporal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.11.1 Formación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.11.2 Gestión del Proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.11.3 Análisis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.11.4 Diseño . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.11.5 Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.11.6 Pruebas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.11.7 Presentación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.11.8 Diagrama de Gantt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.12 Entregrables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Fase de Análisis3.1 Generación de Claves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1.1 Especificación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Cifrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2.1 Especificación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2.2 Funcionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Descifrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3.1 Especificación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3.2 Funcionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.4 Firma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.4.1 Especificación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.4.2 Funcionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.5 Verificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.5.1 Especificación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.5.2 Funcionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.6 Otros procedimientos útiles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.6.1 Orden del Jacobiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.6.2 Mumford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.6.3 Algoritmo de Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.7 Diagrama de clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.7.1 Clase básica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.7.2 Clase Gestor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.8 Prototipo de Interfaz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.8.1 Prototipo Inicio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.8.2 Mensajes de advertencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

v

3.9 Fase de Pruebas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Fase de Diseño4.1 Generación de Claves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Cifrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.3 Descifrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.4 Firma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5 Verificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.6 Otros procedimientos útiles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.6.1 Orden del Jacobiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.6.2 Mumford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.6.3 Algoritmo de Cantor-Lange . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.6.4 Orden de un divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.6.5 Puntos de una curva hiperelíptica . . . . . . . . . . . . . . . . . . . . . . . . 324.6.6 Divisor Semirreducido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.7 Diagrama de clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.7.1 Clase básica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.7.2 Clase Gestor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.8 Prototipo de Interfaz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.8.1 Prototipo Inicio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.8.2 Prototipo Cifrar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.8.3 Mensajes de advertencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.9 Fase de Pruebas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.9.1 Pruebas de las funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.9.2 Pruebas unitarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.9.3 Pruebas de integración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.9.4 Pruebas de aceptación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5 Fase de Implementación5.1 Alternativas tecnológicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.2 Funciones Mathematica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2.1 Problemas con el Paquete FiniteFields . . . . . . . . . . . . . . . . . . . . . 425.2.2 Funciones Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.3 Interfaz gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

6 Fase de Pruebas6.1 Pruebas con Mathematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.2 Pruebas interfaz gráfica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

7 Gestión del proyecto7.1 Cambio de diseño de la interfaz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777.2 Creación de dos paquetes de Mathematica . . . . . . . . . . . . . . . . . . . . . . 797.3 Motivos del desfase temporal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

8 Conclusiones8.1 Líneas futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

A Las matemáticas detrás del proyectoA.1 Primer ejemplo: curvas elípticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83A.2 Curvas Hiperélipticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

A.2.1 Jacobiano y divisores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87A.3 Suma de divisores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

B Código Mathematica

Bibliografía

vi

Índice de figuras

2.1 Descomposición del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Diagrama de Gantt del Trabajo Planificado (1) . . . . . . . . . . . . . . . . . 112.3 Diagrama de Gantt del Trabajo Planificado (2) . . . . . . . . . . . . . . . . . 12

3.1 Diagrama de Clases: Cifrar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2 Diagrama de Clases: Gestor . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.1 Diagrama de Clases: Cifrar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.2 Diagrama de Clases: Gestor . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.3 Prototipo Página Inicio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.4 Prototipo Página Principal: Menú Archivo . . . . . . . . . . . . . . . . . . . 354.5 Prototipo Página Principal: Menú Claves . . . . . . . . . . . . . . . . . . . . 354.6 Prototipo Cifrar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.7 Prototipo Cifrar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.1 Prototipo final para generar claves . . . . . . . . . . . . . . . . . . . . . . . 777.2 Prototipo final para cifrar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777.3 Prototipo final para descifrar . . . . . . . . . . . . . . . . . . . . . . . . . . 787.4 Prototipo final para firmar . . . . . . . . . . . . . . . . . . . . . . . . . . . 787.5 Prototipo final para verificar . . . . . . . . . . . . . . . . . . . . . . . . . . 78

A.1 Curva elíptica E : y2 = x3 − x sobre R . . . . . . . . . . . . . . . . . . . . . . 84A.2 Suma de dos puntos P y Q distintos. . . . . . . . . . . . . . . . . . . . . . . 84A.3 Cálculo de 2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84A.4 Suma de dos puntos P y Q con la misma coordenada x . . . . . . . . . . . . 85A.5 Curva hiperelíptica C : y2 = x5 − 5x3 + 4x sobre R . . . . . . . . . . . . . . . 86A.6 Curva hiperelíptica C : y2 = x5 − 5x3 + 4x sobre R . . . . . . . . . . . . . . . 86A.7 Curva hiperelíptica C : y2 = x5 − 5x3 + 4x sobre R . . . . . . . . . . . . . . . 87

vii

Índice de cuadros

4.1 Prueba 1: Procedimientos Mathematica . . . . . . . . . . . . . . . . . . . . . 374.2 Prueba 2: Procedimiento copiarTexto . . . . . . . . . . . . . . . . . . . . . . 374.3 Prueba 3: Procedimiento copiarTexto . . . . . . . . . . . . . . . . . . . . . . 374.4 Prueba 4: Generación de Claves . . . . . . . . . . . . . . . . . . . . . . . . . 384.5 Prueba 5: Cifrar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.6 Prueba 6: Descifrar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.7 Prueba 7: Firma Digital. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.8 Prueba 8: Verificación Firma. . . . . . . . . . . . . . . . . . . . . . . . . . . 394.9 Prueba 9: Cifrado y Firma Digital . . . . . . . . . . . . . . . . . . . . . . . . 39

6.1 Tiempo en segundos que se trata de calcular M2 con la funcion CalculoM2 . 76

ix

Índice de códigos

5.1 Función PuntosCurva usando polinomios como entradas . . . . . . . . . . . . 425.2 Función PuntosCurva usando listas como entradas . . . . . . . . . . . . . . . 435.3 Función CalculoM2 con polinomios . . . . . . . . . . . . . . . . . . . . . . . . 445.4 Función CalculoM2Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.5 Función jacobiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.6 Función SemiReducido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.7 Función PolinomiosPi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.8 Función Mumford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.9 Función MumfordInverso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.10 Función Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.11 Función Reduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.12 Función Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.13 Función OrdenDivisorCantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.14 Función DivisorPorCteCantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.15 Función RomperMensaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.16 Función ClavesCantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.17 Función CifradoCantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.18 Función DescifradoCantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.19 Función FirmaCantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.20 Función VerificacionCantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.21 Función SumarGrado1Pols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.22 Función DoblarGr1Pols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.23 Función SumarGrado2Pols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.24 Función DoblarGr2Pols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.25 Función SumarGrDistintoPols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.26 Función SumarGradoDistintoPols . . . . . . . . . . . . . . . . . . . . . . . . . 615.27 Función RestarPols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625.28 Función CantorLangePols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625.29 Función DivisorPorCteLangePols . . . . . . . . . . . . . . . . . . . . . . . . . . 655.30 Función OrdenLangePols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.31 Función ClavesLangePols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665.32 Función CifradoLangePols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665.33 Función DescifradoLangePols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.34 Función FirmaLangePols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.35 Función VerificacionLangePols . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.36 Función prueba para usar J/Link . . . . . . . . . . . . . . . . . . . . . . . . . . 685.37 Función cifrar() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.38 Función descifrar()label . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.39 Función firmar()label . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.40 Función verificar(String aux) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.41 Función generacionClaves(string aux) . . . . . . . . . . . . . . . . . . . . . . . 72

B.1 Función SumarGrado1Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91B.2 Función DoblarGr1Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91B.3 Función SumarGrado2Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92B.4 Función DoblarGr2Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93B.5 Función SumarGrDistintoListas . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

xi

B.6 Función SumarGradoDistintoListas . . . . . . . . . . . . . . . . . . . . . . . . . 96B.7 Función RestarListas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96B.8 Función CantorLangeListas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97B.9 Función DivisorPorCtelangeListas . . . . . . . . . . . . . . . . . . . . . . . . . 99B.10 Función OrdenLangeListas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99B.11 Función ClavesLangeListas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100B.12 Función CifradoLangeListas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100B.13 Función DescifradoLangeListas . . . . . . . . . . . . . . . . . . . . . . . . . . . 101B.14 Función FirmaLangeListas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101B.15 Función VerificacionLangeListas . . . . . . . . . . . . . . . . . . . . . . . . . . 101

xii


1. INTRODUCCIÓN

Actualmente y debido al uso de dispositivos móviles de forma habitual (se podría decir que estarconectado a la red forma parte del día a día de la mayoría de las personas), mantener la privacidady la seguridad de las comunicaciones se ha convertido en algo muy importante. Los sistemas decifrado más aceptados se basan en problemas matemáticos que sea muy difíciles de resolver o quetengan una complejidad computacional elevada (es decir, que lleve mucho tiempo y/o recursosencontrar la solución). Dos grandes ejemplos de este tipo de problemas son:

El problema de factorización.

El problema del logaritmo discreto.

El primero de los dos genera el criptosistema RSA y el segundo protocolos de cifrados que usanlos algoritmos de el Gammal. El mayor inconveniente de estos sistemas es que generan clavesdemasiado grandes y cada día los dispositivos informáticos son cada vez más pequeños. Es poresto que el esfuerzo de la comunidad criptográfica se centra en encontrar otros sistemas numéricostradicionales sobre los que definir nuevos protocolos de cifrado que generen claves de menor tamaño.

Con esta motivación, y gracias a haber hecho ya un trabajo que analizaba el comportamientode las curvas hiperelípticas en criptografía, se ha decido realizar este proyecto cuya idea es crearuna herramienta sencilla para que pueda ser utilizada por cualquier usuario sin necesidad de queconozca la complejidad matemática en la que se basan estos algoritmos.

Mediante una serie de formularios, el usuario podrá desarrollar las operaciones que desee apartir de un conjunto de datos que haya cargado previamente. Esto lo hara de una manera visual.Nuestra aplicación se apoyará en Mathematica para realizar lo cálculos necesarios para los procesosde cifrado y firma digital.

1


2. DOCUMENTO DE OBJETIVOS DELPROYECTO

En este primer capítulo del proyecto fin de carrera incluiremos el Documento de Objetivos deProyecto. Este es un documento fundamental a la hora de marcar los objetivos a realizar en elProyecto Fin de Carrera. En él estimaremos los distintos parámetros que marcarán la realizacióndel proyecto como su descripción, las distintas motivaciones que nos han llevado a realizar elproyecto, el tiempo estimado que nos va a llevar realizarlo...

2.1 TÍTULO DEL PROYECTO

Criptografía con curvas hiperelípticas.

2.2 PARTICIPANTES

Proyectante: Verónica González Oquina.

Director : Julio Rubio.

2.3 MOTIVACIONES

Este proyecto nace como la posibilidad de acabar un trabajo ya comenzado. Como Trabajo Finde Máster para la Universidad de Granada se me propuso realizar un estudio de las aplicacionescriptográficas usando curvas hiperelípticas. Una parte de él, era la implementación de un paquetepara Mathematica con las funciones necesarias para crear un protocolo de cifrado basado en curvashiperelípticas, pero por falta de tiempo, fui incapaz de terminarlo. Es por esto que este proyectoes una oportunidad fantástica para finalizar todo el estudio.

2.4 ANTECEDENTES

Como he dicho en el apartado anterior ya existen una serie de funciones implementadas en Mat-hematica. Estas operaciones son solo las que nos permiten trabajar con los divisores del jacobianode una curva hiperelíptica. No forman parte de ningún paquete, por lo que sería necesario crearuno con todas ellas y seguir implementado las funciones que nos permitirían tanto cifrar y descifrarun mensaje, como firmar y verificar este.

3

2. DOCUMENTO DE OBJETIVOS DEL PROYECTO

2.5 DESCRIPCIÓN

El proyecto tendrá como objetivo el cifrado de un mensaje a través de curvas hiperelípticas. Paraello, se creará una interfaz que liberará al usuario de tener que conocer las matemáticas que seocultan detrás del proceso de cifrado.

2.6 HERRAMIENTAS A UTILIZAR

En principio, podemos dividir el proyecto en dos partes distintas:

1. Implementación de todas las funciones necesarias para crear un sistema mediante HECC(Hyperelliptic curve cryptography).

2. Construcción de la interfaz.

Para la primera parte nos serviremos de Mathematica, que nos va a permitir usar funcionescon polinomios de una manera rápida y eficiente. Mientras que para la construcción de la interfazusaremos el lenguaje de programación Java. Se ha elegido este lenguaje por varias razones: essencillo, es bastante bueno para la realización de aplicaciones gráficas y además Mathematicadispone del paquete ’J/Link’que nos facilita la conectividad entre Mathematica y nuestra aplicación.

Por otro lado, Java dispone de una extensa documentación digital, a la que tenemos acceso através de Internet, ya que es un lenguaje muy popular entre los programadores.

Mathematica es un programa para el análisis matemáticos. Es un software de pago. Uno de lospuntos fuertes de Mathematica para nuestro trabajo es la cantidad de funciones para polinomiosque tiene ya implementadas, y sobre todo lo rápido que trabaja con ellas, ya sea sobre polinomiosdefinidos sobre R o con polinomios definidos sobre cuerpos finitos Fq.

2.7 METODOLOGÍA

Seguiremos un ciclo de vida incremental, es decir, iremos construyendo la aplicación por módulosque cumplen diferentes funcionalidades del sistema hasta ir completando las capacidades de nuestraaplicación. Al final de cada ciclo se irán entregando las nuevas versiones del software a nuestrocliente (en este caso a Julio Rubio), cada una de ellas con nuevas funcionalidades.

Un ciclo de vida incremental quiere decir que iremos construyendo la aplicación por módulos quecumplen las diferentes funcionalidades del sistema e que estos módulos irán aumentando gradual-mente las capacidades del software. Se supone que al final de cada ciclo entregaremos una versiónal cliente con nuevas funcionalidades.

Se ha elegido este ciclo de vida ya que:

Al ir construyendo el sistema total a partir de sistemas más pequeños, el riesgo que asumimoses mucho menor.

En caso de error, solo se desecha la última versión.

Es mucho más fácil dar con los requisitos del cliente a escala más pequeña.

4


2.8 VIABILIDAD

Generalmente, esta sección de un proyecto se basa en la viabilidad económica de este, pero ennuestro caso, y al tratarse de un proyecto fin de carrera, este estudio es totalmente distinto.

La viabilidad instrumental del proyecto está parcialmente asegurada ya que no existen muchasaplicaciones de este tipo. Además, como este tipo de protocolos criptográficos crean claves máspequeñas que las habituales, nuestro producto podrá ser usado en dispositivos móviles de tamañoreducido.

En cambio la viabilidad temporal es un poco más difícil de estimar. Nos encontramos en unafase en la que todavía no se ha comenzado a desarrollar el proyecto, por lo que aún no sabemoscuáles van a ser las dificultades que nos vamos a ir encontrando en el proceso que acabamos deempezar.

2.9 RIESGOS

La detección de riesgos es un parte muy importante dentro de todo proyecto. Con un buenplan de detección podemos tener todas las fuentes de riesgo identificadas. Así, si algo fallase,podríamos actuar según lo planificado. En esta sección detallaremos las principales fuentes deriesgo y crearemos un protocolo a seguir en caso de que éstas ocurran.

� Fuentes de Riesgo

1. Inexperiencia de la proyectante: la poca experiencia en desarrollo de proyectos es una fuentede riesgo potencial. A la hora de realizar este proyecto la alumna solo tiene experiencia enrealizar trabajos a menor escala, pero ninguno de esta magnitud. Es por esto que, con todaseguridad, esta inexperienxia causará fallos y errores en todos los aspectos del proyecto. Parasolucionar este problema la alumna deberá estudiar a fondo las las características del proyectoy los manuales de ayuda sobre los diferentes temas tratados en el proyecto.

2. Estimación de fechas para la realización del proyecto no apropiada: predecir el tiempo dedesarrollo de una tarea no es sencillo, por lo que la fecha de entrega del proyecto puedevariar a lo largo del proceso de creación de éste.

3. Diseño: el diseño realizado por la alumna puede que no sea el óptimo. Así, pueden apareceralgunos cambios en el diseño que ralenticen el trabajo.

4. Problemas Software: que pueden ocurrir tanto por la mala instalación de alguna de las he-rramientas como por el mal uso de las mismas.

5. Problemas Hardware: puede que también aparezcan daños físicos en los ordenadores que sevan a utilizar.

6. Pérdida de información: ocasionada por no guardar diferentes versiones al final de cadasesión o por pérdidas de los dispositivos de almacenaje. Nos aseguraremos que esto no paserealizado copias de seguridad en cada sesión.

7. Enfermedad de la proyectante.

5


� Síntomas de riesgo

Al detectar alguno de estos síntomas se procederá como se describe en el apartado 2.9 Plan dedirección de riesgos.

1. Continuos errores que impiden avanzar en el desarrollo del proyecto bajo las fechas planifi-cadas.

2. Según se va avanzando en el proyecto, se anotan las horas invertidas y la fecha en la cual sevan entregando los distintos paquetes. Puede haber un contínuo retraso en las entregas, porlo que la fecha de entrega que habíamos estimado no es la correcta.

3. Mientras se esté diseñando la planificación, se realizará una revisión exhaustiva del mismo.Es en este momento en el que se decidirá si el diseño que se ha propuesto es el adecuado o sinecesita una remodelación.

4. Aparecen nuevos problemas con las herramientas de trabajo que impiden avanzar en el procesode creación.

5. Un equipo puede sufrir deterioro físico por poblemas de temperatura, humedad, golpes, oincluso puede ocurrir que alguna pieza se estropee.

6. Síntomas de enfermedad que retrasen la planificación.

� Cuantificación de riesgos

Podemos evaluar cada fuente de riesgo expuesta anteriormente de forma diferente ya que no todasafectan de igual manera al proyecto: una fuente puede ocasionar daños elevados, como ínfimos. Ennuestro caso:

1. La estimación de fechas realizada puede que no sea la adecuada.

2. Un cambio en el diseño a destiempo puede ser un error muy grave: el trabajo realizadodurante varios meses puede no haber servido para nada. Es por esto que la revisión deldiseño se efectuará antes de la implementación.

3. El riesgo de que la herramienta suponga una barrera para la alumna es baja, ya que hatrabajado ya con ella o con herramientas similares. En caso de ocurra algún fallo con laherramienta y sea necesaria su reinstalación, se dispone de una copia para ello. El riesgo deque esto ocurra es muy bajo.

4. Es poco probable que el equipo con el que se va a trabajar sufra algún tipo de problema, ya quees un odernador de sobremesa que se encuentra colocado en una habitación de temperaturaestable y protegido de golpes.

5. La incapacidad física de la alumna puede ser prolongada o no. Es por esto que podemosconsiderar este factor de riesgo como medio/alto.

� Plan de dirección de riesgos

Para cada fuente de riesgo identificada se actuará según lo descrito en este punto.

6


1. Se pedirá una reunión con el director del proyecto o con alguna otra persona cualificada ycon suficiente experiencia, como para poder orientar y redirigir el proyecto según se creaconveniente.

2. Se realizaría una nueva estimación de las fechas del proyecto, intentado que las nuevas seanmás acordes a la realidad. Los motivos por los que se ha producido esta demora serán anotadosy considerados más adelante para no volver a caer en los mismo errores.

3. Si el diseño es incorrecto, la alumna realizaría los cambios necesarios antes de la implemen-tación.

4. Se reinstalará la herramienta y se comprobará su buen funcionamiento. En caso de quelos errores ocurran por el mal uso de la herramienta, se consultarán tutoriales o se pediráasistencia técnica y orientación a personas que ya hayan utilizado esta herramienta de trabajo.

5. Si el equipo se estropea, se mandará éste a reparación. Mientras tanto se trabajará con losordenadores de las aulas de informática de la Universidad de La Rioja.

6. Ante situaciones de agotamiento o estrés se reducirá el ritmo de trabajo, tomando no másde dos días de trabajo duro seguidos, ni más de uno de descanso para no perder el ritmo.

2.10 COSTES

Para realizar esta aplicación vamos a utilizar las siguientes herramientas:

NetBeans IDE 7.3, de licencia libre.

Wolfram Mathematica 8, propiedad de Wolfram Research y de pago.

2.11 PLANIFICACIÓN TEMPORAL

Podemos distinguir diferentes fases en el proceso de elaboración de este proyecto. Cada faseestará dividida en diferentes actividades. En esta sección mostraremos un diagrama que muestraen que consiste cada fase. Para que sea más sencilla su comprensión, supondremos que cada faseempieza una vez la fase anterior haya sido acabada, aunque el ciclo de vida elegido sea incremental.

7


Figura 2.1.: Descomposición del proyecto

2.11.1 Formación

Esta fase tendrá lugar al comenzar el proyecto, aunque también tendrá lugar durante la ela-boración del mismo a medida que vayan surgiendo dudas y problemas. Podemos diferenciar 3actividades dentro de esta fase:

Aritmética de curvas hiperelípticas: aunque la alumna posee conocimientos previos sobre lamateria, se intentará encontrar un algoritmo de la suma más eficientes.

Lenguaje Java: aparte de refrescar todos los conocimientos sobre este lenguaje estudiados a lolargo de la carrera de informática, la alumna deberá aprender cómo crear interfaces gráficascon Java.

Programación con Mathematica: aunque también se disponen de conocimientos sobre cómoprogramar con esta aplicación, se deberá de profundizar un poco más tanto en el tratamientode las listas como en algunos paquetes específicos, para poder sacar un mayor rendimiento aesta potente herramienta.

2.11.2 Gestión del Proyecto

Esta fase nos ayudará a entender un poco mejor al proyecto que nos disponemos a realizar.

La dividimos en las siguientes actividades:

8


Reuniones con el director: que se llevarán acabo durante todo el proceso de elaboración delproyecto.

Elaboración del DOP: en este documento plasmaremos los distintos parámetros que aparecena la hora de crear un proyecto, haciendo una estimación de todo lo que se quiere conseguir.

Especificación de objetivos: esta actividad la realizaremos al mismo tiempo que la elaboracióndel DOP. En ella se estudiarán las diferentes alternativas que aparecen a lo largo del mismo,los antecedentes...

Estructuración de las tareas: que nos ayudará a planificar mejor el proyecto, para así enten-derlo mejor y comprender qué es lo que hay que hacer en cada momento.

2.11.3 Análisis

En esta fase se definirán conceptualmente cuál es la aplicación que vamos a crear.

Especificación y análisis de los requisitos: se explica cómo debe de funcionar la aplicación ycuáles son los requisitos que ésta debe cumplir.

Análisis de los distintos procedimientos: se abordará la finalidad de la aplicación. Para elloespecificaremos los procedimientos principales.

Identificación de clases y creación de un modelo de clases: se hará un primer acercamientoal posible diagrama de clases final, identificando en un primer momento las clases que van aser necesarias en nuestro proyecto.

Documentación de la fase de análisis: una vez acabadas todas las tareas anteriores, se docu-mentará por escrito todo lo realizado en esta fase.

2.11.4 Diseño

Mejoraremos todo lo hecho en la fase anterior buscando distintas alternativas. En cada tarea semejorará todo lo hecho en la fase de análisis.

Diagramas de clase: se construirán los diagramas de clases que sean necesarios para el sistema.Para ello se utilizará el esquema previo hecho en la fase anterior.

Diseño de las interfaces: se elaborarán una serie de ideas para podernos imaginar mejor cómoserá la aplicación. Esto nos ayudará mucho a la hora de implementar.

Documentación de la fase de diseño: como en la fase anterior, una vez acabadas todas lastareas anteriores, se documentará por escrito todo lo realizado en esta fase.

2.11.5 Implementación

Se llevará a cabo todo lo que se ha analizado y diseñado con anterioridad, para así poder construirnuestra aplicación.

9


Implementación de la interfaz: se creará la aplicación en el lenguaje elegido.

Implementación de funciones con Mathematica: se desarrollarán las funciones relacionadascon el cifrado.

Documentación de la fase de implementación: se elaborará un resumen detallado de todo loocurrido en esta fase.

2.11.6 Pruebas

Se realizarán una serie de pruebas ara verificar que la aplicación funciona tal y como se desea.

Diseño de pruebas a realizar : se crearán una serie de pruebas para verificar la corrección dela aplicación.

Ejecución de las pruebas: se llevan a cabo las pruebas realizadas en la actividad anterior.

Documentación de la fase de pruebas: se documentará en todo lo que se ha ido haciendo enesta fase.

2.11.7 Presentación

Se realizará una memoria del proyecto, además de una presentación para defenderlo delante deltribunal.

Elaboración de la memoria: se reunirán todos los documentos creados durante todas las fasesdel proyecto. Se revisarán y corregirán en caso de fallo.

Elaboración de la presentación: que consistirá en unas diapositivas que expliquen los aspectosprincipales del proyecto.

10


2.11.8 Diagrama de Gantt

Figura 2.2.: Diagrama de Gantt del Trabajo Planificado (1)

11


Figura 2.3.: Diagrama de Gantt del Trabajo Planificado (2)

2.12 ENTREGRABLES

Al finalizar el documento se dispondrán los siguientes entregables:

Memoria del proyecto.

Aplicación realizada.

Presentación del proyecto.

Paquetes de Mathematica.

Archivos de Mathematica con ejemplos y pruebas.

12


3. FASE DE ANÁLISIS

Lo que vamos a hacer en este capítulo es explicar a grandes rasgos cómo funciona la aplicación.Para ello, explicaremos los procedimientos principales usando las cabeceras de los algoritmos.

Se implementará un protocolo criptográfico basado en el sistema el Gammal pero adaptado acurvas hiperelípticas. Para ello será necesarios los siguientes parámetros:

Un cuerpo finito Fq.

Una curva hiperelíptica C.

El número primo p más grande que divida al cardinal de jacobiano asociado a la curva C

Un divisor D de orden primo p (Este divisor no tiene por qué ser reducido).

3.1 GENERACIÓN DE CLAVES

Como el protocolo HECC es un protocolo criptográfico de clave pública, será necesario que cadausuario disponga de dos claves: una privada (que conocerá solo él) y una pública, que será dedominio general.

Por otro lado, todo usuario de la aplicación será consciente de las características del sistema:conocerá tanto la C que se utilizará en el proceso como el cuerpo finito Fq sobre el que está definida,así como el divisor base D.

Veamos ahora como se construyen las dos claves:

1. Clave privada: será un entero aleatorio r ∈ [1, p − 1], siendo p el mayor número primo quedivide al jacobiano (y a su vez será también el orden de D).

2. Clave pública: será el divisor que se obtiene al multiplicar rD = R.

3.1.1 Especificación

{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobreel que se define la curva char, p el número primo más grande que divide al cardinal del jacobianoasociado a la curva hiperelíptica C y el punto base D }

{POST: r ∈ [1, p−1] que será la clave pública, y rD = R que corresponderá a la clave privada}

13


3.2 CIFRADO

El mensaje M que se desea cifrar llegará ya descompuesto en 4 bloques M1,M2,M3,M4. El totalde los bloques será el equivalente al texto completo pero escrito en código ASCII.


{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobre elque se define la curva char, la 4-tupla (M1,M2,M3,M4) que representa al mensaje M , además delos divisores B que será la clave pública del destinatario del mensaje y el punto base D }

{POST: la cuatro tupla (M ′1,M

′2,M

′3,M

′4) que será el mensaje M cifrado y el divisor D′ }

3.2.2 Funcionamiento

Este algoritmo aplicará el protocolo criptográfico de curvas hiperelípticas, y tras pasar un archivode texto plano (es decir, sin cifrar) a la aplicación, lo que hará es devolver un archivo que tenga elcorrespondiente texto cifrado.

3.3 DESCIFRADO

La salida de este algoritmo será una 4-tupla (M1,M2,M3,M4) . Para conseguir el mensajeoriginal, lo que se hará posteriormente es unir estas cuatro partes


{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobreel que se define la curva char, la 4-tupla (M ′

1,M′2,M

′3,M

′4) que representa al mensaje cifrado M ′,

además de un entero b que será la clave privada del destinatario del mensaje y un divisor D′ }

{POST: la cuatro tupla (M1,M2,M3,M4) que será el mensaje M }


Tras mandar un archivo cifrado a Mathematica, nuestra aplicación nos devolverá el correspon-diente archivo sin cifrar, es decir, el archivo original que contiene el texto plano.

3.4 FIRMA

Para firmar un mensaje es necesario utilizar una función Hash, que es una función H : U −→Mque tiene como entrada un conjunto de elementos y los convierte en un rango de salida finito,normalmente cadenas de longitud fija. Es decir, la función actúa como una proyección del conjuntoU sobre el conjunto M . Esta función tiene que ser de colisión baja.

14



{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobre elque se define la curva char, el mensaje M , además del divisor que representa al punto base D yun número entero a que será la clave privada de la persona que firma el mensaje }

{POST: dos número enteros r y s, que representarán la firma digital }


Esta función hará la firma digital de un archivo, es decir, marcará el archivo de tal forma, quesea capaz de identificar al usuario emisor del mensaje de forma única.

3.5 VERIFICACIÓN

Lo que hará este procedimiento es confirmar que el emisor del mensaje es el que realmente seespera. Para esto será necesaria una firma y la clave pública del emisor del mensaje.


{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobre elque se define la curva char, el mensaje M , la firma (r, s) del mensaje, además del divisor A querepresenta la clave pública del emisor del mensaje }

{POST: devuelve verdad si la firma del mensaje pertenece a la persona que ha enviado elmensaje y falso en caso contrario }


Aplicando una serie de operaciones sobre divisores y enteros, este algoritmo verificará que elarchivo seleccionado está firmado por el emisor que se espera.

3.6 OTROS PROCEDIMIENTOS ÚTILES

Además de los procedimientos básicos vistos en las secciones anteriores de este capítulo, tambiénse usarán otros procedimientos que nos facilitarán el trabajo con la aritmética de las curvas hiper-elípticas de género dos. Estos algoritmos que calcularán, entre otras cosas, el orden del jacobiano,la representación de un divisor como un par de polinomios...

A estos procedimientos se les pasará entre otras cosas una lista de polinomios que representaráa un divisor. Ésta tendrá como elementos a tuplas de tres componentes. La primera componenteserá el orden del divisor en ese punto, mientras que las otras dos componente representarán lapunto en sí, es decir las componente x e y del punto.

Veamos con un poco más de detalle cada uno de estos algoritmos:

15


3.6.1 Orden del Jacobiano

Este procedimiento calculará el orden del jacobiano asociado a la curva C para así poder calcularel grupo base sobre el crear el sistema de cifrado.

� Especificación

{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobre elque se define la curva char, además de una lista L que estará formada por los puntos de los queconsta el divisor D }

{POST: devuelve un entero n que corresponde al cardinal del jacobiano}

3.6.2 Mumford

Mediante este procedimiento representaremos los divisores como pares de polinomios y así serámucho más fácil trabajar con el conjunto de clases de divisores de una curva hiperelíptica.

� Especificación


{POST: devuelve un par de polinomios [u, v] que representan a un divisor D. Estos polinomiosserán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 y cumplirán que

u es mónico,

gr(v) < gr(u) < g,

u | v2 + vh(x)− f(x)

}

3.6.3 Algoritmo de Cantor

Este algoritmo se encargará de sumar dos divisores. Se ha intentado encontrar un algoritmo algomás eficiente del algoritmo de Cantor que se ha empleado hasta ahora. Para esto nos hemos fijadoen el trabajo de Tanja Lange ( [CFA06]), que descompone el algoritmo de Cantor clásico teniendoen cuenta la característica del cuerpo sobre el que se define la curva.

� Especificación

{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char y los polinomios u1 = x2+u11x+u10, v1 = v11x+v10 y u2 = x2+u21x+u20,

16


v1 = v11x+ v10 que representan respectivamente a los divisores D1 y D2. Además gr(u1) < gr(u2).}

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = D1 +D2. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 y cumplirán que

u es mónico,

gr(v) < gr(u) < g,

u | v2 + vh(x)− f(x)

}

� Funcionamiento

Lo que se hará en este algoritmo es descomponer el algoritmo de Cantor teniendo en cuentalos elementos del soporte de un divisor. Como estamos trabajando con divisores representadosmediante pares de polinomios, lo que se hará es dividir el algoritmo de Cantor en dos bloques, quedependen del grado del polinomio de grado mayor del primer divisor. Así, obtendremos un nuevoalgoritmo que dependerá solo de los coeficientes de los polinomios de los dos divisores con los quevamos a trabajar.

Por otro lado, este algoritmo necesitará una serie de subprocedimientos. Estos serán los quesiguen:

� SumarGrDos

Esta función sumará dos divisores D1 = [u1, v1] y D2 = [u2, v2] tales que gr(u1) = gr(u2) = 2.

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el que sedefine la curva char y los polinomios u1 = x2+u11x+u10, v1 = v11x+ v10 y u2 = x2+u21x+u20,v1 = v11x+v10 que representan respectivamente a los divisores D1 y D2. Además gr(u1) = gr(u2) =2. }

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = D1 +D2. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }

� SumarGrDistinto

Esta función sumará dos divisores D1 = [u1, v1] y D2 = [u2, v2] tales que gr(u1) = 1 y gr(u2) = 2.

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el que sedefine la curva char y los polinomios u1 = x+u10, v1 = v10 y u2 = x2+u21x+u20, v1 = v11x+v10que representan respectivamente a los divisores D1 y D2. Además gr(u1) = 1 y gr(u2) = 2. }

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = D1 +D2. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }.

17


� Restar

El objetivo de este procedimiento es restar dos divisores de grado distinto. Los divisores vendrándados porD1 = [u1, v1] y D2 = [u2, v2] tales que gr(u1) = 1 y gr(u2) = 2.


{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = D1−D2. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }.

� Doblar

Esta función doblará un divisor D1 = [u1, v1] tal que gr(u1) = 2.

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char y los polinomios u1 = x2 + u21x + u20, v1 = v11x + v10 que correspondenal divisor D1. Además gr(u1) = 2. }

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = 2D1. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }.

� Producto de divisor por constante

Dados un divisor D y un número entero n este algoritmo calculará el divisor nD mediante elalgoritmo del campesino ruso.

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char y los polinomios u1 = x2 + u11x + u10, v2 = v11x + v10 que correspondenal divisor D1 además de un entero n. }

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = nD1. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }.

� Orden de un divisor

Dado un divisor D, este procedimiento nos devolverá el orden de este, es decir, cuantas veceshay que sumarle D a sí mimos para obtener el elemento neutro [1, 0].

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char y los polinomios u1 = x2 + u11x + u10, v2 = v11x + v10 que correspondenal divisor D. }

{POST: devuelve un entero n que será el orden del divisor D }.

18


� Puntos de una curva hiperelíptica

Dada una curva hiperelíptica C : y2 + h(x)y = f(x) esta función nos devolverá el conjunto depuntos racionales asociados a esta.

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char. }

{POST: devuelve una lista formada por todos los puntos racionales de una curva hiperelíptica(menos el punto en el infinito) }.

Nota 3.6.1. Junto a esta función también implementaremos otra función útil que nos calculará elcardinal del conjunto de puntos racionales.

Así tendremos la siguientes especificación:


{POST: devuelve un entero n que será el cardinal del conjunto de los puntos racionales de C }.

� Divisor Semirreducido

Dada una lista de puntos con el correspondiente orden de un divisor en cada uno de los puntos,lo que hará este procedimiento es calcular el divisor semirreducido asociado.

{PRE: L que es una lista con puntos formados por 3-tuplas, en las que la primera componentees el orden del divisor en el punto dado por las siguientes dos coordenada de la tupla. Además,también tendrá como parámetros de entrada a f , h son los polinomios que definen la curva C, lacaracterística del cuerpo sobre el que se define la curva char. }

{POST: una lista L′ compuesta por tres tuplas en las que la primera componente es el orden deldivisor en el punto dado por las siguientes dos coordenada de la tupla. Los elementos de L debencumplir que si Pi ∈ sop(D) entonces −Pi /∈ sop(D), a no ser que Pi = −Pi, que ocurre cuando Pi

es especial. En este caso, la multiplicidad será mi = 1 }.

3.7 DIAGRAMA DE CLASES

Procedamos ahora a desarrollar el diagrama de clases.

Parte de nuestra aplicación será una interfaz que inteactuará con Mathematica y hará muchomás fácil el proceso de cifrado/descifrado al usuario. Cada actividad que se realice (cifrado, firma,verificación...) se hará de forma independiente, sin existir ningún tipo de relación entre ellas.

Por cada acción que realice la aplicación habrá una clase: una para cifrar, otra para descifrar,otra para firmar.. y así con todas y cada una de las acciones. Es por esto que solo daremos elejemplo de unas pocas clases, ya que todas realizarán operaciones análogas.

19


3.7.1 Clase básica

Para empezar vamos a construir la clase Cifrar (el resto de clases tendrán una forma similar).

Figura 3.1.: Diagrama de Clases: Cifrar

Como vemos en la figura 3.1, esta clase tiene dos métodos y un atributo, este último lo explica-remos más adelante, pero podemos decir que funciona como una guía que nos indica dónde está ycuál es el archivo con el que se va a trabajar.

Los dos métodos que aparecen son:

Aceptar(), que realizará el proceso de cifrado.

Cancelar(), que cancelará la ecriptación.

3.7.2 Clase Gestor

Esta clase será la gestora de información: tendrá dos campos: uno que guardará la ruta de ladirección del archivo y otro que nos indicará el nombre de este. Así en todo momento nuestraaplicación sabrá dónde está y cuál es el archivo con el que está trabajando y al finalizar el procesode cifrado (por ejemplo) será capaz de almacenar el nuevo fichero con el texto encriptado en lamisma carpeta donde se encontraba el original.

Figura 3.2.: Diagrama de Clases: Gestor

Como vemos en la figura, esta clase tiene dos atributos privados:

Ruta: contiene la ruta de la carpeta en la que está contenido el archivo.

Nombre_ Archivo: que guardará el nombre del archivo con en el que esté en ese momentotrabajando la aplicación.

3.8 PROTOTIPO DE INTERFAZ

Ahora veremos a grandes rasgos como será la interfaz con el usuario de nuestra aplicación decifrado.

20


Para ello dividiremos esta sección en dos grandes bloques:

En el primero hablaremos de la interfaz que se encontrará el usuario nada más abrir laaplicación.

En el segundo se explicará, a grandes rasgos, en que momentos aparecerán los errores.

3.8.1 Prototipo Inicio

Al iniciar la aplicación el usuario se encontrará una barra de menú con dos opciones: una que sellamará Árchivo’y otra llamada ’Claves’. Especifiquemos los menús de cada una de estas opciones:

Archivo

• Cifrar...: Al hacer click sobre esta opción del submenú se abrirá una ventana que nosdará a elegir una serie de usuarios y nos permitirá elegir un archivo para cifrar.

• Firmar...: aparecerá otra ventana con las opciones de firmado.

• Cifrar y Firmar...: al igual que en las dos opciones anteriores, se creará una ventana quenos permite cifrar y firmar un archivo de texto, eligiendo el archivo con el que deseamostrabajar y el usuario con el que queremos cifrar el mensaje.

• Descifrar...: como antes, aparecerá otra ventana que facilitará al usuario el proceso dedescifrado.

• Verificar Firma...: clickeando sobre esta opción, se abrirá una ventana que ayuda aautentificar el usuario emisor del mensaje, ofreciendo al usuario una lista con los distintosusuarios de los que se disponen las claves y la posibilidad de seleccionar un archivo.

• Mensaje... se abrirá una ventana con un cuadro de texto para copiar un mensaje ycifrarlo, sin necesidad de crear un documento de texto que contenga dicho mensaje.

Claves

• Generar clave pública...: se abrirá una ventana. En ella se podrá crear una clave pública,después de completar una formulario con los datos del usuario.

• Generar clave privada: al hacer click sobre esta opción, se abrirá una ventana quepermitirá al usuario crear una llave privada. En este caso, no será necesario completarun formulario, sino que el usuario se seleccionará de una lista de usuarios y después dehacer click en aceptar, se generará la clave.

• Propiedades de la clave..: aparecerá una ventana con las propiedades de las claves: sobreque curva están definidas, el cuerpo sobre el que está definida la curva... Es decir, losparámentros universales del protocolo criptográfico.

• Eliminar clave/usuario: eliminará la clave y/o usuario del sistema.

21


3.8.2 Mensajes de advertencia

Las ventanas que aparecerán en caso de error serán todas similares.

Estas aparecerán si Mathematica no está abierto mientras se realiza el cifrado, si el ficheroimportado no es el adecuado o está vacío...

3.9 FASE DE PRUEBAS

Podemos dividir las pruebas que vamos a realizar en cuatro grandes bloques:

1. Pruebas de las funciones: se probarán todas las funciones implementadas con Mathematicauna a una. Así verificaremos que todas ellas funcionan correctamente.

2. Pruebas unitarias: que servirán para asegurar que cada módulo funciona correctamente. Estose hará asilando algunas funciones y comprobando que funcionan tal y como queremos.

3. Pruebas de integración: que verificarán que todos los módulos trabajan de manera conjunta.

4. Pruebas de aceptación: que determinarán si todos los requisitos del sistema son cumplidos

En la fase de diseño, se establecerán todas las pruebas que se efectuarán una vez implementadocada módulo.

22


4. FASE DE DISEÑO

En este capítulo se refinará todo lo que hemos hecho en la fase de análisis. Lo que se intentaráhacer es explicar mejor cada una de las funciones que se han descrito en la fase anterior.

Cuando todo esto esté acabado, lo que se intentará es mejorar el rendimiento, intentando utilizartodo lo que Mathematica nos puede llegar a ofrecer.

Antes de nada, se debe tener en cuenta la arquitectura básica de nuestro sistema, en el que existeuna relación bidireccional entre Mathematica y la aplicación Java que vamos a construir. Ambaspartes de nuestro sistema estarán en constante contacto: mientras que una gestionará los archivoseligiendo la fuente y el destino del nuevo archivo cifrado, la otra se aplicará el protocolo de curvashiperelípticas al archivo que se quiere encriptar.

Empecemos pues a dar una lista de los algoritmos más importantes que se usarán a la hora decifrar los archivos seleccionados por el usuario. Pero antes de nada, tengamos en cuenta que:

p es el número primo mayor que divide al jacobiano asociado a la curva hiperelíptica C conla que estamos trabajando.

a y A son respectivamente las claves privada y pública del emisor del mensaje.

b y B son las dos claves (privada y pública) del receptor del mensaje.

D es el divisor (que actúa como punto base) que genera el grupo cíclico con el que estamostrabajando.

Añadir también que recordaremos de nuevo cada una de las especificaciones de cada uno de losprocedimientos que vamos a ver a continuación para que así sea más fácil de comprender cada unode ellos.

Ahora sí, veamos los algoritmo más importantes en este proceso de cifrado.

4.1 GENERACIÓN DE CLAVES

{PRE: f , h que son los polinomios que definenn la curva C, la caracterísitca del cuerpo sobreel que se define la curva char, p el número primo más grande que divide al cardinal del jacobianoasociado a la curva hiperelíptica C y el punto base D }

{POST: r ∈ [1, p−1] que será la clave pública, y rD = R que corresponderá a la clave privada}

1. Se elegirá un entero aleatorio r ∈ [1, p− 1].

2. Mediante el algoritmo del campesino ruso (que explicaremos más adelante) se calculará rD

23

4. FASE DE DISEÑO

4.2 CIFRADO

{PRE: f , h que son los polinomios que definenn la curva C, la caracterísitca del cuerpo sobreel que se define la curva char, la 4-tupla (M1,M2,M3,M4) que representa al mensaje M , ademásde los divisores B que será la clave pública del destinatario del mensaje y el punto base D }

{POST: la cuatro tupla (M ′1,M

′2,M

′3,M

′4) que será el mensaje M cifrado y el divisor D′ }

1. Se genera un entero aleatorio k ∈ [1, p− 1].

2. Se calcula el divisor kB representado por le par de polinomios [x2 + u1x+ u0, v1x+ v0]. Secomprobará que ninfuno de los polinomios tiene algún coeficiente igual a cero. Si es que lostiene, volvemos a 1.

3. Se hacen las multiplicaciones

M ′1 = M1u1

M ′2 = M2u0

M ′3 = M3v1

M ′4 = M4v0

y así obtenemos la 4-tupla que representa al mensaje cifrado.

4. Se calcula D′ = kD.

5. Devuelve el par ((M ′1,M

′2,M

′3,M

′4), kD).

4.3 DESCIFRADO

{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobreel que se define la curva char, la 4-tupla (M ′

1,M′2,M

′3,M

′4) que representa al mensaje cifrado M ′,

además de un entero b que será la clave privada del destinatario del mensaje y un divisor D′ }

{POST: la cuatro tupla (M1,M2,M3,M4) que será el mensaje M }

1. Se calcula el divisor bD′ = bkD = kbD = kB que estará representado por el par de polinomios[x2 + u′

1x+ u′0, v

′1x+ v′0].

2. Se calcula

M1 = M ′1(u

′1)

−1

M2 = M ′2(u

′0)

−1

M3 = M ′3(v

′1)

−1

M4 = M ′4(v

′0)

−1

3. Se devuelve la 4-tupla (M1,M2,M3,M4).

24


4.4 FIRMA

{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobre elque se define la curva char, el mensaje M , además del divisor que representa al punto base D yun número entero a que será la clave privada de la persona que firma el mensaje }

{POST: dos número enteros r y s, que representarán la firma digital }

1. Se calcula el hash del mensaje h = H(M).

2. Se genera un número aleatorio k ∈ [1, p− 1].

3. Se computa el divisor kD, representado por los polinomios [x2 + u1x+ u0, v1x+ v0].

4. Se calcula r = u0 + h mod p.

5. Se calcula s = k − ar mod p

6. Devuelve el par (r, s).

4.5 VERIFICACIÓN

{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobre elque se define la curva char, el mensaje M , la firma (r, s) del mensaje, además del divisor A querepresenta la clave pública del emisor del mensaje }

{POST: devuelve verdad si la firma del mensaje pertenece a la persona que ha enviado elmensaje y falso en caso contrario }

1. Se calcula el hash del mensaje h = H(M).

2. Se calcula el divisor sD + rA = (k − ar)D + rA = kD + (−raD + rA) = kD, que estarárepresentado por el par [x2 + u1x+ u0, v1x+ v0].

3. Se calcula r′ = u0 + h mod p.

4. Si r = r′ devuelve verdad. En caso contrario devuelve falso.

4.6 OTROS PROCEDIMIENTOS ÚTILES

4.6.1 Orden del Jacobiano


{POST: devuelve un entero n que corresponde al cardinal del jacobiano}

25

4. FASE DE DISEÑO

1. Se calcula los valores de M1 y M2.

2. Se realizan los siguientes cálculos:

a1 = M1 − 1− q

a2 =M2 − 1− q2 − a21

2

3. Se resuelve la ecuación x2 + aix+ (a2 − 2q) = 0 y se obtienen dos soluciones complejas γ1 yγ2.

4. Se resuelve las ecuaciones x2−γ1x+q = 0 y x2−gamma2x+q = 0 se obtienen dos solucionescomplejas α1 y α2.

5. Devuelve n =| 1− αr1 |2| 1− αr

1 |2

4.6.2 Mumford


{POST: devuelve un par de polinomios [u, v] que representan a un divisor D. Estos polinomiosserán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 y cumplirán que

u es mónico,

gr(v) < gr(u) < g,

u | v2 + vh(x)− f(x)

}

Supongamos que el divisor D viene dado por la lista L = {(m1, x1, y1), (m2, x2, y2), ..., (mn, xn, yn)}.Así, tendremos que

u =

n∏i=1

(x− xi)mi (4.1)

Además, se tiene que ui = (x−xi)mi , por lo que el polinomio v aparecerá al resolver el siguiente

sistema de ecuaciones modulares polinómicas con el teorema chino de los restos:

v(x) ≡ v1(x) mod u1(x) (4.2)... (4.3)

v(x) ≡ vn(x) mod un(x) (4.4)

donde cada vi es el segundo polinomio que representa al divisor Di = mi(xi, yi).

Notar que el sistema anterior tiene solución única módulo u. Esta solución sería nuestro v.

Así, esta función procederá como sigue:

26


1. Se calcula u =∏n

i=1(x− xi)mi .

2. Se calcula li = u1u2 · · ·ui−1ui+1 · · ·un.

3. Se resuelve 1 = hi(x)mi(x) + ki(x)li(x), teniendo en cuenta que

ki(x)li(x) ≡ 1 mod ui

ki(x)li(x) ≡ 0 mod uj

4. Se calcula v(x) = v1l1k1 + v2l2k2 + · · ·+ vnlnkn mod u

5. Devuelve (u, v)

Para calcular cada polinomio vi del sistema de ecuaciones polinómicas 4.2, este procedimientose apoyará en otro, que funcionará como sigue:

1. Se calcula ui = (x− xi)mi .

2. Se calcula vi(x) =∑mi−1

i ci(x− xi)i. Para determinar los ci se hará lo siguiente:

c0 = yi

Para calcular ci, se construye y resuelve el sistema de mi − 1 ecuaciones con mi − 1incógnitas (que serán los distintos coeficientes ci). Cada ecuación del sistema se obtendrácalculando la derivada de orden mi.

Devuelve (ui, vi)

4.6.3 Algoritmo de Cantor-Lange

{PRE: f , h que son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char y los polinomios u1 = x2+u11x+u10, v1 = v11x+v10 y u2 = x2+u21x+u20,v1 = v11x+ v10 que representan respectivamente a los divisores D1 y D2. Además gr(u1) < gr(u2).}

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = D1 +D2. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 y cumplirán que

u es mónico,

gr(v) < gr(u) < g,

u | v2 + vh(x)− f(x)

}

1. Si D1 = [1, 0], devuelve D2.

2. Si gr(u1) = 1 tenemos dos casos:

a) Si gr(u2) = 1

27

4. FASE DE DISEÑO

1) Si u1 = u2 pero v1 6= v2, devuelve [1, 0].

2) Si u1 = u2 y v1 = v2, devuelve los polinomios

u = u21

v =(f ′(−u10)− v1h

′(−u10))x

2v1 + h(−u10)

+(f ′(−u10)− v1h

′(−u10))u10

2v1 + h(−u10)+ v1

3) Si u1 6= u2, devuelve los polinomios

u = u1u2

v =(v2 − v1)x+ v2u10 − v1u20

u10 − u20

b) Si gr(u2) = 2

1) Si u2(−u10) 6= 0 llama al procedimiento sumarGrDistinto.

2) Si u2(−u10) = 0 puede ocurrir que

a′ Si u21 = 2u10andu20 = u210 se dobla D2 y se resta D1 (estos dos procedimientos

los explicaremos más adelante).

b′ Si v2(−u10) = v1 + h(−u10) devuelve la clase u = x + u21 − u10 and v =v2(−u21 + u10).

c′ En caso contrario primero se dobla [u1, v1] y después se suma [x + u21 −u10, v2(−u21 + u10)], reduciendo el problema a 2b.

3. Si gr(u1) = 2

a) Si u1 = u2 puede ocurrir que

1) Si v1 ≡ −v2 − h mod u1 devuelve [1, 0].

2) Si v1 = v2, tenemos dos casos nuevos:

a′ Si Res(h+ 2v1, u1) 6= 0 doblamos el divisor D1.

b′ Si Res(h+ 2v1, u1) = 0, calculamos el máximo común divisor de los polinomiosh + 2v1 y u1, que será x − x1 y así se obtiene u y v al doblar x + u11 + x1 yv1(−u11 − x1).

3) En caso contrario se obtendrán los polinomios que buscamos al doblar la clase dadapor los polinomios x− v10 − v20

v21 − v11y v1(

v10 − v20v21 − v11

).

b) Si u1 6= u2

1) Si Res(u1, u2) 6= 0, se llamará a la función SumarGrDos.

28


2) Si Res(u1, u2) = 0, se calcula el máximo común divisor de u1 y u2, que será x− x1.Aquí también puede ocurrir que:

a′ Si v1(x1) = v2(x2), se actúa como sigue: se dobla la clase x − x1, v1(x1), paradespués sumar mediante SumarGrDistinto la clase anterior con la clase dadapor x− (−u11−x1) y v1(−u11−x1). Para finalizar se suma de nuevo medianteSumarGrDistinto la clase anterior con la clase dada por x − (−u21 − x1) yv2(−u21 − x1).

b′ v1(x1) 6= v2(x2), se suman las clases dadas por los polinomios x− (−u11 − x1),v1(−u11 − x1) y x− (−u21 − x1), v2(−u21 − x1).

� SumarGrDos

Esta función sumará dos divisores D1 = [u1, v1] y D2 = [u2, v2] tales que gr(u1) = gr(u2) = 2.{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el que sedefine la curva char y los polinomios u1 = x2+u11x+u10, v1 = v11x+ v10 y u2 = x2+u21x+u20,v1 = v11x+v10 que representan respectivamente a los divisores D1 y D2. Además gr(u1) = gr(u2) =2. }

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = D1 +D2. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }

1. Se calcula r, la resultante u1 y u2.

2. Se calcula el casi inverso de u2 mod u1.

3. Se calculamos s′ = rs = ((v1 − v2)inv) mod u1.

4. Si s′0 6= 0

a) Se hace mónico a s′, obteniendo así el polinomio s′′.

b) Se calcula l′ = s′′u2 = x3 + l′2x2 + l′1x+ l′0.

c) Se calcula u = (s(l + h+ 2v2)− t)/u1.

d) Se calcula v = (−h− (l + v2)) mod u.

5. Si s′0 = 0

a) Se calcula s.

b) Se calcula u = (t− s(l + h+ 2v2))/u1, que es de grado uno.

c) Se calcula v = (−h− (l + v2)) mod u, que es constante.

6. Devuelve (u, v)

29

4. FASE DE DISEÑO

� SumarGrDistinto


{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = D1 +D2. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }.

1. Se calcula r = u2 mod u1.

2. Se calcula el inverso u2 mod u1.

3. Se calcula s = ((v1 − v2)inv) mod u1.

4. Se calcula l = su2 = s0x2 + l1x− l0.

5. Se calcula t′ = (f − v2h− v22)/u2 = x3 + t2x2 + t1x+ t0.

6. Se calcula u′ = (t− s(l + h+ 2v2))/u1 = x2 + u′1x+ u′

0.

7. Se calcula v′ = (−h− (l + v2)) mod u′, y v = v′1x+ v′0.

8. Devuelve (u′, v′)

� Restar


{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = D1−D2. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }.

1. Se calculan las coordenadas del punto del soporte de D1. Supongamos que estas coordenadasson (x1, y1).

2. Se calcula el inverso de (x1, y1), que viene dado por (x1,−y1 − h(x1)) y se obtiene el divisor−D1 = [x− x1,−y1 − h(x1)].

3. Se llama a SumarGrDistinto para sumar D2 + (−D1) y así obtener los polinomios deseados.

� Doblar

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char y los polinomios u1 = x2 + u21x + u20, v1 = v11x + v10 que correspondenal divisor D1. Además gr(u1) = 2. }

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = 2D1. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }.

30


1. Se calcula v = (h+ 2v1).

2. Se calcula el resto r entre v, u1.

3. Se calcula el casi inverso inv′ = rinv.

4. Se calcula t = ((f − hv1 − v21)/u1) mod u1 = t1x+ t0.

5. Se calcula s′ = (tinv′) mod u1

6. Si s1 6= 0

a) Se calcula s′′ = x+ s0/s1 y s1.

b) Se calcula l = s′′u1 = x3 + l2x2 + l1x+ l0.

c) Se calcula u′ = s2 + (h+ 2v1)s/u1 + (v21 + hv1 − f)/u21.

d) Se calcula v′ = (−h− (l + v1)) mod u′ = v′1x+ v′0.

e) Devuelve (u′, v′).

7. Si s1 = 0

a) Se calcula s.

b) Se calcula u = (f − hv1 − v21)/u21 − (h+ 2v1)s/u1 − s2.

c) Se calcula v = (−h− (su1 + w1)) mod u.

� Producto de divisor por constante

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char y los polinomios u1 = x2 + u11x + u10, v2 = v11x + v10 que correspondenal divisor D1 además de un entero n. }

{POST: devuelve un par de polinomios [u, v] que representan a un divisor D = nD1. Estospolinomios serán de la siguiente forma u = x2 + u1x+ u0 y v = v1x+ v0 }.

1. Se asigna a P = D1 y a R = D1

2. Si n es múltiplo de 2

a) Se asigna E = n− 1

3. Si n no es múltiplo de 2

a) E ←− n

4. Mientras que E > 0

a) Si E 6= n

31

4. FASE DE DISEÑO

1) Si E no es divisible por dos se calcula R←− R+ P

b) Doblamos P tal que P = doblar(P )

c) Se calcula la mitad de E: E =E

2

5. D = R

6. Devuelve D

4.6.4 Orden de un divisor

{PRE: f , h son los polinomios que definen la curva C, la característica del cuerpo sobre el quese define la curva char y los polinomios u1 = x2 + u11x + u10, v2 = v11x + v10 que correspondenal divisor D. }

{POST: devuelve un entero n que será el orden del divisor D }.

1. uaux = u y vaux = u

2. Inicializamos el contador y la condición del bucle

n = 1

cond = 0

3. Mientras que cond == 0

{uaux, vaux} = Cantor(u, v, aux, vaux, f, h, char)

Incrementamos el valor de n

Si uaux = 1 y vaux = 0, cambiamos el estado de la condición, es decir, cond = 1

4. Devuelve n

4.6.5 Puntos de una curva hiperelíptica


{POST: devuelve una lista formada por todos los puntos racionales de una curva hiperelíptica(menos el punto en el infinito) }.

1. Creamos una lista vacía L = {}.

2. Para i = 0 hasta i ≤ char calcular f(i) y h(i) ambas módulo char.

3. Para j = 0 hasta j ≤ char hacer:

32


a) Si j2 − jh(i) == f(i) módulo char, entonces añadir {i, j} a L.

4. Devuelve L.Nota 4.6.1. La función que calcula el cardinal del conjunto de puntos racionales de una curvahiperleíptica lo que hará es llamar a esta función y mediante la orden Length hallará dicho entero.

4.6.6 Divisor Semirreducido

{PRE: L que es una lista con puntos formados por 3-tuplas, en las que la primera componentees el orden del divisor en el punto dado por las siguientes dos coordenada de la tupla. Además,también tendrá como parámetros de entrada a f , h son los polinomios que definen la curva C, lacaracterística del cuerpo sobre el que se define la curva char. }

{POST: una lista L′ compuesta por tres tuplas en las que la primera componente es el orden deldivisor en el punto dado por las siguientes dos coordenada de la tupla. Los elementos de L debencumplir que si Pi ∈ sop(D) entonces −Pi /∈ sop(D), a no ser que Pi = −Pi, que ocurre cuando Pi

es especial. En este caso, la multiplicidad será mi = 1 }.

A grandes rasgos este procedimiento funcionaría como sigue:

1. En un primer bucle se suman las multiplicidades de los puntos iguales. Así tendremos unalista de puntos que son todos diferentes.

2. En el segundo bucle se restan multiplicidades de puntos opuestos, es decir, si P1 = (x1, y1) yP2 = (x2, y2) tal que y2 = −y1 − h(x1), restamos su multiplicidad y el representante será elque tenga una multiplicidad mayor.

3. En un tercer y último bucle comprobamos que puntos son especiales y les asignamos multi-plicidad uno. Un punto será especial si P1 = −P1, es decir, si y1 = −y1 −H(x1).

4.7 DIAGRAMA DE CLASES

Lo que se hará en esta sección es hacernos una idea más concisa de las clases que se han construidoen la fase de análisis. El modelo en sí no tendrá cambios significativos.

Como ocurría en la fase de análisis, veremos solamente una de las clases, ya que el resto seconstruirían de manera análoga.

4.7.1 Clase básica

Nos volvemos a centrar en la clase Cifrar.

Figura 4.1.: Diagrama de Clases: Cifrar

33

4. FASE DE DISEÑO

Como vemos, a parte de los métodos Aceptar() y Cancelar(), hemos añadido un nuevo método:SeleccionarArchivo(). Este método se encargará de seleccionar el archivo que el usuario desea cifrar.

4.7.2 Clase Gestor

Expliquemos en la clase Gestor. Esta clase es la responsable de guardar la ruta completa delarchivo a cifrar, junto al nombre de este. Se ha creído conveniente añadir algunos atributos nuevos.

Uno de estos atributos sería Texto que tendrá dos estados:

Estado inicial: que contendrá una copia del texto/mensaje que se desea cifrar, es decir, eltexto plano.

Estado final: que almacenará una copia del texto cifrado para después guardarlo en un archivode texto.

Así aparece nuestra variable booleana, estado que nos marcará en que fase del proceso de cifrado(entre otros) nos encontramos.

Además, habrá también otro atributo más: clave, que hará referencia a la clave (ya sea pública oprivada) que se utiliza en casi todos los procesos que se han mencionado en los apartados anteriores.

Junto a todos estos atributos, se ha considerado que también es necesario añadir un métodonuevo, CopiarTexto() que copiará el texto del fichero/mensaje a encriptar si la variable estado noestá inicializada, o el texto del fichero/mensaje cifrado si la variable ya ha cambiado de estado.

Después de todas estas consideraciones, la clase gestor quedaría como muestra la figura 4.2.

Figura 4.2.: Diagrama de Clases: Gestor

4.8 PROTOTIPO DE INTERFAZ

Siguiendo la especificación de interfaz vista en la fase de análisis, podemos dar un prototipo deldiseño de la interfaz de nuestra aplicación.

34


4.8.1 Prototipo Inicio

Figura 4.3.: Prototipo Página Inicio

Cada menú tendrá las siguientes opciones:

Figura 4.4.: Prototipo Página Principal: Menú Archivo

Figura 4.5.: Prototipo Página Principal: Menú Claves

35

4. FASE DE DISEÑO

4.8.2 Prototipo Cifrar

Figura 4.6.: Prototipo Cifrar

El resto de ventanas serán similares a la figura 4.6.

4.8.3 Mensajes de advertencia

Figura 4.7.: Prototipo Cifrar

4.9 FASE DE PRUEBAS

Ahora se procederá a diseñar cada una de las pruebas que se realizarán nuestra aplicación. Comose ha dicho en el capítulo de análisis, existen 4 tipos de pruebas: una que se realizarán a todas ycada una de las funciones de cifrado que se implementarán en Mathematica, además de las pruebasunitarias, de integración y de aceptación.

36


4.9.1 Pruebas de las funciones

Prueba 1

Descripción Se irán comprobando una a una las operaciones implementadascon Mathemtica para ver si los resultados obtenidos son los desea-dos.

Procedimiento Se utilizarán las curvas de género g = 2 con ecuaciones C1 :y2 = x5 + x4 + x3 + 2x2 + x + 1 sobre Z11 y C2 : y2 + xy =x5 + 5x4 + 6x2 + x + 3 sobre Z7 para realizar varios ejemplos.Para ver que cada procedimiento funciona como se espera, serealizarán las trazas de todas y cada una de las funciones y/o secomprobarán con otros algoritmo análogos.

Resultado esperado En cada algoritmo se espera una salida acorde con la especifica-ción que se dio en la fase de análisis.

Cuadro 4.1.: Prueba 1: Procedimientos Mathematica

4.9.2 Pruebas unitarias

Prueba 2

Descripción Se aísla el método copiarTexto y comprobamos que funciona co-rrectamente copiando el texto de un fichero a una cadena legiblepor Mathematica.

Procedimiento De manera aislada probaremos este método con un archivo detexto.

Resultado esperado Lo que se espera de este método es que el texto que contenga elarchivo quede copiado en una lista en Mathematica.

Cuadro 4.2.: Prueba 2: Procedimiento copiarTexto

4.9.3 Pruebas de integración

Prueba 3

Descripción Integración del procedimiento copiarTexto a nuestro sistema.

Procedimiento Probaremos este método con un archivo de texto una vez incluidoen nuestro sistema.

Resultado esperado Copia el texto del fichero en una lista de Mathematica.

Cuadro 4.3.: Prueba 3: Procedimiento copiarTexto

4.9.4 Pruebas de aceptación

El siguiente conjunto de pruebas corresponden a la captura de requisitos de la fase de análi-sis, es decir, comprobaremos que cada una de las acciones que realiza nuestra apliación funcionacorrectamente.

37

4. FASE DE DISEÑO

Prueba 4

Descripción Comprobar que la función Generación de Claves devuelve lasclaves pública y privada de un determinado usuario.

Procedimiento El cliente selecciona creación de claves.

Resultado esperado Devuelve las dos claves que deberá usar el cliente para poderejecutar el resto de opciones de la aplicación.

Cuadro 4.4.: Prueba 4: Generación de Claves

Prueba 5

Descripción Comprobar que la opción Cifrar de nuestra aplicación funcionatal y como queremos.

Procedimiento El usuario seleccionará un fichero de texto prueba.txt y una clavey le hará click sobre Áceptar’.

Resultado esperado Nos devuelve el fichero prueba_ cifrada.txt que contendrá el textocifrado del fichero prueba.txt.

Cuadro 4.5.: Prueba 5: Cifrar

Prueba 6

Descripción Miraremos que la función Descifrar de nuestra aplicación funcio-na tal y como debe.

Procedimiento El usuario escogerá el archivo ya cifrado prueba_ cifrada.txt yuna de las claves y le dará a Áceptar’.

Resultado esperado Un archivo .txt llamado prueba que contenga el texto llano co-rrespondiente.

Cuadro 4.6.: Prueba 6: Descifrar

Prueba 7

Descripción Funcionamiento de la opción Firmar de nuestra aplicación.

Procedimiento El usuario escogerá el archivo prueba.txt y le dará a Áceptar’.

Resultado esperado Se creará un archivo .txt que contenga el texto y la firma digitalcorrespondientes al archivo seleccionado.

Cuadro 4.7.: Prueba 7: Firma Digital

38


Prueba 8

Descripción Funcionamiento de la opción Verificar de nuestra aplicación.

Procedimiento El usuario seleccionará el archivo creado en la prueba anterior yuna clave para después hacer click sobre Áceptar’.

Resultado esperado Una pantalla que nos diga sí el emisor es el que esperábamos

Cuadro 4.8.: Prueba 8: Verificación Firma

Prueba 9

Descripción Comprobar que la opción conjunta Cifrar y Firmar funciona co-rrectamente.

Procedimiento El usuario seleccionará un fichero de texto prueba.txt y una clavey le hará click sobre Áceptar’.

Resultado esperado Nos devuelve el fichero prueba_ cifrada.txt que contendrá el textocifrado del fichero y la firma digital prueba.txt correspondientesa la clave que se le ha pasado a la aplicación.

Cuadro 4.9.: Prueba 9: Cifrado y Firma Digital

Nota 4.9.1. Merece la pena destacar que muchas de las pruebas se realizarán pasando a la aplicaciónvarios usuarios, es decir, constarán de varias pruebas más pequeñas. Este es el caso, por ejemplo,de Verificar (es decir la prueba 4.8), ya que para comprobar que la función se comporta tal ycomo se desea le pasaremos varios usuarios. Así comprobaremos que esta opción acepta las firmasautentificadas o declina las firmas que no se corresponden con el emisor del mensaje.

39


5. FASE DE IMPLEMENTACIÓN

En esta penúltima fase, se abordarán todas las ideas desarrolladas en los capítulos anteriores,así como los problemas que han ido surgiendo según se ha ido avanzando en el proyecto.

Como es de esperar, esta es la fase más costosa del proyecto ya que se trata del grueso de éstepues se deben implementar todas y cada una de las funciones de las que hemos ido hablando.

Este capítulo se organizará en dos apartados:

Un parte que constará de todas las funciones que hemos ido implementando para Mathema-tica.

Otra segunda parte que hablará de la implementación de la interfaz gráfica en JAVA.

Además, y antes de todo esto, también se discutirán las diferentes alternativas de implementaciónbarajadas y el porqué de la elegida.

5.1 ALTERNATIVAS TECNOLÓGICAS

Como ya hemos comentado en los capítulos anteriores, nos hemos decantado por realizar laaplicación criptográfica usando tanto Mathematica como Java. Se eligió trabajar con Mathematicaya que, aunque no es un programa que trabaja con estructuras algebraicas (como en nuestro caso,los cuerpos finitos), tiene ya implementadas un gran número de funciones realmente eficientes quetrabajan con polinomios módulo un número entero p primo.

Por otro lado, también se eligió Java como lenguaje de programación de la interfaz porque hasido el más usado durante toda la carrera y, además, porque gracias a J/Link se puede conectarfácilmente a Mathematica.

La aplicación que hemos desarrollado enviará una serie de archivos a Mathematica para que,gracias a las funciones implementadas en el lenguaje de este programa, este cifre el mensaje.Además, y como hemos comentado con anterioridad, hemos creado una clase Gestor que guardarátoda la información sobre el archivo que queremos encriptar.

5.2 FUNCIONES MATHEMATICA

Antes de ver cuáles son los procedimientos implementados explicaremos cuales son los problemasque nos han ido surgiendo mientras íbamos construyendo todas las operaciones y cuáles han sidolos cambios que hemos decidido introducir para un mejor funcionamiento del programa.

41


5.2.1 Problemas con el Paquete FiniteFields

Según se iban implementando los distintos procedimientos, nos fuimos dando cuenta de que elpaquete de FiniteFields aumentaba notablemente el tiempo de ejecución de todos los procedimien-tos, llegando incluso a bloquear algunos de ellos y obligando unas veces a abortar la función eincluso a matar el núcleo. Se trató de buscar alternativas, pero no se encontraron (entre otras seactualizó la versión de Mathematica a la 9, pero persistían los problemas). Es por esto, que hemosdecidido restringir el campo de aplicación de todas nuestras funciones a curvas hiperelípticas sobrecuerpos finitos de característica p prima, ya que todas las funciones que usaremos en nuestros al-goritmos, y que ya están implementadas en Mathematica, nos permiten añadir la opción Modulus→ p que nos restringe estas operaciones módulo p.

Pero para el cálculo de M2 (el segundo de los valores de entrada del procedimiento que calculael orden del jacobiano) sí que hemos necesitado este paquete, ya que necesitamos saber el cardinaldel conjunto de puntos racionles de la curva C sobre Fp2 .

5.2.2 Funciones Mathematica

Como hemos dicho anteriormente, en este subapartado vamos a ir describiendo cada una de lasfunciones implementadas para la creación de este protocolo criptográfico.

Antes de comenzar, es importante resaltar que algunos de los procedimientos implementado hancambiado a lo largo del proceso para así mejorar la eficiencia de todo el criptosistema.

Empecemos a ver las funciones implementadas. Seguiremos el siguiente orden:

1. Funciones relacionadas con la cardinalidad del jacobiano de a curva.

2. Funciones asociadas a la representación de divisores.

3. Funciones implementadas para la creación del criptosistema utilizando el algoritmo de Can-tor. Aparecerán dos grupos:

a) Funciones que tienen que ver con el algoritmo de Cantor (suma, reducción, orden de undivisor...).

b) Funciones de elGammal adaptado a curvas hiperelípticas.

4. Funciones creadas para conseguir un criptosistema más eficiente. Aquí aparecerán todas lasfunciones implementadas a partir de los textos de Tanja Lange ( [CFA06], [Lan02a], [Lan05]).

� Funciones relacionadas con el Jacobiano de la curva

PuntosCurva

Código 5.1: Función PuntosCurva usando polinomios como entradas

PuntosCurva[f_, h_, char_] := (Module[{Puntos, fi, hi, i, j, M1},Puntos = {};M1 = 1;

42


For[i = 0, i < char, i++,For[j = 0, j < char, j++,fi = Mod[f /. x -> i, char];hi = Mod[h /. x -> i, char];If[fi == Mod[j^2 + j*hi, char],Puntos = Union[Puntos, {{i, j}}];M1 = M1 + 1;];];

];Return[{M1, Puntos}];];

);

Código 5.2: Función PuntosCurva usando listas como entradas

PuntosCurvaLista[f_, h_,char_] := (Module[{Puntos, fi, hi, i, j, M1},Puntos = {};M1 = 1;For[i = 0, i < char, i++,For[j = 0, j < char, j++,fi =Mod[f[[1]] + f[[2]]*i + f[[3]]*i^2 + f[[4]]*i^3 +f[[5]]*i^4 + i^5, char];

hi = Mod[h[[1]] + h[[2]]*i + h[[3]]*i^2, char];If[fi == Mod[j^2 + j*hi, char],Puntos = Union[Puntos, {{i, j}}];M1 = M1 + 1;];];

];Return[{M1, Puntos}];];

);

La función PuntosCurva 5.1 nos devuelve una lista dos elementos:

El primero es la cardinalidad del conjunto de los puntos raciones de C.

Es segundo, es de nuevo una lista que contiene todos los puntos racionales.

Se ha implementado una función en vez las dos que se tenían pensadas (PuntosCurva yOrdenRacionales), porque así no se calcula dos veces el conjunto de puntos racionales a lahora de averiguar el cardinal dicho conjunto, por lo que con este proceso ahorraremos muchotiempo en el futuro.

Como lo que buscamos es un sistema eficiente, se ha desarrollado una segunda versión deeste algoritmo usando dos listas. Una será una lista formada por los coeficientes de f y otracon los coeficiente de h1.

CalculoM2Este procedimiento lo que hace es calcular el valor de los puntos racionales de C pero estavez sobre Fpn . Como hemos dicho antes, esta función sí que usa el paquete FiniteFields.

1En el siguiente capítulo veremos las pruebas realizadas sobre cada algoritmo. En ellas mostraremos el tiempo deejecución de cada una de las funciones, así como el tiempo de ejecución de todo el protocolo criptográfico en losdistintos casos

43


Podríamos decir que ésta es la función menos eficiente de todos los procedimientos creados.Como ocurría en el caso anterior, se han implementado dos funciones: una que usa listas(5.4) y otra que usa polinomios (5.3).

Código 5.3: Función CalculoM2 con polinomios

CalculoM2[f_, h_, char_] := (Module[{M2, fa, ha, i, j, K1},

K1 = GF[char, 2];SetFieldFormat[K1, FormatType -> FunctionOfCode[k1]];M2 = 1;For[i = 0, i < FieldSize[K1], i++,For[j = 0, j < FieldSize[K1], j++,fa = f /. x -> k1[i];ha = h /. x -> k1[i];If[fa == k1[j]^2 + k1[j] *ha,M2 = M2 + 1;];];

];Return[M2];];

);

Código 5.4: Función CalculoM2Listas

CalculoM2Listas[f_, h_,char_] := (Module[{Puntos, fi, hi, i, j, M2, K1, k1, n},(* Funcique calcula los puntos racionales de una curva C:y^2+h(x)y=f(x) *)M2 = 1;K1 = GF[char, 2];n = FieldSize[K1];SetFieldFormat[K1, FormatType -> FunctionOfCode[k1]];Puntos = {};For[i = 0, i < n, i++,For[j = 0, j < n, j++,fi =f[[1]] + f[[2]]*k1[i] + f[[3]]*k1[i]^2 + f[[4]]*k1[i]^3 +f[[5]]*k1[i]^4 + k1[i]^5;

hi = h[[1]] + h[[2]]*k1[i] + h[[3]]*k1[i]^2;If[fi == k1[j]^2 + k1[j]*hi,M2 = M2 + 1;];];

];Return[M2];];

);

Jacobiano

La función Jacobiano 5.5 es una de las más importantes en lo que a la representación de puntosse refiere. Gracias a ella sabremos de qué orden es el divisor base de nuestro criptosistema.Para calcular el orden del jacobiano, lo que hacemos es pasar los valores de los cardinalesde los puntos racionales de C primero sobre Fp (M1) y luego sobre Fp2 (M2), y gracias a lafunción-zeta obtenemos el resultado que deseamos.

44


Código 5.5: Función jacobiano

OrdenJacobiano[M1_, M2_,char_] := (Module[{K1, K2, k1, k2, Points1, Points2, i, j, p, a1,

a2, Res, Gamma1, Gamma2, Res1, Res2, Alpha1, Alpha2, Nn,JacobOrd},

p = char;a1 = M1 - 1 - p;a2 = (M2 - 1 - p^2 + a1^2)/2;

Res = Solve[x^2 + a1*x + (a2 - 2*p) == 0, x];

Gamma1 = Res[[1]][[1]][[2]];Gamma2 = Res[[2]][[1]][[2]];Res1 = Solve[x^2 - Gamma1*x + p == 0, x];Res2 = Solve[x^2 - Gamma2*x + p == 0, x];

Alpha1 = Res1[[1]][[1]][[2]]; Alpha2 = Res2[[1]][[1]][[2]];

Nn = Abs[1 - Alpha1^n]^2*Abs[1 - Alpha2^n]^2;

JacobOrd = Expand[Nn /. n -> 1];

Return[JacobOrd];

];);

� Representación de Divisores

En este apartado veremos todas las funciones que se han implementado para que nos ayudena representar de una manera más cómoda a los divisores que se encuentran en el jacobianode nuestra curva C. Como puede que estas funciones sean un poco más difíciles de entender,explicaremos los pasos que hemos ido siguiendo para implementarlas.

Código 5.6: Función SemiReducido

SemiReducido[L_, f_, h_,char_] := (Module[{Lista, n, Px1, Py1, Px2, Py2, i, j, hx, nPy1,

K1, k1, ord1, ord2},

Lista = Sort[L];n = Length[Lista];

For[i = 1, i <= n, i++,Px1 = Lista[[i]][[1]];Py1 = Lista[[i]][[2]];

For[j = i + 1, j <= n, j++,Px2 = Lista[[j]][[1]];Py2 = Lista[[j]][[2]];

If[(Px1 == Px2) && (Py1 == Py2),

Lista[[i]][[3]] = Mod[Lista[[i]][[3]] + Lista[[j]][[3]], char];Lista = Delete[Lista, j];n = n - 1;];];];

n = Length[Lista];

45


For[i = 1, i <= n, i++,Px1 = Lista[[i]][[1]];Py1 = Lista[[i]][[2]];hx = Mod[h /. x -> Px1, char];nPy1 = Mod[-Py1 - (hx), char];ord1 = Lista[[i]][[3]];

For[j = i + 1, j <= n, j++,Px2 = Lista[[j]][[1]];Py2 = Lista[[j]][[2]];ord2 = Lista[[j]][[3]];

If[Px1 == Px2,If[ord2 > ord1,Lista[[j]][[3]] = Lista[[j]][[3]] - Lista[[i]][[3]];Lista = Delete[Lista, i],Lista[[i]][[3]] = Lista[[i]][[3]] - Lista[[j]][[3]];Lista = Delete[Lista, j];If[Lista[[i]][[3]] == 0, Lista = Delete[Lista, i];n = n - 1;];];n = n - 1;];];

];

n = Length[Lista];

For[i = 1, i <= n, i++,

Px1 = Lista[[i]][[1]];Py1 = Lista[[i]][[2]];

hx = Mod[h /. x -> Px1, char];nPy1 = Mod[-Py1 - (hx), char];If[Py1 == nPy1,Lista[[i]][[3]] = 1;];];

Return[Lista];];

);

A través de la función SemiReducido ( 5.6 ) lo que hacemos es convertir un divisor cual-quiera a un divisor semirreducido. No nos será de gran utilidad a la hora de crear nuestrocriptosistema, pero la hemos considerado que era interesante agregarla a todas las funcionesque hemos creado y así crear un paquete de curvas hiperelípticas para Mathematica másinteresante.

Pasemos a explicar cómo funciona este procedimiento. Como queremos que el divisor de salidasea semirreducido el divisor de entrada pasa por una serie de bucles para que este cumplalas características deseadas. Estos son los bucles:

a) El primer bucle se encarga de sumar todos los puntos iguales del divisor.

b) El segundo bucle suma los puntos opuestos.

c) El tercero lo que hace es establecer la multiplicidad de los puntos especiales a mP = 1.

46


Código 5.7: Función PolinomiosPi

PolinomiosPi[D_, f_, h_, char_] := (Module[{lista, n, mi, i, uaux, vaux, ui, vi, j},

(* Esta funcidevuelve la representacien forma de dos \polinomios de cada uno de los puntos de la lista D,

que representa al divisor D del jacobiano de C *)

lista = {};n = Length[D];

For[i = 1, i <= n, i++,mi = D[[i]][[3]];{uaux, vaux} = {x - D[[i]][[1]], D[[i]][[2]]};{ui, vi} = {uaux, vaux};If[mi > 1,For[j = 1, j <= mi - 1, j++,{ui, vi} = SumaDivisores[uaux, vaux, ui, vi, f, h, char];];

];AppendTo[lista, {ui, vi}];];

Return[lista];];

);

La función PolinomiosPi (código 5.7) creará la representación de Mumford de cada uno delos puntos que se encuentran en el soporto del divisor. Para ello, aplica de manera recursivala operación SumaDivisores (código 5.10) que veremos más adelante.

Código 5.8: Función Mumford

Mumford[Divisor_, f_, h_,char_] := (Module[{u, cordsPix, multsPi, nD, i, lista, fs, nFs, Fs,

Mi, suma, deni, j, denj, Ni, nLista, multi, lista2, vaux, v,dem, coef, sol, num, nA},

(* Este algoritmo calculara representacide Mumford para el \divisor D del jacobiano asociado a C*)

nD = Length[Divisor];lista = {};

If[nD == 1,lista = PolinomiosPi[Divisor, f, h, char];u = lista[[1]][[1]];v = lista[[1]][[2]];Return[{u, v}];];

If[nD > 1,

(* Calculamo el polinomio u *)u = 1;cordsPix = Divisor[[All, 1]];multsPi = Divisor[[All, 3]];

For[i = 1, i <= nD, i++,u = u*(x - cordsPix[[i]])^(multsPi[[i]])];

(* Llamamos a la funciPolinomiosPi para que nos de la \representacide cada punto de D y lo almacenamos en la lista lista. \*)

lista = PolinomiosPi[Divisor, f, h, char];

47


(* Hacemos fracciones simpre en 1/u para meter cada sumando de esta suma en la lista Fs *)

fs = Apart[1/u, x, Modulus -> char];nFs = Length[fs];Fs = {};For[i = 1, i <= nFs, i++,AppendTo[Fs, fs[[i]]];];

(* Calculamos los Mi *)Mi = {};suma = 0;For[i = 1, i <= nFs, i++,For[j = 1, j <= nFs, j++,If[i != j,deni = Denominator[Fs[[i]]];denj = Denominator[Fs[[j]]];If[PolynomialRemainder[deni, denj, x, Modulus -> char] == 0,suma = Together[PolynomialMod[Fs[[i]] + Fs[[j]], char]];Fs = ReplacePart[Fs, i -> suma];Fs = Delete[Fs, j];nFs = Length[Fs];j = j - 1;];];

];];

For[i = 1, i <= nD, i++,dem = Denominator[Fs[[i]]];If[Exponent[dem, x] == 1,coef = dem[[1]];sol = Solve[coef*x == 1, x, Modulus -> char];coef = x /. sol[[1]];num = PolynomialMod[coef*Numerator[Fs[[i]]], char],num = Numerator[Fs[[i]]];];

AppendTo[Mi, num];

];Mi = Reverse[Mi];

(* Calculamos los Ni*)Ni = {};nLista = Length[lista];For[i = 1, i <= nLista, i++,multi = 1;For[j = 1, j <= nLista, j++,If[j != i,multi = PolynomialMod[multi*lista[[j]][[1]], char];];

];AppendTo[Ni, multi];];

(* Hacemos los productos *)lista2 = {};For[i = 1, i <= nD, i++,multi = PolynomialMod[lista[[i]][[2]]*Ni[[i]]*Mi[[i]], char];AppendTo[lista2, multi];];

(* Sumamos *)vaux = Total[lista2];

(* Reducimos *)

48


v = PolynomialRemainder[vaux, u, x, Modulus -> char];

];

Return[{u, v}];];

);

La representación de Mumford se realizará a través de la función Mumford ( 5.8). Con estafunción representaremos cualquier divisor del jacobiano de C como un par de polinomios. Elcálculo de u es fácil de entender ya que solamente multiplicaremos los distintos polinomios ui

que nos generen los punto Pi del soporte, mientras que para el cálculo de V nos serviremosdel Teorema chino de los restos para polinomios y al final del algoritmo aplicaremos unareducción módulo u para que el resultado sea único.

Código 5.9: Función MumfordInverso

MumfordInverso[u_, v_, f_, h_, char_] := (Module[{sol, n, Divisor, Pxi, Pyi, i},

sol = Solve[u == 0, x, Modulus -> char];n = Length[sol];Divisor = {};

For[i = 1, i <= n, i++,Pxi = x /. sol[[i]];Pyi = Mod[v /. x -> Pxi, char];

AppendTo[Divisor, {Pxi, Pyi}];];Return[DeleteDuplicates[Divisor]];];

);

La función MumfordInverso 5.9 se encarga de dar la lista de puntos que pertenecen alsoporte de un divisor (que lo pasaremos como entrada) que está representado como dospolinomios.

A continuación se explican las funciones que se han implementado para la suama de diviso-res. Se han creado tres funciones distintas Cantor, CantorLangePols y CantorLangeListas.Pasamos a explicar cada uan de ellas.

� HECC con Cantor

En esta subsección describiremos todas las funciones necesarias para la creación de nuestrocriptosistema basado en elGammal. Empecemos por ver las funciones relacionadas con elalgoritmo de Cantor.

Funciones relacionadas con el algoritmo de Cantor

Se ha decidido dividir el algoritmo de Cantor (que está implementado en el código 5.12)en dos subalgoritmos: la función Suma (en código 5.10) y la función Reducción (en código5.11). Se ha hecho así porque el primero de los procedimientos se utiliza en otras funciones(como por ejemplo en la función PolinomiosPi 5.7) y porque, además, el paquete que

49


creemos de Mathematica se enriquecerá. Las tres funciones que se muestran a continuaciónhan sido extraídas del libro de G. Frey [CFA06].

Código 5.10: Función Suma

SumaDivisores[u1_, v1_, u2_, v2_, f_, h_,char_] := (Module[{d1, e1, e2, d, c1, c2, s1, s2, s3, u, vaux, v,

uaux, gr, cu2, sol, c, n, aux},

{d1, {e1, e2}} =PolynomialExtendedGCD[u1, u2, x, Modulus -> char];{d, {c1, c2}} =PolynomialExtendedGCD[d1, v1 + v2 + h, x, Modulus -> char];

s1 = c1*e1;s2 = c1*e2;s3 = c2;

u = PolynomialQuotient[u1*u2, d^2, x, Modulus -> char];aux = PolynomialMod[s1*u1*v2 + s2*u2*v1 + s3*(v1*v2 + f), char];vaux = PolynomialQuotient[aux, d, x, Modulus -> char];

v = PolynomialRemainder[vaux, u, x, Modulus -> char];

Return[{u, v}];];

);

Código 5.11: Función Reduccion

Reduccion[u_, v_, f_, h_,char_] := (Module[{uaux, vaux, n, aux1, aux2, coef, sol},

uaux = u;vaux = v;n = Exponent[u, x];

(* Reducimos *)While[n > 2,aux1 =PolynomialQuotient[f - h*vaux - vaux*vaux, uaux, x,Modulus -> char];

aux2 =PolynomialRemainder[-h - vaux, aux1, x, Modulus -> char];uaux = aux1;vaux = aux2;n = Exponent[uaux, x];];

(* Hacemos mco el polinomio u*)n = Exponent[uaux, x] + 1;coef = CoefficientList[uaux, x][[n]];If[coef != 1,sol = Solve[coef*x == 1, x, Modulus -> char];coef = x /. sol[[1]];uaux = Expand[PolynomialMod[coef*uaux, char]];];

Return[{uaux, vaux}];];

);

50


Código 5.12: Función Cantor

Cantor[u1_, v1_, u2_, v2_, f_, h_,char_] := (Module[{uaux, vaux, u, v},

{uaux, vaux} = SumaDivisores[u1, v1, u2, v2, f, h, char];

{u, v} = Reduccion[uaux, vaux, f, h, char];Return[{u, v}];];

);

La función OrdenDivisorCantor calcula el orden de los divisores reducidos se muestra enla código 5.13. Lo que hace esta función es ir sumando recursivamente un divisor consigomismo (mediante la función Suma 5.10) hasta conseguir el divisor [1, 0]. Así el número deveces que se haya realizado esta suma, será el orden del divisor.

Código 5.13: Función OrdenDivisorCantor

OrdenDivisorCantor[u_, v_, f_, h_,char_] := (Module[{uaux, vaux, cond, orden},uaux = u;vaux = v;cond = True;orden = 1;

While[cond,{uaux, vaux} = Cantor[uaux, vaux, u, v, f, h, char];orden = orden + 1;If[{uaux, vaux} == {1, 0},cond = False;];];

Return[orden];

];);

Por último, la código 5.14 muestra la implementación del algoritmo que multiplica un divisorpor una constante, llamada imgs/imp/DivisorPorCteCantor.

Código 5.14: Función DivisorPorCteCantor

DivisorPorCteCantor[n_, u1_, v1_, f_, h_,char_] := (Module[{uP, vP, uR, vR, m, Fin, Fin2, divisible},uP = u1;vP = v1;uR = u1;vR = v1;

If[Mod[n, 2] == 0,m = n - 1,m = n];

While[m > 0,If[m != n,divisible = Divisible[m, 2];

If[divisible == False,

{uR, vR} = Cantor[uR, vR, uP, vP, f, h, char];];];

51


{uP, vP} = Cantor[uP, vP, uP, vP, f, h, char];m = Quotient[m, 2];];

Return[{uR, vR}];

];);

Funciones de Cifrado y Firma

Antes de ver las funciones principales, notemos que se ha creado una función más de lasnecesarias, que se llama RomperMensaje (código 5.15) que lo que hace es crear una listacompuesta por cuatro elementos, que a su vez son listas, a partir de una variable de entradaen formato texto. Los pasos de esta función son:

a) Transforma el mensaje de entrada en una lista compuesta por número que representantodos los caracteres del mensaje.

b) Calcula la parte baja de n =longitud del mensaje

4.

c) Divide la lista creada en 4a en cuatro partes de de longitud n2.

Código 5.15: Función RomperMensaje

RomperMensaje2[M_] := (Module[{lista, n, parte, m1, i, m2, m3, m4, n2, n3},lista = ToCharacterCode[M];n = Length[lista];parte = Floor[n/4];

n2 = parte*2;n3 = parte*3;

m1 = lista[[;; parte]];m2 = lista[[parte + 1 ;; n2]];m3 = lista[[n2 + 1 ;; n3]];m4 = lista[[n3 + 1 ;; n]];

Return[{m1, m2, m3, m4}];];

);

La código 5.16 muestra la función ClavesCantor creada para la generación de claves públicay privada de nuestro protocolo.

Código 5.16: Función ClavesCantor

ClavesCantor[Divisor_, p_, f_, h_,char_] := (Module[{PrivK, PubK, k},PrivK = RandomInteger[{1, p - 1}];PubK =DivisorPorCteCantor[PrivK, Divisor[[1]], Divisor[[2]], f, h,

2Se creó otra versión anterior usando bucles pero era mucho menos eficiente y quedó descartada.

52


char];

Return[{PrivK, PubK}]

];);

A continuación veremos como se ha implementado la función que cifra los mensajes (FunciónCifrarCantor, código 5.17). Las entradas son:

Una cadena de texto (que será el mensaje original).

El divisor base.

La llave pública del destinatario del mensaje.

El orden de dicho divisor.

Los parámetros que definen la curva (es decir f ,h y la característica del cuerpo sobre elque está definida).

La salida es una lista compuesta por dos elementos:

El primero una lista con el mensaje cifrado.

Un divisor.

Ambos será usados en el proceso de cifrado.

Código 5.17: Función CifradoCantor

CifradoCantor[M_, Divisor_, PubK_, p_, f_, h_,char_] := (Module[{k, D2, Co, m, cm1, cm2, cm3, cm4, Divaux, n,

parte, lista, cond, CoU, CoV},

cond = 0;While[cond == 0,k = RandomInteger[{1, p - 1}];D2 = DivisorPorCteCantor[k, PubK[[1]], PubK[[2]], f, h, char];CoU = CoefficientList[D2[[1]], x];CoV = CoefficientList[D2[[2]], x];If[(CoU[[1]] != 0) && (CoU[[2]] != 0) && (CoV[[1]] !=

0) && (CoV[[2]]) != 0,cond = 1;];];

m = RomperMensaje2[M];

Co = CoefficientList[D2[[1]], x];cm1 = m[[1]]*Co[[1]];cm2 = m[[2]]*Co[[2]];


Divaux =DivisorPorCteCantor[k, Divisor[[1]], Divisor[[2]], f, h, char];Return[{{cm1, cm2, cm3, cm4}, Divaux}];

53


];);

La función DescifrarCantor (código 5.18) nos devuelve el mensaje original dados el mensajecifrado, el divisor que nos devuelve la función Cifrado (código 5.17), la clave privada deldestinatario del mensaje, el orden del divisor base y los parámetros que definen la curva.

Código 5.18: Función DescifradoCantor

DescifradoCantor[cM_, Divisor_, PrivK_, p_, f_, h_,char_] := (Module[{Divaux, Co, sol, aux1, aux2, m1, m2, m3, m4},

Divaux =DivisorPorCteCantor[PrivK, Divisor[[1]], Divisor[[2]], f, h,char];

Co = CoefficientList[Divaux[[1]], x];m1 = cM[[1]]/Co[[1]];m2 = cM[[2]]/Co[[2]];

Co = CoefficientList[Divaux[[2]], x];

m3 = cM[[3]]/Co[[1]];m4 = cM[[4]]/Co[[2]];

Return[FromCharacterCode[m1] <> FromCharacterCode[m2] <>FromCharacterCode[m3] <> FromCharacterCode[m4]];

];);

La función FirmaCantor (código 5.19) también da uso a RomperMensaje (código 5.15).Lo que hace esta función es crear una firma digital compuesta por dos valores, que son dosenteros. Para esto, pasaremos como parámetros de entrada (entre otras cosas) el mensajeoriginal, el divisor base y su orden, así como la clave privada del emisor del mensaje.

Código 5.19: Función FirmaCantor

FirmaCantor[M_, Divisor_, p_, priv_, f_, h_,char_] := (Module[{hash, k, Daux, u0, r, s, lista, n, parte, m,

i},

hash = Hash[M];r=0;s=0;While[(r==0)&&(s==0),

k = RandomInteger[{1, p - 1}];

Daux =DivisorPorCteCantor[k, Divisor[[1]], Divisor[[2]], f, h, char];

u0 = CoefficientList[Daux[[1]], x][[1]];r = Mod[u0 + hash, p];

s = Mod[k - priv*r, p];];Return[{r, s}];

];

);

54


Usando VerificacionCantor (código 5.20) obtendremos un valor booleano que será ”True”sila confirmación del emisor es correcta y ”False”si no lo es. Para ello necesitaremos las entradas:

El mensaje cifrado.

El divisor base.

El divisor que corresponde a la clave pública del emisor del mensaje.

El orden del divisor base.

Los dos valores obtenidos de la función Firma (5.19).

Los parámetros que definen la curva.

Código 5.20: Función VerificacionCantor

VerificacionCantor[M_, Divisor_, PK_, p_, r_, s_, f_, h_,char_] := (Module[{hash, Daux1, Daux2, D2, Co, u0, r2},

hash = Hash[M];

Daux1 =DivisorPorCteCantor[s, Divisor[[1]], Divisor[[2]], f, h, char];Daux2 = DivisorPorCteCantor[r, PK[[1]], PK[[2]], f, h, char];

D2 = Cantor[Daux1[[1]], Daux1[[2]], Daux2[[1]], Daux2[[2]], f, h,char];

Co = CoefficientList[D2[[1]], x];u0 = Co[[1]];

r2 = Mod[u0 + hash, p];

Return[r2 == r];

];)

� HECC con Cantor-Lange

En este apartado se mostrarán todas las funciones que tiene que ver con el algoritmo deCantor que descompuso Tanja Lange. Se han implementado dos opciones diferentes de todosestos algoritmos: una que trabaja con polinomios y otra que trabaja con listas, para ver cuálde las dos es más eficiente (los resultados se mostrarán en el siguiente capítulo). En esteapartado solo mostraremos las que trabajan con polinomios, ya que es un poco redundante yrepetitivo poner ambas versiones. El resto de funciones las podemos encontrar en el apéndice.

Funciones relacionadas con el algoritmo de Cantor-Lange usando polinomios

Empecemos por ver cada una de los subprocedimientos que se usan en el algoritmo principalde la suma.

Las funciones más básicas se muestran en los códigos 5.21, 5.22, 5.23, 5.25, 5.26 y 5.27.

55


Notar que para que el procedimiento SumarGrDistintoPols funcione correctamente el poli-nomio u1 tiene que ser de grado 1 y u2 debe tener grado dos.

Código 5.21: Función SumarGrado1Pols

SumarGr1Polinomios[u1_, v1_, u2_, v2_, char_] := (Module[{sol, inv, u, v, u10, u20},

u10 = CoefficientList[u1, x][[1]];u20 = CoefficientList[u2, x][[1]];(* Suma dos divisores distintos,ambos con polinomio u de grado 1 (el punto del soporte no es el \

mismo) *)u = (x + u10)*(x + u20);sol = Solve[(u10 - u20)*x == 1, x, Modulus -> char];inv = x /. sol[[1]];v = ((v2 - v1)*x + v2*u10 - v1*u20)*inv;

Return[{PolynomialMod[u, char], PolynomialMod[v, char]}];

];);

Código 5.22: Función DoblarGr1Pols

DoblarGr1Polinomios[u1_, v1_, f_, h_,char_] := (Module[{df, dh, u, v, sol, dff, dhh, vaux, aux, V0, V1,

aux2, u10},

df = D[f, x];dh = D[h, x];u10 = CoefficientList[u1, x][[1]];dff = df /. x -> -u10;dhh = dh /. x -> -u10;

aux = 2*v1 + dhh;sol = Solve[aux*x == 1, x, Modulus -> char];aux = x /. sol[[1]];aux2 = dff - v1*dhh;

V1 = Mod[aux2*aux, char];V0 = Mod[v1 + aux2*aux*(u10), char];Return[{Expand[(x + u10)*(x + u10), Modulus -> char], V1*x + V0}];

];);

Código 5.23: Función SumarGrado2Pols

SumarGr2Polinomios[u1_, v1_, u2_, v2_, f_, h_,char_] := (Module[{u, Co, u10, u11, gr, v10, v11, u20, u21, v20,

v21, h0, h1, h2, f4, z1, z2, z3, r, inv0, inv1, s1p, s0p, w0,w1, w2, w3, w4, w5, s0, s1, ss0, u0, us1, inv, l0, l1, l2, vs1,v0, aux, v, sol, uf0, uf1, vf0, vf1, w2p, vf0p},

(* Sacamos los coeficientes de todos los polinomios de entrada *)

Co = CoefficientList[u1, x];u10 = Co[[1]]; u11 = Co[[2]];Co = CoefficientList[u2, x];u20 = Co[[1]]; u21 = Co[[2]];Co = CoefficientList[v1, x];If[Length[Co] == 2,v10 = Co[[1]];v11 = Co[[2]],

56


v10 = Co[[1]];v11 = 0;];

Co = CoefficientList[v2, x];If[Length[Co] == 2,v20 = Co[[1]];v21 = Co[[2]],v20 = Co[[1]];v21 = 0;];

Co = CoefficientList[h, x];n = Length[Co];If[n == 0, h0 = 0; h1 = 0; h2 = 0];If[n == 1, h0 = Co[[1]]; h1 = 0; h2 = 0];If[n == 2, h0 = Co[[1]]; h1 = Co[[2]]; h2 = 0];If[n == 3, h0 = Co[[1]]; h1 = Co[[2]]; h2 = Co[[3]]];

f4 = CoefficientList[f, x][[5]];(* Calculamos la resultante*)z1 = u11 - u21;z2 = u20 - u10;z3 = u11*z1 + z2;r = Mod[z2*z3 + z1*z1*u10, char];

(* Calculamos el casi inverso *)inv1 = z1;inv0 = z3;

(* Calculamos s' *)w0 = v10 - v20;w1 = v11 - v21;w2 = inv0*w0;w3 = inv1* w1;

s1p = Mod[(inv0 + inv1)*(w0 + w1) - w2 - w3*(1 + u11), char];s0p = Mod[w2 - u10*w3, char];

(* Si s1p != 0 *)If[s1p != 0,

(* Calcuamos s'' *)

sol = Solve[r*s1p*x == 1, x, Modulus -> char];w1 = x /. sol[[1]];w2 = r*w1;w3 = s1p*s1p*w1;w4 = r*w2;w5 = w4*w4;

s0 = Mod[s0p*w2, char];

(* Calculamos l' *)l2 = Mod[u21 + s0, char];l1 = Mod[u21*s0 + u20, char];l0 = Mod[u20*s0, char];

(* Calculamos u *)

aux = (s0 - u11)*(s0 - z1 + h2*w4) - u10;uf0 =Mod[aux + l1 + (h1 + 2*v21)*w4 + (2 u21 + z1 - f4)*w5, char];uf1 = Mod[2*s0 - z1 + h2*w4 - w5, char];

(* Calculamos v *)w1 = l2 - uf1;w2 = uf1*w1 + uf0 - l1;vf1 = Mod[w2*w3 - v21 - h1 + h2*uf1, char];w2 = uf0*w1 - l0;

57


vf0 = Mod[w2*w3 - v20 - h0 + h2*uf0, char];

(* Devolvemos u y v *)

Return[{uf0 + uf1*x + x^2, vf0 + vf1*x}],

(* Si sp1==0 *)

(* Calculamos s *)

sol = Solve[r*x == 1, x, Modulus -> char];inv = x /. sol[[1]];s0 = Mod[s0p*inv, char];

(* Calculamos u *)

uf0 = Mod[f4 - u21 - u11 - s0*s0 - s0*h2, char];

(* Calculamos v *)

vf0 =Mod[-h0 - s0*u20 + h1*uf0 + s0*u21*uf0 - h2*uf0*uf0 -s0*uf0*uf0 - v20 + uf0*v21, char];

Return[{uf0 + x, vf0}];];];

);

Código 5.24: Función DoblarGr2Pols

DoblarGr2Polinomios[u1_, v1_, f_, h_,char_] := (Module[{Co, u10, u11, v10, v11, h0, h1, h2, f4, f3, f2,

v1gorro, v0gorro, w0, w1, w2, w3, w4, w5, r, inv1, inv0, s1, s0,sol, t1, t0, s2p0, s2p1, l2, l1, l0, up0, up1, s1p0, vp1, vp0,sp0},

(* Dobla un divisor de grado dos *)

(* Sacamos todos los coeficientes *)

Co = CoefficientList[u1, x];u10 = Co[[1]]; u11 = Co[[2]];

Co = CoefficientList[v1, x];If[Length[Co] == 2,v10 = Co[[1]];v11 = Co[[2]],v10 = Co[[1]];v11 = 0,];


Co = CoefficientList[f, x];f4 = Co[[5]];f3 = Co[[4]];f2 = Co[[3]];

(*Calculamos v gorro*)v1gorro = h1 + 2*v11 - h2*u11;v0gorro = h0 + 2*v10 - h2*u10;

(* Calculamos la resultante *)

58


w0 = v11*v11;w1 = u11*u11;w2 = v1gorro*v1gorro;w3 = u11*v1gorro;r = Mod[u10*w2 + v0gorro*(v0gorro - w3), char];

(* Calculamos el casi inverso *)

inv1 = Mod[-v1gorro, char];inv0 = Mod[v0gorro - w3, char];

(* Calculamos t *)w3 = f3 + w1;w4 = 2*u10;t1 = Mod[2*(w1 - f4*u11) + w3 - w4 - h2*v11, char];t0 =Mod[u11*(2*w4 - w3 + f4*u11 + h2*v11) + f2 - w0 - 2*f4*u10 -h1*v11 - h2*v10, char];

(* Calculamos s *)w0 = t0*inv0;w1 = t1*inv1;

s1 = Mod[(inv1 + inv0)*(t0 + t1) - w0 - w1*(1 + u11), char];s0 = Mod[w0 - u10*w1, char];

If[s1 != 0,(* Es decir, si s' tiene grado uno*)(*Calculamos s'' *)

sol = Solve[s1*r*x == 1, x, Modulus -> char];w1 = x /. sol[[1]];w2 = r*w1;w3 = s1*s1*w1;w4 = r*w2;w5 = w4*w4;s2p0 = Mod[s0*w2, char];

(* Calculamos l *)l2 = Mod[u11 + s2p0, char];l1 = Mod[u11*s2p0 + u10, char];l0 = Mod[u10*s2p0, char];

(* Calculamos u *)

up0 = Mod[s2p0*s2p0 + w4*(h2*(s2p0 - u11) + 2*v11 + h1) +w5*(2*u11 - f4), char];

up1 = Mod[2*s2p0 + h2*w4 - w5, char];

(*Calculamos v *)w1 = l2 - up1;w2 = up1*w1 + up0 - l1;vp1 = Mod[w2*w3 - v11 - h1 + h2*up1, char];w2 = up0*w1 - l0;vp0 = Mod[w2*w3 - v10 - h0 - h2*up0, char];

Return[{x^2 + up1*x + up0, vp1*x + vp0}],

(* Si s' es constante *)(* Calculamos s *)

sol = Solve[r*x == 1, x, Modulus -> char];w1 = x /. sol[[1]];sp0 = Mod[s0*w1, char];w2 = u10*sp0 + v10 + h0;

(* Calculamos u *)

up0 = Mod[f4 - sp0*sp0 - sp0*h2 - 2*u11, char];

59


(* Calculamos v *)

w1 = sp0*(u11 - up0) - h2*up0 + v11 + h1;vp0 = Mod[up0*w1 - w2, char];

Return[{x + up0, vp0}];];];

);

Código 5.25: Función SumarGrDistintoPols

SumarGrDistintoPolinomios[u1_, v10_, u2_, v2_, f_, h_,char_] := (Module[{Co, u20, u21, v20, v21, h0, h1, h2, f4, f3, f2,

r, inv, sol, s0, l1, l0, t2, t1, uf1, uf0, vf1, vf0, u10},(* Suma dos divisores que tienen grado distinto.Asumiremos que el grado de u1 es uno y el de u2 es dos *)

(* Sacamos los coeficientes que necesitamos *)

u10 = CoefficientList[u1, x][[1]];Co = CoefficientList[u2, x];u20 = Co[[1]]; u21 = Co[[2]];

Co = CoefficientList[v2, x];If[Length[Co] == 2,v20 = Co[[1]];v21 = Co[[2]],v20 = Co[[1]];v21 = 0,];


Co = CoefficientList[f, x];f4 = Co[[5]];f3 = Co[[4]];


r = Mod[u20 - (u21 - u10)*u10, char];

(* Calculamos el casi invers0 *)

sol = Solve[r*x == 1, Modulus -> char];inv = x /. sol[[1]];

(* Calculamos s *)s0 = Mod[inv*(v10 - v20 + v21*u10), char];

(* Calculamos l *)l1 = Mod[s0*u21, char];l0 = Mod[s0*u20, char];

(* Calculamos t *)t2 = Mod[f4 - u21, char];t1 = Mod[f3 - (f4 - u21)*u21 - v21*h2 - u20, char];

(* Calculamos u *)uf1 = Mod[t2 - s0*s0 - s0*h2 - u10, char];uf0 = Mod[t1 - s0*(l1 + h1 + 2*v21) - u10*uf1, char];

60


(* Calcualmos v *)

vf1 = Mod[(h2 + s0)*uf1 - (h1 + l1 + v21), char];vf0 = Mod[(h2 + s0)*uf0 - (h0 + l0 + v20), char];Return[{x^2 + uf1*x + uf0, vf1*x + vf0}];

];);

Para sumar dos divisores D1 = [u1, v1] y D2 = [u2, v2] tales que gr(u1) = 1 y gr(u2) = 2,sin tener en cuenta qué puntos se encuentran en el soporte de ambos divisores, usaremos lasfunción SumarGradoDistintoPols que se muestra en la código 5.26.

Código 5.26: Función SumarGradoDistintoPols

SumarGradoDistintoPolinomios[u1_, v1_, u2_, v2_, f_, h_,char_] := (Module[{grh, Co, h0, h1, h2, gru1, gru2, sol, cond, aux,

aux2, u20, x1, x2, x3, vaux, u11, u21, v10, v11, v20, v21, gr,r, v0gorro, v1gorro, u10, w0, w1, w2, w3, rcoef, max, z1, z2,z3, v1x1, v2x1, y2, y3, CoU, CoV},

CoU = CoefficientList[u2, x];CoV = CoefficientList[v2, x];u10 = CoefficientList[u1, x][[1]];

Co = CoefficientList[h, x];n = Length[Co];If[n == 0, h0 = 0; h1 = 0; h2 = 0];If[n == 1, h0 = Co[[1]]; h1 = 0; h2 = 0];If[n == 2, h0 = Co[[1]]; h1 = Co[[2]]; h2 = 0];If[n == 3, h0 = Co[[1]]; h1 = Co[[2]]; h2 = Co[[3]]];cond = Mod[u2 /. x -> -u10, char];

If[cond != 0,(* P1 no estn el soporte de D2, es decir,sumamos dos divisores de grado distinto*)

Return[SumarGrDistintoPolinomios[u1, v1, u2, v2, f, h, char]],

(* D2 es el doble de D1: doblamos D2 y le restamos D1 *)

If[(CoU[[2]] == Mod[2*(u10), char]) && (CoU[[1]] ==Mod[(u10)*(u10), char]),

vaux = Mod[v2 /. x -> -u10, char];If[v1 == vaux,aux = DoblarGr2Polinomios[u2, v2, f, h, char];Return[RestarPolinomios[u1, v1, aux[[1]], aux[[2]], f, h, char]],Co = CoefficientList[u2, x];x2 = Mod[Co[[2]] - u10, char];vaux = Mod[v2 /. x -> -x2, char];Return[{x + x2, vaux}];];];(* -P1 estn el soporte de D2 *)

cond = Mod[v2 /. x -> -u10, char];aux2 = h0 + h1*(-u10) + h2*(-u10)^2;aux = Mod[-v1 - aux2, char];Co = CoefficientList[u2, x];x2 = Mod[Co[[2]] - u10, char];vaux = Mod[v2 /. x -> -x2, char];If[cond == aux,Return[{x + x2, vaux}],(* -P1 no estn el soporte de D2 *)

61


aux = DoblarGr1Polinomios[u1, v1, f, h0 + h1*x + h2*x^2,char];

Return[SumarGrDistintoPolinomios[x + x2, vaux, aux[[1]], aux[[2]], f,h, char]];

];];];

);

La función RestarPols (código 5.27) calcula la diferencia entre dos divisores. El grado delpolinomio u2 puede ser 1 o 2, mientras que es necesario que el grado de u1 sea 1.

Código 5.27: Función RestarPols

RestarPolinomios[u1_, v1_, u2_, v2_, f_, h_, char_] := (Module[{h0, h1, h2, sol, vn2, ru, rv, fin, Co, u, v, u20, u10},


u10 = CoefficientList[u1, x][[1]];vn2 = Mod[-v1 - (h2 (-u10)^2 + h1 (-u10) + h0), char];

If[Exponent[u2, x] == 1,Return[SumarGr1Polinomios[u1, vn2, u2, v2, char]];];

If[Exponent[u2, x] == 2,fin =SumarGradoDistintoPolinomios[u1, vn2, u2, v2, f, h, char];

];Return[fin];];

);

Pasemos ahora a ver la función principal, es decir, la función CantorLangePols que noscalcula la suma de dos divisores. En ella hacemos uso de todas las funciones anteriores. En elcaso en el que el grado de u1, los polinomios que representan a D1 serán la primera entraday los que representan a D2 la segunda.

Tenemos que destacar que este procedimiento ha sido el más costoso de implementar. Esto sedebe a que siguiendo los pasos del el algoritmo que encontramos en el libro de Frey ( [CFA06]),no nos daban las mismas salidas que usando el algoritmo de Cantor (código 5.12). Al fijarmeun poco más en cada paso y realizando todos los posibles casos que se iba a poder dar, me dicuenta de que en un principio no se contemplaban todos los casos posibles a la hora de sumardos divisores de grados distintos usando la función SumarGradoDistinto (5.26) (había quecontemplar dos casos más) y que además el algoritmo que muestra el libro para sumar dosdivisores de grado dos era erróneo. Busqué en el resto de artículo escritos por Tanja Lange(ver [CFA06], [Lan05]) y las versiones diferían. Otros artículos referían a aplicar el algoritmode Cantor 5.12 en el caso s = s0 ( [Wol04], [PWP04b]), pero esa opción no me convencía.Así que al final, realicé las operaciones que se siguen en el libro y cambié el cálculo de vf0cuando s = s0.

Código 5.28: Función CantorLangePols

CantorLangePolinomios[u1_, v1_, u2_, v2_, f_, h_,

62


char_] := (Module[{grh, Co, h0, h1, h2, gru1, gru2, sol, u10, u20,cond, aux, aux2, x1, x2, x3, vaux, u11, u21, v10, v11, v20, v21,gr, r, v0gorro, v1gorro, w0, w1, w2, w3, rcoef, max, z1, z2,z3, v1x1, v2x1, y2, y3, CoU, CoV, nv1x1},

grh = Exponent[h, x];Co = CoefficientList[h, x];If[grh == 2, h2 = Co[[3]]; h1 = Co[[2]]; h0 = Co[[1]]];If[grh == 1, h2 = 0; h1 = Co[[2]]; h0 = Co[[1]]];If[grh == 0, h2 = 0; h1 = 0; h0 = Co[[1]]];If[grh < 0, h2 = 0; h1 = 0; h0 = 0];

gru1 = Exponent[u1, x];gru2 = Exponent[u2, x];

If[gru1 == 0, Return[{u2, v2}]];If[gru1 == 1,(* Tanto u1 como u2 tienen grado uno *)

u10 = CoefficientList[u1, x, Modulus -> char][[1]];If[gru2 == 1,u20 = CoefficientList[u2, x, Modulus -> char][[1]];(* u1 y u2 son iguales *)If[u10 == u20,(* v1 y v2 son diferentes, es decir,los divisores tienen en el soporte dos puntos opuestos *)

If[v1 == Mod[-v2 - (h0 + h1*u10 + h2*u10*u10), char],Return[{1, 0}],(* v1 y v2 son iguales, es decir, doblamos el mismo divisor*)

Return[DoblarGr1Polinomios[u1, v1, f, h, char]];],(*Son dos divisores con puntos 2 puntos distintos en el soporte*)

Return[SumarGr1Polinomios[u1, v1, u2, v2, char]];],(* Entramos en el sino, es decir, gru2==2*)

Return[SumarGradoDistintoPolinomios[u1, v1, u2, v2, f, h,char]];

];];

If[gru1 == 2,(* Sacamos los coeficientes de los cuatro polinomios *)



gr = Exponent[v1, x];If[gr < 0, v10 = 0; v11 = 0,Co = CoefficientList[v1, x];If[gr == 0, v10 = Co[[1]]; v11 = 0];If[gr == 1, v10 = Co[[1]]; v11 = Co[[2]]];];

gr = Exponent[v2, x];If[gr < 0, v20 = 0; v21 = 0,Co = CoefficientList[v2, x];If[gr == 0, v20 = Co[[1]]; v21 = 0];If[gr == 1, v20 = Co[[1]]; v21 = Co[[2]]];];

If[(u11 == u21) && (u10 == u20),aux =

63


PolynomialRemainder[v1 + v2 + h, u1, x, Modulus -> char];If[aux == 0,Return[{1, 0}];];If[(v10 == v20) && (v11 == v21),r = Resultant[h + 2*v1, u1, x, Modulus -> char];If[r == 0,(* Calculamos 2P2*)

max = PolynomialGCD[h + v1 + v1, u1, Modulus -> char];sol = Solve[max == 0, x, Modulus -> char];x1 = x /. sol[[1]];x2 = Mod[-u11 - x1, char];vaux = Mod[v1 /. x -> x2, char];Return[DoblarGr1Polinomios[x - x2, vaux, f, h, char]],(* Doblamos un divisor con grado de u igual a 2*)

Return[DoblarGr2Polinomios[u1, v1, f, h, char]];],(* Los polinomios v1 y v2 son distintos, es decir, P1==P3 y P2=-P4 *)

sol = Solve[(v21 - v11)*x == 1, x, Modulus -> char];aux = x /. sol[[1]];x1 = Mod[(v10 - v20)*aux, char];vaux = Mod[v1 /. x -> x1, char];Return[DoblarGr1Polinomios[x - x1, vaux, f, h, char]];],(* Los polinomios u1 y u2 son disfentes *)(*Calculamos la resultante*)

r = Resultant[u1, u2, x, Modulus -> char];If[r != 0,(* Tenemos dos divisores de grado dos distintos *)

Return[SumarGr2Polinomios[u1, v1, u2, v2, f, h, char]],max = PolynomialGCD[u2, u1, Modulus -> char];Co = CoefficientList[max, x];x1 = Mod[-Co[[1]], char];v1x1 = Mod[v1 /. x -> x1, char];v2x1 = Mod[v2 /. x -> x1, char];x2 = Mod[-u11 - x1, char];y2 = Mod[v1 /. x -> x2, char];x3 = Mod[-u21 - x1, char];y3 = Mod[v2 /. x -> x3, char];If[v1x1 == v2x1,(* 2P1+P2+P3 *)

nv1x1 = Mod[-v1x1 - h0 - h1*x1 - h2*x1^2, char];If[v1x1 == nv1x1,Return[SumarGr1Polinomios[x - x2, y2, x - x3, y3, char]],aux = DoblarGr1Polinomios[x - x1, v1x1, f, h, char];

aux2 = SumarGradoDistintoPolinomios[x - x2, y2, aux[[1]],aux[[2]], f, h, char];

Return[SumarGradoDistintoPolinomios[x - x3, y3, aux2[[1]],aux2[[2]], f, h, char]],

],(* P2+P3 *)

Return[SumarGr1Polinomios[x - x2, y2, x - x3, y3, char]];];];];];];

);

64


Las siguientes dos funciones son análogas a las vistas en la sección 4 en las funciones mostradasen las códigos 5.30 y 5.29 respectivamente. Lo único que cambia

a) La forma de realizar la suma.

b) En la función Orden se tiene en cuenta el grado del polinomio u1, ya que de él dependecuál será el orden de las entradas de la función CantorLange.

Código 5.29: Función DivisorPorCteLangePols

DivisorPorCteLangePols[n_, u1_, v1_, f_, h_,char_] := (Module[{uP, vP, uR, vR, m, Fin, Fin2, divisible},uP = u1;vP = v1;uR = u1;vR = v1;If[Mod[n, 2] == 0,m = n - 1,m = n];While[m > 0,If[m != n,divisible = Divisible[m, 2];If[divisible == False,{uR, vR} = CantorLangePolinomios[uR, vR, uP, vP, f, h, char];];];{uP, vP} = CantorLangePolinomios[uP, vP, uP, vP, f, h, char];m = Quotient[m, 2];];Return[{uR, vR}];];

);

Código 5.30: Función OrdenLangePols

OrdenDivisorLangePols[u_, v_, f_, h_,char_] := (Module[{uaux, vaux, cond, orden, aux1, aux2, gru,

gruaux},uaux = u;vaux = v;cond = True;orden = 1;gru = Exponent[u, x];

If[gru == 2,While[cond,

{uaux, vaux} =CantorLangePolinomios[uaux, vaux, u, v, f, h, char];orden = orden + 1;

If[{uaux, vaux} == {1, 0},cond = False;];

];

Return[orden]];If[gru == 1,While[cond,{uaux, vaux} =CantorLangePolinomios[u, v, uaux, vaux, f, h, char];

65


orden = orden + 1;

If[{uaux, vaux} == {1, 0},cond = False;];

];

Return[orden]

];

];);

Funciones de Cifrado y Firma con Cantor Lange

Se podría decir que ambas funciones son idénticas a las vistas en la sección 4 ya que siguenel mismo esquema. la única diferencia es que esta vez usamos operación que multiplica unun divisor por una constante DivisorPorCte de la código 5.29.

Código 5.31: Función ClavesLangePols

ClavesLangePols[Divisor_, p_, f_, h_,char_] := (Module[{PrivK, PubK, k},PrivK = RandomInteger[{1, p - 1}];PubK =DivisorPorCteLangePols[PrivK, Divisor[[1]], Divisor[[2]], f, h,char];


];);

Código 5.32: Función CifradoLangePols

CifradoLangePols[M_, Divisor_, PubK_, p_, f_, h_,char_] := (Module[{k, D2, Co, m, cm1, cm2, cm3, cm4, Divaux, n,


cond = 0;While[cond == 0,k = RandomInteger[{1, p - 1}];D2 = DivisorPorCteLangePols[k, PubK[[1]], PubK[[2]], f, h, char];CoU = CoefficientList[D2[[1]], x];CoV = CoefficientList[D2[[2]], x];If[(CoU[[1]] != 0) && (CoU[[2]] != 0) && (CoV[[1]] !=

0) && (CoV[[2]]) != 0,cond = 1;];];

m = RomperMensaje[M];



66


Divaux =DivisorPorCteLangePols[k, Divisor[[1]], Divisor[[2]], f, h,char];

Return[{{cm1, cm2, cm3, cm4}, Divaux}];

];);

Código 5.33: Función DescifradoLangePols

DescifradoLangePols[cM_, Divisor_, PrivK_, p_, f_, h_,char_] := (Module[{Divaux, Co, sol, aux1, aux2, m1, m2, m3, m4},

Divaux =DivisorPorCteLangePols[PrivK, Divisor[[1]], Divisor[[2]], f, h,char];

Co = CoefficientList[Divaux[[1]], x];m1 = cM[[1]]/Co[[1]];m2 = cM[[2]]/Co[[2]];

Co = CoefficientList[Divaux[[2]], x];

m3 = cM[[3]]/Co[[1]];m4 = cM[[4]]/Co[[2]];


];);

Código 5.34: Función FirmaLangePols

FirmaLangePols[M_, Divisor_, p_, priv_, f_, h_,char_] := (Module[{hash, k, Daux, u0, r, s, lista, n, parte, m,

i},



Daux =DivisorPorCteLangePols[k, Divisor[[1]], Divisor[[2]], f, h,char];

u0 = CoefficientList[Daux[[1]], x][[1]];r = Mod[u0 + hash, p];

s = Mod[k - priv*r, p];];Return[{r, s}];

];

);

Código 5.35: Función VerificacionLangePols

VerificacionLangePols[CM_, Divisor_, PK_, p_, r_, s_, f_, h_,char_] := (Module[{hash, Daux1, Daux2, D2, Co, u0, r2},

67


hash = Hash[CM];

Daux1 =DivisorPorCteLangePols[s, Divisor[[1]], Divisor[[2]], f, h, char];Daux2 = DivisorPorCteLangePols[r, PK[[1]], PK[[2]], f, h, char];

D2 = CantorLangePolinomios[Daux1[[1]], Daux1[[2]], Daux2[[1]],Daux2[[2]], f, h, char];

Co = CoefficientList[D2[[1]], x];u0 = Co[[1]];


Return[r2 == r];

];)

5.3 INTERFAZ GRÁFICA

En este segundo apartado abordaremos el proceso de implementación de la interfaz gráfica.Antes de nada comentar que se ha cambiado el diseño original. Hemos apostado por unaúnica ventana con pestañas porque la aplicación no iba a contar con muchas funcionalidadesy era mucho más práctico disponer de una única ventana con cinco pestañas. Esto se explicaráen el capítulo de gestión del proyecto.

También se ha creído más conveniente crear solamente dos clases: una que será la claseGestor y otra que tendrá todos los procedimientos y variables relacionadas con la ventana dela aplicación.

Como se ha comentado con anterioridad, se ha utilizado J/Link como nexo de unión deMathematica con la aplicación. Para saber mejor como funcionaba las interfaces MathLinky KernelLink, se creó una clase llamada puebaMathematica. El código se muestra a conti-nuación:

Código 5.36: Función prueba para usar J/Link

/** To change this template, choose Tools | Templates* and open the template in the editor.*/package pfc;

import com.wolfram.jlink.*;

public class pruebaMathematica {

static KernelLink ml = null;static String workspace = null;static String[] argv = {"-linkmoder", "launch", "-linkname",

"/Applications/Mathematica.app/Contents/MacOS/MathKernel"};

public void pruebaMathematica() {workspace = "/Users/Veronica/Desktop";

}

public Boolean metodoPrueba() {

try {ml = MathLinkFactory.createKernelLink(argv);

68


} catch (MathLinkException e) {System.out.println("Error: " + e.getMessage());return false;

}

try {ml.discardAnswer();

ml.evaluate("2+2");String solucion = ml.getString();System.out.println("2+2=" + solucion);

} catch (MathLinkException e) {System.out.println("Error: " + e.getMessage());

} finally {ml.close();

}

return null;

}}

Así, podemos dividir 5.3 en dos partes: la primera será la declaración de variables. En ellavemos tres variables estáticas: un objeto KernelLink (que es una de las interfaces de J/Link) ydos otras variables: una un String (la variables workspace) que será la varibale que contendrála ruta donde Mathematica tomará ficheros o los creará y argv, un vector de Strig quecontiene, entre otros, la ruta de la carpeta en la que se localiza el núcleo de Mathematicacon el que trabajaremos.

La segunda parte estará formada por las operaciones: el constructor y otra operación que nossirve para entender mejor el comportamiento de los objeros KernelLink. Para esta función seha creado también un paquete llamado ’prueba’que lo único que hace es realizar la operación2 + 2 y mostrar el resultado por pantalla. Antes de realizar el procedimiento, tenemos queinicializar nuestro objeto KernelLink creando un enlace con el núcleo de Mathematica usan-do MathLinkFactory.createKernelLink(argv). Con este método no lanzamos el núcleo, sinoque creamos un enlace de conexión con este, haciendo que nuestro objeto espere hasta queMathematica nos devuelva un objeto, en este caso un entero.

Crear esta conexión puede lanzar una excepción. Esto lo solucionaremos con el bloque try-catch. Al final de este bloque, cerraremos la conexión usando la función close() sobre el objetoml.

Una vez visto esto, pasemos a ver cuales son las principales funciones Java que hemos im-plementado. Se ha creado una función por cara operación que se desea hacer con nuestrocriptosistema, es decir, cifrar, descifrar, firmar, verificar y generar claves. Además de otrasque van asociadas a los distintos botones de nuestra interfaz.

Código 5.37: Función cifrar()

private boolean cifrar() {



}

try {ml.discardAnswer();ml.evaluate("<< \"HECantor`\"");ml.discardAnswer();

69


ml.evaluate("CifradoCantor[\"/" + gestor.getPathFichero() + "\",\"" + gestor.getNombreFicheroSalida() + "\",\"" + gestor.getCopiaTexto() + "\",{" + gestor.getDivisorBase() + "},{" + gestor.getClavePublica() + "}," + gestor.getOrdenDivisor() + "," + gestor.getF() + "," + gestor.getH() + "," + gestor.getCaracteristica() + ",x]");

ml.waitForAnswer();



}

File fichero = new File("/" + gestor.getPathFichero() + "/" + gestor.getNombreFicheroSalida());

if (fichero.exists()) {return true;

} else {return false;

}}

Código 5.38: Función descifrar()label

private boolean descifrar() {try {

ml = MathLinkFactory.createKernelLink(argv);} catch (MathLinkException e) {

System.out.println("Error: " + e.getMessage());}


ml.evaluate("DescifradoCantor[\"/" + gestor.getPathFichero() + "\",\"" + gestor.getNombreFichero() + ".txt\",\"" + gestor.getNombreFicheroSalida() + ".txt\",{" + gestor.getDivisorBase() + "}," + gestor.getClavePrivada() + "," +gestor.getOrdenDivisor() + "," + gestor.getF() + "," + gestor.getH() + "," +gestor.getCaracteristica() + ",x]");

ml.waitForAnswer();



}




}}

Código 5.39: Función firmar()label

private boolean firmar() {

70




}


ml.evaluate("FirmaCantor[\"/" + gestor.getPathFichero() + "\",\"" + gestor.getCopiaTexto() + "\",\"" + gestor.getNombreFicheroSalida() + "\",{" + gestor.getDivisorBase() + "}," + gestor.getClavePrivada() + "," + gestor.getOrdenDivisor() + "," + gestor.getF() + "," + gestor.getH() + "," + gestor.getCaracteristica() + ",x]");

ml.waitForAnswer();



}




}}

Código 5.40: Función verificar(String aux)

private boolean verificar(String aux) {try {




ml.evaluate("VerificacionCantor[\"/" + gestor.getPathFichero() + "\",\"" + gestor.getCopiaTexto() + "\",{" + gestor.getDivisorBase() + "},{" + gestor.getClavePublica() + "},\"" + gestor.getNombreFichero() + ".txt\"," + gestor.getOrdenDivisor() + "," + gestor.getF() + "," + gestor.getH() + "," + gestor.getCaracteristica() + ",x]");

System.out.println("VerificacionCantor[\"/" + gestor.getPathFichero() + "\",\"" +gestor.getCopiaTexto() + "\",{" + gestor.getDivisorBase() + "},{" + gestor.getClavePublica() + "},\"" + gestor.getNombreFichero() + ".txt\"," + gestor.getOrdenDivisor() + "," + gestor.getF() + "," + gestor.getH() + "," + gestor.getCaracteristica() + ",x]");

ml.discardAnswer();



}

try {

71


String ficheroauxiliar = "/" + gestor.getPathFichero() + "/aux.txt";File file = new File(ficheroauxiliar);FileReader reader = new FileReader(file);BufferedReader bf = new BufferedReader(reader);

int r2, r = 0;aux = bf.readLine();r = Integer.parseInt(aux);aux = bf.readLine();r2 = Integer.parseInt(aux);

bf.close();reader.close();file.delete();

if (r == r2) {return true;


}

} catch (IOException e) {System.out.println("Error: " + e.getMessage());return false;

}}

Código 5.41: Función generacionClaves(string aux)

private boolean generacionClaves(String aux) {try {




ml.evaluate("ClavesCantor[\"" + aux + "\",{" + gestor.getDivisorBase() + "}," +gestor.getOrdenDivisor() + "," + gestor.getF() + "," + gestor.getH() + "," +gestor.getCaracteristica() + ",x]");

ml.waitForAnswer();



}

File fichero = new File(aux + "/claves.txt");



}}

Como podemos ver todas las operaciones son similares: primero se crea el nexo on el nú-cleo, luego se carga el paquete HECantor para después mandar a Mathematica las distintasoperaciones como cadenas de texto. Al final de cada procedimientos se comprueba si se hagenerado el documento correctamente, devolviendo un booleano que nos indica este hecho.

72


Mencionar que a las fucniones 5.41 y 5.40 necesitan como parámentro de entrada una cadenade texto. En el primer caso será la ruta donde se quiere guardar el archivo, mientras que enla función verificar es la ruta del archivo a verificar.

También podemos ver que se llama a la clase Gestor ya que contiene tanto los valores denuestro sistema criptográfico como las operaciones de lectura y modificación de estos. Porotro lado, esta clase clase gruarda las rutas de los archivos y tiene un método encargadocopiar el texto de un archivo a una String.

A la hora de usar nuetra aplicación debemos que tener en cuenta que solo se puede trabajarcon archivos no vacíos y que no contengan saltos de línea. Además, el archivo que carga laconficuración del criptosistema debe de estar compuesto por las siguientes líneas:

a) La ecuación de la función f .

b) La ecuación de la función h.

c) El orden del jacobiano.

d) El dicisor base de nuestro sistema criptográfico.

e) El orden de dicho divisor.

f ) La caracterísitca p prima del cuerpo sobre el que está definida la curva.

Por otro lado, cuando se nos piede meter la calve pública formada por dos polinomios,debemos introducirla sin las llaves, es decir, solamente escribir los dos polinomios separadospor una coma.

Al cargar estos valores, se llama al método ComprobarParametros del paquete prueba, quesolamente comprueba las caracterísitcas básicas que tienen que cumplir cada una de lasentradas, pero no si todos los valores están bien definidos. Es por ello que nos deberemosasegurar antes que hemos creado el archivo con los valores adecuados.

También notar que el Kernel de Mathematica se tiene que encontrar /Applications/Mat-hematica.app/Contents/MacOS/MathKernel, sino la aplicación no funcionará y que los dospaquetes necesarios de Mathematica (prueba.m y HECantor.m incluidos en una carpeta juntoal código de la aplicación) deben de estar instalados.

73


6. FASE DE PRUEBAS

Podemos considerar esta como la última fase de nuestro proyecto. La hemos dividido en dossubfases que se han testeado en distintos periodos de tiempo:

a) La primera fase de pruebas, en las que se realizaron pruebas a todas y cada una de losprocedimientos implementados en Mathematica. Estas pruebas se llevaron a cabo de dosformas:

Una por una, mirando el tiempo de ejecución de cada una de ellas.

Como partes de un paquete de Mathematica llamado CurvasHiperelipticas, paracomprobar si dicho paquete funcionaba adecuadamente.

b) Las pruebas de la segunda fase tratan de comprobar si la interfaz de usuario que se hacreado funciona también de forma deseada.

Es por esto que hemos dividido este apartado en dos secciones, cada una de ellas relacionadacon una de las fases descritas anteriormente. Empezaremos con la fase de pruebas de lasfunciones de Mathematica.

6.1 PRUEBAS CON MATHEMATICA

Según se han ido implementando las funciones diseñadas, se han ido testeando para ver sifuncionan correctamente. Así podemos decir que las pruebas construidas en la fase de diseñohan sido satisfactorias.

Las comprobaciones de que las pruebas funcionan de forma correcta se encuentran en lacarpeta Procedimientos que se encuentra dentro de la prueba Pruebas de funcionamiento deprocedimientos.

Por otro lado, también se efectuaron pruebas a los 3 paquetes de Mathematica que se hancreado. Estas pruebas se encuentran en la carpeta Paquetes que se encuentra dentro de laprueba Pruebas de funcionamiento de procedimientos y que la podemos encontrar en el CDadjunto.

Mientras se iban implementando los distintos métodos que se habían realizado pruebas enel tiempo de ejecución para ver qué funciones eran más eficietnes y serían más útiles. Comomuchas de ellas no han arrojado resultado alguna, no las añadiremos a nuestro estudio. Laúnica prueba que si nos sirve para ver porqué no hemos usado el paquete FiniteFields ennuestro trabajo, es la realizada con la función de OrdenJacobiano. Para ello hemos aplicadolas funciones relacionadas con el cálculo del orden del jacobiano a distintas curvas definidassobre Zp con p un primo pequeño (entre 1 y 31). Mostramos solamente los resultados paralas curvas en las que h = 0. Si se quiere ver el resto de tiempo, ver el documento adjunto enel CD.

75

6. FASE DE PRUEBAS

Z11 Z13 Z17 Z19 Z23 Z29 Z31

15.896502 31.808604 94.177804 147.857748 320.020451 822.920875 1093.832212

Cuadro 6.1.: Tiempo en segundos que se trata de calcular M2 con la funcion CalculoM2

Es fácil imaginar con estos resultados lo que costaría simplemente sumar varias veces undivisor mediante al algoritmo de Cantor o de Cantor-Lange usando el paquete FiniteFields.Se intentó hacer varias pruebas con el algoritmo de Cantor aplicándolo a cuerpos finitos peroen muchos de ellas se quedó bloqueado el ordenador. Es por esto que se desestimó el uso deeste paquete.

Además algunas de las fuentes consultadas afirmaba que este paquete no tenía resultadosóptimos cuando se trabajaba con polinomios.

Las pruebas de tiempo que se realizaron a los distintos algoritmos de la suma no resultaronconcluyentes, ya que al realizarse todas con curvas definidas sobre cuerpos finitos pequeñostardaron tiempos similares en ejecutarse. Es por esto que no se incluye ninguna tabla nifichero adjunto.

Lo mismo ocurre con las pruebas temporales realizadas a PuntosCantor y PuntosCantorLis-tas. Ambos procedimientos tienen tiempos de ejecución similares.

El método de RomperMensaje se ha implementado de dos formas distintas: la primera usando4 bucles y la segunda usando funciones definidas con Mathematica. La segunda opción resultóser más eficiente. Es por esto que es a utilizada en los métodos que implementan nuestroprotocolo criptográfico.

6.2 PRUEBAS INTERFAZ GRÁFICA

Para comprobar que la interfaz funciona de forma deseada se han ido realizando pruebassegún se iban implementando los distintos métodos. Primero los métodos cifrar, descifrar,firmar, verificar y generacionClaves, para después comprobar que todas las funcionalidadesde nuestra aplicación hacían lo que se les pedía.

También se comprobó que el método copiarTexto funcionana correctamente probándolo aparte.

76


7. GESTIÓN DEL PROYECTO

7.1 CAMBIO DE DISEÑO DE LA INTERFAZ

Como no contábamos con el tiempo necesario, se ha decidido simplificar la interfaz gráficade nuestra apliación. Es por esto que ahora la aplicación solo consta de una sola ventana queconsta de cinco pestañas: cada una para cada operación de nuestro criptosistema. Veamos elnuevo diseño de la interfaz.

Figura 7.1.: Prototipo final para generar claves

Figura 7.2.: Prototipo final para cifrar

77

7. GESTIÓN DEL PROYECTO

Figura 7.3.: Prototipo final para descifrar

Figura 7.4.: Prototipo final para firmar

Figura 7.5.: Prototipo final para verificar

Lo que queríamos conseguir conseguir con esta interfaz era que fuese siempre y fácil de

78


manejar por el usuario, algo que sí que creo que se ha conseguido, ya que todas las operacionesse muestran de una forma directa y fácil de entender por el usuario.

Además se ha tenido en cuanta que ninguna de las funciones pueda ser realizada sin habercargado la configuración del sistema: todos los botones estarán desactivados hasta que no seintroduzca el archivo que contiene todos los parámetros. Por otro lado, y ya con el sistema bienconfigurado, los botones que llevan a cabo las operaciones permanecera también bloquedashasta que no se introduzcan las variables necesarias para llevarlas a cabo (clave pública, claveprivada, firma...).

Por otro lado, también consideramos innecesario la creación de una clase para cada funciónde nuestro sistema criptográfico, es decir, una calse Cifrar, otra Descifrar... Es por esto quesolo se ha implementado dos clases en nuestro sistema: una la clase Gestor y otra llamadaPrincipal, que contiene todas las variables y todas las fucniones que son necesarias para quenuestra aplicación funcione correctamente.

7.2 CREACIÓN DE DOS PAQUETES DE MATHEMATICA

Para que nuestra aplicación funcione de manera adecuada hemos creado dos paquetes nue-vos de Mathematica: uno que prueba que los parámentros que se cargan para configurar elsistema son adecuados (quete pueba) y otro que dispone de todas las operaciones de nuestrocriptosistema, HECantor, pero que además trabaja con archivos. A esos nuevos métodos, aparte de los parámetros que ya hemos visto, se les pasa también una ruta (que será la rutadel archivo a trabajar) y el nombre del fichero de salida. Así usando las funciones de Mat-hematica SetDirectory y Export, podemos crear los archivos deseados en la ruta adecuado ycon el nombre que queríamos.

Estos paquetes se econtrarán en el CD adjunto.

7.3 MOTIVOS DEL DESFASE TEMPORAL

Se estimó que la fase de implementación de esta parte habría finalizado para principios defebrero, peroal final ha resultado que ha llevado más tiempo del que se había previsto. Estose debe a varios motivos:

Como hemos dicho se tuvieron que remodelar algunos de los algoritmos debiodo a pro-blemas con el paquete FiniteFields. Además no se entendió muy bien un texo y huboproblemas a la hora de generar los procedmientos de Cantor-Lange. Es más, también seencontraron errores en los textos originales de es estos algoritmos y hubo que encontrarsoluciones para poder llevarlos a cabo.

Enfermedad tanto de la proyectante como de un familiar cercano a ella. Desde diciembrehan ido surgiendo problemas de salud de un familiar, lo que ha impedido que me puedaconcentrar de lleno en el proyecto.

A parte de todo esto el desfase temporal también lo podemos achacar a la inexperiencia dela proyectante a la hora de hacer un trabajo de semejante magnitud.

79


8. CONCLUSIONES

He de decir que el mundo de la criptografía lleva ya tiempo maravillándome. Después deestar un tiempo considerable estudiando este tipo de problemas, y en concreto el que creaprotocolo criptográficos que utilizan curvas hiperelípticas, tenía un especial interés en crearuna apliación informática para ver si era capaz de plasmar todos los conocimientos adquiridosen los útimos años.

Este proyecto me ha servido para refrescar todos los conocimientos adquiridos en la carrera yadquirir algunos nuevos. Después de estar dos años de parón informático (he estado realizandootro tipo de proyectos o formándome en otros ámbitos) fue un poco complicado volver a pasarmucho tiempo delante del ordenador, pero al final ha merecido la pena. Podríamos decir queya manejo con soltura Mathematica y que no había olvidado por completo la programaciónen Java.

Por otro lado, también podemos decir que este trabajo me ha servido para crecer en otro tipode aspectos que no son tiene que ver con el mundo académico. Por ejemplo, he aprendido asuperar obstáculos que antes hubiese dado por imposibles y a no ponerme demasiado nerviosacuando algo no salía como estaba previsto.

8.1 LÍNEAS FUTURAS

Sería interesante hacer un sistema mucho más eficiente. Para ello sería interesante utilizaralgún otro software matemático que reconozca estructuras algebraicas y sea capaz de trabajarcon curvas hiperelípticas de una forma más rápida.

81


A. LAS MATEMÁTICAS DETRÁS DELPROYECTO

En el primero de los apéndices vamos dar algunos conociemientos básicos que nos ayuden aentender todo lo que se ha hecho en el proyecto.

A.1 PRIMER EJEMPLO: CURVAS ELÍPTICAS

Definición A.1.1. Sea K un cuerpo tal que char (K) distinta de 3 y sean ai ∈ K coni = 1, . . . , 6. Llamaremos curva elíptica E sobre un cuerpo K, a la curva dada por la ecuación:

E : y2 + a1xy + a3y = x3 + a2x2 + a4x+ a6

junto a un punto en el infinito, donde, además, cada punto (xi, yi) con coordenadas enK que satisfacen las ecuación anterior, no anula simultáneamente las derivadas parciales2y1 + a1x1 + a3 y 3x1 + 2a2x1 + a4 − a1y1.

Para empezar a hacernos una idea de todo esto vamos a ver un ejemplo mucho más sencillo,la operación suma de los puntos de una curva elíptica, que también es un útil criptográfico.Sea la curva elíptica E : y2 = x3 − x definida sobre R, que muestra la figura A.1.

Los criptosistemas que se basan en curvas elípticas también redefinen los algoritmos delelGammal, es por ello que también necesitamos crear una operación suma sobre los puntosde dicha curva. Se podría pensar que esto puede ser un trabajo horrible, pero en realidad esmucho más fácil de lo que en un primer momento podríamos esperar.

Imaginemos que queremos sumar los puntos P y Q de E. Para ello solamente trazaremos lalínea recta r que une estos dos puntos y que corta a E en otro tercer punto R y reflejar a Ra través del eje OX. Así −R = P ⊕Q.

A la hora de encontrar nuestro punto R tenemos tres casos diferentes que podemos apreciaren las figuras A.2, A.3, A.4

a) Que P = (x1, y1) y Q = (x2, y2) sean distintos. Para sumarlos se trazará la recta queune estos dos puntos. Sea r dicha recta. Como se puede apreciar el la figura A.2, lo quese consigue es que la recta r corte a E en un tercer punto R = (x3, y3). Reflejando R através del eje OX, encontramos el punto P ⊕Q = (x3,−y3).

b) Si P = Q, se tomará r como la recta tangente a P . Así aparecerá un segundo punto,que tras reflejarlo a través del eje OX nos dará el punto P ⊕Q = (x3,−y3), tal y comomuestra la figura A.3.

c) Que P y Q tangan la misma coordenada x,es decir P = (x1, y1) y Q = (x1, y2) tal quey2 = −y1.En este caso, como muestra la figura A.4, no se puede proceder como hastaahora, pero la recta que pasa por estos dos puntos es una recta paralela al eje OY y

83

A. LAS MATEMÁTICAS DETRÁS DEL PROYECTO

Figura A.1.: Curva elíptica E : y2 = x3 − x sobre R

Figura A.2.: Suma de dos puntos P y Q distintos

Figura A.3.: Cálculo de 2P

84


Figura A.4.: Suma de dos puntos P y Q con la misma coordenada x

como hemos dicho antes, el punto en el infinito es tal que todas las rectas paralelas aeste eje pasan por él. Es por esto que P ⊕Q = O.

A este método se le conoce como el método de la tangente. Así, y de una manera muy fácile intuitiva, tenemos ya definida una aplicación que definde la suma dentro del conjunto depuntos de una curva elíptica.

A.2 CURVAS HIPERÉLIPTICAS

Veamos ahora qué es una ecuación hiperelíptica.Definición A.2.1. Sea una curva dada por la ecuación

C : y2 + h(x)y = f(x) (A.1)

tal que h, f ∈ K[x], f es un polinomio mónico con deg(f) = 2g+1 y deg(h) ≤ g. Diremos queC es una curva hiperelíptica de género g sobre K si ningún punto sobre el que está definida lacurva anula a las dos derivadas parciales de C a la vez. Es decir, si 2y+ h = 0 y f ′− h′y = 0no se anulan a la vez para todo P ∈ C.

Si tenemos la curva definida sobre Z11

C : y2 = x5 + x4 + x3 + 2x2 + x+ 1

podemos comprobar de manera fácil que es hiperelíptica ya que si h(x) = 0 y f(x) = x5 −5x3 + 4x calculamos las derivas parciales las derivadas parciales

∂C

∂y= 2y

∂C

∂x= 5x4 + 4x3 + 3x2 + 4x+ 1

que no se anulan en ningún punto, luego C no tiene puntos singulares y por tanto es hiper-

elíptica de género g =gr(f)− 1

2= 2.

85


De manera intuitiva y viendo el ejemplo anterior, podríamos pensar que el método de latangete nos sirve también para sumar los puntos de la curva, pero nada más lejos de larealidad. Veamos algunos ejemplos, esta vez tomando la curva C : y2 = x5 − 5x3 + 4x.

Figura A.5.: Curva hiperelíptica C : y2 = x5 − 5x3 + 4x sobre R


86



Si nos fijamos solamente en la figura A.5, diríamos que no hay ningún problema con estemétodo. Pero, por desgracia, y si nos fijamos en la figura A.6 vemos la recta corta a C en5 puntos, luego la suma no tendría representante único. Es por esto que este método no esválido para este tipo de curvas. Para solucionar esto, formaremos un un grupo cociente desumas finitas de puntos de la curva C módulo sumas finitas de C que a su vez están en otrafunción junto un operador suma, que actuará componente a componente sobre los puntos deC. Como muestra la figura A.7.

En esta figura tenemos que P + Q y R + S son elementos de este grupo cociente. Paraencontrar el punto (P + Q) ⊕ (R + S) solo tendríamos que trazar la curva que pase porestos puntos (en nuestro caso sería una recta) y reflejando T a través del eje OX tenemos laoperación deseada (P + Q) ⊕ (R + S) = −T . Esto ocurre porque todos los elementos estánel grupo cociente definido por r:

Como(P +Q)⊕ (R+ S)⊕ (−T ) = 0 en el conjunto cociente generado por la recta r

se tiene que

(P1 + P2)⊕ (Q1 +Q2) = (R1 +R2) en el conjunto cociente

A.2.1 Jacobiano y divisores

La relación cociente que acabamos de ver crea (a grosso modo) la estructura de la varie-dad jacobiana de la curva hiperelíptica. Es allí donde encontramos los elementos (llamadosdivisores) que no ayudarán a construir nuestro criptosistema.

Como veremos al final de este subapartado, cada divisor del jacobiano de una curva hiper-elíptica se puede representar como un par de polinomios. Es por esto que a continuacióndaremos una serie de resultados matemáticos que nos ayuden a entender esta relación. Paralas demostraciones remitimos a los libros de la bibliografía.

87


Sea C : y2+h(x)y = f(x) es una función hiperelíptica definida sobre K[x, y], podemos definirel anillo coordenado de C sobre K, que denotaremos por K[C] como el anillo cociente

K[C] = K[x, y]/(y2 + h(x)y − f(x))

Por otro lado, si tomamos la clausura algebraica de K, tenemos el anillo coordenado de Csobre K y lo denotaremos por K[C]Nota A.2.2. K[C] es un cuerpo ya que y2 + h(x)y − f(x) es irreducible sobre K[x, y].

Definiremos también el cuerpo de funciones de C sobre K, que denotaremos como K(C),como el cuerpo de fracciones de K[C].Definición A.2.3. Sea C una curva hiperelíptica de género g sobre un cuerpo K dada porla ecuación A.1. Un divisor D , es una suma de puntos en C

D =∑P∈C

mPP, mP ∈ Z,

donde un número finito de mP son distintos de cero. Llamaremos grado de D, que denotaremospor gr(D), al número entero

∑P∈C mP y cada mP es el orden de D en P (se denota por

ordP (D)).

Veamos algunos de los conceptos que tienen que ver con el término divisor:Definición A.2.4. Sea C una curva hiperelíptica de género g sobre un cuerpo K y seaD =

∑P∈C = mPP un divisor. Entonces, llamaremos soporte de D al conjunto sop(D) =

{P ∈ C | mP 6= 0}.

Dentro del conjunto de divisores, podemos encontrar subconjuntos. Primero veamos qué esun divisor semirreducido y cuál es su relación con el conjunto global de divisores.Definición A.2.5. Sea C una curva hiperelíptica de género g sobre un cuerpo K, diremosque un divisor semirreducido es un divisor que tiene la forma

∑miPi − (

∑mi)O, donde

todo mi ≥ 0 y los distintos Pi son puntos finitos tales que cuando Pi ∈ sop(D) entonces−Pi /∈ sop(D), a no ser que Pi = −Pi, que ocurre cuando Pi es especial. En este caso, lamultiplicidad será mi = 1Ejemplo A.2.6. Si consideramos la curva hiperelíptica C : y2 = x5 + x4 + x3 + 2x2 + x + 1definida sobre Z11. Entonces un divisor sería una suma finita de puntos de C, por ejemplo:

D = 3[2, 1]− [5, 9] + 9[7, 0] + [2, 10]

Para construir el divisor semireducido de D no tenemos que fijar en todos los puntos. Es fácilcomprobar que, por ejemplo, −[5, 9] = [5, 2] y [2, 10] = −[2, 1]. Así tendríamos que el divisorsemirreducido asociado a D sería

D′ = 2[2, 1] + [5, 2] + 9[7, 0]

Pero todavía nos queda por dar otro paso: como [7, 0] = [7, 0 − h(7)] = [7, 0] se tiene que elpunto [7, 0] es especial luego su multiplicidad deber ser uno. Así tendríamos que

D′ = 2[2, 1] + [5, 2] + [7, 0]

es un divisor semirreducido tal que D ∼ D′.Lema A.2.7. Sea C una curva hiperelíptica de género g sobre un cuerpo K. Para cadadivisor de grado cero D ∈ Div0C existe un divisor semireducido D1 ∈ Div0C tal que D ∼ D1.

Lo que nos quiere decir el lema anterior es que cada divisor es equivalente a otro que seasemirreducido, que además es único. Pero los divisores que realmente nos importan son losreducidos, ya que son estos con los que trabjaremos más adelante:

88


Definición A.2.8. Sea C una curva hiperelíptica de género g sobre un cuerpo K y D =∑mi(Pi −O) un divisor semireducido. Si

∑mi ≤ g, entonces diremos que D es un divisor

reducido.Definición A.2.9. Sea C una curva hiperelíptica de género g sobre un cuerpo K y seaD =

∑P∈C mPP un divisor. Definimos normal de D a valor

| D |=∑

P∈C\O

| mP |

Al igual que ocurria con los divisores semirreducidos, podemos decir que cada divisor tieneun divisor reducido asociado, tal y como nos muestra el siguiente resultado:Proposición A.2.10. Para cada divisor D ∈ Div0C existe un único divisor reducido D1 talque D ∼ D1.

Es por esto que nosotros trabajaremos solamente con dicisores reducidos a la hora de crearnuestro criptosistema.

Como hemos dicho antes, podemos expresar los divisores reducidos como un par de poli-nomios y así encontrar una representación más familiar para poder trabajar con ellos. Estarepresentación se conoce como representación de Mumford. Así cada elemento de J es unaclase de polinomios que tiene como representantes a dos polinomios distintos [u, v].Teorema A.2.11. Sea C una curva hiperelíptica de género g dada por C : y2+h(x)y = f(x),donde h, f ∈ K[x], gr(f) = 2g + 1, gr(h) ≤ g. Cada clase de divisores no trivial en K puederepresentarse como un único par de polinomios (u(x), v(x)), u, v ∈ K[x], tales que:

a) u es mónico,

b) gr(v) < gr(u) ≤ g,

c) u | v2 + vh− f

A.3 SUMA DE DIVISORES

Una vez tenemos los divisores como elementos conocidos podemos dar la operación suma. Aeste algoritmo se le conoce como algoritmo de Cantor.

Algorithm 1 Algoritmo de CantorRequire: dos clases de divisores D1 = [u1, v1] y D2 = [u2, v2] en la curva C : y2 + h(x)y = f(x)Ensure: Un único divisor reducido D tal que D = D1⊕D2. d1 ← mcd(u1, u2) d← mcd(d1, v1+

v2 + h) s1 ← c1e1, s2 ← c1e2 y s3 ← c2 u ← u1u2

d2y v ← s1u1v2 + s2u2v1 + s3(v1v2 + f)

dmódulo u

1: repeat

2: u′ ← f − vh− v2

uy v′ ← (−h− v) módulo u′

3: u← u′ y v ← v′

4: until gr(u) ≤ gHacemos que u sea mónico.

5: return [u,v]

La primera parte de este algoritmo suma los dos divisores que le pasemos con la entrada,mientras que la segunda (el bloque while) lo que hace es reducir el divisor.

89


Muchas de estas nociones y algoritmos las hemos implementado y se encuentran en el paqueteque hemos generado para Mathematica. Además, se han añadido otras, como la descompo-sición del algoritmo de Cantor para buscar soluciones más eficientes.

90


B. CÓDIGO MATHEMATICA

Es ente segundo apéndice lo que veremos es el resto de funciones de Mathematica que se hanimplementado para comparar la eficiencia de los algoritmo. Así, aquí se muestran todas lasfunciones relacionadas con el algoritmo de Cantor por pasos realizadas con listas. Todas lasfucniones son análogas a las explicadas en el capítulo de implementación, por eso no se creenecesario el tener que decir cuál es su funcionalidad, es decir, solo daremos el código de cadauna de ellas.

Notar que hay dos procedimientos nuevos involucrados en la suma y el doclado de divisoresde grados dos. Estos dos métos tienen en cuenta la resultante y pasan una serie de coeficientesinvolucrados en su cálculo como entrada, evitándonos así calcularlo dos veces y ahorrándosoperaciones.

Pasemos a ver estos procedimientos.

Código B.1: Función SumarGrado1Listas

DoblarGr1Listas[u10_, v1_, f_, h_,char_] := (Module[{df, dh, u, v, sol, dff, dhh, vaux, aux, V0, V1,

aux2,},

dff = (5*(-u10)^4 + 4*f[[5]]*(-u10)^3 + 3*f[[4]]*(-u10)^2 +2*f[[3]]*(-u10) + f[[2]]);

dhh = h[[2]] + 2*h[[3]]*(-u10);

aux = 2*v1 + dhh;sol = Solve[aux*x == 1, x, Modulus -> char];aux = x /. sol[[1]];aux2 = dff - v1*dhh;

V1 = Mod[aux2*aux, char];V0 = Mod[v1 + aux2*aux*(u10), char];

Return[{{Mod[u10*u10, char], Mod[2*u10, char], 1}, {V0, V1}}];

];);

Código B.2: Función DoblarGr1Listas

SumarGr1Listas[u10_, v1_, u20_, v2_, char_] := (Module[{sol, inv, u, v,},(* Suma dos divisores distintos,ambos con polinomio u de grado 1 (el punto del soporte no es el \

mismo) *)u = (x + u10)*(x + u20);sol = Solve[(u10 - u20)*x == 1, x, Modulus -> char];inv = x /. sol[[1]];v = ((v2 - v1)*x + v2*u10 - v1*u20)*inv;

Return[{{Mod[u10*u20, char], Mod[u10 + u20, char],1}, {Mod[v2*u10*inv - v1*u20*inv, char],

91


Mod[(v2 - v1)*inv, char]}}];];

);

Código B.3: Función SumarGrado2Listas

SumarGr2Listas[u1_, v1_, u2_, v2_, f_, h_,char_] := (Module[{u, Co, u10, u11, gr, v10, v11, u20, u21, v20,

v21, h0, h1, h2, f4, z1, z2, z3, r, inv0, inv1, s1p, s0p, w0,w1, w2, w3, w4, w5, s0, s1, ss0, u0, us1, inv, l0, l1, l2, vs1,v0, aux, v, sol, uf0, uf1, vf0, vf1, w2p, vf0p},

(* Suma dos divisores en los que los puntos del soporto son \diferentes entre s de sus opuestos *)

(* Sacamos los coeficientes de todos los polinomios de entrada *)

u10 = u1[[1]]; u11 = u1[[2]];

u20 = u2[[1]]; u21 = u2[[2]];

If[Length[v1] == 2,v10 = v1[[1]];v11 = v1[[2]],v10 = v1[[1]];v11 = 0;];

If[Length[v2] == 2,v20 = v2[[1]];v21 = v2[[2]],v20 = v2[[1]];v21 = 0;];

h0 = h[[1]]; h1 = h[[2]]; h2 = h[[3]];

f4 = f[[5]];(* Calculamos la resultante*)z1 = u11 - u21;z2 = u20 - u10;z3 = u11*z1 + z2;r = Mod[z2*z3 + z1*z1*u10, char];

(* Calculamos el casi inverso *)inv1 = z1;inv0 = z3;

(* Calculamos s' *)w0 = v10 - v20;w1 = v11 - v21;w2 = inv0*w0;w3 = inv1* w1;

s1p = Mod[(inv0 + inv1)*(w0 + w1) - w2 - w3*(1 + u11), char];s0p = Mod[w2 - u10*w3, char];

(* Si s1p != 0 *)If[s1p != 0,

(* Calcuamos s'' *)

sol = Solve[r*s1p*x == 1, x, Modulus -> char];w1 = x /. sol[[1]];w2 = r*w1;w3 = s1p*s1p*w1;w4 = r*w2;w5 = w4*w4;

92


s0 = Mod[s0p*w2, char];

(* Calculamos l' *)l2 = Mod[u21 + s0, char];l1 = Mod[u21*s0 + u20, char];l0 = Mod[u20*s0, char];

(* Calculamos u *)

aux = (s0 - u11)*(s0 - z1 + h2*w4) - u10;uf0 =Mod[aux + l1 + (h1 + 2*v21)*w4 + (2 u21 + z1 - f4)*w5, char];uf1 = Mod[2*s0 - z1 + h2*w4 - w5, char];

(* Calculamos v *)w1 = l2 - uf1;w2 = uf1*w1 + uf0 - l1;vf1 = Mod[w2*w3 - v21 - h1 + h2*uf1, char];w2 = uf0*w1 - l0;vf0 = Mod[w2*w3 - v20 - h0 + h2*uf0, char];

(* Devolvemos u y v *)Return[{{uf0, uf1, 1}, {vf0, vf1}}],

(* Si sp1==0 *)

(* Calculamos s *)

sol = Solve[r*x == 1, x, Modulus -> char];inv = x /. sol[[1]];s0 = Mod[s0p*inv, char];

(* Calculamos u *)

uf0 = Mod[f4 - u21 - u11 - s0*s0 - s0*h2, char];

(* Calculamos v *)

vf0 = Mod[-h0 - s0*u20 + h1*uf0 + s0*u21*uf0 - h2*uf0*uf0 -s0*uf0*uf0 - v20 + uf0*v21, char];

Return[{uf0, vf0}];];];

);

Código B.4: Función DoblarGr2Listas

DoblarGr2Listas[u1_, v1_, f_, h_,char_] := (Module[{Co, u10, u11, v10, v11, h0, h1, h2, f4, f3, f2,

v1gorro, v0gorro, w0, w1, w2, w3, w4, w5, r, inv1, inv0, s1, s0,sol, t1, t0, s2p0, s2p1, l2, l1, l0, up0, up1, s1p0, vp1, vp0,sp0},

(* Dobla un divisor de grado dos *)

(* Sacamos todos los coeficientes *)u10 = u1[[1]];u11 = u1[[2]];

v10 = v1[[1]];v11 = v1[[2]];

h0 = h[[1]]; h1 = h[[2]]; h2 = h[[3]];

f4 = f[[5]];f3 = f[[4]];f2 = f[[3]];

93



(* Calculamos la resultante *)w0 = v11*v11;w1 = u11*u11;w2 = v1gorro*v1gorro;w3 = u11*v1gorro;r = Mod[u10*w2 + v0gorro*(v0gorro - w3), char];

(* Calculamos el casi inverso *)

inv1 = Mod[-v1gorro, char];inv0 = Mod[v0gorro - w3, char];

(* Calculamos t *)w3 = f3 + w1;w4 = 2*u10;t1 = Mod[2*(w1 - f4*u11) + w3 - w4 - h2*v11, char];t0 =Mod[u11*(2*w4 - w3 + f4*u11 + h2*v11) + f2 - w0 - 2*f4*u10 -h1*v11 - h2*v10, char];

(* Calculamos s *)w0 = t0*inv0;w1 = t1*inv1;

s1 = Mod[(inv1 + inv0)*(t0 + t1) - w0 - w1*(1 + u11), char];s0 = Mod[w0 - u10*w1, char];

If[s1 != 0,(* Es decir, si s' tiene grado uno*)(*Calculamos s'' *)

sol = Solve[s1*r*x == 1, x, Modulus -> char];w1 = x /. sol[[1]];w2 = r*w1;w3 = s1*s1*w1;w4 = r*w2;w5 = w4*w4;s2p0 = Mod[s0*w2, char];

(* Calculamos l *)l2 = Mod[u11 + s2p0, char];l1 = Mod[u11*s2p0 + u10, char];l0 = Mod[u10*s2p0, char];

(* Calculamos u *)

up0 = Mod[s2p0*s2p0 + w4*(h2*(s2p0 - u11) + 2*v11 + h1) +w5*(2*u11 - f4), char];

up1 = Mod[2*s2p0 + h2*w4 - w5, char];

(*Calculamos v *)w1 = l2 - up1;w2 = up1*w1 + up0 - l1;vp1 = Mod[w2*w3 - v11 - h1 + h2*up1, char];w2 = up0*w1 - l0;vp0 = Mod[w2*w3 - v10 - h0 - h2*up0, char];Return[{{up0, up1, 1}, {vp0, vp1}}],

(* Si s' es constante *)(* Calculamos s *)

sol = Solve[r*x == 1, x, Modulus -> char];w1 = x /. sol[[1]];

94


sp0 = Mod[s0*w1, char];w2 = u10*sp0 + v10 + h0;

(* Calculamos u *)

up0 = Mod[f4 - sp0*sp0 - sp0*h2 - 2*u11, char];

(* Calculamos v *)

w1 = sp0*(u11 - up0) - h2*up0 + v11 + h1;vp0 = Mod[up0*w1 - w2, char];

Return[{{up0, 1}, vp0}];];];

);

Código B.5: Función SumarGrDistintoListas

SumarGrDistintoListas[u10_, v10_, u2_, v2_, f_, h_,char_] := (Module[{Co, u20, u21, v20, v21, h0, h1, h2, f4, f3, f2,

r, inv, sol, s0, l1, l0, t2, t1, uf1, uf0, vf1, vf0},(* Suma dos divisores que tienen grado distinto.Asumiremos que el grado de u1 es uno y el de u2 es dos *)

(* Sacamos los coeficientes que necesitamos *)

u20 = u2[[1]]; u21 = u2[[2]];

v20 = v2[[1]];v21 = v2[[2]];

h0 = h[[1]]; h1 = h[[2]]; h2 = h[[3]];

f4 = f[[5]];f3 = f[[4]];


r = Mod[u20 - (u21 - u10)*u10, char];

(* Calculamos el casi invers0 *)

sol = Solve[r*x == 1, Modulus -> char];inv = x /. sol[[1]];

(* Calculamos s *)s0 = Mod[inv*(v10 - v20 + v21*u10), char];

(* Calculamos l *)l1 = Mod[s0*u21, char];l0 = Mod[s0*u20, char];

(* Calculamos t *)t2 = Mod[f4 - u21, char];t1 = Mod[f3 - (f4 - u21)*u21 - v21*h2 - u20, char];

(* Calculamos u *)uf1 = Mod[t2 - s0*s0 - s0*h2 - u10, char];uf0 = Mod[t1 - s0*(l1 + h1 + 2*v21) - u10*uf1, char];

(* Calcualmos v *)

vf1 = Mod[(h2 + s0)*uf1 - (h1 + l1 + v21), char];vf0 = Mod[(h2 + s0)*uf0 - (h0 + l0 + v20), char];Return[{{uf0, uf1, 1}, {vf0, vf1}}];

];

95


);

Código B.6: Función SumarGradoDistintoListas

SumarGradoDistintoListas[u10_, v1_, u2_, v2_, f_, h_,char_] := (Module[{grh, Co, h0, h1, h2, gru1, gru2, sol, cond, aux,

aux2, u20, x1, x2, x3, vaux, u11, u21, v10, v11, v20, v21, gr,r, v0gorro, v1gorro, w0, w1, w2, w3, rcoef, max, z1, z2, z3,v1x1, v2x1, y2, y3, CoU, CoV},

cond = Mod[u2[[1]] + u2[[2]]*(-u10) + (-u10)^2, char];If[cond != 0,(* P1 no esn el soporte de D2, es decir,sumamos dos divisores de grado distinto*)

Return[SumarGrDistintoListas[u10, v1, u2, v2, f, h, char]],(* D2 es el doble de D1: doblamos D2 y le restamos D1 *)

If[(u2[[2]] == Mod[2*(u10), char]) && (u2[[1]] ==Mod[(u10)*(u10), char]),

vaux = Mod[v2[[1]] + v2[[2]]*(-u10), char];If[v1 == vaux,aux = DoblarGr2Listas[u2, v2, f, h, char];Return[RestarListas[u10, v1, aux[[1]], aux[[2]], f, h, char]],x2 = Mod[u2[[2]] - u10, char];vaux = Mod[v2[[1]] + v2[[2]]*(-x2), char];Return[{{x2, 1}, vaux}];];

];

(* -P1 estn el soporte de D2 *)

cond = Mod[v2[[1]] + v2[[2]]*(-u10), char];aux2 = h[[1]] + h[[2]]*(-u10) + h[[3]]*(-u10)^2;aux = Mod[-v1 - aux2, char];x2 = Mod[u2[[2]] - u10, char];vaux = Mod[v2[[1]] + v2[[2]]*(-x2), char];If[cond == aux,Return[{{x2, 1}, vaux}],

(* -P1 no estn el soporte de D2 *)

aux = DoblarGr1Listas[u10, v1, f, h, char];Return[SumarGrDistintoListas[x2, vaux, aux[[1]], aux[[2]], f, h,char]];

];];];

);

Código B.7: Función RestarListas

RestarListas[u10_, v1_, u2_, v2_, f_, h_, char_] := (Module[{h0, h1, h2, sol, vn2, ru, rv, fin, Co, u, v, u20},

h2 = h[[3]]; h1 = h[[2]]; h0 = h[[1]];vn2 = Mod[-v1 - (h2 (-u10)^2 + h1 (-u10) + h0), char];

If[Length[u2] == 2,Return[SumarGr1Listas[u10, vn2, u2[[1]], v2, char]];];

96


If[Length[u2] == 3,Return[SumarGradoDistintoListas[u10, vn2, u2, v2, f, h, char]];];];

);

Notar que se han creado otros dos métodos para DoblarGr2Listas y SumarGr2Listas quetienen en cuenta el cálculo de la resultanta, pasando los parámetros calculados como entradasde las funciones. Para ver estos cambios, se remite al código que proporcionamos en el CD.

Código B.8: Función CantorLangeListas

CantorLangeListas[u1_, v1_, u2_, v2_, f_, h_,char_] := (Module[{grh, Co, h0, h1, h2, nu1, nu2, sol, u10, u20,

cond, aux, aux2, x1, x2, x3, vaux, u11, u21, v10, v11, v20, v21,gr, r, v0gorro, v1gorro, w0, w1, w2, w3, rcoef, max, z1, z2,z3, v1x1, v2x1, y2, y3, CoU, CoV, nv1x1},h0 = h[[1]];h1 = h[[2]];h2 = h[[3]];

nu1 = Length[u1];nu2 = Length[u2];

If[nu1 == 1, Return[{u2, v2}]];

If[nu1 == 2,(* Tanto u1 como u2 tienen grado uno *)

u10 = Mod[u1[[1]], char];If[nu2 == 2,u20 = Mod[u2[[1]], char];(* u1 y u2 son iguales *)If[u10 == u20,(* v1 y v2 son diferentes, es decir,los divisores tienen en el soporte dos puntos opuestos *)

If[v1 == Mod[-v2 - (h0 + h1*u10 + h2*u10*u10), char],Return[{{1}, 0}],(* v1 y v2 son iguales, es decir, doblamos el mismo divisor*)

Return[DoblarGr1Listas[u10, v1, f, h, char]];],(*Son dos divisores con puntos 2 puntos distintos en el soporte*)

Return[SumarGr1Listas[u10, v1, u20, v2, char]];],(* Entramos en el sino, es decir, gru2==2*)

Return[SumarGradoDistintoListas[u10, v1, u2, v2, f, h, char]];];];

If[nu1 == 3,

(* Sacamos los coeficientes de los cuatro polinomios *)

u10 = u1[[1]]; u11 = u1[[2]];

u20 = u2[[1]]; u21 = u2[[2]];

v10 = v1[[1]]; v11 = v1[[2]];

v20 = v2[[1]]; v21 = v2[[2]];

If[(u11 == u21) && (u10 == u20),aux =

97


PolynomialRemainder[(v10 + v20 + h0) + (v11 + v21 + h1)*x +h2*x^2, u10 + u11*x + x^2, x, Modulus -> char];

If[aux == 0,Return[{{1}, 0}];];

If[(v10 == v20) && (v11 == v21),


(* Calculamos la resultante *)w0 = v11*v11;w1 = u11*u11;w2 = v1gorro*v1gorro;w3 = u11*v1gorro;r = Mod[u10*w2 + v0gorro*(v0gorro - w3), char];

If[r == 0,(* Calculamos 2P2*)

max = PolynomialGCD[(v10 + v10 + h0) + (v11 + v11 + h1)*x +h2*x^2, u10 + u11*x + x^2, Modulus -> char];

sol = Solve[max == 0, x, Modulus -> char];x1 = x /. sol[[1]];

x2 = Mod[-u11 - x1, char];vaux = Mod[v10 + v11*x2, char];Return[DoblarGr1Listas[Mod[-x2, char], vaux, f, h, char]],

(* Doblamos un divisor con grado de u igual a 2*)

Return[DoblarGr2ResultanteListas[u1, v1, v0gorro, v1gorro,w0, w1, w2, w3, r, f, h, char]];

],(* Los polinomios v1 y v2 son distintos, es decir, P1==P3 y P2=-P4 *)

sol = Solve[(v21 - v11)*x == 1, x, Modulus -> char];aux = x /. sol[[1]];x1 = Mod[(v10 - v20)*aux, char];vaux = Mod[v10 + v11*x1, char];

Return[DoblarGr1Listas[Mod[-x1, char], vaux, f, h, char]];],

(* Los polinomios u1 y u2 son disfentes *)(*Calculamos la resultante*)

z1 = u11 - u21;z2 = u20 - u10;z3 = u11*z1 + z2;r = Mod[z2*z3 + z1*z1*u10, char];

If[r != 0,(* Tenemos dos divisores de grado dos distintos *)

Return[SumarGr2ResultanteListas[u1, v1, u2, v2, z1, z2, z3, r,f, h, char]],

max =PolynomialGCD[u20 + u21*x + x^2, u10 + u11*x + x^2,Modulus -> char];

Co = CoefficientList[max, x];x1 = Mod[-Co[[1]], char];

v1x1 = Mod[v10 + v11*x1, char];v2x1 = Mod[v20 + v21*x1, char];

98


x2 = Mod[-u11 - x1, char];y2 = Mod[v10 + v11*x2, char];x3 = Mod[-u21 - x1, char];y3 = Mod[v20 + v21*x3, char];

If[v1x1 == v2x1,(* 2P1+P2+P3 *)

nv1x1 = Mod[-v1x1 - h0 - h1*x1 - h2*x1^2, char];If[v1x1 == nv1x1,

Return[SumarGr1Listas[Mod[-x2, char], y2, Mod[-x3, char],y3, char]],

aux = DoblarGr1Listas[Mod[-x1, char], v1x1, f, h, char];

aux2 = SumarGradoDistintoListas[Mod[-x2, char], y2,aux[[1]], aux[[2]], f, h, char];

Return[SumarGradoDistintoListas[Mod[-x3, char], y3,aux2[[1]], aux2[[2]], f, h, char]];

],

(* P2+P3 *)

Return[SumarGr1Listas[Mod[-x2, char], y2, Mod[-x3, char], y3,char]];

];];];];];

);

Código B.9: Función DivisorPorCtelangeListas

DivisorPorCteLangeListas[n_, u1_, v1_, f_, h_,char_] := (Module[{uP, vP, uR, vR, m, Fin, Fin2, divisible},uP = u1;vP = v1;uR = u1;vR = v1;

If[Mod[n, 2] == 0,m = n - 1,m = n];

While[m > 0,If[m != n,divisible = Divisible[m, 2];If[divisible == False,{uR, vR} = CantorLangeListas[uR, vR, uP, vP, f, h, char];];];{uP, vP} = CantorLangeListas[uP, vP, uP, vP, f, h, char];m = Quotient[m, 2];];Return[{uR, vR}];];

);

Código B.10: Función OrdenLangeListas

99


OrdenDivisorLangeListas[u_, v_, f_, h_,char_] := (Module[{uaux, vaux, cond, orden, aux1, aux2, gru,

gruaux, lista},uaux = u;vaux = v;cond = True;orden = 1;gru = Length[u];If[gru == 3,While[cond,lista = CantorLangeListas[uaux, vaux, u, v, f, h, char];uaux = lista[[1]];vaux = lista[[2]];orden = orden + 1;If[{uaux, vaux} == {{1}, 0},cond = False;];];Return[orden]];If[gru == 2,While[cond,lista = CantorLangeListas[u, v, uaux, vaux, f, h, char];uaux = lista[[1]];vaux = lista[[2]];orden = orden + 1;If[{uaux, vaux} == {{1}, 0},cond = False;];];Return[orden]];];

);

Código B.11: Función ClavesLangeListas

ClavesLangeListas[Divisor_, p_, f_, h_,char_] := (Module[{PrivK, PubK, k},PrivK = RandomInteger[{1, p - 1}];PubK =DivisorPorCteLangeListas[PrivK, Divisor[[1]], Divisor[[2]], f,h, char];


];);

Código B.12: Función CifradoLangeListas

CifradoLangeListas[M_, Divisor_, PubK_, p_, f_, h_,char_] := (Module[{k, D2, Co, m, cm1, cm2, cm3, cm4, Divaux, n,


cond = 0;While[cond == 0,k = RandomInteger[{1, p - 1}];D2 =DivisorPorCteLangeListas[k, PubK[[1]], PubK[[2]], f, h, char];If[(D2[[1]][[1]] != 0) && (D2[[1]][[2]] !=

0) && (D2[[2]][[1]] != 0) && (D2[[2]][[2]]) != 0,cond = 1;];];

m = RomperMensaje[M];

100


cm1 = m[[1]]*D2[[1]][[1]];cm2 = m[[2]]*D2[[1]][[2]];

cm3 = m[[3]]*D2[[2]][[1]];cm4 = m[[4]]*D2[[2]][[2]];

Divaux =DivisorPorCteLangeListas[k, Divisor[[1]], Divisor[[2]], f, h,char];

Return[{{cm1, cm2, cm3, cm4}, Divaux}];

];);

Código B.13: Función DescifradoLangeListas

DescifradoLangeListas[cM_, Divisor_, PrivK_, p_, f_, h_,char_] := (Module[{Divaux, Co, sol, aux1, aux2, m1, m2, m3, m4},

Divaux =DivisorPorCteLangeListas[PrivK, Divisor[[1]], Divisor[[2]], f,h, char];

m1 = cM[[1]]/Divaux[[1]][[1]];m2 = cM[[2]]/Divaux[[1]][[2]];

m3 = cM[[3]]/Divaux[[2]][[1]];m4 = cM[[4]]/Divaux[[2]][[2]];


];);

Código B.14: Función FirmaLangeListas

FirmaLangeListas[M_, Divisor_, p_, priv_, f_, h_,char_] := (Module[{hash, k, Daux, u0, r, s, lista, n, parte, m1,

m2, m3, m4, i},



Daux =DivisorPorCteLangeListas[k, Divisor[[1]], Divisor[[2]], f, h,char];

u0 = Daux[[1]][[1]];r = Mod[u0 + hash, p];

s = Mod[k - priv*r, p];];

Return[{r, s}];

];

);

101


Código B.15: Función VerificacionLangeListas

VerificacionLangeListas[CM_, Divisor_, PK_, p_, r_, s_, f_, h_,char_] := (Module[{hash, Daux1, Daux2, D2, Co, u0, r2},

hash = Hash[CM];

Daux1 =DivisorPorCteLangeListas[s, Divisor[[1]], Divisor[[2]], f, h,char];

Daux2 =DivisorPorCteLangeListas[r, PK[[1]], PK[[2]], f, h, char];

D2 = CantorLangeListas[Daux1[[1]], Daux1[[2]], Daux2[[1]],Daux2[[2]], f, h, char];

u0 = D2[[1]][[1]];


Return[r2 == r];

];)

102


BIBLIOGRAFÍA

[Aky09] M.M. Akyürek. «The chinese remainder theorem for polynomials and itsapplications». 2009.

[Bla10] R.E. Blahut. «Fast algorithms for signal processing». Cambridge Univer-sity Press, 2010.

[CFA06] H. Cohen, G. Frey y R. Avanzi. «Handbook of elliptic and hyperellipticcurve cryptography». CRC press, 2006.

[Fer07] F.J.M. Ferrer. «Criptosistema el gammal mediante curvas hiperelıpticas».2007.

[Gal11] S. Galbraith. «Mathematics of public key cryptography». Livre en prépa-ration, 2011.

[GKS11] Pierrick Gaudry, David Kohel y Benjamin Smith. «Counting pointson genus 2 curves with real multiplication». Advances in Cryptology–ASIACRYPT 2011, páginas 504–519, 2011.

[GS04] Pierrick Gaudry y Éric Schost. «Construction of secure random curves ofgenus 2 over prime fields». En «Advances in Cryptology-EUROCRYPT2004», páginas 239–256. Springer, 2004.

[Har77] R. Hartshorne. «Algebraic geometry», volumen 52. Springer, 1977.

[HVM04] D.R. Hankerson, S.A. Vanstone y A.J. Menezes. «Guide to elliptic curvecryptography». Springer-Verlag New York Inc, 2004.

[JJMS04] M.J. Jacobson Jr, A.J. Menezes y A. Stein. «Hyperelliptic curves andcryptography». High primes and misdemeanours: lectures in honour of the60th birthday of Hugh Cowie Williams, 41:255–282, 2004.

[Kak] Avi Kak. «Elliptic curve cryptography and digital rights management.lecture notes on computer and network security».

[Kir92] F. Kirwan. «Complex algebraic curves», volumen 23. Cambridge Univer-sity Press, 1992.

[Lana] Tanja Lange. «Efficient arithmetic on hyperelliptic curves over finitefields». URL hyperelliptic.org/tanja/vortraege/taiwan_talk_II.ps. Visitada en enero del 2013.

[Lanb] Tanja Lange. «Elliptic vs. hyperelliptic, part 2». URL www.hyperelliptic.org/tanja/vortraege/ECC_06.ps. Visitada en enero del2013.

103

hyperelliptic.org/tanja/vortraege/taiwan_talk_II.ps

hyperelliptic.org/tanja/vortraege/taiwan_talk_II.ps

www.hyperelliptic.org/tanja/vortraege/ECC_06.ps

www.hyperelliptic.org/tanja/vortraege/ECC_06.ps

BIBLIOGRAFÍA

[Lanc] Tanja Lange. «Elliptic vs. hyperelliptic, part 3 - elliptic strikes back». URLhyperelliptic.org/tanja/vortraege/EC_vs_HEC_III.ps. Visitada enenero del 2013.

[Land] Tanja Lange. «Hyperelliptic curves». URL hyperelliptic.org/tanja/vortraege/taiwan_talk_I.ps. Visitada en enero del 2013.

[Lane] Tanja Lange. «Hyperelliptic curves in cryptography». URLhyperelliptic.org/tanja/vortraege/vorSatoh.ps. Visitada en enerodel 2013.

[Lan02a] T. Lange. «Efficient arithmetic on genus 2 hyperelliptic curves over finitefields via explicit formulae». Informe técnico, Citeseer, 2002.

[Lan02b] Tanja Lange. «Efficient arithmetic on hyperelliptic curves». IEM, 2002.

[Lan05] T. Lange. «Formulae for arithmetic on genus 2 hyperelliptic curves». Ap-plicable Algebra in Engineering, Communication and Computing, 15(5):295–328, 2005.

[LS05] T. Lange y M. Stevens. «Efficient doubling on genus two curves over binaryfields». En «Selected Areas in Cryptography», páginas 170–181. Springer,2005.

[Mag] Magma. «Magma computational algebra system». URL http://magma.maths.usyd.edu.au/magma/. Visitada en enero del 2013.

[Men93] A.J. Menezes. «Elliptic curve public key cryptosystems», volumen 234.Springer, 1993.

[MoWDoCO+96] A. Menezes, University of Waterloo. Dept. of Combinatorics, Optimization,University of Waterloo. Faculty of Mathematics, R. Zuccherato y Y.H.Wu. «An elementary introduction to hyperelliptic curves». Faculty ofMathematics, University of Waterloo, 1996.

[Nal09] D. Nali. «Hyperelliptic curves and their applications to cryptography.».2009.

[Per08] A. Perunicic. «The group structure of elliptic curves defined over finitefields». 2008.

[PWP04a] Jan Pelzl, Thomas Wollinger y Christof Paar. «High performance arith-metic for special hyperelliptic curve cryptosystems of genus two». En «In-formation Technology: Coding and Computing, 2004. Proceedings. ITCC2004. International Conference on», volumen 2, páginas 513–517. IEEE,2004.

[PWP04b] Jan Pelzl, Thomas Wollinger y Christof Paar. «Special hyperelliptic curvecryptosystems of genus two: Efficient arithmetic and fast implementation».Embedded Cryptographic Hardware: Design and Security, 2004.

[Resa] Wolfram Research. «Algebra polynomialextendedgcd». URLhttp://reference.wolfram.com/legacy/v5/Add-onsLinks/StandardPackages/Algebra/PolynomialExtendedGCD.html. Visita-da en enero del 2013.

104

hyperelliptic.org/tanja/vortraege/EC_vs_HEC_III.ps

hyperelliptic.org/tanja/vortraege/taiwan_talk_I.ps

hyperelliptic.org/tanja/vortraege/taiwan_talk_I.ps

hyperelliptic.org/tanja/vortraege/vorSatoh.ps

http://magma.maths.usyd.edu.au/magma/

http://magma.maths.usyd.edu.au/magma/

http://reference.wolfram.com/legacy/v5/Add-onsLinks/StandardPackages/Algebra/PolynomialExtendedGCD.html

http://reference.wolfram.com/legacy/v5/Add-onsLinks/StandardPackages/Algebra/PolynomialExtendedGCD.html


[Resb] Wolfram Research. «Calling mathematica from java». URLhttp://reference.wolfram.com/mathematica/JLink/guide/CallingMathematicaFromJava.html. Visitada en marzo del 2013.

[Resc] Wolfram Research. «How to connect a java program to mathe-matica». URL http://reference.wolfram.com/mathematica/howto/ConnectAJavaProgramToMathematica.html. Visitada en marzo del 2013.

[Resd] Wolfram Research. «Writing java programs that use mathematica».URL http://reference.wolfram.com/mathematica/JLink/tutorial/WritingJavaProgramsThatUseMathematica.html. Visitada en marzo del2013.

[Sad04] S. Sadanandan. «Addition in the jacobian of hyperelliptic curves». Tesisde doctorado, Indian Institute of Technology Madras Germany, 2004.

[Sae97] M. Saeki. «Elliptic curve cryptosystems». Tesis de doctorado, Citeseer,1997.

[saga] sagemath. «Sage en español». URL http://www.sagemath.org/es/. Vi-sitada en enero del 2013.

[sagb] sagemath. «Sage en español». URL http://www.sagemath.org/es/. Vi-sitada en marzo del 2013.

[sagc] sagemath. «Sagemathe en español». URL http://www.sagemath.org/es/. Visitada en enero del 2013.

[Sha71] D. Shanks. «Class number, a theory of factorization, and genera». En«Proc. Symp. Pure Math», volumen 20, páginas 415–440, 1971.

[Sil09] J.H. Silverman. «The arithmetic of elliptic curves», volumen 106. Springer,2009.

[staa] stackexchange. «Failed to connect remote mat-hematica kernel using j/link». URL http://mathematica.stackexchange.com/questions/15097/failed-to-connect-remote-mathematica-kernel-using-j-link.Visitada en marzo del 2013.

[stab] stackexchange. «How do i get java to recognize import com.wolfram.jlink».URL http://mathematica.stackexchange.com/questions/7618/how-do-i-get-java-to-recognize-import-com-wolfram-jlink.Visitada en marzo del 2013.

[stac] stackexchange. «How to do algebra within finite fields in mathe-matica [closed]». URL http://mathoverflow.net/questions/109896/how-to-do-algebra-within-finite-fields-in-mathematica. Visita-da en febrero del 2013.

[stad] stackexchange. «How to do the polynomial stuffover finite fields extensions fast?». URL http://mathematica.stackexchange.com/questions/16159/how-to-do-the-polynomial-stuff-over-finite-fields-extensions-fast.Visitada en febrero del 2013.

105

http://reference.wolfram.com/mathematica/JLink/guide/CallingMathematicaFromJava.html

http://reference.wolfram.com/mathematica/JLink/guide/CallingMathematicaFromJava.html

http://reference.wolfram.com/mathematica/howto/ConnectAJavaProgramToMathematica.html

http://reference.wolfram.com/mathematica/howto/ConnectAJavaProgramToMathematica.html

http://reference.wolfram.com/mathematica/JLink/tutorial/WritingJavaProgramsThatUseMathematica.html

http://reference.wolfram.com/mathematica/JLink/tutorial/WritingJavaProgramsThatUseMathematica.html

http://www.sagemath.org/es/




http://mathematica.stackexchange.com/questions/15097/failed-to-connect-remote-mathematica-kernel-using-j-link



http://mathematica.stackexchange.com/questions/7618/how-do-i-get-java-to-recognize-import-com-wolfram-jlink

http://mathematica.stackexchange.com/questions/7618/how-do-i-get-java-to-recognize-import-com-wolfram-jlink

http://mathoverflow.net/questions/109896/how-to-do-algebra-within-finite-fields-in-mathematica

http://mathoverflow.net/questions/109896/how-to-do-algebra-within-finite-fields-in-mathematica

http://mathematica.stackexchange.com/questions/16159/how-to-do-the-polynomial-stuff-over-finite-fields-extensions-fast



BIBLIOGRAFÍA

[stae] stackexchange. «How to execute a function in the package from ja-va?». URL http://mathematica.stackexchange.com/questions/6368/how-to-execute-a-function-in-the-package-from-java. Visitada enmarzo del 2013.

[staf] stackexchange. «How to install packages?». URL http://mathematica.stackexchange.com/questions/669/how-to-install-packages. Visi-tada en enero del 2013.

[stag] stackexchange. «Looking for “longest common substring” solution».URL http://mathematica.stackexchange.com/questions/6144/looking-for-longest-common-substring-solution/6376#6376. Visi-tada en marzo del 2013.

[stah] stackexchange. «Making mathematica packages».URL http://stackoverflow.com/questions/6633180/making-mathematica-packages. Visitada en marzo del 2013.

[stai] stackexchange. «Mathgraphicsjpanel no output». URLhttp://mathematica.stackexchange.com/questions/8958/mathgraphicsjpanel-no-output. Visitada en marzo del 2013.

[staj] stackexchange. «Using a user defined mathematica package with math-link». URL http://mathematica.stackexchange.com/questions/7823/using-a-user-defined-mathematica-package-with-mathlink.Visitada en marzo del 2013.

[stak] stackoverflow. «Calling java project from mathemati-ca». URL http://stackoverflow.com/questions/2176697/calling-java-project-from-mathematica. Visitada en marzo del2013.

[stal] stackoverflow. «How to install new packages for mathematica?». URLhyperelliptic.org/tanja/vortraege/vorSatoh.ps. Visitada en enerodel 2013.

[SV] J. Scholten y F. Vercauteren. «An introduction to elliptic and hyperellipticcurve cryptography and the ntru cryptosystem».

[Was08] L.C. Washington. «Elliptic curves: number theory and cryptography»,volumen 50. Chapman & Hall, 2008.

[Wen03] Annegret Weng. «Constructing hyperelliptic curves of genus 2 suitable forcryptography». Mathematics of Computation, 72(241):435–458, 2003.

[Wol04] Thomas Wollinger. «Software and hardware implementation of hyperellip-tic curve cryptosystems». Europ. Univ.-Verlag, 2004.

106

http://mathematica.stackexchange.com/questions/6368/how-to-execute-a-function-in-the-package-from-java

http://mathematica.stackexchange.com/questions/6368/how-to-execute-a-function-in-the-package-from-java

http://mathematica.stackexchange.com/questions/669/how-to-install-packages

http://mathematica.stackexchange.com/questions/669/how-to-install-packages

http://mathematica.stackexchange.com/questions/6144/looking-for-longest-common-substring-solution/6376#6376

http://mathematica.stackexchange.com/questions/6144/looking-for-longest-common-substring-solution/6376#6376

http://stackoverflow.com/questions/6633180/making-mathematica-packages

http://stackoverflow.com/questions/6633180/making-mathematica-packages

http://mathematica.stackexchange.com/questions/8958/mathgraphicsjpanel-no-output

http://mathematica.stackexchange.com/questions/8958/mathgraphicsjpanel-no-output

http://mathematica.stackexchange.com/questions/7823/using-a-user-defined-mathematica-package-with-mathlink

http://mathematica.stackexchange.com/questions/7823/using-a-user-defined-mathematica-package-with-mathlink

http://stackoverflow.com/questions/2176697/calling-java-project-from-mathematica

http://stackoverflow.com/questions/2176697/calling-java-project-from-mathematica

hyperelliptic.org/tanja/vortraege/vorSatoh.ps


AGRADECIMIENTOS

A mis padres, por apoyarme y confiar en mí durante todo este tiempo.A mi hermana Ana, por acogerme en su casa cuando peor lo estaba pasando.A Carmen, por darme consejo y calmarme en mucho momenos.A Rombo, por estar siempre dispuesto a sacarme a la calle.A mis amigos, por aguantar con paciencia todos mis cambios de humor.

107

Documents

Sistema criptográfico basado en curvas hiperelípticas · Verónica González Oquina Sistema criptográfico basado en curvas hiperelípticas Julio Rubio García Facultad de Ciencias,