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.