0
$\begingroup$

I recently read the RSA cryptosystem but now I confused in key generation phase. According to the Euler's Theorem, we have just one condition:

e.d = k.ϕ(N) + 1

where:

  • "e" is encryption key.
  • "d" is decryption key.
  • "N" is a number in form of p*q where p and q are both primes.
  • "ϕ(N)" is equal to (p-1)(q-1).

But some of documentations states new conditions as:

  1. e should be small.

  2. gcd(φ(N),e)=1.

  3. e should be an odd number

Now, My question is why I should satisfy these 3 conditions?

I think the second and third conditions are stated just to ensure that "d" is an integer too because of d = (k.φ(N) + 1)/e. Am I correct?

And finally, I think the first conditions is stated to make sure that "d" is enough large. Am I correct?

$\endgroup$

1 Answer 1

2
$\begingroup$

why I should satisfy these ?

  1. $e$ should be small.

There's 3 reasons

  • It's in the interest of speed of the public-key operations (encryption and signature verification), which in RSA take time roughly proportional to $\log e$.
  • It ensures compatibility with some implementations, which limit $e$ to 32 (or is it 31) bits.
  • It makes it impossible to use a small $d$, which would ruin security. The question's final paragraph is right about that.

Notice that for mostly historical reasons, you'll also find recommendations that $e$ is not too small. Definitely, $e\le1$ would be a terrible idea. At the end of the day, the most common and unobjectionable is $e=F_4=2^{(2^4)}+1=65537$, where $F_4$ is the largest known Fermat prime.

  1. $\gcd(\varphi(N),e)=1$.

In this, $\varphi(N)$ differs only in notation from $\phi(N)$ or is it $\Phi(N)$ in the question's "$\phi(N)$ is equal to $(p-1)(q-1)$". That's the Euler totient. $\varphi(N)=(p-1)(q-1)$ holds when $N=p\cdot q$ with $p$ and $q$ distinct primes, which is overwhelmingly likely when $p$ and $q$ are primes chosen randomly enough.

And $\gcd(\varphi(N),e)=1$ is necessary for existence of (integers) $k$ and $d$ such that $e\cdot d=k\cdot\varphi(N)+1$.

$e$ should be an odd number.

Unless $p$ or $q$ is $2$, which would be a bad idea, that follows from $e\cdot d = k\cdot(p-1)(q-1)+1$.

I think the second and third conditions are stated just to ensure that $d$ is an integer too because of $d=(k\cdot\varphi(N)+1)/e$.

Uh, no. Integers and bitstrings are about the only data representations in cryptography, and in RSA they are often assimilated per big-endian convention, so everything is an integer.

That exists $k$ with $e\cdot d=k\cdot\varphi(N)+1$ or (equivalently) $d=(k\cdot\varphi(N)+1)/e$ can be noted $d\equiv e^{-1}\pmod{\varphi(N)}$, and that means $d$ is (an integer representative of) the inverse of $e$ in the multiplicative group of the integers modulo $\varphi(N)$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! You made it clear completely. $\endgroup$
    – milad
    Jun 5, 2021 at 18:18

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.