2
$\begingroup$

RSA private exponent is much larger than RSA public exponent. For example, for a 2048 bit RSA private key, the private exponent can have more than 2000 bits. But the public exponent is usually 65537 (0x10001) which has a much shorter bit length.

Here is my guess of the reason. Let's use define the following symbols to describe RSA algorithm:

  • $n$: modulus
  • $e$: public exponent
  • $d$: private exponent
  • $P$: public key $(e,n)$
  • $S$: private key $(d,n)$

Encrypt a plain message $M$ with $M^e \text{ mod }n$. Decrypt a encrypted message $C$ with $C^d \text{ mod }n$. Since $d$ is much larger than $e$, decryption incurs much more mulipliation compuatuation. So the use of a large priavate exponent is to make the decryption harder.

Is my guess correct?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
8
$\begingroup$

Is my guess correct?

Not really; we don't go out of our way to deliberately slow down the decryption operation. Instead, things are set up that way because that's what's needed for security.

  • It turns out that if $d$ is small (e.g. less than a fourth of the size of $n$), and we tell people what the corresponding $e$ is, it turns out they can factor $n$ efficiently. Hence, $d$ needs to be large to ensure security.

  • There's no similar issue for $e$; telling a people a small $e$ doesn't help them factor $n$ (or otherwise break RSA). Hence, there's no reason not to select a small value (and make the encryption operation faster).

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ In other words: We have the choices of a) picking one of $d,e$ at random and computing the other; this makes both essentially random and hence of (nearly) same size as $n$. b) pick $d$ systematically and compute $e$ from it, which will look like random (and of nearly same size as $n$). c) pick $e$ systematically and compute $d$ from it, which will look like random (and nearly of same size as $n$). Of these, variant b would be stupid because any (even obscure) way of picking $d$ systematically allows for an attack. $\endgroup$
    – Hagen von Eitzen
    Apr 7, 2018 at 10:27
6
$\begingroup$

In addition to poncho's answer: $d$ being approximately $n$ sized is a by-product of computing it as the modular inverse of $e$.

With high probability, the inverse of $x \bmod k$ is approximately $k$ sized, even if $x$ is small.

Improve this answer
$\endgroup$

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.