Conceptos básicos de aritmética modular y RSA.
He recibido varios mensajes privados pidiendo que tratase de explicar los conceptos más básicos de RSA, y su aplicación práctica.
Asi que, sin más preámbulos, allá vamos.
Este post no pretende ser un curso RSA ni nada que se le parezca. Es menos ambicioso. Simplemente trata de explicar, por medio
de ejemplos, las dos formulas fundamentales
Code:
Para cifrar un mensaje -------> MC = M^e(mod N)
Para descifrar ---------------> M = MC^d(mod N)
Donde:
M--------> Mensaje (en claro), y que en RSA debe ser un número, todo lo largo que se desee.
MC-------> Es el mismo mensaje (pero cifrado), que también va resultar ser un numero
p,q------> Dos números primos, elegidos por el propietario de la clave
N--------> Numero que se obtiene de multiplicar los dos números (p * q)
e--------> Número elegido por el propietario de la clave (que se utiliza solo para cifrar)
d--------> Número, que se obtiene en base a (e,p,q) y que se explicará al final.Pregunta: ¿Qué significado tiene la expresión: M^e(mod N) ?
Respuesta: En general, la aritmética modular no es muy utilizada en la vida normal, es por eso que a la mayorÃa nos suena algo rara.
Pero es sencilla de entender. Con un par de ejemplos, seguro que se 'caza' el concepto.
Code:
Ejemplo 1------> 3 = 24(mod 7)
Pregunta-------> ¿Por qué es igual a 3?
Respuesta------> Porque la división: (24 / 7) produce un RESTO = 3
Ejemplo 2------> 100 = 43^6(mod 131).
Pregunta-------> ¿Por qué es igual a 100?
Respuesta------> Porque la división: [ (43^6) / 131) ] produce un RESTO = 100
Otra pregunta--> ¿Que significa la expresión: (43^6)?
Respuesta------> Es la expresión de potenciación. (43) es la base y (^6) es el exponente.
Asà que (43^6) = 6321363049
Por tanto: 43^6(mod 131) = 6.321.363.049(mod 131) = 100Podeis probar con la calculadora de Windows (en modo cientifico):
43---> Boton(y^x)---> 6 ---> Boton(Mod)---> 131---> Boton(=)------->Solucion 100
Resumiendo.
El valor de la expresión: "Z(mod N)" siempre es el valor del RESIDUO de la división (Z / N )
Donde (Z) y (N) Deben ser ambos enteros. Y pueden ser expresiones matemáticas, Ej: (35/5), [(a^5)*(b/4)], etc.
------------------------------------------------------------------------------------------------------------------------------------------------------
Con estos conocimiento ya podemos pasar a cifrar un mensaje, que como se decÃa arriba DEBE SER NUMERICO
(Para evitar desbordamiento de la pantalla de la calculadora, en todos los ejemplos usaré números pequeños).
Ejemplo para cifrar el mensaje en claro(M) = 88
Utilizando como clave de cifrado los números: p=17, q=11, N=(p*q)=187, e = 7
Aplicando la formula para cifrar: MC = M^e(mod N) ,
y sustituyendo los parámetros (M,e,N), por sus valores, (88,7,187)
Tenemos: MC = 88^7(mod 187) = 11
Asà que el mensaje cifrado(MC) es = 11
Y ahora, para comprobarlo, vamos a descifrar del mensaje cifrado(MC) = 11,
Utilizando como clave de descifrado los números: p=17, q=11, N=(p*q)=187, d = 23
Aplicando la formula para descifrar: M = MC^d(mod N) ,
y sustituyendo los parámetros (MC,d,N), por sus valores, (11,23,187)
Tenemos: 11^23(mod 187) = 88
Asà que el mensaje en claro(M) vuelve a ser = 88 (el mismo del que partimos al comienzo)
QUE NOS DEMUESTRA QUE HEMOS CALCULADO BIEN, Y QUE EL ALGORITMO RSA FUNCIONA COMO DICE LA TEORIA.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
NOTA1.
Ahora que alguno de vosotros, ya ha digerido la sopa, se dirá algo asà como: "¿De donde se ha sacado este tÃo el valor del numero (d)?"
Y tiene razón. Pero no se trata de un escamoteo de mago de feria.
La elección de los números (e)(d) es una cuestión delicada. Asà que no entraremos en discusiones teóricas, y daré consejos prácticos
que permitan una buena elección de dichos números. Que nos van a servir para cifrar/descifrar los mensajes.
1. Eleccion de (e)
El propietario de la clave debe elegir un número que sea "relativamente primo" con el valor de [(p-1)*(q-1)].
La expresion [(p-1)*(q-1)] se la conoce con el nombre de "función Fi de Euler" (y suele representarse con 21ª letra del alfabeto griego).
2. Eleccion de (d)
A la hora de elegir (d) se escoge un valor que cumpla d = inv(e, Fi(N), o sea la función inversa necesaria para poder operar con el
modulo Fi(N).
UNA SOLUCION MAS FACIL.
Dado que el cálculo de funciones inversas, no es una tarea sencilla, existe un método llamado "Algoritmo de Euclides Extendido" que
permite calcular el número (d) si conocemos el número (e), y los números (p) y (q).
UNA SOLUCION MUCHO MAS FACIL
Tampoco voy a explicar este algoritmo. Mejor, voy a facilitaros una dirección de Internet que os permitirá realizar el cálculo de funciones
inversas. O sea, calcular (d) si conocemos (e) o calcular (e) si conocemos (d):
http://centros5.pntic.mec.es/ies.de....uclidesext.htm
Esta pagina presenta un cuadro donde hay que introducir:
Code:
En PRIMER NUMERO:---------> valor de (e)
En SEGUNDO NUMERO:--------> valor de Fi(N), o sea el valor de (p-1)*(q-1)
Pulsar el botón: CALCULAR y aparecerá el resultado en el último renglón:
EL INVERSO DE: (e) ES (d) MODULO: Fi(N)Y es asà de fácil.
----------------------------------------------------------------------------------------------------------------------
Algunos comentarios como complemento de lo expuesto:
RSA es un sistema de cifrado asimétrico, y clave pública. Los de asimétrico se refiere a que el transmisor y el receptor utilizan claves
diferentes, siendo una de ellas imposible(?) de averiguar no conociendo la otra.
En RSA, como se ha visto en los ejemplos, para cifrar se requieren los números (e,N), conocidos como 'clave publica' y para descifrar se
requieren los números (d,N), conocidos como clave privada.
Además existen dos números (p, q) que nos permiten conocer el numero (d) que es "la madre de la cordera" para descifrar el mensaje.
Asà que al propietario más le vale tener bien guardados (p,q) junto con (d) para que no le roben la cartera.
De la práctica con los ejemplos, se infiere que los números (p,q) deben ser primos muy grandes para aumentar el tiempo de cálculo, y
protegerse contra ataques de 'fuerza bruta'.
Otro inconveniente(?), es que RSA sólo puede cifrar números. Asà que para cifrar mensajes de texto (letras, números, signos de putua-
ción, etc.) es necesario traducir, previamente, el mensaje a números.
En el caso de datos de ordenador, no hay problema, ya que todos los caracteres, tienen un equivalente numérico (código ASCII).
Asà que los mensajes son considerados como un chorro de bits, que en el fondo no son más que números.
NOTA2.
El programa Nagra2Decrypter, creo que ofrece una opción CALCULATOR, que permite cifrar mensajes. El único inconveniente, es que
trabaja con numeración hexadecimal. De forma que si se desea trabajar con números decimales, será necesario utilizar la calculadora
Windows para traducir tanto las entradas como las salidas.
NOTA3.
Es muy posible que se hayan deslizado errores debidos a la ineptitud del mecanógrafo (yo). Asà que cualquiera que los detecte, serán
bienvenidos sus comentarios, para proceder a su corrección.
Igualmente, si alguna explicación parece poco clara o contradictoria, hacédmelo llegar y procuraré aportar más claridad, si fuese posible.
Saludos.