Что означает gcd(e,phi) != 1 в RSA? Почему всегда выбирают e = 2^n +1, а не 2^n?

В последнее время у меня мало опыта с вопросами в RSA, где e равно 2 ^ n вместо 2 ^ n + 1, и это приводит к тому, что gcd (e, phi) не равен 1... Разве это не сделает закрытый ключ невозможным? получить? Является ли криптосистема Рабина единственным выходом?

Что делает в RSA $\gcd(e,\operatorname{phi})\ne1$ средства?

Шифрование RSA $m\mapsto m^e\bmod n$ является обратимым шифрованием $[0,n)$ если и только если

1. $n$ является произведением различных простых множителей $p_i$ (что выполняется, если $n=p\,q$ для двух больших различных простых чисел $р$ и $q$, самая распространенная установка)
2. и общественный деятель $е$ имеет обратный $d_i$ по модулю каждого $p_i-1$, это $\exists d_i\in\mathbb N: e\,d_i\equiv1\pmod{p_i-1}$. Эквивалентно: и выполняется $\gcd(e,p_i-1)=1$ для каждого $p_i$. Это условие гарантирует, что $m\mapsto\left(m^e\right)^{d_i}\equiv m\pmod{p_i}$ для каждого $m\in\mathbb N$.

Когда выполняется (1), $\operatorname{phi}(n)=\prod(p_i-1)$, поэтому условие $\gcd(e,\operatorname{phi}(n))$ эквивалентно (2).

Почему всегда выбирают $е=2^к+1$ нет $2^к$?

Мы не всегда выбираем $е$ формы $2^k+1$. Например $е=37$ довольно часто (см. это). Мы всегда выбираем $е$ странно в RSA, потому что в противном случае условие $\gcd(e,p_i-1)=1$ не может быть встречено для $p_i>2$, так как $2$ является единственным четным простым числом.

Если использовать даже $е$, это не RSA. Это может быть Криптосистема Рабина.