-
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.