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": las dos personas necesitan tener una clave en común. Fíjate que no se conocen de antes: no pueden tener un "libro de claves" como los espías del siglo XX, y solo tienen Internet para comunicarse. No pueden llamarse por teléfono para enviarse la clave.
¿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á.
Hablaremos de la teoría de la complejidad desde un punto de vista abstracto y sin entrar en detalles
Todo lo que vamos a decir tiene una enorme literatura detrás y basada en la lógica y el álgebra
Por si fuera poco, es un campo del que aún no conocemos casi nada: hay aún muchas preguntas abiertas
El nombre "teoría de la complejidad" está muy bien escogido para describir el campo. Vamos a intentar saber de qué va
Dado un conjunto de datos, existen varios algoritmos que permiten ordenadores: quick sort, bubble, merge...
¿Por qué hay varios algoritmos? Algunos son muy rápidos pero consumen más memoria, otros son muy rápidos si los datos ya están casi ordenados...
¿Existe un algoritmo que sea "el mejor de todos"?
Igual que existe una velocidad máxima de la luz... ¿existe una velocidad máxima para ordenar un array?
No dice **cuál** es el algoritmo más rápido posible, solo calcula **cuánto tiempo** le llevará resolver el problema al mejor algoritmo posible. Si nuestro algoritmo tarda más... sabemos que aún podemos mejorar
"el tiempo mínimo en resolver un problema" es para el problema general, puede haber algunos problemas que teóricamente son complejos pero que "con suerte o por las características concretas d eeste problema" se puede resolver fácilmente
A veces no interesa resolver un problema "en el menor tiempo posible", sino que utilizando "la menor cantidad de memoria posible". Aquí solo he hablado del tiempo como criterio de "mejor", pero en ocasiones se buscará optimizar el uso de "memoria"
Una manera de resolver el sudoku es simplemente probar números uno a uno hasta que se verifique el resultado. Esto es fuerza bruta. ¿Hay algoritmos mejores?
Claro que sí, podemos ser inteligentes: "si esto es un 2, entonces todas estas casillas no pueden contener un 2". **Esto es mucho más eficiente que la fuerza bruta**
¿Cuánto tiempo mínimo le lleva al algoritmo más eficiente posible? De esto va la teoría de la complejidad.
Nota: el objetivo de la teoría de la complejidad no es descubrir el algoritmo más eficiente. **Queremos saber cuánto tiempo le llevará al algoritmo más eficiente para resolver un problema incluso aunque no sepamos cuál es ese algoritmo perfectamente eficiente**. Si diseñamos un sistema de cifrado y podemos demostrar que el mejor atacante, el que use los mejores algiritmos posibles, incluso aquellos que no están aún inventados, va a tardar un tiempo descomunal para romper el sistema... entonces el cifrado es seguro.
Nota: casi siempre será posible resolver las cosas por fuerza bruta, pero a veces habrá algoritmo mejores
En AES no, en AES y en otros algoritmos simétricos sospechamos que la fuerza bruta es el mejor algoritmo posible. Eso es estupendo. Pero AES no resuelve el problema de intercambiar claves.
Para intercambiar una clave de forma segura, a los criptógrafos se les ocurrió probar unos sistemas basados en problemas que podrían tener soluciones mejores que la fuerza bruta. Y decidieron que usar esos problemas era aceptable, siempre que el mejor algoritmo necesitase un tiempo no razonable para resolverlos.
Definiremos qué significa tiempo creciente con el tamaño del problema exactamente:creciente de forma .... ¿lineal? ¿polinomial? ¿exponencial?
Adelanto: razonable significa polinomial: el tiempo necesario para resolverlo crece de forma polinomial con respecto a su tamaño
No es una pregunta trampa: tardamos pocos segundos. Mucho menos tiempo que en resolver el Sudoku
En el vídeo, Simon resuelve el Sudoku que parecía imposible en 20 gloriosos y emocionantes minutos
La teoría de la complejidad se centra en "problemas de decisión", aquellos cuya respuesta es Sí/No
- ¿Es esta solución válida para un problema?
- ¿Es esta solición óptima?
Casi todos los problemas se pueden replantear como una pregunta SI/NO.
El problema tradicional es "con 4 colores", que resulta ser el mínimo posible con cualquier mapa. Pero vamos a exigir 9 colores para poder hacer una observación interesante a continuación.
Obviamente, si 4 colores es el mínimo posible, tiene que ser posible hacerlo con 9 que son más y por tanto además será más fácil.
Los problemas NP-completos son muy interesantes: si podemos resolver uno de ellos rápidamente, de rebote podremos resolver una clase enorme de problemas a la vez.
En el enlace, solucionan un Sudoku transformándolo primero a un problema de coloreado de mapas, resolviendo el problema de coloreado de mapas y deshaciendo la transformación a un Sudoku
Esta es una discusión muy interesante para las matemáticas y que podría tener alguna implicación en criptografía, pero a niveles prácticos nos afecta poco
Vamos a ver con más detalles el problema del logaritmo discreto, porque es el que se usa en casi todos los sistemas que veremos a partir de ahora
Fijaos: se están mapeando todos los números de 1 a 17 en otros números de 1 a 17 de forma "aleatoria". Esto es un "grupo cíclico"
Eso se parece mucho a una permutación pseudoaleatoria, de las que usábamos en el cifrado de bloque
Ya tenemos los conocimientos suficientes para presentar el problema de la primera transparencia:
Simplemente recordemos cuál es el problema que queremos resolver hoy: ¿cómo conseguimos que las dos personas que no se han visto nunca tengan una clave secreta común?
Su paper de 1976 es, junto con el de Shannon (capítulo 1), uno de los más importantes en cruptografía
Recuerda: sabemos que el problema del logaritmo discreto es NP, pero no sabemos si también es P y por tanto y fácil de resolver. Sospechamos muchísimo que no es P y que el algoritmo más rápido posible tomará un tiempo exponencial con el tamaño de la clave. Pero no estamos *matemáticamente* seguros. ¿es P=NP o no? No lo sabemos.