# RSA encryption key conditions

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?

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

• Thank you! You made it clear completely. Jun 5, 2021 at 18:18