Constructions (11 min)

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.