0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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 = 216+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.

$\endgroup$
8
  • 1
    $\begingroup$ how can i change it in the public key file $\endgroup$ Nov 4 '15 at 23:57
  • 1
    $\begingroup$ That depends on the key file format you're using. $\endgroup$ Nov 4 '15 at 23:58
  • $\begingroup$ Can you please help me solve a problem. I am given an encrypted file and a public key . It says that the public exponent is taken wrongly. on analyzing i found the public exponent to be 3 where it should have been 65537. How can i decrypt the file. $\endgroup$ Nov 4 '15 at 23:58
  • $\begingroup$ "Just a text file" doesn't really tell much; a lot of the formats for storing RSA keys are text files (often containing a bunch of base64-encoded data). If it starts with a line like ---- BEGIN (whatever) ----, Google for that line to see what type of key file it is. If it starts with something like <RSAKeyValue> and has lots of angle brackets in general, it's probably in XKMS format. If it's just got two numbers (a large and a small one), well those are probably the modulus and the exponent. $\endgroup$ Nov 5 '15 at 0:09
  • 1
    $\begingroup$ I think you can in fact decrypt a message with a non-standard exponent only given $n$ and $d$. You just factor $n$ using $d$ and then apply the standard methods of decryption. $\endgroup$
    – SEJPM
    Nov 5 '15 at 12:20

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.