Score:1

# 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?
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.
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!)
Score:1

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.