În RSA, ce înseamnă gcd(e,phi) != 1? De ce să alegeți întotdeauna e = 2^n +1 nu 2^n?

Recent, am puține experiențe cu întrebări în RSA, care e este 2 ^ n în loc de 2 ^ n + 1 și care duce la gcd (e, phi) nu este egal cu 1... Asta nu va face cheia privată imposibilă a obține? Este criptosistemul Rabin singura cale de ieșire?

În RSA, ce face $\gcd(e,\operatorname{phi})\ne1$ mijloace?

Criptare RSA $m\mapsto m^e\bmod n$ este o criptare reversibilă a $[0,n)$ dacă și numai dacă

1. $n$ este produsul unor factori primi diferiți $p_i$ (ceea ce este îndeplinit dacă $n=p\,q$ pentru două numere prime mari distincte $p$ și $q$, cea mai comună configurație)
2. și exponentul public $e$ are invers $d_i$ modulo fiecare $p_i-1$, acesta este $\există d_i\in\mathbb N: e\,d_i\equiv1\pmod{p_i-1}$. Echivalent: și ține $\gcd(e,p_i-1)=1$ pentru fiecare $p_i$. Această condiție este să se asigure că $m\mapsto\left(m^e\right)^{d_i}\equiv m\pmod{p_i}$ pentru fiecare $m\in\mathbb N$.

Când (1) este valabil, $\operatorname{phi}(n)=\prod(p_i-1)$, deci condiția $\gcd(e,\operatorname{phi}(n))$ este echivalent cu (2).

De ce alege mereu $e=2^k+1$ nu $2^k$?

Nu alegem întotdeauna $e$ a formei $2^k+1$. De exemplu $e=37$ este destul de comun (vezi acest). Noi alegem mereu $e$ ciudat în RSA pentru că altfel condiția $\gcd(e,p_i-1)=1$ nu poate fi îndeplinită pentru $p_i>2$, deoarece $2$ este singurul prim par.

Dacă se folosește chiar $e$, asta nu este RSA. Asta poate fi Criptosistemul Rabin.