Cifrado asimétrico. Algoritmo de clave pública RSA

Fundamentos del cifrado RSA para la transferencia privada de información mediante clave pública. Implementación práctica del algoritmo desde sus versiones más intuitivas a otras computacionalmente eficientes.

Introducción

Esconder lo que decimos es una cuestión vital que se remonta varios siglos Antes de Cristo. Tanto en banales conversaciones personales como en comunicaciones militares existe algún tipo de codificación y cifrado.

La forma más intuitiva para cifrar información es utilizar una «clave», algo con lo que poder transformar dicha información para hacerla inteligible y poder recuperarla posteriormente. Este método se denomina simétrico, ya que tanto transmisor como receptor utilizan la misma clave para cifrar y descifrar.

Considerando que cualquier canal de comunicación puede ser interceptado este método plantea un problema enorme ¿Cómo acordar claves sin encontrarse físicamente?

La respuesta está en el cifrado asimétrico, un método que permite exponer una clave con la que cifrar información, siendo necesaria una clave distinta para descifrar y que solo conocerá el receptor de un mensaje.

Existen varios métodos de cifrado o algoritmos capaces de hacer esto, siendo el RSA uno de los más populares. Este funciona de la siguiente manera:

1. Un individuo desea recibir mensajes que solo pueda entender él.
2. Hace pública una clave con la que cualquiera puede cifrar un mensaje.
3. Cuando el individuo recibe el mensaje lo descifra utilizando otra clave, una privada que solo conoce él.

El concepto del cifrado asimétrico es fácil, bien distinto es cómo funciona. En este artículo se explican los fundamentos matemáticos, cómo se implementa, en que se basa su seguridad y que precauciones se deben tener en cuenta.

Aplicación básica del algoritmo RSA

Para empezar se realiza un ejemplo sin entrar en detalles, al avanzar se irá profundizando más y más. La idea es que cualquier interesado en este tema pueda detenerse donde desee, sin que sea necesario entender el todo para hacerse una idea de la parte.

Generación de claves

El primer paso lógico será conocer cómo se generan «claves». El proceso gira alrededor de los números primos y sus propiedades, por ahora basta saber que el proceso es:

1. Elegir dos números primos p y q. Se utilizarán valores numéricos pequeños para facilitar el seguimiento del ejemplo, pero como se podrá ver más adelante la seguridad será mayor cuanto más grandes sean. Se elige p = 3, q = 11.

2. Calcular n = p·q. n = 3 · 11 = 33.

3. Mediante la función Euler obtener un número llamado $\large{\varphi(n)}$, que no es más que $\large{\varphi(n)=(p-1)(q-1)}$.

$\varphi(n)=(3-1)(11-1)=20$.

4. Elegir un número ‘e’ coprimo a $\large{\varphi(n)}$ menor que este. Dos números son coprimos cuando su máximo común divisor es 1 => $MCD(e, \varphi(n))=1$. En este caso se puede elegir entre 3, 7, 9, 11, 13, 17 y 19. Se toma e = 7.

5. Encontrar un número ‘d’ que cumpla $\large{e·d \equiv 1 \quad mod(\varphi(n))}$. O en lenguaje llano, que el resto de dividir $\large{e·d /\varphi(n)}$ sea igual a 1.

En este punto se tiene el siguiente conjunto de números:

Las claves se forman de la siguiente manera.

Como se puede ver, las claves son en realidad dos números con uno en común.

Un ejemplo básico

Una vez se tienen las claves, toca cifrar un mensaje que llamaremos ‘m’. Este m representará una letra, símbolo o lo que uno quiera imaginar, pero lo más importante es que no puede ser un número cualquiera. Para que el algoritmo funcione ‘m’ debe ser menor que ‘n’. La siguiente operación cifra el mensaje, siendo ‘cyph’ el número ‘m’ cifrado mediante RSA con la clave pública (e, n).

El mensaje se recupera (descifra) con:

En la siguiente tabla se cifran varios números mediante RSA. Las filas de cada columna muestran los resultados de aplicar las operaciones para el cifrado y descifrado. Por ejemplo, para la primera columna:

Rompiendo el cifrado RSA

A la vista de este ejemplo, podría pensarse que romper el cifrado RSA es relativamente sencillo. Siendo n parte de la clave pública bastaría probar o buscar en una «tabla de multiplicar» de números primos. En la siguiente se muestran los posibles n de los primeros 13 números primos. Para el ejemplo anterior se encuentra fácil que p y q serán 3 y 11 o viceversa.

NOTA: Este código busca el inverso modular por fuerza bruta de una forma muy ineficiente. Más adelante se muestra el método adecuado: "Algoritmo Extendido de Euclides".

function d = inverse_module(e, phi)
  d = uint64(0);
  do
    d = d + 1;
    resto = mod(d * e, phi);
  until (resto == 1)
endfunction

p = 3
q = 11
phi = (p-1)*(q-1)
e = 7
d = inverse_module(e, phi) = 3

Como era de esperar este intento tiene trampa. De forma deliberada no solo se han elegido números pequeños por facilitar la explicación, también para demostrar el fundamento de su seguridad.

En la última tabla, con solo 13 primos se tienen 91 combinaciones. De haber usado números con muchas más cifras la cantidad de combinaciones es inabarcable. Por ejemplo, por debajo del número 1.000.000 se tienen 78.498 primos, equivalente a 3.081.007.251 de combinaciones, siendo necesarios varios gigabytes solo para almacenar los resultados.

De forma habitual se utilizan primos con tamaños entre 1024 bits y 4096 bits en función del nivel de seguridad requerido. En dichos rangos no solo la cantidad de primos es astronómica, si no que por cada primo utilizado la búsqueda por fuerza bruta crece de forma exponencial. Concretamente, utilizando un número ‘x’ de primos, se tienen ‘n’ productos ‘p·q’ únicos tal que:

Haciendo click en el siguiente título se mostrará (sin salir de la página) el desarrollo con el que se halla esta expresión.

Por tanto, la seguridad del cifrado RSA se basa en un problema del que no se conoce solución práctica. Y es que realizar una multiplicación es fácil, pero revertirla muy difícil.

Descomponer un número en sus factores primos no es un problema imposible, pero el tiempo requerido hace que no merezca la pena intentarlo. En la actualidad existen muchos algoritmos que tratan de acelerar esta operación, pero ninguno conocido que lo haga en un tiempo práctico.

Implementación del cifrado RSA

Con lo visto hasta ahora es momento de algo real. Supongamos que se requiere cifrar mediante RSA el «Quijote», un libro fácilmente accesible como fichero ‘.txt’. La copia que se usará contiene 2.151.349 bytes que deberán pasar por la ecuación ‘$m^e\pmod{n}$‘.

Generando claves de 32 bits

El primer paso será elegir un tamaño de la clave. Al disponer de un procesador de 64 bits sería recomendable comenzar por un tamaño máximo de 32 bits, de forma que el resultado de cualquier multiplicación «quepa» en los 64 bits disponibles.

Los primos de partida

% Genera un número primo de forma aleatoria
function prime_n = get_random_prime()
  do
    % Generar un número entre 47 y el máximo de uint16
    prime_n = randi([47, intmax('uint16')], "uint32");
  until(isprime(prime_n))
endfunction

Una vez se tienen los primos p’ y ‘q’ se calcula n y phi inmediatamente. El tamaño de ambos no superará un ‘uint32’.

Una clave de mayor tamaño, por ejemplo de 512 bits, requiere multiplicar dos primos de 256 bits, para lo cual, aparece un problema: generar primos mayores de los tradicionales 64 bits. Más adelante se hablará sobre este problema, por ahora, es suficiente saber que en la práctica esto se realiza como se ha mostrado, generando números de forma aleatoria para comprobar después si son primos.

Clave pública (e, n)

Recordando la introducción, ‘e’ y ‘phi’ serán coprimos, con ‘e’ < ‘phi’, por tanto:

Tratándose de una condición con multitud de candidatos, la elección de ‘e’ es aparentemente subjetiva. En la práctica se toma e = 65537 y la razón se entenderá más adelante, por ahora basta saber que este número acelerará el cifrado. Al ser un número primo siempre será coprimo de cualquier ‘phi’.

A día de hoy, que ‘e’ sea siempre 65537 no supone una vulnerabilidad conocida.

Clave privada (d, n), algoritmo de Euclides extendido

Para que el algoritmo RSA funcione el número ‘d’ en la clave privada debe cumplir:

‘d’ será el número que al multiplicar por ‘e’ y dividir entre $\varphi(n)$ el resto es 1. Comúnmente se denomina a ‘d’ como «inverso modular».

La primera idea que puede surgir para encontrar este número es iterar entre 1 y $\varphi(n) -1$ hasta dar con un ‘d’ que cumpla la condición. Si bien es factible para valores $\varphi(n)$ pequeños, al usar claves grandes como las empleadas en criptografía real se vuelve inasumible.

Calcular de forma eficiente el inverso modular pasa por el «Algoritmo de Euclides Extendido». Este algoritmo consigue dos cosas, la primera calcular el Máximo Común Divisor (MCD) de dos números ‘a’ y ‘b’, la segunda encontrar dos números ‘X’ e ‘Y’ tal que

Para este caso ocurre que ‘a’ y ‘b’ son coprimos, lo que implica que $MCD(a, b) = 1$ y por tanto:

Aplicando el módulo ‘m’ en ambos lados de la ecuación y posteriormente la propiedad de la suma modular

Siendo el producto ‘b·Y’ claramente múltiplo de ‘b’ se tiene $b·Y\mod(b)=0$, simplificando

Expresión que habitualmente se escribe de la siguiente forma, y se lee a·X es congruente con 1.

De la ecuación anterior se tiene que al encontrar ‘X’ en $a·X+b·Y=mcd(a,b)$ cuando $MCD(a,b)=1$, ‘X’ será el inverso modular de ‘a’, justo lo que se pretendía resolver.

Trasladando este desarrollo al caso de la clave privada ‘d’, se tiene que al resolver

se encuentra d = X.

La implementación del algoritmo extendido de Euclides en ordenador se ve a continuación. Entender su funcionamiento no forma parte del cifrado RSA, sin embargo, es interesante como curiosidad matemática. Por ello, después del código se encuentra un desplegable con su desarrollo.

flowchart TD
    START["MCD(a, b)"] --> A[$$q = a / b$$] --> A2[$$r = a - q·b$$]
    A2 --> B{r = 0}
    B -->|YES| C["_MCD = b_"]
    D["_a = b_<br/>_b = r_"] --> A
    B -->|NO| D

function [mcd, x, y] = euclides_extended(a, b)
  a = int64(a);
  b = int64(b);

  x0 = int64(1); x1 = int64(0);
  y0 = int64(0); y1 = int64(1);

  while b ~= 0
    q = idivide(a, b, 'floor');
    r = a - q * b;

    a = b;
    b = r;

    x_next = x0 - q * x1;
    y_next = y0 - q * y1;

    x0 = x1; y0 = y1;
    x1 = x_next; y1 = y_next;
  end

  mcd = a;
  x = x0;
  y = y0;

end

Encriptando el Quijote con RSA

Generadas las claves llega el momento del cifrado. Se tomará uno a uno cada símbolo, asignando un valor numérico a toda letra o signo de puntuación, algo que hacen los ordenadores automáticamente con la codificación ASCII.

Cada valor se pasa por la función de cifrado, obteniendo un ‘c’ por cada símbolo:

Esta función presenta el primer problema: no es posible elevar ‘m’ a la potencia de ‘e’ sin que el resultado exceda el número máximo con el que puede trabajar un procesador.

Resolver esto es sencillo utilizando las propiedades de la aritmética modular. En lugar de calcular directamente la potencia m^e, se itera ‘e’ veces de la siguiente forma:

flowchart TD
A([$$c = m^e $$ mod n]) --> C[$$c = 1$$] --> C2[$$i = 1$$]
C2 --> E{i ≤ e}
E -- YES --> F["c = c · m (mod n)"]
E -- No --> H([$$End$$])
F --> G[i++] --> E

La implementación de la operación en Octave se realiza como una función que denominaremos:

‘c = modular_exp(m, e, n)’

% c = m^e mod(n)
function c = modular_exp(m, e, n)
  m = uint64(b);
  e = uint64(e);
  n = uint64(m);

  c = uint64(1);
  for i = 1 : e
    c = mod(c * m, n);
  endfor
endfunction

En un primer intento e intuyendo que esta solución no es viable se mide cuánto tiempo toma cifrar el primer kilobyte del libro, registrando mínimo, máximo y media en cada bloque de 64 bytes.

En la siguiente imagen se observa que las claves se generan en 8 ms y comienza el cifrado. En el primer bloque de 64 bytes, el byte que más rápido se ha cifrado necesitó 249ms, el más lento 267ms.

Se han tardado ~267 segundos en cifrar 1.024 bytes y hasta 355ms por uno solo, 245ms en el mejor caso. Recordando que esta copia del Quijote contiene 2.151.349 bytes, serían necesarios 6 días y 12h para el cifrado completo.

Midiendo de forma manual el tiempo de desencriptado de un solo byte se tienen 2.475,54 segundos, siendo necesarios más de 170 años para realizar la operación sobre todo el libro cifrado.

La función que realiza ambas operaciones es la misma: un bucle for que itera tantas veces como el valor del exponente. En el caso del cifrado se tienen e = 65.537 iteraciones, sin embargo, para el descifrado se tienen d = 366.735.353, razón por la que existe tal diferencia entre ambas.

Exponenciación eficiente

Acortar el tiempo necesario para realizar $‘m^e\pmod{n}’$ es obligatorio si se pretende usar el cifrado RSA. Para ello la exponenciación binaria se sirve de las propiedades de las potencias para calcular m^e sin multiplicar m·m un número ‘e’ veces. Además, la operación es adaptable para ser manejada de forma eficiente por una máquina que solo «piensa» con ‘0’ y ‘1’.

Imaginemos que queremos calcular 4²³ = 70.368.744.177.664. Con el algoritmo anterior serían necesarias 22 operaciones.

Por otro lado, es posible presentar la operación como

Y seguir desarrollando

Las 22 operaciones se reducen a: $4^3, 4^{10}, (4^{10})^2$

Se ha pasado de 22 a 12 operaciones, la mitad. Al calcular potencias de esta forma el número de operaciones ya no depende del valor del exponente.

Exponenciación binaria

Aunque implementar el anterior método de exponenciación reduciría considerablemente el tiempo de cifrado, es posible optimizar su implementación computacional. Volviendo al cálculo de 4²³, se representa el exponente en binario: $23_{(10}=10111_{(2}=1·{2^4}+0·{2^3}+1·{2^2}+1·{2^1}+1·{2^0}$.

Sabiendo que $x^{a+b}=x^a·x^b$:

Para llevar estas operaciones al terreno de la computación hay que fijarse en la tercera línea $4^{1·{2^4}}·4^{0·{2^3}}·4^{1·{2^2}}·4^{1·{2^1}}·4^{1·{2^0}}$. En ella se tiene que el exponente de 2 va desde 0 a 4, dando una pista de como podría implementarse un bucle.

El siguiente diagrama muestra el algoritmo junto con su implementación.

flowchart TD
START([$$c=m^e$$])-->
INIT[$$c=1$$]-->
CHECK_E{$$e>0$$}-->|YES| AND[$$x = e \land 1$$]-->
BIT{$$x=1$$}-->|YES| MUL[$$c=c·m$$]-->
EXP[$$m = m·m$$]-->
SHIFT[$$e=e \ll 1$$]-->CHECK_E
BIT-->|NO| EXP
CHECK_E-->|NO| END([$$End$$])

% c = m^e mod(n)
function c = modular_exp(m, e, n)
  m = uint64(m);
  e = uint64(e);
  n = uint64(n);

  c = uint64(1);
  
  while(e > 0)
    if(bitand(e, 1))
      c = mod(c * m, n);
    end

    m = mod((m * m), n);
    e = bitshift(e, -1);
  endwhile
endfunction

El número de operaciones con este método depende principalmente de la cantidad de bits que tenga el exponente. Por otro lado, a menor cantidad de ‘1’ en este número, menos multiplicaciones. Es por ello que el número 65.537 se elige como parte de la clave, al contener solamente dos ‘1’ el cifrado se acelera de forma notable respecto a otras elecciones.

RSA y la exponenciación binaria

Toca comprobar que la exponenciación binaria mejora el tiempo de ejecución del algoritmo RSA. La modificación para implementar exponenciación y módulo es la siguiente:

% c = m^e mod(n)
function c = modular_exp(m, e, n)
  m = uint64(b);
  e = uint64(e);
  n = uint64(m);

  c = uint64(1);
  m = mod(m, n);

  for i = 1 : e
    c = mod(c * m, n);
  endfor
endfunction

% c = m^e mod(n)
function c = modular_exp(m, e, n)
  m = uint64(m);
  e = uint64(e);
  n = uint64(n);

  c = uint64(1);
  m = mod(m, n);

  while(e > 0)
    if(bitand(e, 1))
      c = mod(c * m, n);
    end

    m = mod((m * m), n);
    e = bitshift(e, -1);
  endwhile
endfunction

Como ligera modificación se ha añadido ‘m = mod(m, n);’ al inicio. Esto hace que el valor de ‘m’ sea lo más pequeño posible antes de comenzar a hacer multiplicaciones con el.

Con esta modificación hecha al ejecutar el cifrado sobre el primer kilobyte del libro se tiene el siguiente resultado.

La reducción de tiempo durante el cifrado pasa de ~267 segundos a ~0,6ms, casi 500 veces más rápido. Nada comparado con la reducción en el tiempo de descifrado, donde cada byte a pasado de ~2475 segundos a ~0,0007, más de 3 millones de veces inferior.

Encriptado total del Quijote con RSA

Llega el momento de encriptar totalmente el libro y hay que hablar de hardware. Si alguien intenta replicar estas pruebas encontrará tiempos diferentes a los mostrados aquí. Hasta ahora los tiempos de ejecución se han medido en un Intel i7-11800H, no pudiendo extrapolar los resultados a otra CPU. De todas formas, las mejoras implementadas estarán ahí, aunque siempre relativas al procesador que ejecute el algoritmo.

Dicho esto, se modifica el script para procesar totalmente el libro. También se modifica la cadencia de los mensajes informativos, pasando de bloques de 64 bytes a 64kB para no saturar la pantalla de información.

De los más de 6 días de partida se ha pasado a menos de 20 minutos, convirtiendo al algoritmo en algo práctico para según que casos.

Un detalle que debe tenerse en cuenta es que el tamaño del fichero encriptado ha aumentado en un factor de cuatro. La explicación no es otra que el uso de claves de 32 bits con datos de 8 bits. La exponenciación modular hará que el dato encriptado original ocupe tantos bits como tenga la clave. La operación módulo asegura que este tamaño nunca sea superior al número a ‘n’.

Desencriptado del Quijote

Recuperar el contenido original era la tarea más exigente al tener que iterar tantas veces como el valor de la clave privada. Vista la mejora en el tiempo de cifrado, es de esperar que aquí se tenga una mejora significativa. Aun así se espera que esta operación no supere a la de encriptado, pues el número de bits a ‘1’ en la clave privada será habitualmente superior al de la clave pública.

En ~25 minutos se ha desencriptado el contenido, un tiempo superior al de encriptado tal como se podía intuir.

Tiempo de ejecución

Si el tiempo necesario es «mucho» o «poco» dependerá de la necesidades y expectativas del usuario. Ciertamente puede parecer lento, pero también hay que tener en cuenta que el encriptado está corriendo en Octave, un lenguaje interpretado. En la entrada «Cálculo de pérdidas en inversores monofásicos» se migró el cálculo a Java para reducir drásticamente el tiempo de ejecución necesario. En este sentido, no se recomendaría migrar a Java este algoritmo, ya que puede beneficiarse del acceso a hardware que ofrecen lenguajes como C/C++ o Rust.

Ataques estadísticos sobre RSA

La encriptación tal y como se ha implementado simplemente transforma ciertos bytes en palabras de 32 bits. Esta correspondencia 1:1 es muy peligrosa al abrir la puerta a un análisis estadístico de los datos.

Por ejemplo, es posible contar el número de veces que una letra se repite en un texto y generar un histograma, algo que en Octave se haría así:

data = fread(...) % Carga el contenido de un archivo

[symbols, ~, idx] = unique(data); % Identifica los símbolos presentes en 'data'
count = accumarray(idx, 1); % Cuenta las veces que aparece cada símbolo

[count_sorted, index_sorted] = sort(count, "descend"); % Ordena la cuenta de cada símbolo
symbols_sorted = symbols(index_sorted); % Crea una lista de los símbolos ordenados

Al pasar este código por el Quijote se tiene el siguiente histograma:

Los 6 símbolos más repetidos son:

En la siguiente imagen se observa la misma estadística, pero esta vez sobre el fichero encriptado con las claves:

• n = 3244881917
• e = 65537
• d = 1708605953

Los números que más se repiten:

Evidentemente, el número de veces que se repiten determinados números en el texto original y cifrado es el mismo.

Para un atacante sería posible buscar que letras son las más usadas para cada idioma. En Wikipedia: «Frecuencia de aparición de letras», se encuentra que ‘e’, ‘a’, ‘o’, ‘s’ y ‘n’, son las más repetidas en castellano. A partir de ahí, es posible reconstruir más de la mitad del texto, basta alguien con conocimiento del idioma para completar el resto.

Empaquetado de información

Evitar un ataque como el anterior es posible si en lugar de byte a byte el cifrado se hace sobre un grupo de ellos. Por ejemplo, al agrupar el texto en bloques de 2 caracteres se obtiene un número de 16 bits que puede cifrarse con las herramientas usadas hasta ahora*.

*Recordando que dada una clave 'n' no podrá cifrarse ningún valor mayor a esta. En este caso, empaquetando en bloques de 16 bits se debe cumplir n > 65.536.

Al hacer esto suceden dos cosas más:

• El tamaño del fichero cifrado se reduce al empaquetar dos símbolos. En este caso a la mitad, ya que ahora 32 bits cifrados contienen 16 bit de información.

• Los tiempos bajan al trabajar sobre dos símbolos al mismo tiempo. En las siguientes imágenes también se ha eliminado la medida de tiempos parciales, siendo 4 veces más rápido el cifrado y descifrado respecto a la ejecución anterior.

Finalmente el histograma queda de la siguiente manera:

Aunque han desaparecido los patrones más evidentes todavía pueden reconocerse algunos. Las combinaciones ‘e’ seguido de ‘espacio’, con ‘a’ también seguido de ‘espacio’ son las más evidentes. No es posible reconstruir el texto con facilidad, pero tampoco es imposible. Es necesario aumentar más el tamaño del empaquetado, lo que obliga a utilizar claves más grandes. Ningún cifrado sirve de nada si está expuesto a ataques tan simples como estos.

Otra posibilidad es mantener el cifrado byte a byte, pero esta vez añadiendo un byte aleatorio. Como se verá ahora, la protección ante este tipo de ataques aumenta drásticamente con este método.

% Cifrar con padding aleatorio
% Aquí data_in[] contiene la información original
padding = bitand(randi([0, 65535], "uint16"), 65280);
tmp = uint16(bitor(padding, uint16(data_in(i))));
data_out(i) = modular_exp(tmp, e, n);

% Descifrar eliminando el padding
% Aquí data_in[] contiene la información cifrada
tmp = uint16(modular_exp(data_in(i), d, n));
data_out(i) = uint8(bitand(tmp, 255));

El histograma tras cifrar y agregar dicho byte es:

A primera vista no parece posible distinguir patrón alguno, por lo que ataques sencillos pierden atractivo. En muchísimas ocasiones un sistema es tan seguro como interese vulnerarlo, muchos atacantes pierden interés ante una aparente complejidad.

En aplicaciones reales se combina empaquetado con inserción de datos aleatorios, un mensaje no solo debe ser secreto, si no que tampoco debe generar dos cifrados idénticos. Un posible esquema muy parecido al utilizado en industria sería el siguiente, donde «Random padding» es información generada al azar y «Message» es el mensaje que realmente se quiere transmitir. Toda esta información se agrupa en un bloque de 256 bits y se cifra con claves de al menos 512 bits, siendo sumamente improbable que varios cifrados seguidos sobre el mismo mensaje generen una salida repetida.

packet
 title Relleno aleatorio para cifrado RSA
 0-7: "00"
 8-15: "02"
 16-95: "Random padding"
 96-103: "00"
 104-255: "Message"

Cuando usar RSA

A pesar de que la implementación utilizada es puramente académica, pueden obtenerse ciertas conclusiones al aprender sus fundamentos.

La primera es que RSA siempre merece la pena cuando se necesitan las ventajas de la criptografía asimétrica. Es decir, que alguien pueda transmitir información sin preocuparse si el canal de comunicación está intervenido.

Otra conclusión es que la carga computacional de este algoritmo es muy elevada para poder ser utilizado en transferencias de datos masivas. Ninguna implementación profesional en ningún lenguaje de bajo nivel puede competir con la velocidad de un cifrado simétrico. De hecho, muchas arquitecturas de procesadores incluyen aceleradores hardware para cifrados simétricos, como el conjunto de instrucciones AES-NI de x86 para cifrado AES. La única excepción a considerar sería el uso de componentes tipo FPGA/ASIC, algo que ya se ha realizado con excelentes resultados, pero un alto coste.

Con estás ventajas e inconvenientes aparece el uso más habitual en la actualidad, que consiste en utilizar RSA para intercambio de claves o autenticación. De esta forma el volumen de información a cifrar con RSA es pequeño, empleándose únicamente para proteger una clave simétrica.

El proceso sería el siguiente:

1. Se genera una clave simétrica aleatoria.
2. Se cifra la información con dicha clave generando un paquete de información.
3. Dicha clave se cifra con RSA.
4. Se envía tanto la clave cifrada como la información.
5. El receptor desencripta la clave simétrica y recupera la información.

Este procedimiento permite enviar grandes volúmenes de información mientras se cambia la clave al mismo tiempo, haciendo muy difícil romper la encriptación simétrica por fuerza bruta.

RSA y las claves de «muchos» bits

Para cerrar, se abre un nuevo reto, que es como hacer cálculos con números tan grandes.

Si bien la eficacia del algoritmo se basa en la facilidad de realizar una multiplicación y la dificultad de factorizarla, utilizar claves pequeñas puede suponer un riesgo a medida que la potencia de computación avanza.

Una búsqueda en internet muestra artículos como este, donde claves de 1024 bits han comenzado a mostrar debilidades con la tecnología actual, no siendo recomendable utilizar menos de 2048 bits.

En la práctica manejar números tan grandes es un problema. Los procesadores habituales de propósito general tienen 64 bits, siendo necesario utilizar distintas técnicas para abarcar números de mayor tamaño. No es imposible multiplicar, por ejemplo, números de 128 bits en un procesador de 64, pero cabe esperar que dicha operación necesite al menos el doble de tiempo.

En un principio se planteó cubrir aquí este problema, sin embargo, dado el tamaño que ha alcanzado esta entrada y el tamaño que será necesario para cubrir esto, se ha decidido comenzar una nueva entrada que será publicada en el futuro. En ella, además de hablar sobre el manejo de grandes números (BigNumber), se implementarán optimizaciones que han quedado fuera como la «multiplicación modular» o «reducción de Montgomery«.