RSA, obteniendo clave privada

[LaiaxanIV]

Buenas gente!
Tengo un problema a la hora de obtener la clave privada a través de la clave pública.

Código (python) [Seleccionar] Expandir


from Crypto.PublicKey import RSA
import gmpy

pub = RSA.importKey("""-----BEGIN PUBLIC KEY-----
MIIBITANBgkqhkiG9w0BAQEFAAOCAQ4AMIIBCQKCAQAA0kl7JrOq0XcvkdpibzgA
x2kU/9bbd9FYS+yMqyMWTSTJOcB892YHCVtfRRdmUVJQXiWGQBq0mHmlMOREuHVb
RIBrsOPNeWl4s1bu3RfY+UdlVQh4b696RkjY+EZjAwDrAtP2GKZ8xuKcnGbeyOoq
SThjFxcwUpFyC6upDOhOy6pIVwIWe3DIlcuhHaw/963GN7fDJBzGr2cRunP3TYP6
4a7BtCNEVp8C4b5TaNJVb0jsrvRh5PHNlVMbCIRQGIzEn4l/X4y2sQfYCgV4Pwm7
Vq5gzxgKgjVIgItOHqs9WCmA0PuMqB2A2l0qU1JPiR7DEh2FwUUdLn+deuz3bHTB
AgMBAAE=
-----END PUBLIC KEY-----""");

n = long(pub.n);
e = long(pub.e);
print n;
print e;

p = 14188273085411836729;
q = 280615323801319888452039197798402115977;

d = long(gmpy.invert(e,(p-1)*(q-1)))
print d
key = RSA.construct((n,e,d,p,q));
print key.exportKey('PEM',pkcs=1);
f1 = open("rsa.pem","wb")
f1.write(key.exportKey('PEM',pkcs=1))

message = "Un mensaje cualquiera"
signature = key.sign(message,'')
print pub.verify(message,signature)


La p y la q las he obtenido usando el Sage, para conseguir factorizar el modulo. El último print da false, y si cifro un mensaje y lo descifro tampoco parece estar correcto. No se que puedo estar haciendo mal...
Espero que me podais ayudar. Gracias

[kub0x]

Buenas LaiaxanIV,

he hecho un code en C# como prueba para cifrar/descifrar un número cualquiera. He de decir que la construcción de la clave privada 'd' la he hecho a mano utilizando el concepto de la multplicativa inversa, sin emplear el extended euclidean (el cual yo recomiendo).

Para calcular la clave privada simplemente calculamos la inversa de 'e' en 'phi' ((p-1).(q-1)). Y me dirás, joe pero en tu método tienes que saber el totient de phi, phi((p-1).(q-1)), por lo tanto tienes que conocer la factorización de (p-1).(q-1). Claro, pero en este ejemplo es trivial calcularlo, porque son números pequeños, sino sería una locura, ya que tendríamos que conocer la factorización de 'n' y de phi(n).

Obtenemos 'd' de la siguiente forma:

d = e ^ phi(phi(n))- 1 (mod phi(n))
d = e ^ phi(phi((p).phi(q)))- 1 (mod (phi(p).phi(q))
d = e ^ phi((p-1).(q-1))- 1 (mod ((p-1).(q-1))

Código (csharp) [Seleccionar] Expandir


BigInteger p = 14188273085411836729, q = BigInteger.Parse("280615323801319888452039197798402115977");
BigInteger n = BigInteger.Multiply(p,q);
BigInteger phi = BigInteger.Multiply(p-1, q-1);
BigInteger phiphi = BigInteger.Parse("646779039649951876929832079791621951934669155860480000000"); //Calculado en http://www.numberempire.com/numberfactorizer.php simplemente multiplica el totient de p-1 por el totient de q-1 y tienes el totient del totient
BigInteger d = BigInteger.ModPow(65537, phiphi-1, phi);
BigInteger r = BigInteger.ModPow(BigInteger.Multiply(65537, d), 1, phi);
Console.WriteLine(r); //Comprobamos que la multiplicativa inversa se cumple e.d (mod phi(n)) = 1
BigInteger c = BigInteger.ModPow(12345, 65537, n); //Calculamos el ciphertext 'c'
BigInteger m = BigInteger.ModPow(c, d, n); //Recuperamos el mensaje original
Console.WriteLine(m);

Saludos!