1 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 2 00:00:03,827 --> 00:00:07,557 definimos que significa ser seguro para un sistema de encriptación de clave pública. Si 3 00:00:07,557 --> 00:00:11,142 recordamos, necesitabamos seguridad ante atacantes activos. Y en particular, 4 00:00:11,142 --> 00:00:15,211 definimos nuestro objetivo: la seguridad de texto cifrado elegido. Esta semana, vamos a construir dos 5 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 6 00:00:19,281 --> 00:00:22,914 este segmento, vamos a comenzar por contruir claves de encriptacion públicas a partir 7 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 8 00:00:27,124 --> 00:00:31,064 concepto general llamado funcion trampa. Entonces, ¿qué es una funcion trampa? 9 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 10 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, 11 00:00:39,585 --> 00:00:43,685 la función f, y la inversa de la función f. Entonces el algoritmo 12 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 13 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 14 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 15 00:00:56,869 --> 00:01:01,639 inversa ahora del conjunto Y al conjunto X. Entonces la idea es de que puedas evaluar 16 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 17 00:01:06,588 --> 00:01:12,443 usando la clave secreta, SK. Entonces, ¿a qué me refiero con inversión? Precisamente, si 18 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 19 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 20 00:01:21,727 --> 00:01:26,142 evalúo la inversa en el punto resultante, debería obtener el punto original X 21 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 22 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 23 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 24 00:01:41,508 --> 00:01:46,897 un punto de Y. Luego, si alguien tiene la clave secreta, básicamente puede ir en 25 00:01:46,897 --> 00:01:53,758 la dirección inversa, aplicando esta clave secreta. Así que ahora que 26 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 27 00:01:58,289 --> 00:02:02,652 trampa es segura. Y asi, diremos que este triplete G F Finversa, es seguro 28 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 29 00:02:06,903 --> 00:02:10,986 lo que es una función de camino único. La idea es básicamente que 30 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 31 00:02:15,516 --> 00:02:19,639 secreta SK. Vamos a definirlo mas precisamente. Como es habitual lo definimos usando un 32 00:02:19,639 --> 00:02:23,764 juego. Aquí tenemos nuestro juego entre el retador y el adversario. Y el juego 33 00:02:23,764 --> 00:02:27,496 funciona com sigue. Básicamente el retador generará una clave pública y 34 00:02:27,496 --> 00:02:31,622 una clave secreta. A continuación generará un valor aleatorio X, enviará la clave pública 35 00:02:31,622 --> 00:02:36,116 al adversario, y evaluará la función en el punto X y 36 00:02:36,116 --> 00:02:40,160 enviará el resultado Y al adversario. Asi que todo lo que el adversario observa es 37 00:02:40,160 --> 00:02:44,653 una clave pública, que define lo que la función es, y a continuación 38 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 39 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 40 00:02:54,097 --> 00:02:58,507 función trampa es segura si la probabilidad de que el adversario invierta 41 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 42 00:03:03,143 --> 00:03:07,271 el adversario sea capaz de alterar la pre imagen de 'y' es de hecho una probabilidad 43 00:03:07,271 --> 00:03:11,907 negligible y si esto es válido para todos los algoritmos eficientes, decimos que esta 44 00:03:11,907 --> 00:03:17,882 función trampa es segura. De nuevo, abstractamente, es un concepto realmente 45 00:03:17,882 --> 00:03:21,885 interesante, en que podemos evaluar la función en dirección directa muy 46 00:03:21,885 --> 00:03:26,150 fácilmente. Pero nadie puede evaluar la función en dirección inversa si no 47 00:03:26,150 --> 00:03:30,311 tiene la función trampa, la clave secreta SK, que entonces, de repente les permite 48 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, 49 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 50 00:03:39,552 --> 00:03:43,528 hacerlo. Aquí tenemos nuestra función trampa, G, F y F inversa. La otra 51 00:03:43,528 --> 00:03:47,605 herramienta que vamos a necesitar, es un esquema simétrico de encriptación, y voy a 52 00:03:47,605 --> 00:03:51,531 asumir que el esquema de encriptación es de hecho seguro ante ataques activos, en 53 00:03:51,531 --> 00:03:55,350 particular necesito disponer de encriptación autenticada. Observad que el 54 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. 55 00:04:00,726 --> 00:04:05,790 Estos son dos conjuntos distintos, y vamos a necesitar también una función hash 56 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 57 00:04:09,937 --> 00:04:14,033 los sistemas de encriptación simétricos. Y ahora, que tenemos estos 3 componentes, podemos 58 00:04:14,033 --> 00:04:17,821 de hecho construir el sistema de encriptación público del modo siguiente: el generador de 59 00:04:17,821 --> 00:04:21,764 claves para el sistema de encriptación público es básicamente exactamente el mismo 60 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 61 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 62 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 63 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 64 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. 65 00:04:43,898 --> 00:04:48,545 Aplicará la función trampa a este x aleatorio para obtener y. 66 00:04:48,545 --> 00:04:53,130 y es la imagen de x bajo la función trampa. Entonces, continuará y 67 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 68 00:04:58,272 --> 00:05:03,290 simétrica. Y finalmente encriptará el texto M usando esta clave acabada 69 00:05:03,290 --> 00:05:08,123 de generar. Y entonces mostrará el valor y que acaba de calcular, que es 70 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í 71 00:05:13,260 --> 00:05:18,366 es como la encriptación funciona. Y quiero destacar de nuevo, que la función trampa 72 00:05:18,366 --> 00:05:23,112 solo se aplica a este valor aleatorio X, mientras que el mensaje es encriptado 73 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 74 00:05:28,098 --> 00:05:32,959 elegimos aleatoriamente. Así, ahora que entendemos la encriptación, veamos como desencriptar. 75 00:05:32,959 --> 00:05:37,366 Bien, el algoritmo de desencriptación toma una clave secreta como entrada, y el texto cifrado. 76 00:05:37,366 --> 00:05:41,551 El texto cifrado contiene 2 componentes, el valor Y y el valor C 77 00:05:41,551 --> 00:05:46,070 Así, el primer paso que vamos a dar, va a ser aplicar la transformación inversa, 78 00:05:46,070 --> 00:05:50,366 la función trampa inversa para el valor 'y', y esto nos dará de 79 00:05:50,366 --> 00:05:54,495 el valor original 'x' que elegimos durante la encriptación. Permitidme que pregunte, ¿Como derivamos 80 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, 81 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 82 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 83 00:06:09,372 --> 00:06:13,783 algoritmo de desencriptación simétrico para desencriptar el texto cifrado 'c'. Obtenemos el 84 00:06:13,783 --> 00:06:17,741 mensaje original 'm' y este es nuestro resultado. Así es como el sistema de encriptación 85 00:06:17,741 --> 00:06:22,321 público funciona, cuando la función trampa es usada solo para encriptar 86 00:06:22,321 --> 00:06:26,788 un valor aleatorio 'x', mientras que el mensaje real 'm' es encriptado usando 87 00:06:26,788 --> 00:06:31,244 el sistema simétrico. Aquí en los dibujos, tenemos el mensaje 'm', obviamente el texto plano 88 00:06:31,244 --> 00:06:35,545 podría ser bastante grande. Aquí tenemos el cuerpo del texto descifrado que 89 00:06:35,545 --> 00:06:39,953 puede ser bastante largo, es de hecho encriptado usando el sistema simétrico. Y de nuevo, 90 00:06:39,953 --> 00:06:44,039 remarco que la clave para el sistema simétrico es simplemente el valor hash de 'x'. 91 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 92 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 93 00:06:52,641 --> 00:06:56,888 que primero desencriptamos el encabezado para obtener 'x', y a continuación desencriptamos el cuerpo usando 94 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 95 00:07:01,829 --> 00:07:06,542 un sistema como este, obviamente quereis verificar que la desencriptación es de hecho 96 00:07:06,542 --> 00:07:10,605 la inversa de la encriptación. Y mas importante, quereis preguntar por qué este sistema 97 00:07:10,605 --> 00:07:14,963 es seguro. Y de hecho, hay un bonito teorema de seguridad aquí que dice, que sí 98 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 99 00:07:18,900 --> 00:07:22,634 de camino único si el adversario no tiene la clave secreta. El sistema de 100 00:07:22,634 --> 00:07:26,621 encriptación simétrica, proporciona encriptación autenticada, y la función hash es un 101 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 102 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 103 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 104 00:07:38,280 --> 00:07:42,317 sistema como este, usaríais SHA256, o alguno de los 105 00:07:42,317 --> 00:07:47,252 otros sistemas explicados en clase. Así que bajo estas 3 condiciones 106 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 107 00:07:51,863 --> 00:07:56,416 ante CCA, la 'ro' denota el hecho que la seguridad esta fijada en lo que llamamos 108 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 109 00:08:00,572 --> 00:08:05,012 explicación. Lo que quiero que recordeis es que si la función trampa 110 00:08:05,012 --> 00:08:09,000 es una función segura, el sistema simétrico de encriptación es seguro 111 00:08:09,000 --> 00:08:13,017 contra manipulación, de modo que proporciona encriptación autenticada, y H 112 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 113 00:08:17,468 --> 00:08:22,245 usariamos SHA256, entonces, de hecho, el sistema que acabamos de mostrar es seguro ante CCA 114 00:08:22,245 --> 00:08:27,615 texto cifrado escogido. Debería deciros que de hecho hay un estandar 115 00:08:27,615 --> 00:08:31,752 ISO que define este modo de encriptación. ISO 116 00:08:31,752 --> 00:08:35,781 son las siglas de Internationa Standards Organization. Así que este 117 00:08:35,781 --> 00:08:40,456 sistema particular ha sido estandarizado, y es una buena cosa usarlo. Me referiré 118 00:08:40,456 --> 00:08:44,947 a este como encriptación ISO en los próximos segmentos. PAra concluir este segmento, quiero 119 00:08:44,947 --> 00:08:48,925 advertiros sobre un modo incorrecto de usar una función trampa para construir 120 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 121 00:08:53,328 --> 00:08:57,572 que viene a la mente, y es completamente inseguro. Permitidme mostraros, como no 122 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, 123 00:09:01,762 --> 00:09:05,696 bien, aplicar la función trampa directamente al mensaje 'm'. Así que 124 00:09:05,696 --> 00:09:10,047 encriptamos aplicando simplemente la función al mensaje 'm', y desencriptamos simplemente 125 00:09:10,047 --> 00:09:14,180 aplicando f inversa al texto cifrado 'c' para recuperar el mensaje original 'm'. Funcionalmente, 126 00:09:14,180 --> 00:09:18,639 de hecho, desencriptar es la inversa de encriptar, y esto es 127 00:09:18,639 --> 00:09:22,881 completamente inseguro por muchas, muchas razones. El modo más fácil de ver que 128 00:09:22,881 --> 00:09:26,960 es inseguro, es que simplemente, esto es encriptación deterministica. 129 00:09:26,960 --> 00:09:30,944 Podeis advertir que no se está usando ninguna aleatoriedad. Cuando encriptamos un mensaje 'm' 130 00:09:30,944 --> 00:09:34,154 y ya que es deterministico, no puede ser 131 00:09:34,154 --> 00:09:37,948 semanticamente seguro. Pero de hecho, tal como dije, cuando instanciamos esta función trampa 132 00:09:37,948 --> 00:09:41,644 con implementaciones particulares, por ejemplo con la función trampa RSA 133 00:09:41,644 --> 00:09:44,951 hay muchos, muchos ataques que son posibles con esta 134 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 135 00:09:48,794 --> 00:09:52,830 durante todo este módulo, y dehecho en el próximo segmento voy a mostraros 136 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 137 00:09:56,699 --> 00:10:00,717 recordarais es que deberíais usar un sistema de encriptación, como el estandar ISO, 138 00:10:00,717 --> 00:10:04,992 y nunca deberíais aplicar la función trampa directamente al mensaje 'm' 139 00:10:04,992 --> 00:10:09,010 Aunque en el próximo segmento veremos otros modos de encriptar usando una función 140 00:10:09,010 --> 00:10:13,233 trampa que son también correctos, pero este método particular es muy claramente 141 00:10:13,233 --> 00:10:17,560 incorrecto. OK. Ahora que entendemos como construir encriptación de clave pública 142 00:10:17,560 --> 00:10:21,423 a partir de una función trampa, la pregunta siguiente es como construir funciones 143 00:10:21,423 --> 00:10:24,360 trampa, y vamos a ver esto en el próximo segmento.