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:

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

2 Answers 2


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

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

  • $\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
    Commented May 29, 2015 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$ Commented May 29, 2015 at 16:55
  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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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