0
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ You can use a python library to build up your key from the information you have. $\endgroup$ – ddddavidee May 28 '15 at 5:46
0
$\begingroup$

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-----
$\endgroup$
  • $\begingroup$ I accepted this one because there were good specifics and a key although I'm not sure if I should have given it to Bristol who answered more than adequately first. I couldn't get this key working, but someone else got it (here if anyone is interested: puzzling.stackexchange.com/questions/15424/…) $\endgroup$ – Quark May 29 '15 at 16:35
  • $\begingroup$ You'd still have to import it into gpg, which might mean signing it using openssl command to create a certificate or something, I know gpgsm can import PEM files but I don't know what other requirements there might be, or how you assign that key to a specific user ID, etc. $\endgroup$ – Steve Peltz May 29 '15 at 16:55
0
$\begingroup$
  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.

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