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.