# Constructing RSA private key, given public key

As part of a puzzle I was given an RSA 256-bit public key and an encrypted message.

The key itself is very weak, having exponent e = 65537 and modulus N = 00:c0:fb:55:b3:ed:f5:19:bf:8d:3a:2a:60:e8:bc:6e:1c:94:f0:5c:17:19:f8:38:ff:45:0b:01:0f:47:96:27:fb

I can determine p and q by using an arbitrary precision library and iterating through until I find something that satisfies N mod p = 0, and then get q = N/p

From there it's straightforward to get phi = (p-1)(q-1) and to calculate d = e^-1 mod phi

My question is this: Given d and N, how do I actually construct the private key as binary data suitable for use with e.g. openSSL?

-
For the factoring part, I'd use gmp-ecm. –  fgrieu Nov 29 '12 at 7:53
@fgrieu: Do you happen to know if in this case (assuming $N$ is product of two 128-bit primes) the elliptic curve method is more efficient than the number field sieve? –  j.p. Nov 29 '12 at 8:15
@jug: no, I do not know. But GNFS implementations have a reputation to be complex to use and setup, when gmp-ecm is an easy to use ECM implementation that will do the job, and even comes as an ubuntu package. –  fgrieu Nov 29 '12 at 11:25