47

As far as I remember you encrypt the message using public key and decrypt it using private key. My question is whether it is possible to get a public key from an RSA private key. For example if I have a key like this:

-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQCtrKVnwse4anfX+JzM7imShXZUC+QBXQ11A5bOWwHFkXc4nTfE
Or3fJjnRSU5A3IROFU/pVVNiXJNkl7qQZK5mYb8j3NgqX8zZJG7IwLJ/Pm2sRW5Q
j32C/uJum64Q/iEIsCg/mJjDLh1lylEMEuzKgTdWtoeLfxDBL2AJ20qXzQIDAQAB
AoGBAKNXi0GpmjnCOPDxLFg5bvQVfhLSFCGMKQny1DVEtsfgZmbixv5R2R41T4+d
CHJMdEsUFFJ6I7CRLTcg1SDU8IhcAWCBRSNeVuomCHlQG16ti8HxwhiwIcjvDz/z
NC2sL5ZJ2eJnhbtXLdf6pxxO1pA5vLp1AX06IaETO977XvupAkEA+ZgtGZybyUkf
tEA3ekXc5eLoW+zgU0C1fATWcIZ8Iq5YV1BW+3oAzf8HgIbkQh4LM2qa6An3l+vW
NXR4wICHkwJBALIhrcdJqKw36qiyenq+m78klp5SnurQifVt0Sy1GMWyOUqYz5jK
t9sGo9Qn6GDuYe/XGXKWQW25PkEYXxxPPx8CQQCpICyvRidp5VrOURVGjUB5pZ+9
am02/In9V2nXJcnH1kuWHqJSFQGmlEEJHl5dTu5YEMyWnupezzd/UUThbDZxAkAz
TNO5QxNalbf04YG4e9Bq2eSur+iog2pXzkqhb3404UDypNOUkz0jzOO9o8ieschu
xCnGAFPTf7fYE2bAxmnNAkEA0/3bdsvJclquypqP9CQeQnxGwQtWz6+yn07gj3U1
V19mdeKCUZWklRarrcr67u9DdEx+JowyEY/ppzgeQtW01g==
-----END RSA PRIVATE KEY-----

can I get a public key?

  • 122
    This key is now leaked to the internet and no longer safe for use outside of examples, just so you realise that. – LvB Oct 27 '17 at 9:39
  • 15
    "Here is the key to my house. Who wants to make a copy?" – basic6 Oct 27 '17 at 10:12
  • 56
    I would hope that the OP generated an example key just for use in this question and then immediately disposed of it. – Baldrickk Oct 27 '17 at 11:31
  • 46
    @basic6 "Here is the key to my house. How do I make me a lock for it?" – a CVn Oct 27 '17 at 14:34
  • 2
    You need to clarify whether you're asking about just the private key (in which case the answer is no) or the private key file, which by convention (as here) includes both keys. – chrylis -on strike- Oct 27 '17 at 20:11
63

can I get a public key?

It's easy using openssl rsa:

$ openssl rsa -in the-private-key-from-your-question.pem  -pubout
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCtrKVnwse4anfX+JzM7imShXZU
C+QBXQ11A5bOWwHFkXc4nTfEOr3fJjnRSU5A3IROFU/pVVNiXJNkl7qQZK5mYb8j
3NgqX8zZJG7IwLJ/Pm2sRW5Qj32C/uJum64Q/iEIsCg/mJjDLh1lylEMEuzKgTdW
toeLfxDBL2AJ20qXzQIDAQAB
-----END PUBLIC KEY---

If you want to get an idea of what is contained in a key file, you can pass the -text option to see a human-readable (sort of) debug dump. This way you can see that a key file contains both private information but also the public information. Especially it contains the modulus and publicExponent which fully describe the public key:

$ openssl rsa -text -in the-private-key-from-your-question.pem
Private-Key: (1024 bit)
modulus:
    00:ad:ac:a5:67:c2:c7:b8:6a:77:d7:f8:9c:cc:ee:
    29:92:85:76:54:0b:e4:01:5d:0d:75:03:96:ce:5b:
    01:c5:91:77:38:9d:37:c4:3a:bd:df:26:39:d1:49:
    4e:40:dc:84:4e:15:4f:e9:55:53:62:5c:93:64:97:
    ba:90:64:ae:66:61:bf:23:dc:d8:2a:5f:cc:d9:24:
    6e:c8:c0:b2:7f:3e:6d:ac:45:6e:50:8f:7d:82:fe:
    e2:6e:9b:ae:10:fe:21:08:b0:28:3f:98:98:c3:2e:
    1d:65:ca:51:0c:12:ec:ca:81:37:56:b6:87:8b:7f:
    10:c1:2f:60:09:db:4a:97:cd
publicExponent: 65537 (0x10001)
privateExponent:
(…)
  • 24
    @Pysis: this answer is not about "finding" the public from the public key. It is simple that all information needed for both the private and the public part are stored in the private key file. In the public key file instead all information regarding the private part are missing. – Steffen Ullrich Oct 27 '17 at 13:37
  • 3
    @Pysis This is asymmetric encryption. – user207421 Oct 27 '17 at 17:24
  • 2
    @Pysis Yes, asymmetric encryption is "slightly asymmetric". – user253751 Oct 28 '17 at 2:59
  • 1
    @SteffenUllrich That sentence should be part of your answer – Bergi Oct 28 '17 at 11:10
  • 3
    @Mehrdad: in the context of real world information security anything which is practically infeasible is considered infeasible. Information-theoretic security is irrelevant here since it assumes unlimited computing power which simply does not exist. Thus all information regarding the private part are missing should be read as all information which make it possible in practice to derive the private key are missing. – Steffen Ullrich Oct 29 '17 at 7:50
26

In practice, yes, you can get the public key from the private key. In principle, it would be possible to create an RSA private key from which the corresponding public key cannot be easily obtained, but this would require using both a non-standard key generation method and a non-standard private key storage format.


Let's quickly review the basics. An RSA public key consists of two values:

  • the modulus n (a product of two secretly chosen large primes p and q), and
  • the public exponent e (which can be the same for many keys and is typically chosen to be a small odd prime, most commonly either 3 or 216+1 = 65537).

An RSA private key, meanwhile, requires at a minimum the following two values:

  • the modulus n (same as in the public key), and
  • the private exponent d (calculated from the public exponent e and the factors p and q of the modulus).

However, most formats for storing RSA private keys, including the PKCS1 RSAPrivateKey format shown in your question, actually store a bunch of additional values as well, including:

  • the public exponent e,
  • the factors p and q of the modulus,
  • the reduced private exponents dp = d mod (p − 1) and dq = d mod (q − 1), and
  • the "CRT coefficient" qinv = q−1 mod p.

In particular, the inclusion of the public exponent e in the private key format means that the public key can be trivially extracted from a PKCS1 compliant private key file. Also, even if the public exponent e was not included in the private key file, knowing the factors p and q of the modulus allows either exponent to be easily calculated from the other. And, finally, even if we didn't know the factors of the modulus, for RSA keys generated in the usual way we could simply test the most commonly used values of e and see which one of them generates ciphertexts that can be correctly decrypted using the given private key.


All that said, if we were to use a non-standard RSA key generation algorithm that chose e (or d) randomly from the admissible range of values (i.e. the integers greater than 1 and less than and coprime with λ(n) = lcm(p − 1, q − 1)), and if we used a non-standard RSA private key format that only stored the bare minimum information for decryption (i.e. n and d), then it would not be possible to calculate the public key from the private key without effectively cracking the key (i.e. factoring the modulus).

Indeed, if used in such a non-standard manner, the RSA algorithm becomes "symmetric" in the sense that neither of the keys (n, e) and (n, d) can be effectively computed from the other and either one could be arbitrarily designated as the private key. In principle, if you didn't let the private key holder know the corresponding "public" key (which, of course, means it wouldn't really be public any more), then they could only decrypt messages but not encrypt them. Alas, the practical usefulness of any such scheme is rather limited by the simple fact that whoever generates the key pair will inevitably end up knowing both halves of it anyway.

  • I frown about the last sentence. As e is considered public anyway, not forgetting e (and p and q) can hardly be considered a back door available to the owner of the private key. (And if an adversary obtains the private key d, they also have the public key e and won) – Hagen von Eitzen Oct 27 '17 at 18:20
  • 1
    @HagenvonEitzen: The last paragraph is talking about the (nonstandard) usage case where e is neither public nor small. – R.. Oct 27 '17 at 19:15
  • 2
    @HagenvonEitzen: Indeed, I mentioned that issue in the linked crypto.SE post. Any scheme that relies on the "public" key not being derivable from the "private" key must necessarily keep the "public" key secret from at least some parties (and thereby violate one of the standard assumptions of public-key crypto) for that feature to be of any use. But I can see how that paragraph may have been misleading; hopefully the rewritten version is at least a little bit clearer. – Ilmari Karonen Oct 27 '17 at 19:25
  • 2
    RSA has an interesting mathematical property that decryption uses the same formula as encryption, just with d instead of e. Thanks to this, you can swap e and d (i.e. use the private key for encryption and the public one for decryption). Then you get the electronic signature scheme. – ivan_pozdeev Oct 27 '17 at 22:14
4

Yes. It's quite easy too. If you look at RSA specification, a public key needsn and e. A private key might have p q d. Use these to calculate.

n=p*q
e=mod_inverse(d,euler_totient(n))

If you want to pack them to a PEM format back see https://github.com/ius/rsatool

  • 11
    Framed as a mathematical answer, this is wrong. A private key could have only n and d, and from that, it is impossible in general to calculate e. It's usually possible in practice only because e is almost always selected among a handful of values. Framed as a practical answer, this is wrong: e is, in practice, always included with the other parameters (at least n and d, usually also the parameters needed for CRT-based calculation). – Gilles 'SO- stop being evil' Oct 27 '17 at 8:45
  • 2
    Agreed, but practically RSA with CRT private keys are usually stored as a tuple of (n, e, d, p, q, dP, dQ, qInv) which is the case here. I was jut trying to set the components mathematically. – sudhackar Oct 27 '17 at 8:57
  • 1
    Yes: practically, private keys are usually stored as a tuple which contains e. There is no need to calculate e. – Gilles 'SO- stop being evil' Oct 27 '17 at 16:54
  • @Gilles From the post: "a public key needs n and e." and from sudhackar's comment: "but practically RSA with CRT private keys are usually stored as a tuple of (n, e, d, p, q, dP, dQ, qlnv)", which leads me to the conclusion that practically, private keys are usually stored as a tuple which contains the private key. There is no need to calculate the private key, thus making this entire question and all of its answers irrelevant. I don't understand your most recent comment. sudhackar's answer is showing how to find the set of possible public keys from the least useful information possible. – wizzwizz4 Oct 29 '17 at 17:12
  • @wizzwizz4 If you have p, q and d, you have more than the least useful information possible for a private key. I've never seen private keys with p, q and d but not n and e. You need n to do anything useful with the key and storing p and q instead of n doesn't gain any storage. – Gilles 'SO- stop being evil' Oct 29 '17 at 18:18

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.