WEBVTT

00:00:00.000 --> 00:00:04.090
En el segmento anterior vimos cómo construir encriptación 
públicamente con funciones de puerta falsa,

00:00:04.090 --> 00:00:08.390
en este segmento vamos a construir una función de 
puerta falsa clásica llamada RSA.

00:00:08.390 --> 00:00:13.295
Pero primero vamos a repasar rápidamente qué es una
función de puerta falsa. Recordemos que una función

00:00:13.295 --> 00:00:17.283
de puerta falsa está formada por tres funciones. Hay 
un algoritmo de generación de claves, la función

00:00:17.283 --> 00:00:21.056
propiamente dicha y la inversa de la función. 
El algoritmo de generación de claves

00:00:21.056 --> 00:00:25.313
genera una clave pública y una clave privada.
Y en este caso, en esta lección, la clave pública

00:00:25.313 --> 00:00:29.786
va a definir una función que relaciona el 
conjunto X consigo mismo.

00:00:29.786 --> 00:00:33.882
Por esta razón llamo a estos objetos permutaciones de
puerta falsa, en oposición a funciones de puerta falsa,

00:00:33.882 --> 00:00:37.978
simplemente porque la función relaciona X consigo 
mismo, mientras que una función de puerta falsa

00:00:37.978 --> 00:00:43.356
podría relacionar el conjunto X con cualquier conjunto 
arbitrario Y. Ahora, siendo conocida la clave pública,

00:00:43.356 --> 00:00:47.819
la función, como indicamos, básicamente define esta 
función del conjunto X al conjunto X.

00:00:47.819 --> 00:00:52.914
Y, conociendo la clave secreta, podemos 
invertir esta función. Por tanto,

00:00:52.914 --> 00:00:57.401
esta función F evalúa la función en la dirección 
directa y esta función, F inversa,

00:00:57.401 --> 00:01:02.059
que implica la clave secreta SK, calcula F 
en la dirección inversa. Ahora

00:01:02.059 --> 00:01:06.489
decimos que la permutación de puerta falsa es 
segura si la función definida por la clave pública

00:01:06.489 --> 00:01:11.033
es de hecho una función unidireccional, lo 
que significa que es fácil de evaluar,

00:01:11.033 --> 00:01:15.404
pero sin la puerta falsa (la clave secreta), 
es difícil de invertir.

00:01:15.404 --> 00:01:20.076
Antes de que veamos nuestro primer ejemplo de permutación 
de puerta falsa, quisiera hacer una revisión rápida

00:01:20.076 --> 00:01:24.467
de algunos elementos de aritmética que vamos a 
necesitar. Y, en particular, vamos a

00:01:24.467 --> 00:01:28.632
repasar algunos elementos de la aritmética modular 
con números compuestos. Así, aquí tenemos nuestro

00:01:28.632 --> 00:01:33.192
módulo N, que es el producto de dos números primos, 
y vosotros deberíais estar imaginando que

00:01:33.192 --> 00:01:37.864
P y Q son números de aproximadamente el mismo 
tamaño, puesto que P y Q particulares son ambos

00:01:37.864 --> 00:01:42.407
aproximadamente del tamaño de la raíz cuadrada de N. Por
tanto, ambos son de aproximadamente el mismo tamaño.

00:01:42.407 --> 00:01:46.834
Recordemos que denotamos ZN al conjunto de enteros de 
cero a N menos 1 y ya dijimos que podemos

00:01:46.834 --> 00:01:51.318
sumar y multiplicar módulo N. Denotamos como 
ZN estrella el conjunto de

00:01:51.318 --> 00:01:55.801
elementos invertibles en ZN. O sea, todos los 
elementos que tienen un inverso modular.

00:01:55.801 --> 00:02:00.925
Y dijimos que, de hecho, X es invertible si y sólo si 
X y N son primos entre sí (coprimos).

00:02:00.925 --> 00:02:05.928
Además, también os dije que el número 
de elementos invertibles en ZN estrella

00:02:05.928 --> 00:02:11.147
se denota mediante la función fi de N. Por tanto,
fi de N es el número de elementos invertibles en

00:02:11.147 --> 00:02:15.814
ZN estrella. Y os dije que cuando N es el producto 
de dos números primos diferentes, entonces, de hecho,

00:02:15.814 --> 00:02:20.788
fi de N es igual a P menos uno por Q menos uno, 
y si lo desarrolláis, veréis que es

00:02:20.788 --> 00:02:26.007
realmente igual a N menos P menos Q más uno. 
Ahora recordad que dije que P y Q son del orden

00:02:26.007 --> 00:02:30.858
de la raíz cuadrada de N, lo que significa 
que P más Q es también del orden

00:02:30.858 --> 00:02:35.675
de la raíz cuadrada de N. Lo cual significa 
que realmente fi de N es del orden de

00:02:35.675 --> 00:02:41.050
N menos dos veces la raíz cuadrada de N. Así, 
en otras palabras, es muy, muy próxima a N.

00:02:41.050 --> 00:02:45.158
Básicamente, al restar la raíz cuadrada de N de 
un número, N, que en nuestro caso va a ser

00:02:45.158 --> 00:02:49.425
un número enorme, de unos 600 dígitos.
Y así, al restar de un número de 600

00:02:49.425 --> 00:02:53.533
dígitos la raíz cuadrada de ese número de 
600 dígitos, o sea un número de 300 dígitos,

00:02:53.533 --> 00:02:57.534
apenas afecta al tamaño del número. Lo 
cual significa que fi de N es realmente, pero lo

00:02:57.534 --> 00:03:01.908
que se dice realmente próxima a N y quiero 
que recordéis esto, ya que, de hecho,

00:03:01.908 --> 00:03:06.122
lo utilizaremos una y otra vez. Y el hecho de que 
fi de N sea realmente próximo a N, significa que

00:03:06.122 --> 00:03:11.094
si escogemos un elemento módulo N al azar es 
muy, muy probable que pertenezca a Z con estrella,

00:03:11.094 --> 00:03:15.633
así que es muy improbable que al escoger un 
elemento aleatorio al final acabemos

00:03:15.633 --> 00:03:20.085
escogiendo un elemento que no sea invertible.
Bien. Por tanto recordad esto, que,

00:03:20.085 --> 00:03:25.479
de hecho, casi todos los elementos de ZN son 
invertibles. Y, lo último que nos hará falta,

00:03:25.479 --> 00:03:30.939
es el teorema de Euler, que vimos la semana 
pasada, que básicamente dice que

00:03:30.939 --> 00:03:36.332
para todo elemento x en ZN con estrella, si elevo x a 
la potencia fi de N, obtengo 1 en ZN.

00:03:36.332 --> 00:03:42.527
Así, en otras palabras, obtengo uno módulo N. Lo 
diré una vez más porque esto será

00:03:42.527 --> 00:03:47.466
crítico para lo que viene. De nuevo, x elevado a 
fi de N es igual a uno módulo N.

00:03:47.466 --> 00:03:51.997
Así, ahora que disponemos de los fundamentos 
necesarios, ya podemos describir la

00:03:51.997 --> 00:03:55.927
permutación de puerta falsa RSA. Se trata de 
una construcción clásica, clásica, clásica en

00:03:55.927 --> 00:04:00.811
criptografía que se publicó por primera vez en 
Scientific American en 1977; se trata de un

00:04:00.811 --> 00:04:05.576
artículo muy conocido en criptografía. Y desde 
entonces, desde hace 35 años,

00:04:05.576 --> 00:04:10.340
la permutación de puerta falsa RSA se ha utilizado 
profusamente en aplicaciones criptográficas.

00:04:10.340 --> 00:04:15.110
Por ejemplo, SSL y TLS utilizan RSA tanto para 
certificados como para intercambio de claves.

00:04:15.110 --> 00:04:19.452
Hay muchos sistemas de correo electrónico seguro 
y sistemas de archivos seguros que utilizan RSA para

00:04:19.452 --> 00:04:23.515
encriptar correos electrónicos y archivos del sistema de 
archivos. Y hay muchas, muchas, muchas diferentes

00:04:23.515 --> 00:04:27.690
aplicaciones de este sistema. Así, ésta es una 
construcción criptográfica muy, muy clásica

00:04:27.690 --> 00:04:32.541
y voy a mostraros como funciona. Debería comentar 
que el nombre de RSA deriva de sus

00:04:32.541 --> 00:04:37.150
inventores: Ron Rivest, Adi Shamir y Len Adleman, 
quienes estaban todos en el MIT cuando

00:04:37.150 --> 00:04:41.758
hicieron este importante descubrimiento. Así, 
ahora estamos listos para describir la permutación de

00:04:41.758 --> 00:04:46.425
puerta falsa RSA. Para ello, tengo que describir 
el algoritmo de generación de claves,

00:04:46.425 --> 00:04:50.159
la función F y la función inversa de F. Así que veamos... 
La forma en que funciona el algoritmo de generación

00:04:50.159 --> 00:04:54.826
de claves es la siguiente: lo que hacemos es 
generar dos números primos, P y Q,

00:04:54.826 --> 00:04:59.143
cada uno de los cuales tendrá, digamos, del 
orden de 1000 bits, o sea, ya sabéis, unos

00:04:59.143 --> 00:05:03.751
300 dígitos, y el módulo RSA simplemente va a ser
el producto de ambos números primos.

00:05:03.751 --> 00:05:08.801
Lo siguiente que haremos es escoger dos
exponentes, e y d, tales que el producto de

00:05:08.801 --> 00:05:13.894
e y d sea uno módulo fi de N. Lo que esto 
significa es que, primero,

00:05:13.894 --> 00:05:19.051
E y D son coprimos de fi de N y, segundo, son 
mutuamente inversos modulares

00:05:19.051 --> 00:05:24.014
módulo fi de N. Y entonces, generamos 
la clave pública como el par

00:05:24.014 --> 00:05:29.172
N, coma, e y la clave secreta (privada), N, coma, d.
Debo mencionar que el exponente e,

00:05:29.172 --> 00:05:34.586
que al número "e" en ocasiones se le denomina 
exponente de encriptación y al exponente "d" en

00:05:34.586 --> 00:05:39.135
ocasiones se le denomina exponente de desencriptado. 
Y veréis por qué me refiero continuamente a ellos

00:05:39.135 --> 00:05:43.189
como exponentes en un momento. Ahora, la forma 
en que la función RSA se define

00:05:43.189 --> 00:05:46.902
es realmente sencilla. Por simplicidad, voy 
a definirla como una función

00:05:46.902 --> 00:05:51.801
de ZN estrella a ZN estrella. Y la forma en que 
se define la función es, simplemente, dado un

00:05:51.801 --> 00:05:57.001
valor de entrada x, lo único que hacemos es elevarlo 
a la potencia e en ZN. Por tanto, nos limitamos a

00:05:57.001 --> 00:06:02.137
calcular x elevado a e, módulo N. Eso es todo. Y 
para desencriptar, lo que hacemos es, simplemente,

00:06:02.137 --> 00:06:07.451
dado un valor de entrada y, simplemente elevamos 
y a la potencia d, módulo N. Y eso es todo.

00:06:07.451 --> 00:06:12.483
Así, ahora podéis ver por qué me refería a "e" y "d" 
como exponentes. Son los valores a los

00:06:12.483 --> 00:06:17.767
que "x" e "y" se elevan. Así, vamos a verificar 
rápidamente que la inversa de F realmente

00:06:17.767 --> 00:06:22.673
invierte la función F. Para eso vamos a ver qué ocurre 
cuando calculamos "y" elevado a "d". Así,

00:06:22.673 --> 00:06:27.515
supongamos que "y" es el valor de la función RSA 
para cierto valor "x". En ese caso,

00:06:27.515 --> 00:06:33.045
lo que es "y" elevado a "d", en realidad es RSA de 
x elevado a la potencia "d". RSA de x, por sí misma,

00:06:33.045 --> 00:06:39.006
es simplemente "x" elevado a "e" módulo N. Y, por tanto, 
"y" elevado a "d" es simplemente "x" elevado a

00:06:39.006 --> 00:06:44.896
"e" por "d" módulo N. De nuevo, simplemente usando 
las reglas de exponenciación, los exponentes se

00:06:44.896 --> 00:06:50.857
multiplican y obtenemos "x" elevado a "e" por "d". Pero, 
¿qué sabemos sobre "e" por "d"? "e" por "d" dijimos que

00:06:50.857 --> 00:06:57.390
es uno módulo fi de N. Y lo que esto significa es que 
existe algún entero tal que "e" por "d" es

00:06:57.390 --> 00:07:04.177
igual a k por fi de n más uno. Esto es lo que 
significa que "e" por "d" sea

00:07:04.177 --> 00:07:09.820
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

00:07:09.820 --> 00:07:14.453
lo que escribí aquí. Así, tenemos x elevado a k por 
fi de n mas uno. Pero ahora, de nuevo

00:07:14.453 --> 00:07:19.868
usando las reglas de exponenciación, podemos 
reescribir esto como x elevado a fi de N, elevado

00:07:19.868 --> 00:07:24.827
a k, por x. Esto es realmente lo mismo que 
k por fi de N más 1 como exponente.

00:07:24.827 --> 00:07:29.917
Me he limitado a separar el exponente en
sus diferentes componentes.

00:07:29.917 --> 00:07:35.137
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í,

00:07:35.137 --> 00:07:41.394
¿a qué es igual todo este producto? Bien, puesto que 
x elevado a fi de N es igual a uno, uno

00:07:41.394 --> 00:07:45.961
elevado a k es también igual a uno. Por tanto,
todo este término de aquí es simplemente igual a uno.

00:07:45.961 --> 00:07:50.757
Y lo que nos queda es x. Así, lo que hemos 
probado es que si tomamos la salida de la

00:07:50.757 --> 00:07:55.210
función RSA y la elevamos a "d", obtenemos 
de nuevo x. Lo cual significa que

00:07:55.210 --> 00:07:59.663
al elevar a "d" básicamente se invierte la 
función RSA, que es lo que

00:07:59.663 --> 00:08:04.638
queríamos mostrar. Así, eso es todo. Esta es 
la descripción completa de la función. Hemos

00:08:04.638 --> 00:08:08.972
descrito la generación de la clave, la propia 
función que consiste simplemente en elevar

00:08:08.972 --> 00:08:13.410
a la potencia de "e" módulo N, y la función 
inversa, que consiste en elevar a la

00:08:13.410 --> 00:08:17.483
potencia de "d", también módulo N. La siguiente 
pregunta es ¿por qué esta función es segura?

00:08:17.483 --> 00:08:21.609
En otras palabras, ¿por qué esta función es unidireccional 
si todo lo que tengo es sólo una clave pública

00:08:21.609 --> 00:08:26.409
pero no tengo la clave privada? Y para argumentar 
que esta función es unidireccional,

00:08:26.409 --> 00:08:31.454
básicamente enunciamos el supuesto RSA, que 
básicamente dice que la función RSA es una

00:08:31.454 --> 00:08:36.626
permutación unidireccional. Y, formalmente, la 
forma en que se enuncia es que, básicamente para todo

00:08:36.626 --> 00:08:41.416
algoritmo eficiente A, si genero dos números 
primos p y q,

00:08:41.416 --> 00:08:46.397
números primos aleatorios p y q, los multiplico 
para obtener el módulo N y luego escojo un

00:08:46.397 --> 00:08:51.103
valor aleatorio y en ZN estrella y proporciono 
el módulo, el exponente y el valor y al

00:08:51.103 --> 00:08:55.893
algoritmo A, la probabilidad de que obtenga el 
inverso de RSA en el punto y, esto es,

00:08:55.893 --> 00:09:00.336
de que obtenga "y" elevado a uno partido "e" (esto 
es lo que el inverso realmente es), esta

00:09:00.336 --> 00:09:04.606
probabilidad es negligible. Así, esta suposición 
se denomina supuesto RSA.

00:09:04.606 --> 00:09:09.338
Básicamente enuncia que RSA es una permutación
unidireccional cuando sólo se proporciona una clave pública.

00:09:09.338 --> 00:09:13.954
Y, consecuentemente, es una permutación de puerta falsa 
porque tiene una puerta falsa, y esto la hace 
tiene

00:09:13.954 --> 00:09:19.501
fácil de invertir para cualquiera que conozca la 
puerta falsa. Así, ahora que tenemos una permutación

00:09:19.501 --> 00:09:23.717
de puerta falsa segura, podemos simplemente combinarla 
con nuestra construcción de encriptación pública

00:09:23.717 --> 00:09:27.826
y tendremos nuestro primer sistema real de 
encriptación pública. Y así, lo que

00:09:27.826 --> 00:09:32.362
haremos es simplemente insertar la permutación 
de puerta falsa RSA en la construcción estándar

00:09:32.362 --> 00:09:36.151
ISO que vimos en el segmento anterior. 
Así, si os acordáis, dicha

00:09:36.151 --> 00:09:40.207
construcción estaba basada en un sistema 
de encriptación simétrica que tenía que proporcionar

00:09:40.207 --> 00:09:44.438
encriptación autentificada. Y estaba también basada 
en una función hash que relaciona,

00:09:44.615 --> 00:09:48.866
bien, transfiriéndolo al mundo RSA, 
relaciona elementos en

00:09:48.866 --> 00:09:54.202
ZN con claves secretas para el 
sistema de clave simétrica. Y ahora, la

00:09:54.202 --> 00:09:58.947
forma en que el esquema de encripción funciona es 
realmente fácil de describir. Básicamente el algoritmo G

00:09:58.947 --> 00:10:03.751
básicamente ejecuta el algoritmo de generación de 
claves RSA y genera una clave pública y una

00:10:03.751 --> 00:10:07.813
clave privada, igual que antes. Fijaos en que la 
clave pública contiene el exponente de

00:10:07.813 --> 00:10:11.948
encripción y la clave privada contiene el 
exponente de desencriptado. Y la forma en que

00:10:11.948 --> 00:10:16.298
encriptamos es la siguiente. Bien, vamos a escoger 
un valor aleatorio de "x" en ZN, vamos a

00:10:16.298 --> 00:10:21.468
aplicar la función RSA a esta "x", vamos a reducirla 
a una clave simétrica generando su "hash",

00:10:21.468 --> 00:10:26.453
así que calcularemos H de "x" para obtener 
la clave "k", y entonces la salida será

00:10:26.453 --> 00:10:31.130
"y" junto a la encriptación del mensaje 
usando la clave simétrica "k". Y, en la

00:10:31.130 --> 00:10:35.930
práctica, la función "hash" H se implementaría 
mediante SHA-256 y

00:10:35.930 --> 00:10:40.977
utilizaríais el operador SHA-256 para 
generar una clave simétrica que se pudiese

00:10:40.977 --> 00:10:45.687
utilizar en el sistema de encriptación simétrica. 
Así es como encriptaríamos

00:10:45.687 --> 00:10:50.084
y la forma en que desencriptariamos es 
básicamente como vimos en el segmento

00:10:50.084 --> 00:10:54.951
anterior, pero lo primero que haríamos es 
utilizar la clave privada para invertir

00:10:54.951 --> 00:10:59.758
la cabecera del texto cifrado. Así, calcularíamos 
la inversa RSA de "y", que nos proporcionaría

00:10:59.758 --> 00:11:04.566
el valor de "x". A continuación aplicaríamos 
la función "hash" a "x" para obtener

00:11:04.566 --> 00:11:09.198
la clave k. Y entonces ejecutaríamos el
algoritmo de desencriptación del sistema

00:11:09.198 --> 00:11:15.171
simétrico sobre el texto cifrado y esto produciría 
el mensaje original, "m".

00:11:15.171 --> 00:11:19.103
Y en su momento enunciamos un teorema en el 
segmento anterior indicando que si la permutación

00:11:19.103 --> 00:11:23.087
de puerta falsa RSA es segura, Es y Ds, el esquema de 
encriptación simétrica proporciona

00:11:23.087 --> 00:11:27.175
encriptación segura y, como dijimos, H es un 
oráculo aleatorio, esto es,

00:11:27.332 --> 00:11:31.421
ya sabéis, un tipo de función aleatoria de 
ZN al espacio de claves. Entonces, de hecho, este

00:11:31.421 --> 00:11:35.720
sistema presenta seguridad de texto cifrado escogido y 
es un buen sistema de encriptación pública a usar.

00:11:36.240 --> 00:11:41.729
Así, ahora que tenemos nuestro primer ejemplo de un buen 
sistema de encriptación pública, quisiera daros un

00:11:41.729 --> 00:11:46.978
rápido aviso sobre cómo no utilizar RSA para 
encriptación. Y esto es algo, de nuevo, que

00:11:46.978 --> 00:11:51.101
ya dijimos en el segmento anterior. Y voy a 
repetirlo aquí, salvo que voy a

00:11:51.101 --> 00:11:55.534
hacerlo específico para RSA. Así, me gustaría 
llamarlo RSA "de libro",

00:11:55.534 --> 00:11:59.400
que es lo primero que se le ocurre a 
uno cuando piensa en

00:11:59.400 --> 00:12:03.678
encriptar usando RSA, a saber, la clave secreta 
y la clave privada serán como antes,

00:12:03.678 --> 00:12:08.162
pero en lugar de utilizar una función 
"hash" para generar una clave simétrica, lo

00:12:08.162 --> 00:12:12.337
que haremos es usar directamente RSA para 
encriptar el mensaje dado, "m". Y entonces,

00:12:12.337 --> 00:12:16.202
utilizaremos directamente un exponente de desencriptado 
para desencriptar el texto cifrado y

00:12:16.202 --> 00:12:20.773
obtener el texto llano, "m". Voy a llamar a esto 
"RSA de libro" porque hay muchos libros que

00:12:20.773 --> 00:12:25.350
describen la encripción RSA de este 
modo. Y esto es completamente erróneo.

00:12:25.350 --> 00:12:29.495
Así no es como funciona la encripción RSA. Se 
trata de un sistema inseguro. En particular,

00:12:29.495 --> 00:12:33.936
se trata de encripción determinista y, por tanto, 
no es posible que sea semánticamente segura y,

00:12:33.936 --> 00:12:38.542
de hecho, existen múltiples ataques y voy a 
mostraros un ataque en un minuto.

00:12:38.542 --> 00:12:42.709
Pero el mensaje que quiero que quede 
claro aquí es que RSA es únicamente

00:12:42.709 --> 00:12:47.151
una permutación de puerta falsa. Por si misma 
no es un sistema de encriptado. Tenéis que

00:12:47.151 --> 00:12:51.427
integrarlo en el estándar ISO, por ejemplo, 
para convertirlo en un sistema de encriptado.

00:12:51.427 --> 00:12:55.826
Por si mismo, no es más que una función. 
Así, vamos a ver cuál es el problema si

00:12:55.826 --> 00:13:00.225
intentáis utilizar RSA "de libro", en otras palabras, 
si intentáis encriptar un mensaje

00:13:00.225 --> 00:13:04.975
utilizando RSA directamente. Y os pondré un 
ejemplo de ataque del mundo de la web.

00:13:04.975 --> 00:13:09.725
Imaginad que tenéis un servidor web. El servidor 
web tiene una clave RSA privada. Aquí la

00:13:09.725 --> 00:13:14.738
denotaremos como N y "d". Y tenemos un navegador
web que está intentando establecer una sesión

00:13:14.738 --> 00:13:19.124
segura, una sesión segura SSL con el servidor web. 
La forma en que SSL funciona es que el

00:13:19.124 --> 00:13:23.401
navegador web empieza enviando este 
mensaje "CLIENT HELLO" que significa, ¡eh, quiero

00:13:23.401 --> 00:13:27.787
establecer una sesión segura contigo! El servidor 
web responde con un mensaje "SERVER HELLO"

00:13:27.787 --> 00:13:32.430
que contiene la clave pública del servidor 
y entonces el navegador web continuará y

00:13:32.430 --> 00:13:36.615
generará una clave aleatoria denominada clave 
secreta pre-máster, encriptará la clave

00:13:36.615 --> 00:13:40.692
secreta pre-máster usando [RSA] (N.T. el original dice "k") 
y enviará el resultado cifrado al servidor web.

00:13:40.692 --> 00:13:44.932
El servidor web lo desencriptará y entonces el 
servidor web también tendrá "k", por lo que

00:13:44.932 --> 00:13:49.336
ahora ambos disponen de una clave compartida que 
pueden usar para establecer una sesión segura entre

00:13:49.336 --> 00:13:53.630
ellos. Lo que quiero mostraros es qué va mal si 
utilizamos directamente la función RSA

00:13:53.630 --> 00:13:57.762
para encriptar "k". En otras palabras, si directamente 
se encripta "k" usando "k" elevado a "e"

00:13:57.762 --> 00:14:02.828
módulo N y pongamos por caso, supongamos, 
que "k" es una clave de 64 bits.

00:14:02.828 --> 00:14:08.097
Vamos a tratar "k" como un entero en el rango 
de 0 a dos elevado a 64.

00:14:08.097 --> 00:14:13.100
Más exactamente, dos elevado a 64 menos uno, y 
ahora lo que vamos a hacer es

00:14:13.100 --> 00:14:18.302
lo siguiente. En primer lugar, supongamos que 
"k" se puede factorizar en un producto de

00:14:18.302 --> 00:14:23.705
números de tamaños aproximadamente iguales. Así, 
podemos escribir "k" como k1 por k2, donde k1 y k2

00:14:23.705 --> 00:14:29.745
son enteros y ambos son, digamos, menores que dos 
elevado a 34. Y resulta que esto sucede con una

00:14:29.745 --> 00:14:34.508
probabilidad del 20%, o sea, una de cada 
cinco veces "k" se podrá

00:14:34.508 --> 00:14:39.740
escribir en esta forma. Pero ahora, si introducimos esta "k", 
"k" igual a k1 por k2, si la introducimos en la

00:14:39.740 --> 00:14:45.241
ecuación que define el texto cifrado, podéis ver 
que simplemente sustituimos con k1 por k2

00:14:45.241 --> 00:14:50.875
y entonces podemos mover k1 al otro lado, por lo 
que acabamos obteniendo una ecuación,

00:14:50.875 --> 00:14:55.897
a saber, C dividido por k1 elevado a "e" es igual a 
k2 elevado a "d". Daros cuenta que si multiplico ambos

00:14:55.897 --> 00:15:00.659
lados por k1 elevado a "e", obtengo que C es 
igual a k1 por k2 elevado a "e"

00:15:00.659 --> 00:15:06.374
que es precisamente esta ecuación de aquí. De acuerdo, 
así que lo único que he hecho ha sido reemplazar "k" con

00:15:06.374 --> 00:15:11.955
k1 por k2 y dividir por k1 elevado a "e". Esto 
os debería ser ya familiar.

00:15:11.955 --> 00:15:16.146
Así que ahora tenemos dos variables en esta 
ecuación. Por supuesto, c es conocido por el

00:15:16.146 --> 00:15:20.092
atacante, "e" es conocido por el atacante y N 
es conocido por el atacante. Las dos

00:15:20.092 --> 00:15:24.518
variables de esta ecuación son k1 y k2 y 
las hemos separado en

00:15:24.518 --> 00:15:28.891
distintos lados de la ecuación y, como resultado, 
podemos realizar un ataque por "encuentro en

00:15:28.891 --> 00:15:33.157
la mitad" contra esta ecuación. Así, vamos a 
realizar el ataque por "encuentro en la mitad". Lo que

00:15:33.157 --> 00:15:37.524
haríamos es construir una tabla de todos los 
posibles valores de la parte izquierda. Así,

00:15:37.524 --> 00:15:43.392
todos los posibles valores de C dividido entre k1 elevado 
a "e", de los que hay 2 elevado a 34. Y entonces,

00:15:43.584 --> 00:15:48.878
para todos los valores posibles de la parte derecha, 
esto es, para todos los posibles valores

00:15:48.878 --> 00:15:54.175
de k2 elevado a "e", vamos a comprobar si este 
valor se encuentra en la tabla que hemos

00:15:54.175 --> 00:15:58.749
construido en el paso uno. Y si esto es así, entonces 
habremos encontrado una colisión y, básicamente,

00:15:58.749 --> 00:16:03.265
tenemos una solución a esta ecuación. Por tanto, tan 
pronto como encontremos un elemento de la forma

00:16:03.265 --> 00:16:07.962
k2 elevado a "e" que se encuentre en la tabla que hemos 
construido en el paso uno, habremos solucionado esta

00:16:07.962 --> 00:16:12.717
ecuación y encontrado k1 y k2. Y, por 
supuesto, una vez encontrados k1 y k2,

00:16:12.717 --> 00:16:16.950
podemos recuperar "k" fácilmente simplemente 
multiplicándolos. Así, multiplicamos

00:16:16.950 --> 00:16:21.428
k1 y k2 y obtenemos la clave secreta "k". ¿De acuerdo?
Por lo tanto, hemos roto, básicamente,

00:16:21.428 --> 00:16:25.604
este sistema de encriptación. ¿Y cuántos nos llevó?
Bien, por la fuerza bruta

00:16:25.604 --> 00:16:29.890
lo podríamos haber roto en tiempo 2 a la 64, 
simplemente probando todas las posibles claves. Pero

00:16:29.890 --> 00:16:33.792
este ataque, daros cuenta, llevó un tiempo 2 a la 34 
para el paso número uno. Bien, llevó

00:16:33.792 --> 00:16:38.353
algo más de 2 a la 34 porque tuvimos que 
realizar esas exponenciales.

00:16:38.518 --> 00:16:42.969
El paso dos llevó un tiempo 2 a la 34, de nuevo 
ligeramente más que 2 a la 34

00:16:42.969 --> 00:16:47.530
a causa de las exponenciales. Así, digamos que 
el algoritmo en su conjunto llevó un tiempo

00:16:47.530 --> 00:16:52.277
2 a la 40. La cuestión es que se trata de mucho, 
mucho menos tiempo que 2 a la 64. Así, aquí

00:16:52.277 --> 00:16:56.667
tenéis un ejemplo en el que si encriptáis usando 
RSA directamente, dicho de otro modo, si

00:16:56.667 --> 00:17:01.296
calculáis "k" elevado a "e" módulo N en lugar 
de seguir el estándar ISO,

00:17:01.296 --> 00:17:05.983
por ejemplo, entonces tenéis un ataque que se realiza 
mucho más rápidamente que la búsqueda exhaustiva.

00:17:05.983 --> 00:17:10.730
Tenéis un ataque que se ejecuta en tiempo 2 a la 40, 
en lugar de en tiempo 2 a la 64.

00:17:10.730 --> 00:17:14.985
De acuerdo, así este es un buen ejemplo de cómo 
se pueden torcer las cosas si utilizáis la

00:17:14.985 --> 00:17:19.299
permutación de puerta falsa RSA directamente 
para encriptar un mensaje. Así, la idea a

00:17:19.299 --> 00:17:23.670
recordar aquí es nunca, nunca, nunca uséis 
RSA directamente para encriptar. Tenéis que

00:17:23.670 --> 00:17:27.868
ir a través de un mecanismo de encriptación, por 
ejemplo el estándar ISO. Y, de hecho,

00:17:27.868 --> 00:17:32.354
en el próximo segmento vamos a ver otras 
formas de utilizar RSA para construir

00:17:32.354 --> 00:17:33.620
encriptación de clave pública.