Por Agustín

(Reitero mis disculpas hacia los que esto ya se lo saben, benditos ellos)

Vamos a tratar de aclarar la parte más misteriosa del algoritmo RSA, es decir, el funcionamiento de las operaciones de cifrado y de descifrado, que en nuestra primera entrega se dejó en el aire. Me ha sido útil parte del contenido de este documento, pero hay otras muy buenas explicaciones en la Red. Todo es cuestión de apoyar un poco los codos y tratar de seguir el razonamiento...

Recordemos que disponemos de dos números primos, p y q, y de su producto N=p*q, con los que obteníamos el valor (p-1)*(q-1), que. como luego veremos, es la función φ(N) de Euler. Recordemos también que se eligió un número entero e que fuera coprimo con (p-1)*(q-1) es decir que no tuvieran ningún divisor común. Este valor e, junto con el producto N, constituyen la Clave Pública. Posteriormente obtuvimos otro número entero d, que será la Clave Privada, que junto con e cumple la condición:

e*d – 1 = múltiplo de (p-1)*(q-1) = (p-1)*(q-1) * y

donde y es un entero.

En nuestro ejemplo, los valores que obtuvimos fueron

p = 439
q = 449
N = 197111
(p – 1)*(q - 1) = 196224
e = 1045
d =  ((p – 1)*(q - 1)* y + 1)/e = 5821
(para y = 31)

Ahora no tenemos más remedio que arremangarnos un poco, matemáticamente hablando. Empezaremos por hablar de la función φ de Euler, también llamada “indicatriz”, y que, para un número entero n es igual al número de enteros positivos menores o iguales a n y que son coprimos con él, es decir, que no tienen divisores comunes. Por ejemplo:

φ(1) = 1  {1}
φ(2) = 1  {1}
φ(3) = 2  {1, 2}
φ(4) = 2  {1, 3}
φ(5) = 4  {1, 2, 3, 4}

En general, para un número p primo, φ(p) = p – 1

Como además, se trata de una función multiplicativa, es decir que φ(a*b) = φ(a)*φ(b), tenemos que:

(p-1)*(q-1) = φ(p)*φ(q) = φ(p*q) = φ(N)

¡Aaaaarf! Ahora debemos tomar un poco de aire, y seguir.

La gracia del cifrado asimétrico es que nuestros corresponsales toman nuestra clave pública, y con el mensaje convertido en un número x, se limitan a hacer la operación:

Cifrado
C = x^e modulo N  [i]

Y nosotros, recuperamos el mensaje con nuestra clave privada

Descifrado
x = C^d modulo N [ii]

Y aquí nos quedamos con la pregunta: ¿Por qué funciona esto?
Si reemplazamos [i] en [ii], tendremos:

Descifrado
x = C^d modulo N = (x^e)^d modulo N = x^(e*d) modulo N [iii]

Ahora recordemos la relación que hay entre el producto e*d y (p-1)*(q-1), de forma que [iii] se puede reescribir así:

Descifrado
x = x^(e*d) modulo N = x^((p-1)*(q-1)*y + 1) modulo N
x = (x^((p-1)*(q-1))^y) * x modulo N
(el  +1 del exponente nos da x como factor)

Ahora sólo nos queda demostrar (más o menos, que tampoco esto es Princeton) que

 (x^((p-1)*(q-1))^y modulo N = 1

El pequeño teorema de Fermat afirma que:

a^(p-1) modulo p = 1
siendo p primo y a no divisible por p

Pero el Teorema de Euler-Fermat nos dice que:

 x^φ(N) modulo N = 1,
 y por lo tanto, también
 (x^(p-1)(q-1))^y modulo N = 1

De este modo, obtenemos que C^d modulo N = x, nuestro mensaje buscado.

(En el posterior debate se ha aclarado más esta cuestión: Ver (1) y (2))

Ejemplo: Las dos primeras letras de la palabra KRIPTOPOLIS tienen los valores 21 28 en la tabla de caracteres. De manera que para mandar KR como mensaje, tenemos x = 2128.

Cifrado
KR = 2128
C = 2128^1045 modulo 197111 = 17797
Descifrado
x = 17797^5821 modulo 197111 = 2128
2128 = KR