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?

  • 1
    $\begingroup$ What have you tried? $\endgroup$
    – kelalaka
    Jun 2, 2022 at 16:26
  • $\begingroup$ 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. $\endgroup$
    – dlfls
    Jun 2, 2022 at 16:36
  • $\begingroup$ 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!) $\endgroup$
    – dlfls
    Jun 2, 2022 at 16:37

1 Answer 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.