# In RSA, What does gcd(e,phi) != 1 means? Why always choose e = 2^n +1 not 2^n?

Recently I have few experiences with Questions in RSA which e is 2^n instead of 2^n+1, and that leads to gcd(e, phi) is not equal to 1... Won't this make the private key impossible to get? Is the Rabin cryptosystem the only way out?

• What have you tried? Commented Jun 2, 2022 at 16:26
• I tried the Rabin cryptosystem, to find the two square roots (only one prime number is used so 2 square roots instead 4) and do it repeatedly as my e is a multiple of 2. Commented Jun 2, 2022 at 16:36
• And I used N as public key, and p as the private key in this case. Since d won't generate and phi won't be helpful. (but please correct me if this is incorrect!) Commented Jun 2, 2022 at 16:37

## 1 Answer

In RSA, what does $$\gcd(e,\operatorname{phi})\ne1$$ means?

RSA encryption $$m\mapsto m^e\bmod n$$ is a reversible encryption of $$[0,n)$$ if and only if

1. $$n$$ is the product of distinct prime factors $$p_i$$ (which is met if $$n=p\,q$$ for two large distinct primes $$p$$ and $$q$$, the most common setup)
2. and the public exponent $$e$$ has an inverse $$d_i$$ modulo each $$p_i-1$$, that is $$\exists d_i\in\mathbb N: e\,d_i\equiv1\pmod{p_i-1}$$. Equivalently: and it holds $$\gcd(e,p_i-1)=1$$ for each $$p_i$$. This condition is to ensure that $$m\mapsto\left(m^e\right)^{d_i}\equiv m\pmod{p_i}$$ for every $$m\in\mathbb N$$.

When (1) holds, $$\operatorname{phi}(n)=\prod(p_i-1)$$, therefore the condition $$\gcd(e,\operatorname{phi}(n))$$ is equivalent to (2).

Why always choose $$e=2^k+1$$ not $$2^k$$?

We don't always choose $$e$$ of the form $$2^k+1$$. For example $$e=37$$ is quite common (see this). We always choose $$e$$ odd in RSA because otherwise the condition $$\gcd(e,p_i-1)=1$$ can not be met for $$p_i>2$$, because $$2$$ is the only even prime.

If one uses even $$e$$, that's not RSA. That can be the Rabin cryptosystem.