Are public key and private key interchangeable for RSA?

Question

On the one hand, I hear people saying that the two keys are totally interchangeable, the first one will decrypt what the second one encrypted. This makes me think that the two keys are interchangeable.

But on the other hand, RSA generated keys appear to have different length, and on another topic encrypting with a private key was called “signing” and was deemed less safe than encrypting with a public key. (2)

On top of that comes the idea that the private key should be kept undisclosed when the public key should be openly distributed in the wild. (3)

I planned to receive data from an unique server, so my idea was to keep a public key on that server to encrypt data, and distribute a private key to all the possible customers, but this goes against (3). Conversely, if I distribute public keys and encrypt my data with the private key, the encryption is less safe according to (2).

Should I distribute a public key and encrypt with a private one to satisfy (2) or the other way around?

NB: in my case, performance is not an issue.

Haig

No? Never distribute a private key – Devise

signing is not "less safe" then encrypting. – Areaway

Possible duplicate of public key for encryption; private key for de-cryption? – Filicide

Answer 1

Your public key is used to encrypt a message, your private one to decrypt it. Thus with the public key, which you distribute, anyone can encrypt a message safe in the knowledge that only you (or someone with your private key) can decrypt it. To answer your question directly, no they are not interchangeable. You should never distribute your private key.

If you want to share a key with multiple possible customers, then there are really two options. Either you abandon asymmetric cryptography and find a secure way to distribute a symmetric key, for use with something like AES instead of RSA, to each of them, or you ask each of them to generate a key pair and provide you with their public key. Then you can decrypt what comes from the server, and re-encrypt for each customer. The number of customers will help dictate your choice between the two.

Grady

It looks like the second method has a lot more overhead with decryption and re-encryption in the middle. – Klatt

Answer 2

The answer depends on whether you are asking your question out of mathematic curiosity, or for purely practical, cryptographic reasons.

• If you are implementing a crypto system you should never disclose your private key, so in this sense the keys are absolutely not interchangeable. Furthermore, the usage scenario you describe seems like a good match for authentication rather than confidentiality, so the message that is sent by the server to the clients should indeed be signed and not encrypted. If you need confidentiality as well, you need a few more steps in your protocol.

• From a mathematical point of view, the answer is OTOH "yes", presuming you use an internal representation of the private key that only contains the modulus N and the exponent D, and the other exponent E is generated randomly. The formula that describes the relation between the two exponents is 1 = E*D (mod phi(N)), so from a mathematical point of view it doesn't really matter which exponent is which.

But on the other hand, RSA generated keys appear to have different length

If you are using an implementation that produces RSA private keys that are significantly longer than the corresponding public keys, this almost always means the implementation is absolutely not suitable for using public and private keys interchangeably. The difference in length is usually due to a combination of the following:

• The public exponent E is not generated randomly, but is a small, fixed constant, such as 3 or 0x10001. The private exponent D will on the other hand be almost as large as the modulus, so the private key data will be almost twice the size of the public key data. If you only got a RSA private key (N,D), your first guess on the public exponent would be either of the values 3 or 0x10001, and it would be easy the check if the guess is correct. Should you want the keys to be interchangeable, the exponent you pick first has to be picked randomly as an odd integer greater than 1 and less than phi(N) and with no prime factors in common with N or phi(N).
• The private key data includes the factors P,Q of the public modulus N.
• The private key data includes the public exponent E.

Doit

Thanks for drawing the distinction between the math and the practical use of a real system. I've seen the topic presented both ways and it seemed contradictory since the distinction was not made. Also, I think some practical systems store the public key in a data file such that if you know the private key, you can extract the public key, leading some people to the conclusion that you can recreate a public key given a private key. – Fumble

@Fumble In some cases the information saved in the private key include the prime factors (P,Q) and the private exponent (D). This is enough to derive the public exponent (E). – Bonkers

Thanks very much for the excellent clarification. It seems that the explanations that claim that the keys in the pair are mathematically or functionally equivalent are not correct, at least in some implementations. – Fumble

@AlexV: The private key is NEVER disclosed. Signatures are meant to be generated using the private key. If you have used an implementation that does it backwards, you likely have a major security issue on hand. – Bonkers

@HenrickHellström I was taught that digital signatures are created by encrypting the hash of the plain text with the private key, then verified by decrypting the cipher text with the public key (also verifying the hash). Is this still how it is done when the second exponent is trivial? Thanks! – Thin

@AdamWinter What you were taught was an over-simplification. It is not really done that way, because real life encryption involves encoding the plain text prior to the public key operation, while signing involves encoding the digest prior to the private key operation. The decryption operation and verification operation will involve the respective decoding operations. If you try to generate a signature by encrypting with the private key, you will get the wrong encoding and the signature will be invalid. – Bonkers

@HenrickHellström I should have left the stuff about hashing out of the question. I get that there will also be an encoding standard for the PKI. My question relates to the original question here, regarding interchangeability/two-way-street of of the public and private keys. If I understand you correctly, in actual implementations, the second exponent is trivial and the public key is the modulus. Can you then decrypt, with the public key, something encrypted with the private key? Is that how a signature is verified in that case? Thanks again. – Thin

@HenrickHellström Looking further into this, I've now realized that you can "decrypt" your plain text (go the other direction) with the private key in order to get an output that the public key can "encrypt" to the get the original message. mathaware.org/mam/06/Kaliski.pdf – Thin

@AdamWinter As I tried to explain, what you describe is, at best, correct for "schoolbook RSA", but not for the kind of RSA that adults use in real life crypto-systems. If you e.g. try to pass raw plain text to a properly implemented RSA-PKCS#1 decryption function, you will not get some form of alternative cipher text, but an error message. (An error message of sorts, might be added, because production grade cipher systems might, or might not, in such cases be implemented to treat such input as an attempt from an adversary to perform a timing attack, and silently output garbage.) – Bonkers

So, no mathematical difference between two keys, in practice the much shorter key is used as a public key and the longer one kept private, many times when tools like openssl generate "private key" they generate material for both keys so both can be inferred. – Josi