WEBVTT 00:00:00.000 --> 00:00:03.827 En el ultimo segmento, explicamos que es un sistema de encriptación de clave pública. Y 00:00:03.827 --> 00:00:07.557 definimos que significa ser seguro para un sistema de encriptación de clave pública. Si 00:00:07.557 --> 00:00:11.142 recordamos, necesitabamos seguridad ante atacantes activos. Y en particular, 00:00:11.142 --> 00:00:15.211 definimos nuestro objetivo: la seguridad de texto cifrado elegido. Esta semana, vamos a construir dos 00:00:15.211 --> 00:00:19.281 familias de sistemas de encriptación de clave pública que son seguros para ataques de texto cifrado elegido. Y en 00:00:19.281 --> 00:00:22.914 este segmento, vamos a comenzar por contruir claves de encriptacion públicas a partir 00:00:23.059 --> 00:00:27.124 de una construcción llamada la permutación trampa (o puerta falsa). Entonces vamos a comenzar por definir un 00:00:27.124 --> 00:00:31.064 concepto general llamado funcion trampa. Entonces, ¿qué es una funcion trampa? 00:00:31.064 --> 00:00:35.484 Bueno, una función trampa básicamente es una función que va de un grupo X a un 00:00:35.484 --> 00:00:39.585 grupo Y. Y esta realmente definido por un triplete de algoritmos. Hay un algoritmo de generación, 00:00:39.585 --> 00:00:43.685 la función f, y la inversa de la función f. Entonces el algoritmo 00:00:43.685 --> 00:00:47.892 de generación, básicamente lo que hace cuando lo ejecutas, es generar un par de claves, una 00:00:47.892 --> 00:00:52.098 clave pública y una clave secreta. La clave pública va a definir una función específica 00:00:52.098 --> 00:00:56.869 del conjunto X al conjunto Y. Y luego la clave secreta va a definir la función 00:00:56.869 --> 00:01:01.639 inversa ahora del conjunto Y al conjunto X. Entonces la idea es de que puedas evaluar 00:01:01.639 --> 00:01:06.588 la función en cualquier punto usando un EPK público y luego puedas invertir la función 00:01:06.588 --> 00:01:12.443 usando la clave secreta, SK. Entonces, ¿a qué me refiero con inversión? Precisamente, si 00:01:12.443 --> 00:01:17.255 miramos cualquier par de clave pública y clave secreta generados por el algoritmo de generación de claves 00:01:17.255 --> 00:01:21.727 G, entonces ocurre que si evalúo la función en el punto X, y a continuación 00:01:21.727 --> 00:01:26.142 evalúo la inversa en el punto resultante, debería obtener el punto original X 00:01:26.142 --> 00:01:30.670 de vuelta. Asi que la imagen que deberíais tener en mente es esta, hay un conjunto X grande, y 00:01:30.670 --> 00:01:35.857 un conjunto Y grande, y luego, esta función mapea cualquier punto de X a un punto de Y 00:01:35.857 --> 00:01:41.508 y esto puede ser hecho usando la clave pública. Así que de nuevo, cualquier punto de X puede ser mapeado a 00:01:41.508 --> 00:01:46.897 un punto de Y. Luego, si alguien tiene la clave secreta, básicamente puede ir en 00:01:46.897 --> 00:01:53.758 la dirección inversa, aplicando esta clave secreta. Así que ahora que 00:01:53.758 --> 00:01:58.289 entendemos lo que es una función trampa, vamos a definir que significa que una función 00:01:58.289 --> 00:02:02.652 trampa es segura. Y asi, diremos que este triplete G F Finversa, es seguro 00:02:02.652 --> 00:02:06.903 si de hecho esta función FPK es lo que se llama una funcíón de camino único. Y permitidme explicar 00:02:06.903 --> 00:02:10.986 lo que es una función de camino único. La idea es básicamente que 00:02:10.986 --> 00:02:15.516 la función puede ser evaluada en cualquier punto, pero invertirla es difícil sin la clave 00:02:15.516 --> 00:02:19.639 secreta SK. Vamos a definirlo mas precisamente. Como es habitual lo definimos usando un 00:02:19.639 --> 00:02:23.764 juego. Aquí tenemos nuestro juego entre el retador y el adversario. Y el juego 00:02:23.764 --> 00:02:27.496 funciona com sigue. Básicamente el retador generará una clave pública y 00:02:27.496 --> 00:02:31.622 una clave secreta. A continuación generará un valor aleatorio X, enviará la clave pública 00:02:31.622 --> 00:02:36.116 al adversario, y evaluará la función en el punto X y 00:02:36.116 --> 00:02:40.160 enviará el resultado Y al adversario. Asi que todo lo que el adversario observa es 00:02:40.160 --> 00:02:44.653 una clave pública, que define lo que la función es, y a continuación 00:02:44.653 --> 00:02:49.483 observa la imagen de esta función en el punto aleatorio X, y su objetivo es básicamente invertir 00:02:49.483 --> 00:02:54.097 la función en este punto Y. OK así que él produce un X primo. Y dijimos que la 00:02:54.097 --> 00:02:58.507 función trampa es segura si la probabilidad de que el adversario invierta 00:02:58.507 --> 00:03:03.143 la función en el punto dado 'y', es negligible. En otras palabras, dado 'y', la probabilidad de que 00:03:03.143 --> 00:03:07.271 el adversario sea capaz de alterar la pre imagen de 'y' es de hecho una probabilidad 00:03:07.271 --> 00:03:11.907 negligible y si esto es válido para todos los algoritmos eficientes, decimos que esta 00:03:11.907 --> 00:03:17.882 función trampa es segura. De nuevo, abstractamente, es un concepto realmente 00:03:17.882 --> 00:03:21.885 interesante, en que podemos evaluar la función en dirección directa muy 00:03:21.885 --> 00:03:26.150 fácilmente. Pero nadie puede evaluar la función en dirección inversa si no 00:03:26.150 --> 00:03:30.311 tiene la función trampa, la clave secreta SK, que entonces, de repente les permite 00:03:30.311 --> 00:03:35.424 invertir la función muy, muy fácilmente. Asi, usando el concepto de una función trampa, 00:03:35.424 --> 00:03:39.552 no es muy difícil construir un sistema de encriptación público, y permitidme mostrar como 00:03:39.552 --> 00:03:43.528 hacerlo. Aquí tenemos nuestra función trampa, G, F y F inversa. La otra 00:03:43.528 --> 00:03:47.605 herramienta que vamos a necesitar, es un esquema simétrico de encriptación, y voy a 00:03:47.605 --> 00:03:51.531 asumir que el esquema de encriptación es de hecho seguro ante ataques activos, en 00:03:51.531 --> 00:03:55.350 particular necesito disponer de encriptación autenticada. Observad que el 00:03:55.350 --> 00:04:00.726 sistema de encriptación simétrica toma claves de K y la función trampa toma datos de X. 00:04:00.726 --> 00:04:05.790 Estos son dos conjuntos distintos, y vamos a necesitar también una función hash 00:04:05.790 --> 00:04:09.937 que vá de X a K. En otras palabras, mapea elementos del conjunto X a claves para 00:04:09.937 --> 00:04:14.033 los sistemas de encriptación simétricos. Y ahora, que tenemos estos 3 componentes, podemos 00:04:14.033 --> 00:04:17.821 de hecho construir el sistema de encriptación público del modo siguiente: el generador de 00:04:17.821 --> 00:04:21.764 claves para el sistema de encriptación público es básicamente exactamente el mismo 00:04:21.764 --> 00:04:25.655 que la generación de claves para las funciones trampa. Asi que ejecutamos g para la función 00:04:25.655 --> 00:04:29.956 trampa, obtenemos una clave pública y una clave secreta. Y estas van a ser las claves 00:04:29.956 --> 00:04:34.171 pública y secreta para el sistema de encriptación público. Ahora, ¿como encriptamos?, bien, empecemos 00:04:34.171 --> 00:04:38.978 con la encriptación. El algoritmo de encriptación toma una clave pública y un mensaje 00:04:38.978 --> 00:04:43.898 como entrada. Así que lo que hará es generar un x aleatorio del conjunto X mayúscula. 00:04:43.898 --> 00:04:48.545 Aplicará la función trampa a este x aleatorio para obtener y. 00:04:48.545 --> 00:04:53.130 y es la imagen de x bajo la función trampa. Entonces, continuará y 00:04:53.130 --> 00:04:58.272 generará una clave simétrica mediante el hash de x. Así esta es una clave simétrica para el sistema de clave 00:04:58.272 --> 00:05:03.290 simétrica. Y finalmente encriptará el texto M usando esta clave acabada 00:05:03.290 --> 00:05:08.123 de generar. Y entonces mostrará el valor y que acaba de calcular, que es 00:05:08.123 --> 00:05:13.260 la imagen de x, junto con la encriptación del mensaje M bajo el sistema simétrico, así 00:05:13.260 --> 00:05:18.366 es como la encriptación funciona. Y quiero destacar de nuevo, que la función trampa 00:05:18.366 --> 00:05:23.112 solo se aplica a este valor aleatorio X, mientras que el mensaje es encriptado 00:05:23.112 --> 00:05:28.098 usando un sistema de clave simétrico, y usando una clave que fué derivada del valor X que 00:05:28.098 --> 00:05:32.959 elegimos aleatoriamente. Así, ahora que entendemos la encriptación, veamos como desencriptar. 00:05:32.959 --> 00:05:37.366 Bien, el algoritmo de desencriptación toma una clave secreta como entrada, y el texto cifrado. 00:05:37.366 --> 00:05:41.551 El texto cifrado contiene 2 componentes, el valor Y y el valor C 00:05:41.551 --> 00:05:46.070 Así, el primer paso que vamos a dar, va a ser aplicar la transformación inversa, 00:05:46.070 --> 00:05:50.366 la función trampa inversa para el valor 'y', y esto nos dará de 00:05:50.366 --> 00:05:54.495 el valor original 'x' que elegimos durante la encriptación. Permitidme que pregunte, ¿Como derivamos 00:05:54.495 --> 00:06:00.042 la clave de desencriptación simetrica K a partir de este 'x' que acabamos de obtener? Bueno, 00:06:00.042 --> 00:06:04.736 esto es una pregunta fácil. Básicamente calculamos el hash de 'x' de nuevo. Esto nos dá K igual que 00:06:04.736 --> 00:06:09.372 durante el encriptado. Y ahora que tenemos la clave de encriptación simétrica, podemos aplicar el 00:06:09.372 --> 00:06:13.783 algoritmo de desencriptación simétrico para desencriptar el texto cifrado 'c'. Obtenemos el 00:06:13.783 --> 00:06:17.741 mensaje original 'm' y este es nuestro resultado. Así es como el sistema de encriptación 00:06:17.741 --> 00:06:22.321 público funciona, cuando la función trampa es usada solo para encriptar 00:06:22.321 --> 00:06:26.788 un valor aleatorio 'x', mientras que el mensaje real 'm' es encriptado usando 00:06:26.788 --> 00:06:31.244 el sistema simétrico. Aquí en los dibujos, tenemos el mensaje 'm', obviamente el texto plano 00:06:31.244 --> 00:06:35.545 podría ser bastante grande. Aquí tenemos el cuerpo del texto descifrado que 00:06:35.545 --> 00:06:39.953 puede ser bastante largo, es de hecho encriptado usando el sistema simétrico. Y de nuevo, 00:06:39.953 --> 00:06:44.039 remarco que la clave para el sistema simétrico es simplemente el valor hash de 'x'. 00:06:44.039 --> 00:06:48.232 Y entonces, el encabezado de el texto cifrado es simplemente la aplicación de la función 00:06:48.232 --> 00:06:52.641 trampa a este 'x' aleatorio que escogimos. Así que durante la desencriptación, lo que ocurre es 00:06:52.641 --> 00:06:56.888 que primero desencriptamos el encabezado para obtener 'x', y a continuación desencriptamos el cuerpo usando 00:06:56.888 --> 00:07:01.829 el sistema simétrico para obterer finalmente el texto plano original 'm'. Como es habitual cuando muestro 00:07:01.829 --> 00:07:06.542 un sistema como este, obviamente quereis verificar que la desencriptación es de hecho 00:07:06.542 --> 00:07:10.605 la inversa de la encriptación. Y mas importante, quereis preguntar por qué este sistema 00:07:10.605 --> 00:07:14.963 es seguro. Y de hecho, hay un bonito teorema de seguridad aquí que dice, que sí 00:07:14.963 --> 00:07:18.900 la función trampa con la que empezamos es segura, en otras palabras que es una función 00:07:18.900 --> 00:07:22.634 de camino único si el adversario no tiene la clave secreta. El sistema de 00:07:22.634 --> 00:07:26.621 encriptación simétrica, proporciona encriptación autenticada, y la función hash es un 00:07:26.621 --> 00:07:30.558 oráculo aleatorio, lo que simplemente significa que es una función aleatoria del conjunto X a 00:07:30.558 --> 00:07:34.696 el conjunto de claves K. Así, un oráculo aleatorio es un tipo de idealización de lo que se 00:07:34.696 --> 00:07:38.280 debería ser una función hash. En la práctica, por supuesto, cuando vais a implementar un 00:07:38.280 --> 00:07:42.317 sistema como este, usaríais SHA256, o alguno de los 00:07:42.317 --> 00:07:47.252 otros sistemas explicados en clase. Así que bajo estas 3 condiciones 00:07:47.252 --> 00:07:51.863 de hecho, el sistema que acabamos de describir es seguro ante textos cifrados escogidos, así que es seguro 00:07:51.863 --> 00:07:56.416 ante CCA, la 'ro' denota el hecho que la seguridad esta fijada en lo que llamamos 00:07:56.416 --> 00:08:00.572 un oráculo aleatorio (ro). Pero esto es un detalle que tampoco es muy importante para nuestra 00:08:00.572 --> 00:08:05.012 explicación. Lo que quiero que recordeis es que si la función trampa 00:08:05.012 --> 00:08:09.000 es una función segura, el sistema simétrico de encriptación es seguro 00:08:09.000 --> 00:08:13.017 contra manipulación, de modo que proporciona encriptación autenticada, y H 00:08:13.017 --> 00:08:17.468 es en cierto modo una buena función hash, una función aleatoria que en práctica 00:08:17.468 --> 00:08:22.245 usariamos SHA256, entonces, de hecho, el sistema que acabamos de mostrar es seguro ante CCA 00:08:22.245 --> 00:08:27.615 texto cifrado escogido. Debería deciros que de hecho hay un estandar 00:08:27.615 --> 00:08:31.752 ISO que define este modo de encriptación. ISO 00:08:31.752 --> 00:08:35.781 son las siglas de Internationa Standards Organization. Así que este 00:08:35.781 --> 00:08:40.456 sistema particular ha sido estandarizado, y es una buena cosa usarlo. Me referiré 00:08:40.456 --> 00:08:44.947 a este como encriptación ISO en los próximos segmentos. PAra concluir este segmento, quiero 00:08:44.947 --> 00:08:48.925 advertiros sobre un modo incorrecto de usar una función trampa para construir 00:08:48.925 --> 00:08:53.328 un sistema de encriptación de clave pública. Y de hecho, este método puede ser el primero 00:08:53.328 --> 00:08:57.572 que viene a la mente, y es completamente inseguro. Permitidme mostraros, como no 00:08:57.572 --> 00:09:01.762 encriptar usando una función trampa. Bueno, la primera cosa que podría venir a la mente es, 00:09:01.762 --> 00:09:05.696 bien, aplicar la función trampa directamente al mensaje 'm'. Así que 00:09:05.696 --> 00:09:10.047 encriptamos aplicando simplemente la función al mensaje 'm', y desencriptamos simplemente 00:09:10.047 --> 00:09:14.180 aplicando f inversa al texto cifrado 'c' para recuperar el mensaje original 'm'. Funcionalmente, 00:09:14.180 --> 00:09:18.639 de hecho, desencriptar es la inversa de encriptar, y esto es 00:09:18.639 --> 00:09:22.881 completamente inseguro por muchas, muchas razones. El modo más fácil de ver que 00:09:22.881 --> 00:09:26.960 es inseguro, es que simplemente, esto es encriptación deterministica. 00:09:26.960 --> 00:09:30.944 Podeis advertir que no se está usando ninguna aleatoriedad. Cuando encriptamos un mensaje 'm' 00:09:30.944 --> 00:09:34.154 y ya que es deterministico, no puede ser 00:09:34.154 --> 00:09:37.948 semanticamente seguro. Pero de hecho, tal como dije, cuando instanciamos esta función trampa 00:09:37.948 --> 00:09:41.644 con implementaciones particulares, por ejemplo con la función trampa RSA 00:09:41.644 --> 00:09:44.951 hay muchos, muchos ataques que son posibles con esta 00:09:44.951 --> 00:09:48.794 construcción particular, y por tanto no debeis usarla nunca, nunca, jamás, y voy a repetirlo 00:09:48.794 --> 00:09:52.830 durante todo este módulo, y dehecho en el próximo segmento voy a mostraros 00:09:52.830 --> 00:09:56.699 un número de ataques sobre esta implementación particular. OK, lo que me gustaría que 00:09:56.699 --> 00:10:00.717 recordarais es que deberíais usar un sistema de encriptación, como el estandar ISO, 00:10:00.717 --> 00:10:04.992 y nunca deberíais aplicar la función trampa directamente al mensaje 'm' 00:10:04.992 --> 00:10:09.010 Aunque en el próximo segmento veremos otros modos de encriptar usando una función 00:10:09.010 --> 00:10:13.233 trampa que son también correctos, pero este método particular es muy claramente 00:10:13.233 --> 00:10:17.560 incorrecto. OK. Ahora que entendemos como construir encriptación de clave pública 00:10:17.560 --> 00:10:21.423 a partir de una función trampa, la pregunta siguiente es como construir funciones 00:10:21.423 --> 00:10:24.360 trampa, y vamos a ver esto en el próximo segmento.