Melesio Márquez Oropeza

Alba M. Sánchez Gálvez

Facultad de Ciencias de la Computación

Conceptos

Criptografía de Llave pública tipo ElGamal

Implementación

Resultados

Consideraciones Finales

Criptografía con Curvas Elípticas

Curva ElípticaSe define por medio de una ecuación:

E: y2 = x3 + ax + b

(Ecuación reducida de Weierstrass)

Los coeficientes a,b pueden ser números Reales o estar en un campo finito de orden p GF(p).

Campos Finitos

Campos Finitos

Curva Elíptica (y2 = x3 + ax + b)

Si se cumple que: 4a3 + 27b2 ≠ 0

Entonces E define un grupo abeliano G(E)

Se definen 2 Operaciones : Adición y multiplicación

Curva Elíptica (y2 = x3 + ax + b)Suma: método de la cuerda y tangente

Curva Elíptica (y2 = x3 + ax + b)

Multiplicación (método binario)

Conceptos

El algoritmo de ElGamal

Implementación

Resultados

Consideraciones Finales

Criptografía con Curvas Elípticas

Criptografía de Llave Pública

Problema del Logaritmo Discreto (ELDP)La seguridad de CCE depende de la dificultad del

ECDL:Sean P y Q dos puntos en una curva elíptica, tales

que: kP = Q, donde k es un escalar.

Dados P y Q, no es factible computacionalmente obtener k, si k es lo suficientemente grande.

k es llamado el logaritmo discreto de Q en la base P.

Criptosistema ElGamalSe establece una curva E sobre un campo

finito Fp

Se elige un entero s y se elige un punto P

Calcular B = sP

Los puntos P,B, Fp y la curva E forman la clave pública

Criptosistema ElGamal

Criptosistema ElGamal1) Se obtiene la Clave Pública del receptor

2)Se convierte el mensaje a un punto ME(Fp)

3)Se elige un entero aleatorio k y se calcula M1 = kP

4)Calcular M2 = M + kB

5)Se envían M1 y M2 al receptor

Criptosistema ElGamalPara obtener el mensaje:

M = M2 – sM1

Lo anterior funciona ya que :

M2 – sM1 = (M + kB) – s(kP) = M + skP – skP = M

Criptosistema ElGamalLos puntos M1 y M2 son públicos

Si se puede calcular el logaritmo discreto, se puede utilizar P y B para encontrar s (la clave Privada)

Se utiliza s para obtener el mensaje haciendo:

M = M2 - kB

Criptosistema ElGamalEs importante generar un k aleatorio distinto

para cada mensajeSi tenemos M y M’ , y encriptamos utilizando

el mismo numero k M1 = M1’

Se calcula M2’ – M2 = M’ – M

Si conocemos M, entonces:M’ = M – M2 + M2’

Ataques conocidos

Búsqueda exahustiva – Calcular sucesivamente los multiplos de P:

2P, 3P, … hasta obtener Q

Puede tomar hasta n pasos, (n es el orden de la Curva)

Ataques conocidos

POLLARD’S RHO ALGORITHM.

Versión aleatorizada del Baby-step Gigant step

pasos

Conceptos

El algoritmo de ElGamal

Implementación

Resultados

Consideraciones Finales

Criptografía con Curvas Elípticas

Arquitectura

Aritmética en E(Fp)

Protocolo Criptográfico

Mensaje

CRIPTOSISTEMACRIPTOSISTEMA

Diagrama de clasesAritmética

Curva

Punto

Diagrama de clasesElGamal

Implementacion AritmeticaLibrería JAVA : BigInteger

Funciones de soporte para aritmética de precisión arbitraria.

Ej.

Implementación AritméticaArchivo que contiene los parámetros de una

curva

Curvas recomendadas por NIST

Implementacion El GamalConstructor de Clase:

La aritmética es transparente al algoritmo

Implementación CifradorConvertir una cadena de texto a elemento de

Fp:

M - es el mensaje convertido a elemento de FpL -es el tamaño del alfabeto

Ci – El carácter i-ésimo de la cadena

Implementación

Implementación

Implementación

Conceptos

El algoritmo de ElGamal

Implementación

Resultados

Consideraciones Finales

Criptografía con Curvas Elípticas

Tiempos de ejecución

ConclusionesLa importancia de separar los componentes

de un criptosistema basándonos en el paradigma POO.

Flexibilidad de las librerías de JAVA para la implementación de la aritmética

Posibilidad de extender el criptosistema agregando módulos

!!GRACIAS!!