Skip to main content
3 of 3
never used *without* proper padding ;)
Mikero
  • 14.5k
  • 2
  • 35
  • 56

But what is the most appropriate choice for it?

For public exponent $e$, small values are preferred like $\{3, 5, 17, 257, \text{ or } 65537\}$. With this, we can guarantee that the number of operations is low. We can control this with our choice. Of course, for the choice of $e$, we must have $\gcd(e,p)=1$ for any prime $p$ divides the modulus $n$. This guarantees that we have the inverse of $e$ such that $e\cdot d = 1 \bmod \phi(n)$, and $\gcd(e',n) = \gcd(e,n)$

Should it be small compared to $\phi(n)$ or approach it?

You can choose a public exponent $e'$ bigger than $\phi(n)$, however due to the congruence, we can always find an $e$ such that $ e' \equiv e \bmod \phi(n)$ with $e < \phi(n)$.

Of course, RSA should never be used without proper padding scheme. For example, if you use $e=3$ without a proper padding scheme than you will be vulnerable to cube-root attack.

And note that RSA Signing is Not RSA Decryption!

kelalaka
  • 49.5k
  • 12
  • 119
  • 205