Decrypt RSA message with part of private key censored?

Question

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

Answer 1

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?