Can RSA keys be swapped?

Question

On a theoretical level, is there anything inherently different about public vs private keys?

During RSA key generation there are two keys generated, key A and key B. Key A is private and Key B is public. Could key B be private and key A be public?

• Is the choice of which key to be private arbitrary?
• Would either key work equally well as the private with the other being public?
• Is there some mathematical property that necessitates key A is private?

I know that the on disk format is different and I can't just rename the files. But I'm talking about the raw binary key without any encoding, formatting or metadata.

Answer 1

In RSA there are three important components:

• A public exponent
• A private exponent
• A common modulus (used both with the private and public keys)

So, then, the public key consists of the public exponent and the modulus, while the private key consists of the private exponent and modulus.

But the way things are typically implemented, the public exponent is almost always 65537 (or 0x10001) -- the same value for every key. So only the modulus is unique.

You can see, then, how swapping the private and public key would be problematic here. If everybody's secret was 65537, that wouldn't be very secret. So instead we keep the less-easily-predicted exponent secret, and call that one the private key.

You can check your TLS certificate now in your browser that the public exponent is 65537:

Answer 2

Mathematically, an RSA key pair is a number n which is the product of two large probable primes p and q, and a pair of numbers (d, e) such that d × e - 1 is a multiple of (p - 1) × (q - 1). The numbers d and e are known as exponents (for a reason we'll see in a minute). There are a few more constraints but they treat d and e symmetrically. The public key is the pair of numbers (n, e) and the private key is the pair of numbers (n, d).

(Private key files often contain more than just n and d, but that's a matter of concrete format, and a matter of private key files usually containing the public key too.)

So in this respect, yes, RSA keys could be swapped.

However, the point of a public/private key pair is that one of the keys remains secret while the other is made public. The number n has to be used on both sides, so it's public. One of d and e — conventionally, the one written d — is kept secret and e becomes public. If d is to be kept secret, it must not be easy to guess.

The heart of the RSA operation is raising a large number (about as many bits as the key size) to the power of d or e. This is an expensive (slow) operation, so it is nice to choose d and e to make it not too slow. This entails making d and e small (or as a second-best having few bits set to 1 in their binary representation). However, if you make d small, you make it guessable by enumeration. So d, the private exponent, has to be large. On the other hand, e can be kept small; for mathematical reasons it has to be odd and cannot be 1, but 3 is a perfectly good choice, and the secondmost common one. For historical reasons, the most common choice of e is 65537, which is 10000000000000001 in binary.

Thus in an RSA key pair as is done in practice for good reasons, given the private key (n, d), one can find the public key (n, e) by guessing possible values of e (is it 65537? If not, is it 3? If not, try a few more small numbers.) For this reason, the public key and the private key cannot be interchanged.

Note that this is a property of RSA. Some other public key algorithms (such as DSA) have public and private keys which live in different mathematical spaces.

Answer 3

The description below applies to RSA public key cryptography. The public key is the pair (e, n) and the private key is (d, n), where n is a product of 2 huge prime numbers. e and d are multiplicative inverses.

Let x ^ y denote x raised to the y power mod n. All operations are performed mod n

Take message m, where m < n. As e and d are multiplicative inverses,

 (m ^ e) ^ d is equal to m
 (m ^ d) ^ e is also equal to m

So, there is nothing special about e or d as far as the mathematics is concerned. e, which is part of the public key, is a small number, typically 3 or 65537, and d, which is part of the private key, is e's multiplicative inverse and will be a huge random number. You want the private key to be a huge random number which cannot be guessed and the only way to get d is to factor n, which is computationally infeasible for large n.

You encrypt a message by computing (m ^ e). Call it c. You decrypt by computing (c ^ d) which will give you m. As e is much smaller than d, encrypting a message using RSA is much faster than decrypting it.

In fact, you go the other way when signing -- typically hash of the message is signed. h = hash(m) Compute s = (h ^ d) to get the signature of hash. You verify signature by computing s ^ e to get back h.