Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
@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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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