RSA para no iniciados

[tetiviri]

MUCHISIMAS MUCHISIMAS GRACIAS!!!
Me has hecho un favor enorme. ¿Me podrias explicar un poco como lo has hecho?

Lo dicho, ha sido todo un detalle que hayas respondido en cuestion de una hora.
Gracias!

[ghastlyX]

Primero factorizas n y obtienes p = 173 y q = 409.

Calculas d, tal que d * e (mod phi(n)) = 1. Recuerda que phi(n) = (p - 1) * (q - 1). Para calcular d hice este código en C:

Código (c) [Seleccionar] Expandir

#define E 19
#define PHI_N 70176 //(p - 1) * (q - 1)

#include <stdio.h>

int main()
{
    int i;
    for(i = 0; i < 70757; i++)
    {
          if(((i * E) % PHI_N) == 1) printf("d = %d\n", i);
    }
    return 0;
}

Una vez tenemos d = 7387, desciframos cada letra. Si llamamos c a la letra a descifrar y m la letra original, m = (c ^ d) (mod n). Así ya tendrás el mensaje descifrado en números:
{19, 20, 1, 20, 5, 13, 1, 14, 21, 9, 5, 14, 5, 20, 5, 7, 22, 19, 16, 17, 1, 19, 1, 17, 19, 9, 13, 16, 20, 20, 22, 6, 9, 3, 9, 3, 9, 5, 14, 21, 5, 13, 5, 14, 21, 5, 20, 7, 19, 1, 14, 4, 5, 20}

Así tan sólo te queda sustituirlo por las letras, que no tiene mucho misterio xDD. Hice este programa para que me lo hiciera solo si no te apetece hacerlo a mano:

Código (c) [Seleccionar] Expandir

#include <stdio.h>

int main()
{
    int i;
    char abc[] = " ABCDEFGHIJKLMNÑOPQRSTUVWXYZ";
    int cifrado[] = {19, 20, 1, 20, 5, 13, 1, 14, 21, 9, 5, 14, 5, 20, 5, 7, 22, 19, 16, 17, 1, 19, 1, 17, 19, 9, 13, 16, 20, 20, 22, 6, 9, 3, 9, 3, 9, 5, 14, 21, 5, 13, 5, 14, 21, 5, 20, 7, 19, 1, 14, 4, 5, 20};
    for(i = 0; i < 54; i++) printf("%c", abc[cifrado[i]]);
    return 0;
}

Para hacer el paso de descifrar tendrás problemas con elevar a d según qué métode utilices. La calculadora de Windows sorprendentemente parece que lo realiza bien, yo utilizo un sistema de cadenas para estas cuentas tan bestias.

Un saludo de ghastlyX

[cccp2006]

Hola chicos primero muchas gracias por las aportaciones sobre rsa me han ayudado mucho. He tenido problemas con la precisión y errores de desbordamiento cuando trabajaba con exponentes muy grandes. Por si acaso alguien ha tenido el mismo problema, lo he resuelto de la siguiente manera:
Por ejemplo
18^23 mod 55
es equivalente a: (18^5*18^5*18^5*18^5*18^3) mod 55
Haciéndolo así no me da el error de desbordamiento y la precisión es buena.
Por aportar algo aunque debe ser una chorrada.
Un saludo.

ejemplo para sql server
El resultado correcto es 2
Select (power(18.0,23.0)) % 55 en este caso me da 5
Select power(18.0,5.0)*power(18.0,5.0)*power(18.0,5.0)*power(18.0,5.0)*power(18.0,3.0))% 55 este me da 2 que es correcto

[garc]

No he querido abrir ningun post para este tema porque creo que esta muy extendido y a la vez reducido, como bien pone para principiantes (mi caso), aun no controlo el tema pero.. resulta que como bien dice el compañero del post anterior, cuando elevo 18 a 23 al recorrer el modulo 55 me devuelve como resultado 12. Lo cual no corresponde con el resultado correcto. Alguien puede aclararme esto? mi hipotesis es que el pc *se folla la mente*. No me refiero al pc en si, se que tiene capacidad para eso y mucho mas, pero en mi caso lo he hecho mediante java con la clase Math.pow(18,23) divido 55 el resto me devuelve 12. 

[kub0x]

Buenas noches,

el método equivalente a la hora de trabajar con exponenciales modulares es ModPow. En Java debería encontrarse en la clase BigInteger. Por lo que veo 18^23 tiene 95 bits quzia algo se está desbordando.

Aun así compañero, si tratas de obtener 18^23 mod 55, te recomiendo que hagas potencias de 18 y cuando el resultado sea mayor que 55 haces el módulo y sigues multiplicando por 18 al módulo obtenido:

18*18 es mayor que 55 por lo tanto haces el mod, que da 49, ahora 49*18 mod 55 y así 23 veces. Hay mejores métodos si te interesa busca por Modular Exponentiation.

[garc]

Gracias de antemano, ya pensaba que tenia que iniciarme en otro lenguaje que no se desbordara con esos productos. Probaré tu método, seguiré bicheando.