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.