Cifrado asimétrico o de clave pública

RSA y curvas elípticas

Juan Vera del Campo - juan.vera@professor.universidadviu.com

Como decíamos ayer...

center

El cifrados de flujo (ej. ChaCha) y de bloque (ej. AES) permiten enviar mensajes computacionalmente seguros. Con Diffie-Hellman, dos personas que no se han conocido nunca pueden tener una clave común.

¿Qué hay de los demás servicios de seguridad?

El protocolo de intercambio de claves Diffie-Hellman permitió por primera vez en la historia que dos personas cualquiera que no se conocían mantuviesen una conversación confidencial por medios dgitales...

...pero su artículo no se llamó "Solución al problema de intercambio de claves". Tenía un título mucho más ambicioso: Nuevas direcciones en la criptografía

¿Qué direcciones eran esas?

Foto: https://www.publicdomainpictures.net/en/view-image.php?image=363738&picture=signpost-giving-directions (CC0)

Hoy hablamos de...

  1. Criptografía asimétrica
  2. RSA
  3. Curvas elípticas
  4. Los límites de la criptografía asimétrica
  5. Conclusiones

Criptografía asimétrica

Firmado digital de contratos

New Directions in Cryptography (Whitfield Diffie y Martin Hellman, 1976) exploraba qué se necesitaba para que dos empresas pudiesen firmar un contrato mercantil:

  1. Confidencialidad, sin tener una clave secreta común
  2. Autenticación de la identidad (llamada "autencidad de usuario" en el paper original)
  3. Integridad del contrato (llamada "autenticidad del mensaje")
  4. No repudio del contrato por ninguna de las partes

Es la lista que conocemos como "los servicios básicos de seguridad" (tema 1)

El primer punto, "confidencialidad", se resolvía con los cifrados que estaban apareciendo ese mismo año (DES)...

...pero se necesitaba intercambiar primero una clave simétrica

Propuesta: protocolo de intercambio de claves

Y se dieron cuenta: se puede extender la misma idea para solucionar todo lo demás

Criptografía asimétrica o de clave pública

También conocida como criptografía de clave pública

Cada persona tiene dos claves:

  • : clave pública, todos la conocen
  • : clave secreta, nadie más la conoce

Hay una relación matemática entre ambas: no las puedes escogerlas al azar. Pero si conoces la pública, no puedes sacar la privada más que por fuerza bruta

Usos de la criptografía asimétrica

Según si usamos la clave pública o la privada para cifrar, podemos hacer dos cosas:

  • cifrar mensajes --> servicio de confidencialidad/distribución de claves
  • firmar digitalmente mensajes --> servicio de autenticación

La criptografía simétrica también nos permitía cifrar, pero no firmar

Esquema de cifrado

center

  • Todos conocen la clave de Bob, solo Bob conoce la clave
  • Cualquier puede cifrar un mensaje para Bob, solo Bob puede descifrarlo: confidencialidad

Esquema de firma electrónica

center

  • Solo Bob puede cifrar con su clave y cualquier puede descifrar con
  • Pero si pueden descifrar el mensaje, todos saben que el mensaje solo puede haberlo enviado Bob: autenticación

Trap door functions, funciones trampa

Las matemáticas de la criptografía asimétrica utilizan funciones trampa:

  • Si conoces , entonces calcular es fácil (problema P, tiempo polinomial)
  • Si conoces , entonces calcular es muy difícil (problema NP, tiempo exponencial)

No encontramos una función trampa hasta 1976

Vimos en teoría de la complejidad que los problemas NP (pero probablemente no P, no NP-Completos) son buenos candidatos para funciones trampa

La mayor parte de problemas NP solo son difíciles en el caso general. Es decir: tenemos algoritmos eficientes que funcionan casi siempre. Ejemplo: sudoku

Pero necesitamos que calcular sea muy difícil siempre

La dificultad ha sido encontrar esos problemas matemáticos que fuesen difíciles siempre

Problema del Logaritmo Discreto, revisitado

Resuelve la :

  • Eso es fácil y se puede extender a cualquier problema similar:
  • Si te dan y y te preguntan ...

Para más detalles de este problema, consulta tema 4

Resuelve la :

  • Ten en cuenta: . Puedes probar los números uno a uno
  • Solución:
  • Si no has podido resolverlo, no es porque no tengas suficientes conocimientos... es que no sabemos hacerlo rápidamente: Problema del Logaritmo Discreto (DLP)
  • ...pero calcular es rápido
  • El DLP es una trap door function
  • ...probablemente. Recuerda tema 4: no sabemos si P=NP

La dificultad está en la aritmética modular: partiendo del resultado, no es fácil saber cuántas vueltas ha dado a la rueda

Ejemplo: ¿cuánto vale x? Recuerda que

center

https://miro.medium.com/max/2400/1*YZieEVE_LsNK4i94KNnZqg.png

Problema: resuelve dado , y en la ecuación

Si probamos con , que no es primo, el problema:

Tiene todas estas soluciones (compruébalo):

Pero:

no tiene solución para ningún número entero

Problema: resuelve dado , y en la ecuación

Si el módulo es primo, la solución de siempre existe y es única, que es lo que interesa para poder cifrar y descifrar:

también tiene restricciones, aunque normalmente ó

Protocolo Diffie-Hellman, revisitado

Dos usuarios y que no se han visto nunca:

  1. Acuerdan y primos entre sí
  2. Escogen números en secreto y
  3. Se envían entre ellos:
  4. Calculan en secreto:
    • :
    • :
  5. Y usan como clave de cifrado un algoritmo simétrico

Observa: para que un atacante que solo conoce , , y (claves públicas) pueda calcular , tiene que resolver , que se supone difícil

Claves secretas y claves públicas

  • Alice y Bob acuerdan y primos entre sí por canales que no son seguros. El atacante conoce y
  • Cuando Alice y Bob se intercambian y , el canal aún no es seguro. El atacante conoce y
  • y nunca salen de los ordenadores de Alice ni Bob, nunca se intercambian. El atacante no los conoce, Bob no conoce y Alice no conoce

Dado que el atacante (o cualquiera) conoce , , y , esta información es pública

y es información privada y solo conocida por Alice y Bob, respectivamente

Paso 1 Qué sabe Alice Qué sabe Bob Qué es público
1 , , ,
2 , ,
3 ,
4

Recuerda hipótesis DDH: solo se puede calcular fácilmente si conoces o bien o bien , pero no se puede calcular fácilmente si conoces solo y

Alice y Bob, que no se habían visto nunca antes, puede utilizar como clave de un cifrado simétrico de flujo o bloque como ChaCha20 ó AES

Problemas de Diffie Hellman: Man in the middle

center

Diffie-Hellman no protege contra MitM porque no permite autenticar mensajes.Necesitamos otras tecnologías.

Usos de Diffie-Hellman

  • Acuerdo inicial de una clave que luego puede usarse para cifrar las comunicaciones usando criptografía simétrica: es la etapa inicial de HTTPS
  • Pero no permite autenticar a la otra parte
  • Tampoco permite cifrar mensajes

Nuevas direcciones

El DLP, en la versión D-H de 1976, no una solución completa: permite hacer acuerdo de claves, pero no cifrado, ni firma, ni autenticado

En pocos años aparecieron nuevas funciones basadas en las mismas ideas que D-H, pero que permitían hacerlo todo: RSA, ElGammal, DSA, Pailier...

Luego, las soluciones se refinaron con curvas elípticas: ECDH (Elliptic Curves Diffie-Hellman), ECDSA (Elliptic Curves DSA)...

Lo que no era público en 1976 es que en realidad la "non-secret encryption" ya se había descubierto antes, en 1969, por James H. Ellis, y en 1973 Clifford Cocks ya había desarrollado una trap door function completa que permitía el cifrado ...

... pero se protegió como secreto militar británico, y no se desprotegió hasta 1996

Fuente: https://en.wikipedia.org/wiki/Clifford_Cocks

Cifrado y firmado

Algoritmo Firma Cifrado Acuerdo de claves
RSA Sí Sí Una parte cifra la clave que va a usarse
ElGammal Sí Sí Una parte cifra la clave que va a usarse
DSA Sí No Una parte cifra la clave que va a usarse
D-H No No Sí, es su único uso

Técnicamente, los sistemas propuestos sirven o bien para firmar, o bien para cifrar o distribuir claves. Los algoritmos son ligeramente diferentes si se usan para firmar o para cifrar, pero no estudiaremos las diferencias

RSA

RSA

A method for obtaining digital signatures and public-key cryptosystems, Ron Rivest, Adi Shamir, Leonard Adleman, 1978

trap door function: dificultad del cálculo de la raíz -ésima() para valores de con ciertas propiedades

Background: https://hsto.org/getpro/habr/post_images/453/10e/602/45310e602d784a489301bf1996edef68.jpg

El problema RSA (RSAP)

Calcula :

Pista: es producto de dos primos que no conoces

Es decir, dado , y , calcula :

para recuperar (descifrar) el mensaje original a partir de hace falta invertir:

Si no es primo el cálculo de

Es computacionalmente difícil para valores de con factores desconocidos

Hemos cifrado un mensaje pero no hay manera de descifrar el resultado ... sin conocer "la trampa" (trap function)

La "trampa" usa el teorema de Euler: si los factores de son conocidos, entonces:

es la función indicatriz de Euler, "totient function", la trap door function de RSA

El mensaje se puede descifrar fácil si conoces

se puede calcular fácil si conoces los factores primos de . Es decir, si puedes factorizar

No conocemos ningún algoritmo eficiente para factorizar un número. Este es el problema computacionalmente difícil de RSA

Teniendo en cuenta eso, para calcular a partir de , tomando un atajo dando la vuelta "por el otro lado", exponenciando suficientemente para llegar otra vez hasta :

Hace falta encontrar una tal que:

Es decir, tiene que ser el inverso de en el anillo cíclico

solo existe si y no tienen factores en común (son coprimos)

¿Cuál es el inverso de un número en un anillo? El que multiplicado por el número da . Ejemplo: es el inverso de en los números reales:

¿Qué pasa con los enteros? Que no tienen inverso dentro de los propios enteros: no hay ningún entero que multiplicado por dé .

Cuando añadimos aritmética modular a los enteros, sí que pueden haber inversos:

3 es el inverso de 7 en el anillo cíclico , 9 es inverso de sí mismo en el anillo cíclico

6 no tiene inverso en el anillo cíclico . Esto es porque 6 y 10 tienen factores comunes (no son coprimos)

Existen algoritmos eficientes para calcular el inverso de un número en un anillo cíclico . Es decir, el cálculo de dado y es posible y eficiente

El protocolo RSA: generación de par de claves

  1. Escoge dos números , primos
  2. Calcula: . Su número de bits es el tamaño de clave
  3. Calcula:
    • Protocolo original:
    • Versión moderna:
  4. Escoge al azar que sea coprimo de (sin factores en común)
  5. Calcula:
  6. Claves:
  7. Se descartan , ,

El protocolo: cifrado y descifrado

Cifrado: Para enviar un mensaje a Alice, obtengo su clave pública y calculo:

Descifrado: Alice utiliza su clave privada

Ejemplo (lo veremos con ejercicios)

Claves:

    • (tamaño de clave: 9 bits)
  • (escogido al azar, pero y coprimo con él)
  • (calculado con algoritmo de Euler)

Cifrado:

Descifrado:

Velocidad de proceso

Para crear el par de claves hay que buscar:

  • números muy grandes que sean primos (y otras condiciones): y
  • número muy grande que sea coprimo de
  • inversos de un número entero:

Es decir: la elección de un par de claves es un proceso muy lento. Segundos, minutos, horas si las claves son grandes

A cambio: el cifrado y descifrado son relativamente rápidos comparados con otros sistemas de cifrado asimétrico

En cualquier caso, es muy lento comparado con cualquier proceso de cifrado simétrico

Tamaño de claves

Hemos visto que tanto Diffie-Hellman como RSA necesitan números primos

Los números primos están muy separados entre sí: el número de primos menores que es

Ejemplo: hay números primos menores de

"Son pocos primos"

Por eso: la criptografía basada en estas funciones necesita claves mucho más largas que la criptografía simétrica

Fuente: https://en.wikipedia.org/wiki/Prime_number_theorem
Gráfico: https://en.wikipedia.org/wiki/Ulam_spiral

Simétrica (bits) RSA (bits) D-H (, )
80 1024 1024, 160
128 3072 3072, 224
192 7680 7680, 384
256 15360 15360, 512

Es decir: para intercambiar una clave AES-256 aprovechando todos sus bits, necesitamos claves RSA de 15360 bits

Si usamos tamaños de clave RSA de 4096 bits (tamaño típico), podremos intercambiar una clave simétrica equivalente a AES-128

¿Podemos encontrar trap door functions que no estén basadas en primos, y por tanto necesiten claves más cortas?

Curvas elípticas

Propuestas como trap door function en 1987 por Neal Koblitz y Victor S. Miller de forma independiente

Necesitan claves más cortas que la criptografía asimétrica basadas en DLP o RSAP para ofrecer una seguridad equivalente

  • Ventaja: necesitan menos proceso y memoria, se pueden implementar en máquinas pequeñas: móviles, tarjetas inteligentes...
  • Problema: teoría matemática compleja

Curva elíptica

Curva plana en un cuerpo finito que consiste en los puntos que satisfacen la ecuación:

Los cuerpos finitos son estructuras mátemáticas creadas con polinomios y aritmética modular

Ejemplo:

(por ahora simplificamos la explicación representando la curva los reales, sin módulos)

center

Trap door function

Dado un punto , definimos una operación "proyección" como:

es "la proyección de recta que une y , reflejada al otro lado de la curva"

center

Usamos el símbolo "suma" por tradición, pero no es una "suma geométrica"

Y lo volvemos a aplicar, varias veces, desde el mismo origen

center

En vez de empezar con dos puntos, podemos empezar con uno solo, y la recta inicial es la tangente a la cura. El resto sigue igual

center

Fuente: https://medium.com/@icostan/animated-elliptic-curves-cryptography-122fff8fcae

Esta es la trap door function:

Es la aplicación de veces la proyección sobre el punto

Dado y ... ¿cuánto vale ?

Eso es el problema difícil de las curvas elípticas:

No sabemos calcular a partir de y

Mapeando la curva en un campo finito

En realidad en criptografía no trabajamos sobre los reales, sino que mapeamos en un grupo finito de los enteros.

Es decir, con aritmética modular de un numero primo muy grande. El número de bits de este entero es "el tamaño de la clave"

Ejemplo número primo grande de 256 bits:

Ejemplos de mapeado en campos finitos: https://graui.de/code/elliptic2/

Ejemplo (es solo un ejemplo, el primo tiene que ser mucho más grande):

Fuente: https://www.youtube.com/watch?v=mFVKuFZ29Fc&list=PLN9KZDpNfsHMd7d7PX87JGesGY_Qzyb3V

Ejemplo de proyección sobre los enteros

center

Tamaño de clave

La gran ventaja de las curvas elípticas en criptografía (EEC) es que nos permiten utilizar criptografía asimétrica con una clave mucho más pequeña

Simétrica RSA D-H (, ) EEC
80 1024 1024, 160 160
128 3072 3072, 224 256
192 7680 7680, 384 384
256 15360 15360, 512 512

Es decir, pone la criptografía asimétrica al alcance de pequeños dispositivos

center

NOTA: RSA está basado en "factorización", DSA y D-H en "logaritmo discreto"

https://www.keylength.com/en/compare/

Elección de la curva

No se suele escoger "cualquier curva elíptica", sino alguna de las ya existentes. Cada una tiene propiedades ligeramente diferentes, algunas están patentadas y otras provocan dudas (parte de las revelaciones de Snowden, 2013)

La Curve25519, propuesta por Daniel J. Bernstein en 2005, se considera segura:

sobre el cuerpo de los enteros creado por el primo

Tiene un tamaño de clave de 256 bits, equivalente a 128 bits en clave simétrica

Aceptada por varios estándares

Elliptic Curve Diffie-Hellman: ECDH

Protocolo:

  1. Alice y Bob escogen una curva elíptica y un punto inicial
  2. Alice escoge en secreto y Bob escoge en secreto
  3. Se envían:
    • Alice a Bob:
    • Bob a Alice:
  4. Escogen como secreto

Nota que un atacante no podría calcular a partir de ó : Tiene que calcular o bien o bien , y eso es difícil

Elliptic Curve DSA: ECDSA

DSA es un algoritmo de firmado digital clásico, basado en ElGammal (1985). Es similar a RSA pero basado en el problema del logaritmo discreto

Ha sido estándar FIPS hasta hace poco, pero probablemente será retirado en el futuro próximo

Existe una adaptación de DSA a curvas elípticas: ECDSA, que es la implementación que probablemente se estandarizará: FIPS 186-5 (2019, aún borrador)

¿Y RSA?

El protocolo RSA no se ha adaptado a criptografía de curva elíptica

Pero RSA ha sido y aún es el sistema más utilizado para certificados digitales, y hay millones de estos certificados activos

(es decir, aún hay millones de claves RSA públicas en uso)

La situación quizá cambie en el futuro

Los límites de la criptografía asimétrica

Limitaciones

  • Los esquemas descritos no cifran bytes, sino números: tenemos que ser capaces de codificar nuestro mensaje en un número entero. No ciframos "hola", sino el número "0x686f6c61"

  • Los mensajes que se pueden cifrar con criptografía asimétrica son muy cortos, de tamaño similar al tamaño de la clave

  • En RSA, el número "5" siempre se cifrará igual (¡compruébalo!). Eso es mala idea: quizá el enemigo no sepa qué estamos cifrando, pero sabe que es lo mismo que antes. Otros cifrados asimétricos como DSA son naturalmente probabilísticos, no hace falta añadirlo como un extra

  • Todos ellos son muchísimo más lentos que la criptografía simétrica para cifrar. Tanto, que no se usan par cifrar, solo para distribuir claves o hformar digitalmente

En realidad suele usarse un cifrado mixto: con asimétrica se cifra la clave simétrica que es la que realmente se usa para cifrar

PKCS#1

PKCS#1 (RFC8017): recomendaciones para utilizar correctamente RSA, y es obligatorio que las librerías que uses las implementen. Por ejemplo:

  • Añade random padding al inicio de un mensaje, de forma que dos mensajes iguales se cifren de forma diferente cada vez... pero se descifren igual
  • Diferencias de implementación de RSA en esquemas de cifrado y firmado
  • Cómo hacer correctamente la conversión entre mensajes (cadenas de bytes) y enteros (que es lo que cifra RSA)

Computación cuántica

  • La computación cuántica no rompe la criptografía simétrica AES, ChaCha... aunque sí que exige que se usen claves el doble de largas: mínimo 256 bits para AES
  • La computación cuántica impedirá utilizar todos los algoritmos asimétricos actuales: RSA, DSA, D-H... y también sus versiones con curvas elípticas
  • Ya existen algoritmos nuevos para los sistemas actuales resistentes a una hipotética computación cuántica. Tema dedicado: Criptografía post-cuántica

https://cso.computerworld.es/cibercrimen/la-amenaza-cuantica-la-computacion-cuantica-y-la-criptografia
https://www.ccn.cni.es/index.php/es/docman/documentos-publicos/boletines-pytec/495-ccn-tec-009-recomendaciones-transicion-postcuantica-segura/file

Conclusiones

Resumen

  • Criptografía asimétrica: cada persona tiene dos claves, una para cifrar y otra para descifrar. Una de esas claves es pública (es decir, cualquiera puede conocer la clave pública de otra persona) y la otra es secreta
  • No se utiliza para cifrar mensajes: es muchísimo más lenta que el cifrado simétrico
  • Se utiliza para:
    • intercambiar claves simétricas
    • firmado digital
    • identidad digital
  • Ejemplos clásicos: RSA, DSA, D-H. Basados en el problema de la factorización de números primos y logaritmo discreto. Los ejemplos clásicos necesitan tamaños de clave grandes y eso dificulta su implementación
  • Basar la seguridad en curvas elípticas (EC) permite claves mucho más pequeñas
  • Ejemplos modernos: ECDH, ECDSA, que son adaptaciones de D-H y DSA sobre curvas elípticas

Referencias

Las curvas elípticas son un concepto complejo. Esto son algunas propuestas explicativas:

Ejercicios:

Continúa en: Funciones de Hash y Blockchains

¡Gracias!

Parecería que con lo que conocemos ya hemos resuelto el problema de comunicar dos personas de forma secreta Pero en realidad tenemos un "elefante en la habitación": ¿cómo se intercambian una clave de forma segura dos personas que no han hablado nunca antes, ni tienen otra forma de comunicació que Internet? Este es el problema de intercambio de clave. No fue resuelto hasta 1976 con una serie de conceptos completamente nuevos: cada persona tiene dos claves, una pública conocida por todo el mundo y otra privada y secreta. El algoritmo inventado en 1976 se llama Diffie-Hellman, y aún lo estamos utilizando. Antes de empezar necesitaremos un poco de teoría de complejidad. Vamos allá.

Atención: este tema es matemáticamente denso, pero no es necesario seguir todos los detalles. Si tienes interés en los detalles, por favor, consulta los papers y libros especilizados. Los objetivos del tema es conocer la base de la criptografía asimétrica, cómo funciona y cómo se usa.

Fíjate que no estoy diciendo que la pública se use para cifrar y la privada para descifrar o viceversa Normalmente, si cifras con una puedes descifrar con la otra. Y según la que uses puedes cifrar o firmar documentos, como veremos a continuación

Veremos que la criptografía asimétrica usa el cifrado principalmente para distribuir claves, pero el cifrado real de un mensaje se sigue haciendo con criptografía simétrica

Recuerda que en realidad no sabemos si el DLP es difícil: solo lo sospechamos muy fuertemente

Fundaron la empresa RSA Security LLC, que sigue siendo uno de los mayores proveedores de seguridad del mundo - Hablamos de Ron Rivest en el tema 3, creador de RC4 - Adi Shamir hizo más aportaciones fundamentales a la criptografía - Leonard Adleman ha seguido investigando en teoría de la complejidad

Fíjate: necesitamos alguna manera de convertir mensajes a números. Lo verás en los ejercicios

Nota: podemos intercambiar claves AES-256 con un D-H de 1024 bits. Solo que, de forma efectiva, solo estaremos escogiendo 80 bits de la clave AES-256. Es decir, sería equivalente a un (no existente) AES-80

Observa: la curva sobre los reales se mapea en un toroide, con la marca de "números enteros", limitados por aritmética modular. Las intersecciones son los puntos de la gráfica 2D de al lado

A cambio, son más complejas de entender y programar pero eso como usuarios no es algo que importe

Bernstein es el creador de Chacha20 del [tema 3](03-simetrica.html)

Veremos el cifrado mixto en las siguientes sesiones y en los ejercicios