¡Enhorabuena por su coraje, amable lector! Comencemos sin más preámbulos. Ya sabe, si se aburre no tiene más que saltarse este apartado. Con total confianza. A fin de cuentas, éste es su libro.

El algoritmo RSA se basa en la dificultad matemática de factorizar números primos grandes: dado el número n = p*q, conocer los valores de p y q. En lo que sigue, supondremos que todos los números que aparecen son enteros positivos.

El método que nos enseñaron de pequeños consiste en dividir n por todos los números inferiores a él. Podemos refinar este método, y dividir sólo por los números primos menores que la raíz cuadrada de n. Por ejemplo, ¿es 143 primo? Es impar, así que no es divisible por dos. En cuanto a los demás posibles factores, probémoslos uno por uno:

143/3--= 47.666--no

143/5--= 28.6----no

143/7--= 20.428--no

143/11-= 13------sí

Este sencillo procedimiento de división quizá le suene, es el típico test de primalidad que aprendemos en la escuela. Es fácil de usar para números pequeños. Pero cuando n es muy grande, resulta inviable. Hay otros métodos de factorización más eficientes y rápidos, pero del mismo modo se convierten en poco prácticos si n es lo bastante grande.

Afortunadamente, existen tests de primalidad más sencillos. Uno de ellos, denominado Test de Primalidad de Fermat (TPF) está basado en el Pequeño Teorema de Fermat, que dice:

“Si p es un número primo, y a es un número cualquiera entre 1 y p, entonces se cumple que la división a^(p-1) / p tiene resto igual a uno”

No parece tan obvio, pero los matemáticos, que saben de eso más que nosotros, nos afirman que ese teorema se cumple. Así, tenemos una prueba que no nos exige probar todos los posibles factores de un número grande. Estupendo, salvo por una pega. Dos pegas. No, mejor tres pegas.

La primera pega es que el TPF es un test probabilístico. Quiero decir con esto que no tenemos certeza de que un número sea primo, sino tan sólo que puede que lo sea. El problema es que, en el campo de la lógica, a => b no significa necesariamente b => a. Por ejemplo, supongamos que todos los coches Ford sean azules. Si usted ve un Ford, entonces es azul. Pero si usted ve un coche azul, no tiene por qué ser un Ford.

Eso es lo que le pasa aquí. Si p es primo, entonces se cumple el TPF; pero si se cumple el TPF ¿es p primo? La respuesta es: a veces sí, a veces no. No hay certeza. Pero podemos utilizar el TPF como prueba probabilística. Escojamos un número a y hagamos el TPF. Si p no pasa el test, entonces no es primo. Si, por el contrario, lo pasa, entonces volveremos a aplicarle el TPF con otro valor de a. Y luego otro. Y luego otro. Y otro. Hagamos el test un número elevado de veces. Si p los pasa todos, entonces la probabilidad de que sea primo será muy elevada.

Desafortunadamente, existen números que pueden pasar el TPF para todos los valores posibles de a, y a pesar de ello, no ser primos; reciben el nombre de números de Carmichael. Si nos ha tocado uno, estamos de mala suerte, porque el TPF no nos permitirá detectar que realmente es un número compuesto. Afortunadamente, los números de Carmichael son muy raros: para números de cien dígitos, hay aproximadamente un número de Carmichael por cada trillón de números primos.

Le dije que había tres pegas. He dejado la más gorda para el final. Según el TPF, hay que comprobar si resto de dividir a^(p-1) por p es igual a la unidad. Esa es una operación endiabladamente lenta. Por poner un ejemplo sencillo, sea a=2 y p=997. Son números sencillos y pequeños, y sin embargo 2^996 ¡es un número de trescientas dígitos de longitud! ¿Esto es un test de primalidad práctico? ¿En qué estaba usted pensando, señor Quirantes?

Afortunadamente, hay un método de calcular el resto de a^(p-1) / p sin necesidad de efectuar la división, ni por supuesto la potenciación. El inconveniente es que requiere un pequeño cambio de chip mental, pero es algo que vamos a utilizar después para describir el algoritmo RSA, así que vamos a intentarlo. Se trata del concepto de aritmética modular.

Habitualmente, cuando hacemos la división c=a/b lo que suele interesarnos es el cociente. Si a, b son dos números reales, el cociente es c, y el resto es cero. Si, como en el caso que nos ocupa, se trata de números enteros, entonces el cociente no tiene por qué ser exacto. Bien, pues en la aritmética modular no nos interesa el cociente, sino el resto.

Para esta nueva operación, utilizaremos la notación “mod”. Cuando escribimos a mod n (“a módulo n”) nos estamos refiriendo a “el resto que obtenemos al dividir a por n” Cuando queramos indicar que al dividir a entre n obtenemos b, lo escribiremos así:

Quizá no lo sepa, pero usted utiliza de vez en cuando la aritmética modular sin darse cuenta. Eche un vistazo a un reloj digital. Son las once de la noche, es decir, las 23:00. Dentro de cuatro horas, ¿qué hora será? 23+4 son 27, pero nadie dice “son las veintisiete”. Su reloj no marca 27:00 sino 3:00, que es el resto de dividir 27 entre 24; podemos decir que nos muestra la hora “módulo 24”. De forma similar, el famoso reloj Big Ben londinense marca las horas “módulo 12” y nunca —salvo por error— dará quince campanadas.

La aritmética modular es algo más engorrosa que la tradicional, pero es la pieza fundamental para poder operar con números muy grandes. Volvamos al ejemplo del TPF. Se trata de averiguar si el resto de la división a^(p-1) / p es igual a uno. En aritmética modular, lo escribimos como a^(p-1) mod p = 1

Para calcular, echaremos mano de algunas propiedades de la aritmética modular. Para ello, tendremos que olvidarnos de las reglas que nos enseñaron en el colegio. Por ejemplo, la propiedad distributiva de la multiplicación decía que (a+b)*c = a*c + b*c. Aquí la cosa es algo distinta. Vamos a utilizar esta propiedad de la aritmética modular:

Voy a decirlo con palabras. Para averiguar cuál es el resto de dividir (a*b)/n, haremos lo siguiente:

Y listo. Fíjense que no hemos tenido que multiplicar a*b, ni dividir el resultado por n. Apliquémoslo al TPF, donde tenemos que hallar a^(p-1) mod p. No hay más que generalizar la propiedad anterior:

y obtener fácilmente el resto que buscamos, incluso si p es un número de cien dígitos.

Creo que de momento ya hemos introducido suficientes matemáticas para comenzar con el algoritmo RSA. Partiremos de dos números primos grandes (p, q) y su producto n=p*q. Calculemos también el número F=(p-1)(q-1). El número n es público, pero p y q no lo son.

Vamos ahora a construir la clave privada y la clave pública. La clave pública e será un número tal que F y e sean primos relativos. Con “primos relativos” queremos decir que no tengan divisores comunes, es decir, que su máximo común divisor sea uno. No tienen por qué ser primos ellos mismos. Por ejemplo, los números 15 y 14, a pesar de ser números compuestos, son primos relativos.

Ahora vamos con la clave privada d, un número que cumpla que ed mod F = 1; se dice en este caso que d es el inverso (multiplicativo) de e módulo F. El problema es que, en aritmética modular, el inverso es muy difícil de calcular. Peor aún, a veces existe inverso y a veces no. Se puede demostrar que la condición necesaria para que exista inverso es que los números e y F sean primos relativos. Por eso le hemos exigido esa condición específica al número e.

Ya estamos preparados para cifrar el mensaje M, que vamos a representar mediante un número entero. Es preciso que M sea menor que n; en caso de lo que no lo sea, lo dividiremos en bloques m₁, m₂, etc. Por comodidad, vamos a suponer que nos encontramos en el caso M<n. Para obtener el mensaje cifrado C, realizaremos la siguiente operación:

Fíjense que tenemos un número M enorme, elevado a una potencia e, pero no importa porque, como ya hemos visto, la aritmética modular me permite operar con facilidad. El proceso opuesto, el descifrado, lo realizamos calculando el siguiente número:

Veamos cómo el proceso nos devuelve el mensaje M. O mejor, no lo veamos. O mejor aún, decida usted. Vuelvo a darle el control, querido lector. Estrictamente hablando, puede usted saltarse la explicación que sigue y pasar al apartado siguiente. No se perderá gran cosa. Sin embargo, me considero en la obligación de proporcionarle esa explicación. Es usted quien escoge, que para eso ha pagado el libro (bueno, confío en que habrá usted pagado el libro). Así, pues, si desea seguir la explicación, siga leyendo estas líneas. Si por el contrario, desea poner fin a la clase, salte al apartado siguiente pulsando este enlace.

Si está leyendo usted esta frase, es que ha decidido quedarse y apuntarse a la explicación completa. Así sea. Lo haré lo más fácil que pueda, aunque no le garantizo nada. Vamos, en primer lugar, a desarrollar la potencia C^d:

Como ed mod F=1, eso significa que existe un número k tal que ed = kF+1, así que:

C^d = M^(ed)

-----= M^(kF+1)

-----= M*M^(kF)

-----= M*(M^F)^k

El resto de la demostración dependerá de si M y p tienen factores comunes o no. Y con “factores comunes” me refiero a los no triviales, de forma que el número 1 no vale. Vamos a cubrir las dos posibilidades

1) M y p no tienen divisores comunes. Puesto que p es primo, podemos aplicar el test de primalidad de Fermat:

[M^(p-1)]^2 mod = [M^(p-1) mod p)*( M^(p-1) mod p)] mod p

--------------------= 1 mod p

Siguiendo el mismo razonamiento, cualquier potencia del tipo M^a(p-1) mod p es igual a la unidad. En particular, vamos a elevar M^(p-1) a la potencia k(q-1):

M^[k(p-1)(q-1)+1] mod p

= M*M^[k(p-1)(q-1)] mod p

=[(M mod p)* M^[k(p-1)(q-1)] mod p

= [(M mod p)] mod p

= M

En el ultimo paso, he hecho un poco de trampa. “M mod p” es el resto de dividir M entre p, y lo habitual es suponer que p está comprendido entre 0 y M-1. Si dividimos 55 entre 9, decimos que el resto es uno porque 55=9*6+1. Pero también podemos decir que 55=9*5 +10. Según eso, “55 mod 9” es igual a uno, pero también es igual a diez. Incluso podríamos decir que 55 mod 9 = 55, ya que es cierto que 55=9*0+55. Habitualmente es una tontería escribirlo así, pero lo importante es que la aritmética modular me permite ponerlo en la forma que me resulte más favorable. De modo que es perfectamente válido afirmar que M mod p = M. Y eso es lo que acabamos de hacer en el desarrollo anterior.

Se estará preguntando el por qué de todo este baile modular. El motivo es que, como dijimos antes, ed = kF+1, y F era igual a (p-1)(q-1), así que k(p-1)(q-1)+1 = ed. Es decir, lo que acabamos de demostrar es que:

pero eso sí, solamente en el caso de que M y p no tengan divisores comunes. Veamos ahora el caso de que sí los tenga.

2) M y p tienen divisores comunes. Puesto que el número 1 no vale (por ser un divisor común trivial) y p es un número primo, la única posibilidad es que M sea divisible por p. Eso significa que cualquier potencia de M también será divisible por p, es decir, dará resto cero. En particular M^(ed) es exactamente divisible por p, o dicho con aritmética modular:

Pero dar resto cero también es dar resto M. Si dividimos 54 entre 9 el resto es cero (54 = 9*6+0) pero también nueve, ya que podemos escribir 54=9*5+9. Por lo general no lo hacemos así, pero es perfectamente válido, de modo que nadie puede objetar a que nosotros escribamos:

Con ello, hemos demostrado que, en cualquiera de los dos casos (con o sin divisores comunes), se cumple la relación:

Eso es eso es lo mismo que decir que el número (M^ed – M) es exactamente divisible por p. A continuación, podemos repetir el mismo argumento para el número q. El resultado será:

que nuevamente lo podemos expresar diciendo que (M^ed – M) es exactamente divisible por p.

Y ahora viene el elemento final, que espero sea de su agrado. Si el número (M^ed – M) es exactamente divisible por p, y también por q, significa que también es divisible por p*q, es decir por n. Lo que significa que:

2) DESCRIPCIÓN MATEMÁTICA DE RSA (SÓLO PARA VALIENTES)