criptografÍa - departamento de matemática aplicada...
TRANSCRIPT
CRIPTOGRAFÍA5º CURSO DE INGENIERÍA INFORMÁTICA
E.T.S.I. Informática
Universidad de Sevilla
Curso 2007/2008
Criptografía de clave pública
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CRIPTOGRAFÍA DE CLAVE PÚBLICA
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
SI la clave es pública cualquiera puede
descifrar,… ¿o no?
Idea fundamental:
◦ Asimetría separación de claves: una pública que
cifra y otra privada que descifra.
Dos ejemplos:
1. El cartero fiel:
Clave pública: mi dirección.
Clave privada: la llave de mi buzón.
2. El fabricante de cajas de seguridad:
Clave pública: una caja abierta, que se bloquea al cerrarla.
Clave privada: mi llave de la caja.
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CRIPTOGRAFÍA DE CLAVE PÚBLICA
Cifrado y descifrado asimétrico: la clave
pública la tienen todos, la clave privada
sólo la tiene el destinatario:
¡Ni el mismo emisor puede descifrar!
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CRIPTOGRAFÍA DE CLAVE PÚBLICA
El concepto de criptosistema de clave pública fue
descubierto por James Ellis (Government
Communications Headquarters) al final de los años
60 (7 años antes que DH).
Clifford Cocks desarrolló esas ideas y descubrió un
criptosistema equivalente a RSA en 1973 (3-4 años
antes que Rivest, Shamir y Adleman).
Malcolm Williamson, buscando fallos en el trabajo de
Cocks, descubre el Intercambio de claves DH en
1975 (un año antes que Diffie y Hellman).
Un poco de (pre)historia:
Los servicios secretos no supieron valorar estos
descubrimientos, pero los mantuvieron en secreto y el mérito
fue para otros.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CRIPTOGRAFÍA DE CLAVE PÚBLICA
Whitfield Diffie y Martin Hellman publicaron
el artículo “New Directions in Cryptography”
en 1976.
• Los autores afirman que
sería posible implementar
criptosistemas de clave
pública usando esotéricas
funciones relacionadas con
difíciles problemas
matemáticos.
• No hacen propuestas
concretas.
Hellman, Merkle y Diffie
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CRIPTOGRAFÍA DE CLAVE PÚBLICA
¿Cuáles son esas mágicas funciones
matemáticas?
Funciones de un solo sentido:
◦ En realidad son funciones biyectivas… ¡de otra forma no
se podría descifrar!
◦ Lo importante es que para ser capaz de invertirlas hay
que conocer cierta información: ¡la clave privada!.
◦ Si no se conoce la clave privada es computacionalmente
imposible invertir la función.
¿Quién conoce una función así?
◦ Esta pregunta queda en pie tras el artículo de Diffie y
Hellman.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CRIPTOGRAFÍA DE CLAVE PÚBLICA
La función de un solo sentido,
trabajando en el sentido fácil.
La información necesaria es
pública.
La función sólo puede invertirse
si se conoce la clave privada.
Sólo para tus ojos.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: MOCHILA DE MERKLE-HELMAN
Merkle y Hellman propusieron en 1977 el
que fue (probablemente) el primer
sistema de cifrado de clave pública.
Basado en el problema subset-sum:
El problema es NP-completo y es llamado
a menudo el problema de la mochila.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: UN PARÉNTESIS MATEMÁTICO
El caso de la mochila supercreciente:Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: GENERACIÓN DE CLAVES
Cada usuario crea su clave pública y
la correspondiente clave privada:Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: CIFRADO Y DESCIFRADO
B cifra un mensaje para A
A descifra el mensaje de B
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: ¿POR QUÉ FUNCIONA EL DESCIFRADO?
La operación que se realiza en el descifrado es:Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: SEGURIDAD
El problema general subset-sum es NP-completo,
pero el particular de la mochila derivada de una
supercreciente no lo es.
Se conoce un ataque capaz de romper el
criptosistema en tiempo polinomial.
El único sistema criptográfico basado en el
problema de la mochila para el que aún no se
conoce un ataque con éxito es el de Chor-
Rivest.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA
En 1977 Ron Rivest, Adi Shamir y Len Adleman
propusieron un criptosistema de clave pública
sustentado en el que pasó a llamarse el
problema RSA, basado en la factorización de
enteros.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: UN PARÉNTESIS MATEMÁTICO
Inversos módulo n :Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: UN PARÉNTESIS MATEMÁTICO
Teorema Chino del Resto (TCR)Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: UN PARÉNTESIS MATEMÁTICO
s = 1, t = m, q = e;
mientras (q > 0)
si (q & 1) // si q es impar
s = s * t;
q = q / 2; // división entera(desplazamiento)
t = t * t;
retorna s;
100 =11001002
1──M──► 2──C──► 4 ──M──► 8 ──C──► 64──C──► 4096 ──C──► 16777216 ──M──► 33554432──C──► 1125899906842624──C──► 1267650600228229401496703205376
Cálculo de potencias enteras
o La idea:
o El seudocódigo de una versión no recursiva sería así:
o Sin ordenador es un poco diferente. Ejemplo de cálculo de 2100:
⟶ 1C1C0C0C1C0C0 ⟶ MCMC0C0CMC0C0 ⟶ MCMCCCMCC
No son100 multiplicaciones,
sino sólo 9 (máximo = 2· nº de
bits del exponente - 1).
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: UN PARÉNTESIS MATEMÁTICO
Si el número obtenido no es primo volvemos a
sortear los bits intermedios y repetimos hasta
obtener un primo.
Construcción de primos grandes
1 * * ················· * * 1
Se construye un entero impar de 𝑘 bits:
El primero y el último bit se ponen a 1 y los bits
intermedios se eligen al azar.
La probabilidad de que el número así construido
sea primo es de 2 / (𝑘·ln 2)
¿Cómo saber si hemos encontrado un primo?
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: UN PARÉNTESIS MATEMÁTICO
Test de primalidad de Miller-RabinCriptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: UN PARÉNTESIS MATEMÁTICO
Búsqueda de primos fuertes: test de
GordonCriptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: EL PROBLEMA
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA Y LA FACTORIZACIÓN
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: GENERACIÓN DE CLAVES
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: CIFRADO Y DESCIFRADO
B cifra un mensaje para A
1. Obtiene la clave pública de A (𝑛, 𝑒)2. Representa el mensaje como un entero 𝑚
en el intervalo [0, 𝑛-1]3. Calcula 𝑐 = 𝑚𝑒 mod 𝑛.4. Envía el texto cifrado 𝑐 a A.
A descifra el mensaje de B
1. Usa su clave privada para recuperar
𝑚 = 𝑐𝑑 mod 𝑛.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: ¿POR QUÉ FUNCIONA EL DESCIFRADO?
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: DESCIFRADO CON EL TCR
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: SEGURIDAD
En 1977 Ron Rivest profetizó que factorizar
un número de 125 dígitos llevaría 40.000
billones de años.
El desafío RSA-129 (129 dígitos, 425 bits):
◦ 1143816257578888676692357799761466120102182967212423
6256256184293570693524573389783059712356395870505898
9075147599290 026879543541
= 34905295108476509491478496199038
98133417764638493387843990820577 *
32769132993266709549961988190834
461413177642967992942539798288533
◦ Resuelto en abril de 1994 por un equipo dirigido por D.
Atkins, M. Graff, A. Lenstra y P. Leyland usando 600
ordenadores conectados a través de Internet.
◦ http://www.math.okstate.edu/~wrightd/numthry/rsa129.html
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: SEGURIDAD
Con el siguiente escenario:
◦ Capacidad de cálculo (mips por año):
◦ La potencia de cálculo se multiplica por 10 cada 5 año y
las Matemáticas avanzan cada año.
Tamaños recomendados de claves:
Particular (P) Gran empresa (E) Gobierno (G)
10.000 10.000.000 1.000.000.000
Año Contra P Contra E Contra G
1995 768 1280 1536
2000 1024 1280 1536
2005 1280 1536 2048
2010 1280 1536 2048
2015 1536 2048 4096
2045 8192 16384 32768
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: NECESIDAD DE RELLENO
1. Algunos valores del mensaje pueden dar
cifrados inseguros:
◦ Los valores m=0 y m=1 siempre se cifran en sí mismos.
◦ Con exponentes pequeños y valores pequeños de m, el
cifrado podría ser estrictamente menor que el módulo y el
texto en claro podría obtenerse haciendo la raíz e-ésima,
sin tener en cuenta el módulo.
2. Siempre hay mensajes que se cifran en sí
mismos (al menos 9). De hecho su número
exacto es :
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: NECESIDAD DE RELLENO
3. RSA es determinista, por lo que es viable un ataque de texto elegido: el atacante construye un diccionario de textos probables y sus cifrados. Interceptando un texto cifrado, el atacante puede usar este diccionario para descifrar el mensaje.
Protección: combinar RSA con algún esquema de relleno (como por ejemplo estándares como PKCS).
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: ATAQUE DE PRIMOS CERCANOS
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: FACTORIZACIÓN DE FERMAT
Mersenne propuso a Fermat el problema de decidir si era primo el número 2027651281
Fermat contestó rápidamente:
2027651281 = 44021· 46061
El método:
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: MÚLTIPLES CLAVES QUE DESCIFRAN
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: MÚLTIPLES CLAVES QUE DESCIFRAN
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: ELECCIÓN DE CLAVES
Algunos criterios para una buena clave:
Existen algoritmos para generar buenas claves
y pruebas para validar su calidad.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: ELECCIÓN DE CLAVES
Error: elegir un mismo módulo n y distribuir
distintos pares (𝘦, 𝘥) a los usuarios de la
organización.
◦ Por lo delicado de la buena elección del módulo, es un error
bastante frecuente.
◦ El problema es que el conocimiento de un simple par (𝘦, 𝘥)puede revelar la factorización de n y romper todo el
sistema.
Debe evitarse el uso repetido de un pequeño
exponente de cifrado.
◦ Por ejemplo, un mensaje enviado a 3 destinatarios que han
elegido e=3, es muy probable que pueda ser descifrado
usando el TCR.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
ELGAMAL
En 1985, Taher Elgamal publicó un artículo
titulado ‘A Public key Cryptosystem and A
Signature Scheme based on discrete Logarithms’.
طاهر الجمل
Taher Elgamal
Propone un novedoso sistema de
cifrado de clave pública basado en el
problema del logaritmo discreto.
El criptosistema de Elgamal ha
demostrado ser muy flexible y algunos
de los sistemas más modernos se
inspiran en él.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
ELGAMAL: UN PARÉNTESIS MATEMÁTICO
El problema del logaritmo discreto
◦ Un grupo (𝐺, ·) de 𝑛 elementos es cíclico si existe
un 𝑔 ∊ 𝐺 (generador) tal que 𝐺 = {1, 𝑔, 𝑔²,⋯ , 𝑔𝑛⁻¹}.Entonces para todo 𝑎 ∊ 𝐺 existe un entero 𝑘 con
0≤ 𝑘 ≤ 𝑛―1 tal que 𝑔𝑘 = 𝑎. Se dice que 𝑘 es el
logaritmo discreto de 𝑎 de base 𝑔.
◦ El problema del logaritmo discreto consiste en
hallar 𝑘 conocidos 𝐺, 𝑔 y 𝑎.
◦ En grupos finitos grandes (p. e. en el grupo
multiplicativo de ℤ𝑝 con 𝑝 un primo fuerte), este
problema es computacionalmente intratable.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
ELGAMAL: UN PARÉNTESIS MATEMÁTICO
Búsqueda de un generadorCriptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
ELGAMAL: GENERACIÓN DE CLAVES
Cada usuario crea su clave pública y
la correspondiente clave privada:
1. Construye un primo grande 𝑝 y un generador
del grupo multiplicativo de ℤ𝑝.
2. Elige aleatoriamente un entero 𝑎, 1 ≤ 𝑎 ≤ 𝑝 - 2y calcula 𝛽 = 𝑔𝑎 mod 𝑝.
3. La clave pública es (𝑝, 𝑔, 𝛽). La clave privada es
𝑎.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
ELGAMAL: CIFRADO Y DESCIFRADO
B cifra un mensaje para A
1. Obtiene la clave pública de A (𝑝, 𝑔, 𝛽) .2. Representa el mensaje como un entero 𝑚
en el intervalo [0, 𝑝―1].3. Elige al azar un entero 𝑘, 1 ≤ 𝑘 ≤ 𝑝 – 2.
4. Calcula 𝛾 = 𝑔𝑘 mod 𝑝 y 𝛿 = 𝑚 · 𝛽 𝑘 mod 𝑝.5. Envía el texto cifrado 𝑐 = (𝛾, 𝛿) a A.
A descifra el mensaje de B
1. Usa su clave privada para recuperar
𝑚 = 𝛾𝑝 – 1 – a · 𝛿 mod 𝑝.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
ELGAMAL: ¿POR QUÉ FUNCIONA EL DESCIFRADO?
Por el Teorema de Fermat, se tiene que
en ℤ𝑝
Y entonces:
Con lo que
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
ELGAMAL: EFICIENCIA
El proceso de descifrado hace sólo una potencia,
pero el de cifrado requiere dos, de exponente 𝘬,
que pueden hacerse más rápidas eligiendo
adecuadamente el exponente.
Una desventaja es que el mensaje cifrado es el
doble de largo que el original.
Una gran ventaja es que al elegirse 𝘬 de forma
aleatoria, el cifrado de un mismo texto dará
resultados diferentes, aunque esto es
transparente para el descifrado.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
ELGAMAL: SEGURIDAD
La seguridad de Elgamal se basa en la dificultad
de resolver un problema de logaritmo discreto.
Resulta crítico que se usen diferentes enteros
aleatorios 𝑘 para cada mensaje. Si se usara el
mismo 𝑘 para 𝑚₁ y 𝑚₂, dando lugar a los cifrados
(𝛾₁, 𝛿₁) y (𝛾₂, 𝛿₂), entonces 𝛿₁/ 𝛿₂= 𝑚₁ / 𝑚₂ y
el conocimiento de uno de los mensajes revelaría
el otro.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: CRIPTOGRAFÍA DE CURVAS ELÍPTICAS
No se trata de un nuevo criptosistema, sino de un nuevo enfoque.
Se trata de usar funciones de un solo sentido en un contexto nuevo, usando una aritmética que hace los problemas más difíciles.
Las curvas elípticas han sido muy estudiadas desdehace más de150 años. Su uso en Criptografía fuepropuesto en 1985 independientemente por Neal Koblitz (Univ. de Washington) y Victor Miller (IBM, Yorktown Heights).
Una curva elíptica es una curva en el plano tal que cada línea que la corta en 2 puntos, la corta además exactamente en un tercer punto.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: UN POCO DE MATEMÁTICAS
Una curva elíptica sobre ℝ está formada por el
conjunto de los puntos (𝑥, 𝑦) tales que satisfacen
una ecuación de la forma 𝑦²= 𝑥³ + 𝑎𝑥 + 𝑏 con 𝑎, 𝑏números reales cumpliendo 4𝑎³+27𝑏²≠0.
Cada elección de 𝑎 y 𝑏 da lugar a
una curva diferente.
En http://www.certicom.com/
content/live/resources/ecc_tutori
al/ecc_javaCurve.html se pueden
experimentar las curvas
resultantes para distintos valores.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: UN POCO DE MATEMÁTICAS
Una curva elíptica sobre un cuerpo finito está
formada por un conjunto finito de puntos.
• Hay simetría
horizontal .
• Nótese que tiene 31puntos.
• El número de puntos
de la curva no es
siempre primo, por
lo que se elige un
subgrupo cíclico
suficientemente
grande.
Curva elíptica 𝑦² = 𝑥³ + 𝑥 +10 sobre 𝔽₂₃
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: UN POCO DE MATEMÁTICAS
Aritmética geométrica:
◦ El opuesto (negativo) de un punto 𝑃= (𝑥, 𝑦) es su simétrico
respecto al eje 𝑥 : ‒𝑃= (𝑥, ‒𝑦).
◦ Para sumar dos puntos 𝑃, 𝘘 (con 𝑃≠‒𝘘 ) se traza una línea
que los une, que corta a la curva en otro punto 𝘙; entonces
𝑃+𝘘 = ‒𝘙.
Para sumar 𝑃 y ―𝑃 lo anterior no
funciona ya que la línea que los
une no corta a la curva en otro
punto. Para evitar este problema
se añade un punto del infinito que
se designa por 𝒪, y por definición
se dice que 𝑃+(‒𝑃)=𝒪 (y por
tanto 𝑃 + 𝒪 = 𝑃).
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: UN POCO DE MATEMÁTICAS
Aritmética geométrica:
◦ Para sumar 𝑃 consigo mismo se traza la tangente en 𝑃, que
corta a la curva en otro punto ‒ 𝘙; entonces 2𝑃 = 𝑃 + 𝑃 = 𝘙
Caso especial:
Si 𝑃= (𝑥, 0) entonces
la tangente es vertical
y no corta de nuevo a
la curva. Entonces se
establece que 2𝑃 = 𝒪
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: UN POCO DE MATEMÁTICAS
Aritmética algebraica:
Haciendo que todo funcione:
◦ http://www.certicom.com/content/live/resources/ecc_tutorial
/ecc_javaCurve.html
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: UN POCO DE MATEMÁTICAS
Curvas elípticas sobre cuerpos finitos:
◦ En Criptografía los cálculos deben ser exactos, por lo que se
usan curvas elípticas sobre cuerpos finitos, que contendrán
un número finito (aunque muy grande) de puntos.
◦ Algunos cuerpos finitos bien conocidos: F=ℤ𝘱 con 𝘱 primo
(usados en RSA, Elgamal, …)
◦ Otros: cuerpos finitos F𝘱𝘮 con 𝘱 primo. Los elementos del
cuerpo se representan como polinomios.
◦ Ejemplos interactivos con curvas elípticas en cuerpos finitos:
http://www.certicom.com/content/live/resources/ecc_tutorial/ecc
_twopoints.html
http://www.certicom.com/content/live/resources/ecc_tutorial/ecc
_ecfm24.html
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: UN POCO DE MATEMÁTICAS
El problema del logaritmo discreto en curvas elípticas:
◦ Dados dos puntos 𝑃 y 𝘘 en el grupo (aditivo) de la curva, encontrar un entero 𝘬 tal que 𝘬𝑃=𝘘
◦ Ejemplo: en la curva elíptica definida sobre F₂₃ por la ecuación 𝘺²=𝘹³+9𝘹+17, hallar el logaritmo discreto 𝘬 de 𝘘=(4, 5) de base 𝑃=(16,5)
Mediante fuerza bruta:
Así el logaritmo discreto de 𝘘 en base 𝑃 es 𝑘=9.
◦ En un caso real, 𝑘 será muy grande y este ataque serácomputacionalmente imposible.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: ELGAMAL ELÍPTICO
Cada usuario construye su clave pública y la
correspondiente privada:
◦ Elige un primo 𝑝 y una curva elíptica sobre ℤ𝑝
𝑦²= 𝑥³ + 𝑎𝑥 + 𝑏 con 4𝑎³+27𝑏² ≢ 0 (mod 𝑝).
◦ Elige un punto 𝐺 de la curva que sea de orden
primo (el orden es el primer entero 𝑞 tal que
𝑞𝐺 = 𝒪) y de tamaño similar a 𝑝.
◦ Se elige un entero 𝑑∊ [0, 𝑞―1] y se hace 𝘉 = 𝑑𝘎.
◦ La clave pública es (𝑎, 𝑏, 𝑞, 𝘎, 𝘉).
◦ La clave privada es 𝑑.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: ELGAMAL ELÍPTICO
B cifra un mensaje para A
1. Obtiene la clave pública de A (𝑎, 𝑏, 𝑞, 𝘎, 𝘉).2. Representa el mensaje como un punto 𝑀 en la
curva.3. Elige al azar un entero 𝑘, 1 ≤ 𝑘 ≤ 𝑞 – 2.
4. Calcula 𝛤 = 𝑘𝐺 y 𝛥 = 𝑀 + 𝑘𝘉.5. Envía a A el texto cifrado 𝑐 = (𝛤, 𝛥).
A descifra el mensaje de B
1. Usa su clave privada para calcular:
𝛥 – 𝑑𝛤 = 𝑀 + 𝑘𝘉 – 𝑑𝑘𝐺 = 𝑀 + 𝑘𝑑𝐺– 𝑑𝑘𝐺 = 𝑀
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: ELGAMAL ELÍPTICO
Dos problemas en Elgamal elíptico:
1. ¿Cómo representar un mensaje que es una
cadena de bits como un punto de la curva?
Una propuesta: se convierte el mensaje en un
número 𝑥 y se toma un punto 𝑀 = (𝑥 , ±𝑦) de la
curva. El signo de 𝑦 no importa, pero el problema es
que puede que no exista tal punto.
Hay otras opciones, pero ninguna natural.
2. Puede ser vulnerable a ataques de texto
cifrado elegido.
El Gamal elíptico no es un estándar.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: ALGUNOS ESTÁNDARES
Estándar P1363 de la IEEE de criptografía de clave pública: Standard Specifications For Public-Key Cryptography.
http://grouper.ieee.org/groups/1363/
14.2 - Grupo de evaluación criptográfica Europeo NESSIE: New European Schemes for Signature, Integrity and Encryption.
http://www.cryptonessie.org/
14.3 - Grupo de evaluación criptográfica Japonés CRYPTREC: Cryptography Research and Evaluation Committee
http://www.ipa.go.jp/security/enc/CRYPTREC/index-e.html
14.4 - Estándar SECG: The Standards for Efficient CryptographyGroup (SECG)
http://www.secg.org/
14.5 - Estándar NIST: The NIST Computer Security Division
http://csrc.nist.gov/
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: ALGUNOS ESTÁNDARES
El criptosistema basado en curvas elípticas más
ampliamente respaldado es el llamado Integrated
Encryption Scheme (IES).
IES ha sido aprobado como estándar por distintas
entidades: ANS X9F1, CRYPTREC, IEEE P1363,
NESSIE, NSA Suite B.
Puede verse con más detalle en
◦ http://en.wikipedia.org/wiki/Integrated_Encryption
_Scheme
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: SEGURIDAD
Certicom es la principal empresa comercial de CCE, esta organización posee 130 patentes, y ha vendido licencias a NSA por 25 millones de dólares.
También ha patrocinado varios desafíos a algoritmos CCE. El más complejo resuelto hasta ahora, con clave de 109 bits, fue roto por un equipo de investigadores a principios de 2003. usando un ataque masivo en paralelo basado en el ataque de cumpleaños, con más de 10.000 PC's de tipo Pentium funcionando continuamente durante 540 días.
Se estima que la longitud de clave mínima recomendada para CCE (163 bits) requeriría 108
veces los recursos utilizados para resolver el problema con 109 bits.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: SEGURIDAD
Ataque basado en la paradoja del cumpleaños
¿De qué tamaño debe ser un grupo de
personas elegidas al azar para que la
probabilidad de tener al menos dos con el
mismo cumpleaños sea mayor del 50%?
¡Sólo 23!
Idea básica: las colisiones (valores repetidos) aparecen antes
de lo esperado; por ejemplo: si un banco autentica sus
transacciones bancarias con 64 bits, el número de
autenticaciones será 2⁶´≅ 18 trillones.
En un ataque de cumpleaños un atacante en realidad sólo
necesita ver 2³²≅ 4000 millones de transacciones.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: SEGURIDAD
Tamaños estimados de claves en los distintos problemas estudiados para obtener una seguridad equivalente:
Un tamaño pequeño implica una mejor gestión de las claves, más velocidad, menor tamaño del cifrado y menos necesidad de memoria.
PLD (bits) RSA (bits) PLDE (bits) Ratio
1024 1024 163 1:6
3072 3072 256 1:12
7680 7680 384 1:20
15360 15360 512 1:30
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CCE: CONCLUSIONES
Las buenas implementaciones de CCE son muy seguras: no se les conoce ningún ataque subexponential que haya tenido éxito.
Más atractivos que los anteriores porque requieren claves mucho más cortas para el mismo nivel de seguridad.
Más rápidos que los anteriores.
Menores requerimientos de memoria que los anteriores.
Ideales para dispositivos portátiles como PDAs, smartcards, móviles, etc.
Algunos ejemplos de protocolos que usan CCE:
◦ EC Digital Signature Algorithm (ECDSA).
◦ Intercambio de llaves EC Diffie-Hellman (ECDH).
Sólo un problema: ¡es aún nuevo!
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas