En el ultimo segmento, explicamos que es un sistema de encriptación de clave pública. Y definimos que significa ser seguro para un sistema de encriptación de clave pública. Si recordamos, necesitabamos seguridad ante atacantes activos. Y en particular, definimos nuestro objetivo: la seguridad de texto cifrado elegido. Esta semana, vamos a construir dos familias de sistemas de encriptación de clave pública que son seguros para ataques de texto cifrado elegido. Y en este segmento, vamos a comenzar por contruir claves de encriptacion públicas a partir de una construcción llamada la permutación trampa (o puerta falsa). Entonces vamos a comenzar por definir un concepto general llamado funcion trampa. Entonces, ¿qué es una funcion trampa? Bueno, una función trampa básicamente es una función que va de un grupo X a un grupo Y. Y esta realmente definido por un triplete de algoritmos. Hay un algoritmo de generación, la función f, y la inversa de la función f. Entonces el algoritmo de generación, básicamente lo que hace cuando lo ejecutas, es generar un par de claves, una clave pública y una clave secreta. La clave pública va a definir una función específica del conjunto X al conjunto Y. Y luego la clave secreta va a definir la función inversa ahora del conjunto Y al conjunto X. Entonces la idea es de que puedas evaluar la función en cualquier punto usando un EPK público y luego puedas invertir la función usando la clave secreta, SK. Entonces, ¿a qué me refiero con inversión? Precisamente, si miramos cualquier par de clave pública y clave secreta generados por el algoritmo de generación de claves G, entonces ocurre que si evalúo la función en el punto X, y a continuación evalúo la inversa en el punto resultante, debería obtener el punto original X de vuelta. Asi que la imagen que deberíais tener en mente es esta, hay un conjunto X grande, y un conjunto Y grande, y luego, esta función mapea cualquier punto de X a un punto de Y y esto puede ser hecho usando la clave pública. Así que de nuevo, cualquier punto de X puede ser mapeado a un punto de Y. Luego, si alguien tiene la clave secreta, básicamente puede ir en la dirección inversa, aplicando esta clave secreta. Así que ahora que entendemos lo que es una función trampa, vamos a definir que significa que una función trampa es segura. Y asi, diremos que este triplete G F Finversa, es seguro si de hecho esta función FPK es lo que se llama una funcíón de camino único. Y permitidme explicar lo que es una función de camino único. La idea es básicamente que la función puede ser evaluada en cualquier punto, pero invertirla es difícil sin la clave secreta SK. Vamos a definirlo mas precisamente. Como es habitual lo definimos usando un juego. Aquí tenemos nuestro juego entre el retador y el adversario. Y el juego funciona com sigue. Básicamente el retador generará una clave pública y una clave secreta. A continuación generará un valor aleatorio X, enviará la clave pública al adversario, y evaluará la función en el punto X y enviará el resultado Y al adversario. Asi que todo lo que el adversario observa es una clave pública, que define lo que la función es, y a continuación observa la imagen de esta función en el punto aleatorio X, y su objetivo es básicamente invertir la función en este punto Y. OK así que él produce un X primo. Y dijimos que la función trampa es segura si la probabilidad de que el adversario invierta la función en el punto dado 'y', es negligible. En otras palabras, dado 'y', la probabilidad de que el adversario sea capaz de alterar la pre imagen de 'y' es de hecho una probabilidad negligible y si esto es válido para todos los algoritmos eficientes, decimos que esta función trampa es segura. De nuevo, abstractamente, es un concepto realmente interesante, en que podemos evaluar la función en dirección directa muy fácilmente. Pero nadie puede evaluar la función en dirección inversa si no tiene la función trampa, la clave secreta SK, que entonces, de repente les permite invertir la función muy, muy fácilmente. Asi, usando el concepto de una función trampa, no es muy difícil construir un sistema de encriptación público, y permitidme mostrar como hacerlo. Aquí tenemos nuestra función trampa, G, F y F inversa. La otra herramienta que vamos a necesitar, es un esquema simétrico de encriptación, y voy a asumir que el esquema de encriptación es de hecho seguro ante ataques activos, en particular necesito disponer de encriptación autenticada. Observad que el sistema de encriptación simétrica toma claves de K y la función trampa toma datos de X. Estos son dos conjuntos distintos, y vamos a necesitar también una función hash que vá de X a K. En otras palabras, mapea elementos del conjunto X a claves para los sistemas de encriptación simétricos. Y ahora, que tenemos estos 3 componentes, podemos de hecho construir el sistema de encriptación público del modo siguiente: el generador de claves para el sistema de encriptación público es básicamente exactamente el mismo que la generación de claves para las funciones trampa. Asi que ejecutamos g para la función trampa, obtenemos una clave pública y una clave secreta. Y estas van a ser las claves pública y secreta para el sistema de encriptación público. Ahora, ¿como encriptamos?, bien, empecemos con la encriptación. El algoritmo de encriptación toma una clave pública y un mensaje como entrada. Así que lo que hará es generar un x aleatorio del conjunto X mayúscula. Aplicará la función trampa a este x aleatorio para obtener y. y es la imagen de x bajo la función trampa. Entonces, continuará y generará una clave simétrica mediante el hash de x. Así esta es una clave simétrica para el sistema de clave simétrica. Y finalmente encriptará el texto M usando esta clave acabada de generar. Y entonces mostrará el valor y que acaba de calcular, que es la imagen de x, junto con la encriptación del mensaje M bajo el sistema simétrico, así es como la encriptación funciona. Y quiero destacar de nuevo, que la función trampa solo se aplica a este valor aleatorio X, mientras que el mensaje es encriptado usando un sistema de clave simétrico, y usando una clave que fué derivada del valor X que elegimos aleatoriamente. Así, ahora que entendemos la encriptación, veamos como desencriptar. Bien, el algoritmo de desencriptación toma una clave secreta como entrada, y el texto cifrado. El texto cifrado contiene 2 componentes, el valor Y y el valor C Así, el primer paso que vamos a dar, va a ser aplicar la transformación inversa, la función trampa inversa para el valor 'y', y esto nos dará de el valor original 'x' que elegimos durante la encriptación. Permitidme que pregunte, ¿Como derivamos la clave de desencriptación simetrica K a partir de este 'x' que acabamos de obtener? Bueno, esto es una pregunta fácil. Básicamente calculamos el hash de 'x' de nuevo. Esto nos dá K igual que durante el encriptado. Y ahora que tenemos la clave de encriptación simétrica, podemos aplicar el algoritmo de desencriptación simétrico para desencriptar el texto cifrado 'c'. Obtenemos el mensaje original 'm' y este es nuestro resultado. Así es como el sistema de encriptación público funciona, cuando la función trampa es usada solo para encriptar un valor aleatorio 'x', mientras que el mensaje real 'm' es encriptado usando el sistema simétrico. Aquí en los dibujos, tenemos el mensaje 'm', obviamente el texto plano podría ser bastante grande. Aquí tenemos el cuerpo del texto descifrado que puede ser bastante largo, es de hecho encriptado usando el sistema simétrico. Y de nuevo, remarco que la clave para el sistema simétrico es simplemente el valor hash de 'x'. Y entonces, el encabezado de el texto cifrado es simplemente la aplicación de la función trampa a este 'x' aleatorio que escogimos. Así que durante la desencriptación, lo que ocurre es que primero desencriptamos el encabezado para obtener 'x', y a continuación desencriptamos el cuerpo usando el sistema simétrico para obterer finalmente el texto plano original 'm'. Como es habitual cuando muestro un sistema como este, obviamente quereis verificar que la desencriptación es de hecho la inversa de la encriptación. Y mas importante, quereis preguntar por qué este sistema es seguro. Y de hecho, hay un bonito teorema de seguridad aquí que dice, que sí la función trampa con la que empezamos es segura, en otras palabras que es una función de camino único si el adversario no tiene la clave secreta. El sistema de encriptación simétrica, proporciona encriptación autenticada, y la función hash es un oráculo aleatorio, lo que simplemente significa que es una función aleatoria del conjunto X a el conjunto de claves K. Así, un oráculo aleatorio es un tipo de idealización de lo que se debería ser una función hash. En la práctica, por supuesto, cuando vais a implementar un sistema como este, usaríais SHA256, o alguno de los otros sistemas explicados en clase. Así que bajo estas 3 condiciones de hecho, el sistema que acabamos de describir es seguro ante textos cifrados escogidos, así que es seguro ante CCA, la 'ro' denota el hecho que la seguridad esta fijada en lo que llamamos un oráculo aleatorio (ro). Pero esto es un detalle que tampoco es muy importante para nuestra explicación. Lo que quiero que recordeis es que si la función trampa es una función segura, el sistema simétrico de encriptación es seguro contra manipulación, de modo que proporciona encriptación autenticada, y H es en cierto modo una buena función hash, una función aleatoria que en práctica usariamos SHA256, entonces, de hecho, el sistema que acabamos de mostrar es seguro ante CCA texto cifrado escogido. Debería deciros que de hecho hay un estandar ISO que define este modo de encriptación. ISO son las siglas de Internationa Standards Organization. Así que este sistema particular ha sido estandarizado, y es una buena cosa usarlo. Me referiré a este como encriptación ISO en los próximos segmentos. PAra concluir este segmento, quiero advertiros sobre un modo incorrecto de usar una función trampa para construir un sistema de encriptación de clave pública. Y de hecho, este método puede ser el primero que viene a la mente, y es completamente inseguro. Permitidme mostraros, como no encriptar usando una función trampa. Bueno, la primera cosa que podría venir a la mente es, bien, aplicar la función trampa directamente al mensaje 'm'. Así que encriptamos aplicando simplemente la función al mensaje 'm', y desencriptamos simplemente aplicando f inversa al texto cifrado 'c' para recuperar el mensaje original 'm'. Funcionalmente, de hecho, desencriptar es la inversa de encriptar, y esto es completamente inseguro por muchas, muchas razones. El modo más fácil de ver que es inseguro, es que simplemente, esto es encriptación deterministica. Podeis advertir que no se está usando ninguna aleatoriedad. Cuando encriptamos un mensaje 'm' y ya que es deterministico, no puede ser semanticamente seguro. Pero de hecho, tal como dije, cuando instanciamos esta función trampa con implementaciones particulares, por ejemplo con la función trampa RSA hay muchos, muchos ataques que son posibles con esta construcción particular, y por tanto no debeis usarla nunca, nunca, jamás, y voy a repetirlo durante todo este módulo, y dehecho en el próximo segmento voy a mostraros un número de ataques sobre esta implementación particular. OK, lo que me gustaría que recordarais es que deberíais usar un sistema de encriptación, como el estandar ISO, y nunca deberíais aplicar la función trampa directamente al mensaje 'm' Aunque en el próximo segmento veremos otros modos de encriptar usando una función trampa que son también correctos, pero este método particular es muy claramente incorrecto. OK. Ahora que entendemos como construir encriptación de clave pública a partir de una función trampa, la pregunta siguiente es como construir funciones trampa, y vamos a ver esto en el próximo segmento.