3

So, I got this problem and I have no clue how to solve it.

I have an RSA private key with a part of it censored.

$ cat key.pem
-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQDGlcensoredcensoredcensoredcensored1TUxhnjkCbowxZc
7PIpI1E2Po6aIgCBd9+6i0NUIfYm8vR6kqiqLz8k8o4LYoBkq/9Jx7pgV2Jqhr4u
wvlaQQUzi9c4qPKXp+QGoUu9f1zp8ORIMpeJmF7uA20DC93uba07qdC6twIDAQAB
AoGBAIovDuYnGiiQS6K27L4EY8e/5sbqAwdlTOVlWsfz+ai3DLNiFPSbbT1Wx9G4
4b06X6O258SD1suZ/g/ICnmnxxe5ua3a5+iiDIwGYmBDcNfq5gMq/d+1/UJF/Bb4
A1nuH2iUg6gRTPEpbg2+RYwquyWenFbqfHMgXqbHVGmOXj7hAkEA8rChKjs5zVmd
j9Gk53psry4CtuxRc39NrHuLqat9Iu0MA51Sgv4c+8dgo75DVAnT5PoLBhHJJAVa
e+rUMC4kfwJBANF7jcKzJ2UuPmL6JpbWcyirybjMIm2eCxR5U1bYlNYT+A49oOFS
Eg5woswgCyH9gDPk2Zwpq3qud9HD7Rn0bckCQQDHgwdrRXc2ZybN1eZAWffBaAzZ
PpuTXKOJWaOuX4mnTcLjsdDkWW2QWw8Kbd7B1rZ49kpbugFmeHQzjRDVbwmXAkBm
T3nFBcrP1+4QWSxPrx0/V+eFoe2OrAmtTjQtzkmi5M3Z5q+UXIkFFG3uVBgb2bur
nLHLW26s1Fkg0hgS/RZBAkAFnE+7QvRCW4+v3OsIkN63f+GIjHfCuv8L15RpBLlf
XXQyOmmu8YekTu5vbFHtSAiLyuW1yCeSsNmKYkX6Ew99
-----END RSA PRIVATE KEY-----

As you can see, the first part line is partially censored. The task is yo decrypt this message:

Qe7+h9OPQ7PN9CmF0ZOmD32fwpJotrUL67zxdRvhBn2U3fDtoz4iUGRXNOxwUXdJ2Cmz7zjS0DE8
ST5dozBysByz/u1H//iAN+QeGlFVaS1Ee5a/TZilrTCbGPWxfNY4vRXHP6CB82QxhMjQ7/x90/+J
LrhdAO99lvmdNetGZjY=

My first guess would be to bruteforce the part missing, but that doesn't seem realistic to do.

Anyone know if this is even possible? And if so how would you go about to do it? The key is 824 characters long and the censored part is 32 character, however I do not know if each character of the censoring corresponds to one in the private key...

user3080544
  • 33
  • 3
  • You need to learn the encoding (ASN.1) and figure out what is censored first. If it's just a public prime then there are relatively few of those in use and it will be quick. – Thomas M. DuBuisson Dec 08 '13 at 19:12
  • Do you have the *public key*? Brute-forcing would mean that you would have to try $2 ^ 192$ possibilities, which I do not advice :P – Maarten Bodewes Dec 08 '13 at 19:23
  • @owlstead No I do not have the public key :( And yeah, I kind of suspected that that would be dumb :D I have looked at https://polarssl.org/kb/cryptography/asn1-key-structures-in-der-and-pem and some other explanation, but I can't seem to find a good break down of the different parts of the key.. – user3080544 Dec 08 '13 at 19:32
  • Just try brute force recompose that PEM format private key. If that fails, It falls back to the same protection level as not knowing the private key at all. (That may still cost you life time to complete). – Ken Cheung Dec 08 '13 at 19:33

1 Answers1

4

You can solve this using an online ASN.1 parser (or openssl asn1parse), where you will find out that the base 64 string - the text in the middle, between the lines starting with --- - is an ASN.1 encoding of the private key. The second element within the SEQUENCE - which has been altered - contains the modulus, not the private exponent. The structure is defined in PKCS#1, which is a rather readable standard, also copied in RFC 3447

The modulus is normally public, but if you haven't got the public key, you can still recreate it: How to factor RSA modulus given the public and private exponent?

Community
  • 1
  • 1
Maarten Bodewes
  • 90,524
  • 13
  • 150
  • 263
  • Nice, thanks. So what I need to do now when I have e,d, p and q. To recreate m and encode it again? And then replace it in the key and decrypt it? – user3080544 Dec 08 '13 at 20:22
  • Yes, recreate *n*, the modulus, just as you described. Normally *n* is used for the modulus, but always expect differences in notation. – Maarten Bodewes Dec 08 '13 at 20:23
  • Do you have any tips on doing this? When I recreate n, by multiplying p and q the numbers are so large that I have problems with converting to hex. Tried doing it directly with the hex numbers but I end up with a 1059 bit representation. The result should be 1024 bit right? – user3080544 Dec 08 '13 at 21:14
  • Yes, the modulus is always the same as the key size. I haven't tried the proposed solution, I just knew what to look for... Try crypto.stackexchange.com if you have trouble with the algorithm itself, or try a separate question here posting your current code. Note that the given modulus should contain enough correct bits to verify the results using a binary compare. – Maarten Bodewes Dec 08 '13 at 21:25