En el segmento anterior vimos cómo construir encriptación públicamente con funciones de puerta falsa,
en este segmento vamos a construir una función de puerta falsa clásica llamada RSA.
Pero primero vamos a repasar rápidamente qué es una función de puerta falsa. Recordemos que una función
de puerta falsa está formada por tres funciones. Hay un algoritmo de generación de claves, la función
propiamente dicha y la inversa de la función. El algoritmo de generación de claves
genera una clave pública y una clave privada. Y en este caso, en esta lección, la clave pública
va a definir una función que relaciona el conjunto X consigo mismo.
Por esta razón llamo a estos objetos permutaciones de puerta falsa, en oposición a funciones de puerta falsa,
simplemente porque la función relaciona X consigo mismo, mientras que una función de puerta falsa
podría relacionar el conjunto X con cualquier conjunto arbitrario Y. Ahora, siendo conocida la clave pública,
la función, como indicamos, básicamente define esta función del conjunto X al conjunto X.
Y, conociendo la clave secreta, podemos invertir esta función. Por tanto,
esta función F evalúa la función en la dirección directa y esta función, F inversa,
que implica la clave secreta SK, calcula F en la dirección inversa. Ahora
decimos que la permutación de puerta falsa es segura si la función definida por la clave pública
es de hecho una función unidireccional, lo que significa que es fácil de evaluar,
pero sin la puerta falsa (la clave secreta), es difícil de invertir.
Antes de que veamos nuestro primer ejemplo de permutación de puerta falsa, quisiera hacer una revisión rápida
de algunos elementos de aritmética que vamos a necesitar. Y, en particular, vamos a
repasar algunos elementos de la aritmética modular con números compuestos. Así, aquí tenemos nuestro
módulo N, que es el producto de dos números primos, y vosotros deberíais estar imaginando que
P y Q son números de aproximadamente el mismo tamaño, puesto que P y Q particulares son ambos
aproximadamente del tamaño de la raíz cuadrada de N. Por tanto, ambos son de aproximadamente el mismo tamaño.
Recordemos que denotamos ZN al conjunto de enteros de cero a N menos 1 y ya dijimos que podemos
sumar y multiplicar módulo N. Denotamos como ZN estrella el conjunto de
elementos invertibles en ZN. O sea, todos los elementos que tienen un inverso modular.
Y dijimos que, de hecho, X es invertible si y sólo si X y N son primos entre sí (coprimos).
Además, también os dije que el número de elementos invertibles en ZN estrella
se denota mediante la función fi de N. Por tanto, fi de N es el número de elementos invertibles en
ZN estrella. Y os dije que cuando N es el producto de dos números primos diferentes, entonces, de hecho,
fi de N es igual a P menos uno por Q menos uno, y si lo desarrolláis, veréis que es
realmente igual a N menos P menos Q más uno. Ahora recordad que dije que P y Q son del orden
de la raíz cuadrada de N, lo que significa que P más Q es también del orden
de la raíz cuadrada de N. Lo cual significa que realmente fi de N es del orden de
N menos dos veces la raíz cuadrada de N. Así, en otras palabras, es muy, muy próxima a N.
Básicamente, al restar la raíz cuadrada de N de un número, N, que en nuestro caso va a ser
un número enorme, de unos 600 dígitos. Y así, al restar de un número de 600
dígitos la raíz cuadrada de ese número de 600 dígitos, o sea un número de 300 dígitos,
apenas afecta al tamaño del número. Lo cual significa que fi de N es realmente, pero lo
que se dice realmente próxima a N y quiero que recordéis esto, ya que, de hecho,
lo utilizaremos una y otra vez. Y el hecho de que fi de N sea realmente próximo a N, significa que
si escogemos un elemento módulo N al azar es muy, muy probable que pertenezca a Z con estrella,
así que es muy improbable que al escoger un elemento aleatorio al final acabemos
escogiendo un elemento que no sea invertible. Bien. Por tanto recordad esto, que,
de hecho, casi todos los elementos de ZN son invertibles. Y, lo último que nos hará falta,
es el teorema de Euler, que vimos la semana pasada, que básicamente dice que
para todo elemento x en ZN con estrella, si elevo x a la potencia fi de N, obtengo 1 en ZN.
Así, en otras palabras, obtengo uno módulo N. Lo diré una vez más porque esto será
crítico para lo que viene. De nuevo, x elevado a fi de N es igual a uno módulo N.
Así, ahora que disponemos de los fundamentos necesarios, ya podemos describir la
permutación de puerta falsa RSA. Se trata de una construcción clásica, clásica, clásica en
criptografía que se publicó por primera vez en Scientific American en 1977; se trata de un
artículo muy conocido en criptografía. Y desde entonces, desde hace 35 años,
la permutación de puerta falsa RSA se ha utilizado profusamente en aplicaciones criptográficas.
Por ejemplo, SSL y TLS utilizan RSA tanto para certificados como para intercambio de claves.
Hay muchos sistemas de correo electrónico seguro y sistemas de archivos seguros que utilizan RSA para
encriptar correos electrónicos y archivos del sistema de archivos. Y hay muchas, muchas, muchas diferentes
aplicaciones de este sistema. Así, ésta es una construcción criptográfica muy, muy clásica
y voy a mostraros como funciona. Debería comentar que el nombre de RSA deriva de sus
inventores: Ron Rivest, Adi Shamir y Len Adleman, quienes estaban todos en el MIT cuando
hicieron este importante descubrimiento. Así, ahora estamos listos para describir la permutación de
puerta falsa RSA. Para ello, tengo que describir el algoritmo de generación de claves,
la función F y la función inversa de F. Así que veamos... La forma en que funciona el algoritmo de generación
de claves es la siguiente: lo que hacemos es generar dos números primos, P y Q,
cada uno de los cuales tendrá, digamos, del orden de 1000 bits, o sea, ya sabéis, unos
300 dígitos, y el módulo RSA simplemente va a ser el producto de ambos números primos.
Lo siguiente que haremos es escoger dos exponentes, e y d, tales que el producto de
e y d sea uno módulo fi de N. Lo que esto significa es que, primero,
E y D son coprimos de fi de N y, segundo, son mutuamente inversos modulares
módulo fi de N. Y entonces, generamos la clave pública como el par
N, coma, e y la clave secreta (privada), N, coma, d. Debo mencionar que el exponente e,
que al número "e" en ocasiones se le denomina exponente de encriptación y al exponente "d" en
ocasiones se le denomina exponente de desencriptado. Y veréis por qué me refiero continuamente a ellos
como exponentes en un momento. Ahora, la forma en que la función RSA se define
es realmente sencilla. Por simplicidad, voy a definirla como una función
de ZN estrella a ZN estrella. Y la forma en que se define la función es, simplemente, dado un
valor de entrada x, lo único que hacemos es elevarlo a la potencia e en ZN. Por tanto, nos limitamos a
calcular x elevado a e, módulo N. Eso es todo. Y para desencriptar, lo que hacemos es, simplemente,
dado un valor de entrada y, simplemente elevamos y a la potencia d, módulo N. Y eso es todo.
Así, ahora podéis ver por qué me refería a "e" y "d" como exponentes. Son los valores a los
que "x" e "y" se elevan. Así, vamos a verificar rápidamente que la inversa de F realmente
invierte la función F. Para eso vamos a ver qué ocurre cuando calculamos "y" elevado a "d". Así,
supongamos que "y" es el valor de la función RSA para cierto valor "x". En ese caso,
lo que es "y" elevado a "d", en realidad es RSA de x elevado a la potencia "d". RSA de x, por sí misma,
es simplemente "x" elevado a "e" módulo N. Y, por tanto, "y" elevado a "d" es simplemente "x" elevado a
"e" por "d" módulo N. De nuevo, simplemente usando las reglas de exponenciación, los exponentes se
multiplican y obtenemos "x" elevado a "e" por "d". Pero, ¿qué sabemos sobre "e" por "d"? "e" por "d" dijimos que
es uno módulo fi de N. Y lo que esto significa es que existe algún entero tal que "e" por "d" es
igual a k por fi de n más uno. Esto es lo que significa que "e" por "d" sea
uno módulo fi de N. Así, podemos simplemente reemplazar "e" por "d" con k por fi de n más uno. Y eso es
lo que escribí aquí. Así, tenemos x elevado a k por fi de n mas uno. Pero ahora, de nuevo
usando las reglas de exponenciación, podemos reescribir esto como x elevado a fi de N, elevado
a k, por x. Esto es realmente lo mismo que k por fi de N más 1 como exponente.
Me he limitado a separar el exponente en sus diferentes componentes.
Ahora, x elevado a fi de N por el teorema de Euler, sabemos que x elevado a fi de N es igual a uno. Así,
¿a qué es igual todo este producto? Bien, puesto que x elevado a fi de N es igual a uno, uno
elevado a k es también igual a uno. Por tanto, todo este término de aquí es simplemente igual a uno.
Y lo que nos queda es x. Así, lo que hemos probado es que si tomamos la salida de la
función RSA y la elevamos a "d", obtenemos de nuevo x. Lo cual significa que
al elevar a "d" básicamente se invierte la función RSA, que es lo que
queríamos mostrar. Así, eso es todo. Esta es la descripción completa de la función. Hemos
descrito la generación de la clave, la propia función que consiste simplemente en elevar
a la potencia de "e" módulo N, y la función inversa, que consiste en elevar a la
potencia de "d", también módulo N. La siguiente pregunta es ¿por qué esta función es segura?
En otras palabras, ¿por qué esta función es unidireccional si todo lo que tengo es sólo una clave pública
pero no tengo la clave privada? Y para argumentar que esta función es unidireccional,
básicamente enunciamos el supuesto RSA, que básicamente dice que la función RSA es una
permutación unidireccional. Y, formalmente, la forma en que se enuncia es que, básicamente para todo
algoritmo eficiente A, si genero dos números primos p y q,
números primos aleatorios p y q, los multiplico para obtener el módulo N y luego escojo un
valor aleatorio y en ZN estrella y proporciono el módulo, el exponente y el valor y al
algoritmo A, la probabilidad de que obtenga el inverso de RSA en el punto y, esto es,
de que obtenga "y" elevado a uno partido "e" (esto es lo que el inverso realmente es), esta
probabilidad es negligible. Así, esta suposición se denomina supuesto RSA.
Básicamente enuncia que RSA es una permutación unidireccional cuando sólo se proporciona una clave pública.
Y, consecuentemente, es una permutación de puerta falsa porque tiene una puerta falsa, y esto la hace tiene
fácil de invertir para cualquiera que conozca la puerta falsa. Así, ahora que tenemos una permutación
de puerta falsa segura, podemos simplemente combinarla con nuestra construcción de encriptación pública
y tendremos nuestro primer sistema real de encriptación pública. Y así, lo que
haremos es simplemente insertar la permutación de puerta falsa RSA en la construcción estándar
ISO que vimos en el segmento anterior. Así, si os acordáis, dicha
construcción estaba basada en un sistema de encriptación simétrica que tenía que proporcionar
encriptación autentificada. Y estaba también basada en una función hash que relaciona,
bien, transfiriéndolo al mundo RSA, relaciona elementos en
ZN con claves secretas para el sistema de clave simétrica. Y ahora, la
forma en que el esquema de encripción funciona es realmente fácil de describir. Básicamente el algoritmo G
básicamente ejecuta el algoritmo de generación de claves RSA y genera una clave pública y una
clave privada, igual que antes. Fijaos en que la clave pública contiene el exponente de
encripción y la clave privada contiene el exponente de desencriptado. Y la forma en que
encriptamos es la siguiente. Bien, vamos a escoger un valor aleatorio de "x" en ZN, vamos a
aplicar la función RSA a esta "x", vamos a reducirla a una clave simétrica generando su "hash",
así que calcularemos H de "x" para obtener la clave "k", y entonces la salida será
"y" junto a la encriptación del mensaje usando la clave simétrica "k". Y, en la
práctica, la función "hash" H se implementaría mediante SHA-256 y
utilizaríais el operador SHA-256 para generar una clave simétrica que se pudiese
utilizar en el sistema de encriptación simétrica. Así es como encriptaríamos
y la forma en que desencriptariamos es básicamente como vimos en el segmento
anterior, pero lo primero que haríamos es utilizar la clave privada para invertir
la cabecera del texto cifrado. Así, calcularíamos la inversa RSA de "y", que nos proporcionaría
el valor de "x". A continuación aplicaríamos la función "hash" a "x" para obtener
la clave k. Y entonces ejecutaríamos el algoritmo de desencriptación del sistema
simétrico sobre el texto cifrado y esto produciría el mensaje original, "m".
Y en su momento enunciamos un teorema en el segmento anterior indicando que si la permutación
de puerta falsa RSA es segura, Es y Ds, el esquema de encriptación simétrica proporciona
encriptación segura y, como dijimos, H es un oráculo aleatorio, esto es,
ya sabéis, un tipo de función aleatoria de ZN al espacio de claves. Entonces, de hecho, este
sistema presenta seguridad de texto cifrado escogido y es un buen sistema de encriptación pública a usar.
Así, ahora que tenemos nuestro primer ejemplo de un buen sistema de encriptación pública, quisiera daros un
rápido aviso sobre cómo no utilizar RSA para encriptación. Y esto es algo, de nuevo, que
ya dijimos en el segmento anterior. Y voy a repetirlo aquí, salvo que voy a
hacerlo específico para RSA. Así, me gustaría llamarlo RSA "de libro",
que es lo primero que se le ocurre a uno cuando piensa en
encriptar usando RSA, a saber, la clave secreta y la clave privada serán como antes,
pero en lugar de utilizar una función "hash" para generar una clave simétrica, lo
que haremos es usar directamente RSA para encriptar el mensaje dado, "m". Y entonces,
utilizaremos directamente un exponente de desencriptado para desencriptar el texto cifrado y
obtener el texto llano, "m". Voy a llamar a esto "RSA de libro" porque hay muchos libros que
describen la encripción RSA de este modo. Y esto es completamente erróneo.
Así no es como funciona la encripción RSA. Se trata de un sistema inseguro. En particular,
se trata de encripción determinista y, por tanto, no es posible que sea semánticamente segura y,
de hecho, existen múltiples ataques y voy a mostraros un ataque en un minuto.
Pero el mensaje que quiero que quede claro aquí es que RSA es únicamente
una permutación de puerta falsa. Por si misma no es un sistema de encriptado. Tenéis que
integrarlo en el estándar ISO, por ejemplo, para convertirlo en un sistema de encriptado.
Por si mismo, no es más que una función. Así, vamos a ver cuál es el problema si
intentáis utilizar RSA "de libro", en otras palabras, si intentáis encriptar un mensaje
utilizando RSA directamente. Y os pondré un ejemplo de ataque del mundo de la web.
Imaginad que tenéis un servidor web. El servidor web tiene una clave RSA privada. Aquí la
denotaremos como N y "d". Y tenemos un navegador web que está intentando establecer una sesión
segura, una sesión segura SSL con el servidor web. La forma en que SSL funciona es que el
navegador web empieza enviando este mensaje "CLIENT HELLO" que significa, ¡eh, quiero
establecer una sesión segura contigo! El servidor web responde con un mensaje "SERVER HELLO"
que contiene la clave pública del servidor y entonces el navegador web continuará y
generará una clave aleatoria denominada clave secreta pre-máster, encriptará la clave
secreta pre-máster usando [RSA] (N.T. el original dice "k") y enviará el resultado cifrado al servidor web.
El servidor web lo desencriptará y entonces el servidor web también tendrá "k", por lo que
ahora ambos disponen de una clave compartida que pueden usar para establecer una sesión segura entre
ellos. Lo que quiero mostraros es qué va mal si utilizamos directamente la función RSA
para encriptar "k". En otras palabras, si directamente se encripta "k" usando "k" elevado a "e"
módulo N y pongamos por caso, supongamos, que "k" es una clave de 64 bits.
Vamos a tratar "k" como un entero en el rango de 0 a dos elevado a 64.
Más exactamente, dos elevado a 64 menos uno, y ahora lo que vamos a hacer es
lo siguiente. En primer lugar, supongamos que "k" se puede factorizar en un producto de
números de tamaños aproximadamente iguales. Así, podemos escribir "k" como k1 por k2, donde k1 y k2
son enteros y ambos son, digamos, menores que dos elevado a 34. Y resulta que esto sucede con una
probabilidad del 20%, o sea, una de cada cinco veces "k" se podrá
escribir en esta forma. Pero ahora, si introducimos esta "k", "k" igual a k1 por k2, si la introducimos en la
ecuación que define el texto cifrado, podéis ver que simplemente sustituimos con k1 por k2
y entonces podemos mover k1 al otro lado, por lo que acabamos obteniendo una ecuación,
a saber, C dividido por k1 elevado a "e" es igual a k2 elevado a "d". Daros cuenta que si multiplico ambos
lados por k1 elevado a "e", obtengo que C es igual a k1 por k2 elevado a "e"
que es precisamente esta ecuación de aquí. De acuerdo, así que lo único que he hecho ha sido reemplazar "k" con
k1 por k2 y dividir por k1 elevado a "e". Esto os debería ser ya familiar.
Así que ahora tenemos dos variables en esta ecuación. Por supuesto, c es conocido por el
atacante, "e" es conocido por el atacante y N es conocido por el atacante. Las dos
variables de esta ecuación son k1 y k2 y las hemos separado en
distintos lados de la ecuación y, como resultado, podemos realizar un ataque por "encuentro en
la mitad" contra esta ecuación. Así, vamos a realizar el ataque por "encuentro en la mitad". Lo que
haríamos es construir una tabla de todos los posibles valores de la parte izquierda. Así,
todos los posibles valores de C dividido entre k1 elevado a "e", de los que hay 2 elevado a 34. Y entonces,
para todos los valores posibles de la parte derecha, esto es, para todos los posibles valores
de k2 elevado a "e", vamos a comprobar si este valor se encuentra en la tabla que hemos
construido en el paso uno. Y si esto es así, entonces habremos encontrado una colisión y, básicamente,
tenemos una solución a esta ecuación. Por tanto, tan pronto como encontremos un elemento de la forma
k2 elevado a "e" que se encuentre en la tabla que hemos construido en el paso uno, habremos solucionado esta
ecuación y encontrado k1 y k2. Y, por supuesto, una vez encontrados k1 y k2,
podemos recuperar "k" fácilmente simplemente multiplicándolos. Así, multiplicamos
k1 y k2 y obtenemos la clave secreta "k". ¿De acuerdo? Por lo tanto, hemos roto, básicamente,
este sistema de encriptación. ¿Y cuántos nos llevó? Bien, por la fuerza bruta
lo podríamos haber roto en tiempo 2 a la 64, simplemente probando todas las posibles claves. Pero
este ataque, daros cuenta, llevó un tiempo 2 a la 34 para el paso número uno. Bien, llevó
algo más de 2 a la 34 porque tuvimos que realizar esas exponenciales.
El paso dos llevó un tiempo 2 a la 34, de nuevo ligeramente más que 2 a la 34
a causa de las exponenciales. Así, digamos que el algoritmo en su conjunto llevó un tiempo
2 a la 40. La cuestión es que se trata de mucho, mucho menos tiempo que 2 a la 64. Así, aquí
tenéis un ejemplo en el que si encriptáis usando RSA directamente, dicho de otro modo, si
calculáis "k" elevado a "e" módulo N en lugar de seguir el estándar ISO,
por ejemplo, entonces tenéis un ataque que se realiza mucho más rápidamente que la búsqueda exhaustiva.
Tenéis un ataque que se ejecuta en tiempo 2 a la 40, en lugar de en tiempo 2 a la 64.
De acuerdo, así este es un buen ejemplo de cómo se pueden torcer las cosas si utilizáis la
permutación de puerta falsa RSA directamente para encriptar un mensaje. Así, la idea a
recordar aquí es nunca, nunca, nunca uséis RSA directamente para encriptar. Tenéis que
ir a través de un mecanismo de encriptación, por ejemplo el estándar ISO. Y, de hecho,
en el próximo segmento vamos a ver otras formas de utilizar RSA para construir
encriptación de clave pública.