La permutación de puerta falsa RSA (18 min)

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.