Las tripas del sistema RSA
*B escoge p,q, primos de 150 cifras y calcula n=pq.
Solamente B en todo el mundo
sabe que n=pq y solamente B conoce el número (p-1)(q-1).
*B escoge e
razonablemente grande y que sea relativamente primo con el número
(p-1)(q-1) (es
decir, el MCD de e
y (p-1)(q-1)
es 1). (No hace falta que e
sea tan grande como n).
*B hace público su código
para que le envíen mensajes, que será (e,n).
*B calcula el único número
d
tal que
d.e=1 (mod (p-1)(q-1))
y lo mantiene en secreto ya que
¡d es su descodificador!
Lo calcula fácilmente
mediante el algoritmo de Euclides aplicado a (p-1)(q-1)
y e del que resulta
fácilmente
1=d.e-h.(p-1)(q-1)
*Veamos ahora por qué
funciona todo bien.
A quería enviar a
B el mensaje M y calculó
M'=M^e (mod n)
B calcula ahora M'^d y obtiene el
resto de este número al dividir por n, pero
M'^d=M^[ed] (mod n)=
M^[1+h(p-1)(q-1)] (mod n) =
=M.M^[h(p-1)(q-1)] (mod n)
Pero, por el "pequeño" teorema
de Fermat resulta que
M^[(p-1)(q-1)]=1 (mod n)
y así
M.M^[h(p-1)(q-1)] (mod n)=M
(mod n)
y por lo tanto
M'^d=M (mod n)
es decir
las operaciones que hace
B le proporcionan efectivamente el mensaje M.