How to decrypt a PGP message with only the two primes and the public exponent?

Question

I'm trying to decrypt a PGP Message that is encrypted with an RSA key, but I only have this information:

Public exponent: 65537

Prime 1: c447376fcf2a4d4f03840c83f68b23202f081f8561a1f0295703df258a96b8fd6cc8cb307558d60cbd692a45ed2414370349e28badf0f180419fc1df2cd87e99

Prime 2: d876bd7c4963b8c06f148da504d1f7c7b9b20a719a0d3788eacc7effa7acb9cc200ef3a18a29fb5c733d45e04104ef3e7fc77f3ec847526b0c5d50506a2f471b

It seems when generating a key, the primes are automatically generated so I can't find any tools online that will help me any.

Here's where I'm currently at:

~$ gpg -d green.gpg.asc
gpg: encrypted with RSA key, ID 00000000
gpg: decryption failed: secret key not available

The end goal is I'd like to create a key that can be imported which would then allow the above command to decrypt the message.

Here's the file I'm trying to decrypt for context:

• green.gpg.asc (492k)

Answer 1

Using a bignum library such as OpenSSL, you can calculate everything very easily.

Create a new RSA structure using RSA_new(). Convert the hex strings to BIGNUMs using BN_hex2bn(), storing them in rsa->p, rsa->q and rsa->e.

Calculate p-1 and q-1 into temporary variables using BN_copy() and BN_sub_word(). Multiply those two into a third temporary variable using BN_mul().

Now calculate
rsa->d = $e^{-1} \mod (p-1)(q-1)$ using BN_mod_inverse().

Calculate
rsa->dmp1 = $d \mod (p-1)$ and
rsa->dmq1 = $d \mod (q-1)$ using BN_mod().

Finally, calculate
rsa->iqmp = $q^{-1} \mod p$ using BN_mod_inverse()

You can verify that everything is correct with RSA_check_key(), it should return 1.

Now print it out using PEM_write_RSAPrivateKey() (pass NULL or 0 for all the arguments after the first two).

-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQCl9yDhwwZY1O2wkqgRl0Aben8sYiTvZBG43yRszEkm7u1Ku3Vt
zSlLaLWeeCTmv0aRfBNUrQUPDeC+62G3U32DS/ITFeHksVw+hHFeHsygb934in0T
mqwixHloW4ObRvhGTOdm2+j+TmWkxrbnK/rI9rLdkKtE7Z8P9Zf0XgjJIwIDAQAB
AoGAf0aFBf19GZS5b4cYstzOQgRwEMZ3UsroOGGP2ovTsbLbcUtPY9RJTdZQKeYz
Tm3znVCMtow1a/UVnPSALIovnsuQ6WzcRcX6kAweL1csiDfaoGp/i0qHd40MO5Oq
T/OdnYY2h+p5xQZF3KLgO7IFoA72ESjQuBRQkXmYhG6k3VECQQDERzdvzypNTwOE
DIP2iyMgLwgfhWGh8ClXA98lipa4/WzIyzB1WNYMvWkqRe0kFDcDSeKLrfDxgEGf
wd8s2H6ZAkEA2Ha9fEljuMBvFI2lBNH3x7myCnGaDTeI6sx+/6esucwgDvOhiin7
XHM9ReBBBO8+f8d/PshHUmsMXVBQai9HGwJAAsRuR6lIE2b1ybrTcXpsuFtxZeBf
jATy0ENBtinKDjmkewBCYqUp/2v8O5hYy5VtYSJ9izKcnwsL4dC98MfsoQJBANCN
poamlsOb8+nThpgcTCRLzzOsvAXb6bh/CiT6wbnI52JAbPUW+azbAr/eDgbZElg+
N2Sfxcesh58oEDIeFt0CQQDAYdUF25f4KIrAPPoP+RXrAFftdiMwKBCkSn8a2UqJ
BZW74QQon+lkRV94BDVUPoowHLBPLaIImhTrv+bXHzX9
-----END RSA PRIVATE KEY-----

Answer 2

1. Look up the OpenPGP secret key format (some kind of ASN.1 I think?).
2. Use your favourite bignum implementation to multiply p by q and store this as the modulus n (in the correct format).
3. To calculate the decryption exponent, you need $d$ such that $ed=1 \pmod{(p-1)(q-1)}$. This can be found with the extended Euclidean algorithm (the wikipedia pages for RSA and the Euclidean algorithm explain the details) - you're probably going to end up implementing this in your favourite bignum library too.
4. Store $d$ in the secret key file you're building, import it into gnupg and decrypt normally.

Depending on what programming languages you know, there may be shortcuts - instead of building a key file you might be able to build a key data structure directly and use your language's gnupg/libgcrypt wrapper to work with that.