# 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

OpenSSL private key format, for RSA, follows the ASN.1 syntax given at the end of PKCS#1 (the structure is then encoded with DER, then Base64, and PEM header and footer lines are added). This is easy if you know these formats, but, in practice, you will be happier if using a library which does the encoding for you. For instance, OpenSSL (the library) lets you create a private key as a bunch of big integers (because that's what a RSA private key is -- again, read PKCS#1).

That being said:

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

I hope you are patient !

(Hint: read this. Factoring a 256-bit integer is feasible, but not immediate. You'll need a bit of computing with a smart algorithm like quadratic sieve.)

-