Is it possible to correct the exponent of an RSA public key if it has been altered?

Question

Is it possible to change the exponent of an RSA public key?

Answer 1

Yes, it is possible to change the public encryption exponent of an RSA key.

Indeed, this requires no special computation. An RSA public key consists of two numbers: the modulus $n$, which is a product of two large (secret) primes $p$ and $q$, and the encryption exponent $e$, which is usually a small fixed prime (most often, 3 or 65,537 = 2¹⁶+1). If you want, you can simply pick (almost) any other exponent instead of $e$ and encrypt with it.

(You'll have to somehow let the owner of the key know which exponent you used to encrypt the message, but that's easy enough to solve: since the encryption exponent is public information, you can simply send it alongside the message.)

Of course, in order to decrypt the message, the recipient needs to know the corresponding decryption exponent $d$. If they kept the original primes $p$ and $q$ used to calculate the modulus (which most RSA private key formats do store, if only because knowing them allows the use of more efficient decryption algorithms), then they can easily calculate the correct decryption exponent $d^*$ for any valid encryption exponent $e^*$ simply by taking the modular inverse of $e^*$ modulo $\lambda(n)$ $=$ $\operatorname{lcm}(p-1, q-1)$, just like they calculated the original decryption exponent when they generated the RSA key pair. Indeed, even if the recipient only knows the modulus $n$ and the original public and private exponents $e$ and $d$, they can use the fact that $ed \equiv 1 \pmod{\lambda(n)}$ to factor the modulus and then proceed as above.

All that said, not quite every encryption exponent is valid. Obviously, the choice $e = 1$ would be totally insecure, since the encrypted message would just be identical to the decrypted one. Slightly less obviously, in order for the modular inverse to exist (and thus for the message to be uniquely decryptable), the encryption exponent must be coprime to both $p-1$ and $q-1$. This could be a problem if someone other than the owner of the private key wanted to change the exponent, since both $p$ and $q$ have to be kept secret for the RSA key to be secure. A fairly safe choice, in this situation, would be to pick $e$ to be a random large prime less than the modulus; the odds of such a prime being a factor of either $p-1$ or $q-1$ is vanishingly small. Indeed, even smaller primes could be fairly safely chosen, provided that they're not too small; using $e = 2$ would obviously be a bad idea (since $p-1$ and $q-1$ are always even), but anything over, say, 1,000 should be reasonably safe.

In particular, if you happened to know that $p$ and $q$ were both safe primes (so that $(p-1)/2$ and $(q-1)/2$ are both also prime), and differed by no more than a factor of, say, four (as they should, if the RSA key is generated in the usual way), then any prime strictly greater than 2 and less than $\sqrt{n}/4$ should be safe to use as the public exponent.