Este artículo es un anexo para explicar los detalles matemáticos de la criptografía de clave pública. También te recomiendo que leas el artículo principal: La computación cuántica no matará a la criptografía.
Diffie-Hellman ??
En 1978 Whitfield Diffie y Martin Hellman encontraron una forma segura para que Alice y Bob se pusieran de acuerdo sobre una clave secreta. Funciona de esta manera:
- Alice y Bob están de acuerdo (sin necesidad de hacerlo por un canal seguro) en un gran primo p y un número base, también conocido como generador g < p.
- Alice crea su par de claves eligiendo un número al azar a < p y calculando
A se convierte en la llave pública de Alice. a se convierte en la llave privada de Alice.
Ten en cuenta que todas las operaciones se hacen mod p. Esto significa «módulo p”. La operación de módulo da como resultado el resto de dividir un número por otro. Por ejemplo,
- 7 mod 7= 0 (7 divide a 7 sin resto)
- 8 mod 7 = 1 (8 dividido por 7 tiene un resto de 1)
- 9 mod 7 = 2 (9 dividido por 7 tiene un resto de 2)
Utilizas la operación de módulo cuando conviertes las horas en formato de 24h a formato de pm: 20:00 =20 mod 12 =8pm
- Bob crea su par de claves eligiendo algún número al azar b < p y calculando
B se convierte en la llave pública de Bob. b se convierte en la llave privada de Bob.
- Alice envía públicamente A a Bob y Bob envía B a Alice.
- Alice calcula su secreto compartido como
Bob calcula su secreto compartido como
Desde
y
tenemos que
Desde aquí pueden derivar con seguridad una llave secreta de S.
¿Por qué es esto seguro? ?
Eve sólo conoce A y B, pero para encontrar S necesitaría calcular a o b. Sin embargo, cualquiera (incluyendo Alice y Bob) necesitaría ejecutar una operación de logaritmo discreto para obtener cualquier clave privada que no sea la suya, porque
El cálculo del logaritmo discreto es un problema difícil cuando los números involucrados son grandes.
Diffie-Hellman es un protocolo de acuerdo clave basado en el problema del logaritmo discreto.
RSA ?
Basándose en la idea de la clave pública, Ron Rivest, Adi Shamir y Len Adleman fueron capaces de encontrar un mecanismo que permitiera tanto la encriptación como la firma, como se explicó anteriormente. Es así:
Creación de claves ?
- Alicia crea un par de claves eligiendo dos grandes primos p, q y los multiplica para obtener el módulo RSA, n.
- Alicia elige al azar un número d < (p-1)(q-1), que es relativamente primo con (p-1)(q-1), es decir: el único factor común entre d y (p-1)(q-1) es 1.
- Calcula e como el inverso del módulo d (p-1)(q-1). Entonces, tenemos que
Esto hace que
(Puedes encontrar una demostración en el Capítulo VI del documento original de la RSA). Así que ? puede recuperarse de su exponencia a la potencia de ? o ? ya que
Y
- Alice publica (e,n) como su clave pública mientras conserva (d,n) como su clave privada.
Encriptación ⛓
Digamos que Bob quiere enviar un mensaje privado M a Alice mientras Eve está escuchando su canal de comunicación.
- Bob encripta la M usando la clave pública de Alice (e,n) para obtener un cifrado C
- Bob envía la C a Alice
- Alice descifra la C exponiéndola al poder de su clave privada, d
Firma ?
Digamos que Alice quiere firmar un mensaje M.
- Alice encripta M usando su clave privada para obtener un cifrado S
- Alice envía (M,S) a Bob. Ella podría encriptarlo antes de usar la clave pública de Bob si quisiera que la conversación se mantuviera en privado, pero nos saltaremos eso.
- Bob descifra la S usando la clave pública de Alice para obtener la M’.
- Bob verifica que M’=M. Esa encriptación sólo pudo ser hecha por Alice usando su clave privada.
Alguien podría argumentar que no hay necesidad de que Alice proporcione M ya que lo que sea M’ puede ser aceptado como un cifrado preparado por Alice si es algo que tiene sentido.
Sin embargo, me estoy saltando aquí algunos detalles… Toda esta matemática es compleja y consume tiempo de procesador. Además, encriptar mensajes más grandes que n requiere algún tipo de división de texto claro. En la práctica, lo que Alice encripta es un hash de su mensaje y lo que Bob verifica es que el hash desencriptado es igual al hash del texto claro proporcionado por Alice.
No quería introducir el hash en la explicación para simplificar el proceso al máximo. Si sabes lo que es un hash, probablemente te hagas una idea. De lo contrario, piense en un hash como una huella dactilar de tamaño fijo de un mensaje.
¿Por qué es esto seguro? ?
A Eve o a cualquiera que escuche la conversación le costaría mucho trabajo conseguir el exponente secreto d de Alice. Su mejor opción es calcular d a partir de (e,n), pero la única forma fácil de hacerlo es con
Así que el problema es factorizar ? para obtener ? y ?. Recuerda que ? = ??.
Como se ha explicado antes, esto también es un problema difícil cuando los números son grandes.
RSA es un criptosistema de clave pública basado en el problema del factoraje.
Curva elíptica ➰
La criptografía de curva elíptica proporciona métodos de cifrado y firma basados en el problema del logaritmo discreto en campos finitos definidos por una curva elíptica, típicamente de 256 bits de longitud.
Un criptosistema de firma de curva elíptica de 256 bits proporciona aproximadamente el mismo nivel de seguridad que el RSA4096 y es mucho más rápido para firmar y aproximadamente igual de rápido para la verificación de la firma.
La curva elíptica se usa muy frecuentemente para firmar, ya que es mucho más eficiente que el RSA. Se utiliza, por ejemplo, en Bitcoin y Ethereum.
Las matemáticas detalladas de la criptografía de curva elíptica están fuera del alcance de este artículo. Sólo recuerda que esto se basa en el problema del logaritmo discreto y, por lo tanto, puede ser atacado usando el algoritmo de Shor.
El algoritmo de Shor ?
La idea principal del algoritmo de Shor es que los campos de números discretos usados para RSA y los criptosistemas basados en registros discretos tienen un comportamiento periódico. Así que, si puedes encontrar el período asociado con la clave que estás tratando de descifrar, puedes fácilmente (y clásicamente) calcular la clave.
Calcular los períodos de las funciones periódicas es una forma diferente de decir calcular las frecuencias asociadas a una señal. Y tenemos las herramientas matemáticas para hacerlo: La transformación de Fourier (FT). Puedes pensar en la transformación de Fourier como si fuera la pantalla de un ecualizador de sonido, mostrando gráficos de barras que indican las frecuencias que nuestro sistema de sonido está reproduciendo.
El cálculo de los períodos asociados a una gran clave criptográfica también es una tarea compleja, pero tenemos un eficiente algoritmo cuántico para hacerlo: La Transformada Cuántica de Fourier (QFT).
La versión de factorización ?
Entonces, asumamos que tenemos una computadora cuántica que puede ejecutar el QFT por nosotros. Sólo la parte de QFT requiere un ordenador cuántico. El resto se puede hacer de forma clásica.
Queremos factorizar un gran módulo RSA:
Elija un número arbitrario a<N
Ejecute QFT para obtener el período ω de
Si obtienes un número impar para ω, elige otra a, ya que tendrás que calcular ω/2 más tarde.
Debido a que ω es el período de f(x), sabemos que
Por lo tanto,
Ahora, recuerda que el mod N significa el recordatorio después de dividir por N. Esto significa que
Ahora podemos obtener lo anterior como factor de dos términos:
Esto significa que:
son múltiplos de los factores de k o N. Por lo tanto, obtengamos el mayor divisor común entre uno de ellos. El cálculo del GCD de los grandes números es una tarea que puede ser ejecutada eficientemente en computadoras clásicas usando el algoritmo de Euclides.
Después de calcular el GCD se puede obtener la solución (uno de los factores primos de N) o una no solución (trivial (1 o N) o se puede haber elegido un factor de k).
Las posibilidades de quedar atrapado en un problema (ω o no solución) mientras se ejecuta el algoritmo son del 37,5%. Por lo tanto, es posible que tengas que ejecutarlo un pequeño número de veces antes de obtener la solución, pero deberías obtener una solución fácilmente.
Versión del logaritmo discreto ?
Como antes, asumamos que tenemos una computadora cuántica que puede ejecutar el QFT por nosotros. Sólo la parte de QFT requiere un ordenador cuántico. El resto se puede hacer de forma clásica.
Antes de entrar, necesitaremos ayuda de Euler:
Por lo tanto, p es primo, porque todos los números más pequeños que p, {1,2,…,p-1}, son coprimeros con p.
El teorema de Euler establece que para que a y n sean coprimeros:
En otras palabras:
Ahora, recuerden los componentes de Diffie-Hellman, que usaremos en este ejemplo:
- Y es la llave pública,
- g es el generador y es conocido,
- x es la llave privada que intentaremos recuperar,
- p es el número primo usado para definir Z*p y es conocido.
Estamos listos para ir con Shor.
Ejecuta QFT para obtener los puntos ω y ω´de:
Por lo que
Eso significa que
Por lo que
Vamos a reemplazar Y considerando que:
Entonces quedaría:
Ahora, acordaros de la teoría de Euler:
Por lo que,
Y finalmente
Así que, una vez que tengas los dos periodos de
sólo necesitas una división para recuperar la clave privada ?.
¡Sigue leyendo! Aquí puedes seguir con el anexo II: detalles sobre computación cuántica.
Jaime Gómez García
Universia
Architecture and IT & Telecom Infrastructure expert. I learn about the Internet, networks and applied cryptography every day since the mid 90’s.
