4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ For the factoring part, I'd use gmp-ecm. $\endgroup$
    – fgrieu ♦
    Nov 29, 2012 at 7:53
  • $\begingroup$ @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? $\endgroup$
    – j.p.
    Nov 29, 2012 at 8:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu ♦
    Nov 29, 2012 at 11:25

1 Answer 1

Reset to default
8
$\begingroup$

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.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.