3
$\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?

$\endgroup$
1

2 Answers 2

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).

$\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$ 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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.