Can I get a public key from an RSA private key?

Question

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:

can I get a public key?

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 09:39
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
@basic6 "Here is the key to my house. How do I make me a lock for it?" — user, Oct 27 '17 at 14:34
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 -cautiouslyoptimistic-, Oct 27 '17 at 20:11
@chrylis I think they have given the representation they're asking about. — ivan_pozdeev, Oct 27 '17 at 22:18
Same question on StackOverflow: [Given a private key, is it possible to derive its public key?](https://stackoverflow.com/questions/696472/given-a-private-key-is-it-possible-to-derive-its-public-key/696545) — sleske, Oct 28 '17 at 11:42
@MichaelKjörling: it's probably safe to post the key to your house if you're `user162408`... unless you also post identifying information somewhere else... — user541686, Oct 28 '17 at 20:57
@Mehrdad The set of all leaked keys is smaller than the set of all keys... so trying keys from the set of leaked keys first is a good idea. If the key is in there, you've saved time. If not, you haven't lost any as you would've needed to try those anyway. — wizzwizz4, Oct 29 '17 at 17:00
@SteffenUllrich's answer explained the question, and here is a similar question: https://stackoverflow.com/questions/5244129/use-rsa-private-key-to-generate-public-key — bearzyj, Jun 19 '19 at 11:06
Yes you can. https://devopslife.io/recovering-ssh-public-key-with-the-private-key/ — Unnikrishnan, May 23 '20 at 15:50
Related: https://crypto.stackexchange.com/questions/45151/anatomy-of-an-rsa-private-key — mti2935, Feb 17 '21 at 17:08

Steffen Ullrich · Answer 1 · 2017-10-28T12:15:41.613

74

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:
(…)

edited Oct 28 '17 at 12:15

answered Oct 27 '17 at 06:40

Steffen Ullrich

184,332
29
363
424

As an extension, it is highly difficult or impossible to find the private key for a given public key, since that is the basis of the security symmetric encryption is supposed to provide, right? Just thinking how this is slightly asymmetric in a way, and how those technical details are constructed. – Pysis Oct 27 '17 at 13:29
28

@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
The 'finding' part was tangential, and meant as background, highlighting an overview of symmetric key encryption. I think you still answered my question, as the data is in the compound file format, not in the key data itself. Thanks. – Pysis Oct 27 '17 at 14:14
3

@Pysis This is *asymmetric* encryption. – user207421 Oct 27 '17 at 17:24
Ok, I may not have the security terms correct, but at least the sentiment was carried through. – Pysis Oct 27 '17 at 19:11
2

@Pysis Yes, asymmetric encryption is "slightly asymmetric". – user253751 Oct 28 '17 at 02:59
1

@SteffenUllrich That sentence should be part of your answer – Bergi Oct 28 '17 at 11:10
@SteffenUllrich: I just want to point out that this is wrong: *"In the public key file instead all information regarding the private part are missing."* If only the private key can decrypt data encrypted with the public key, then clearly the public key needs to "know" everything the private key knows. (Any "extra" information cannot help the private key decrypt anything encrypted by an entity who never had that information!) The problem is that extracting the information into a useful form requires you to first break RSA. What need *not* be true is for the public key to be in the private key! – user541686 Oct 28 '17 at 21:01
1

@Mehrdad: Either I don't understand your argument or you don't understand asymmetric encryption like RSA. The idea is that you can encrypt data with one information (public key) but need __different__ information for decryption (private key). Thus, the public key does not need to contain and should not contain the secret information on how to decrypt, i.e. it should not have all the information of the private key. – Steffen Ullrich Oct 28 '17 at 22:51
@SteffenUllrich: n = pq... meaning you can just factor *n* (public) to get back *p* and *q* (private)... – user541686 Oct 28 '17 at 23:17
@Mehrdad: There is no *"__just__ factor"* - What you assume here to be a simple issue is exactly the problem which is considered very hard to solve (i.e. possible but takes long time) and which is what makes RSA secure in the first place. See [Wikipedia: RSA problem](https://en.wikipedia.org/wiki/RSA_problem): *"The most efficient method known to solve the RSA problem is by first factoring the modulus N, a task believed to be impractical if N is sufficiently large."* – Steffen Ullrich Oct 29 '17 at 07:06
@SteffenUllrich: yes, and it seems like you didn't understand my first comment, as now you're just repeating part of it back at me (specifically the 2nd-to-last sentence about breaking RSA) while not understanding the rest of it. Read my comment again, and do it *carefully*. Look up the term *"information-theoretic security"*. You're familiar with *"computational security"*, which is **NOT** the same thing. There is a crucial difference between some information *not existing* and that information being merely *difficult to process*. This difference is exactly what I was pointing out to you. – user541686 Oct 29 '17 at 07:24
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 07:50
@immibis That statement was before it was clarified how the public key data was found, that the key data and file structure were distinct, one having more information than the other. – Pysis Oct 29 '17 at 14:24
" It is simple that all information needed for both the private and the public part are stored in the private key file" Private key consists from the module and the private exponent. Public key consists from the same module and the public exponent. In most known implementations the public exponent is 65537. Thus logically, if you have the private key and know the public exponent of 65537 you also have the public key. – Andrew Savinykh Oct 29 '17 at 19:47
@AndrewSavinykh: the public exponent is also contained in the private key file as shown in the answer (output of `openssl rsa -text`). – Steffen Ullrich Oct 29 '17 at 20:07

Ilmari Karonen · Answer 2 · 2017-10-27T19:26:07.337

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 2¹⁶+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 d_p = d mod (p − 1) and d_q = d mod (q − 1), and
the "CRT coefficient" q_inv = q⁻¹ 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
@HagenvonEitzen: The last paragraph is talking about the (nonstandard) usage case where e is neither public nor small. — R.. GitHub STOP HELPING ICE, Oct 27 '17 at 19:15
@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
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
Good explanation! But still not clear is it safe to assume the public key will not be deduced from only knowing the private key. — Kos, Sep 18 '21 at 10:06
@Kos: I though the bolded sentence at the top answered that pretty clearly: no, it's not safe to assume that. (At least not unless you go to extreme lengths to make it safe, as described in the rest of the answer, in which case you presumably also know how to analyze the security properties of your modified RSA scheme yourself. If you can't do that, then no, it's still not safe.) — Ilmari Karonen, Sep 18 '21 at 12:21

sudhackar · Answer 3 · 2017-10-27T14:40:25.257

5

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

edited Oct 27 '17 at 14:40

answered Oct 27 '17 at 06:34

sudhackar

248
1
9

15

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 08: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 08: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
@Gilles I didn't mean "the smallest amount of information that is useful", I meant "the information that has the least usefulness" with the restriction that it should still be feasible. I apologise for the ambiguity of my previous comment - I was trying to stay within the 500 character limit. – wizzwizz4 Oct 29 '17 at 19:21
@wizzwizz4 "private keys are usually stored as a tuple *which contains the **private** key*. There is no need to calculate the **private** key"? O.o If you meant "public" in the latter two instances, then that's largely the point of the top answer - the info is already there, all you need to do is output it in a useable format. Gilles's point as I understand is this: either the info derived in this answer is already available (in the tuple commonly stored), or difficult to derive (with the absolute minimum required in a private key). In neither case is this answer useful. – muru Oct 30 '17 at 04:56
@muru I did mean public. And this answer _isn't_ practically useful in the situation stated by the question, but it _is_ useful in that it provides insight into a property of the values used in the keys. – wizzwizz4 Oct 30 '17 at 16:55

score 2 · Answer 4 · answered Feb 17 '21 at 14:16

2

if you need it for ssh use this command

ssh-keygen -y -f private_key.pem

answered Feb 17 '21 at 14:16

Ahmed Abdelazim

121
3

Can I get a public key from an RSA private key?

4 Answers4

Linked