Trong RSA, gcd(e,phi) != 1 nghĩa là gì? Tại sao luôn chọn e = 2^n +1 chứ không phải 2^n?

Gần đây, tôi có một số kinh nghiệm với Câu hỏi trong RSA mà e là 2^n thay vì 2^n+1 và điều đó dẫn đến gcd(e, phi) không bằng 1... Điều này có làm cho khóa riêng không thể thực hiện được không để có được? Có phải hệ thống mật mã Rabin là lối thoát duy nhất?

Trong RSA, làm gì $\gcd(e,\operatorname{phi})\ne1$ có nghĩa?

mã hóa RSA $m\mapsto m^e\bmod n$ là một mã hóa đảo ngược của $[0,n)$ nếu và chỉ nếu

1. $n$ là tích của các thừa số nguyên tố phân biệt $p_i$ (được đáp ứng nếu $n=p\,q$ cho hai số nguyên tố lớn khác nhau $p$ và $q$, thiết lập phổ biến nhất)
2. và số mũ công khai $e$ có một nghịch đảo $d_i$ modulo mỗi $p_i-1$, đó là $\exists d_i\in\mathbb N: e\,d_i\equiv1\pmod{p_i-1}$. Tương đương: và nó giữ $\gcd(e,p_i-1)=1$ cho mỗi $p_i$. Điều kiện này nhằm đảm bảo rằng $m\mapsto\left(m^e\right)^{d_i}\equiv m\pmod{p_i}$ Cho mọi $m\in\mathbb N$.

Khi (1) giữ nguyên, $\operatorname{phi}(n)=\prod(p_i-1)$, do đó điều kiện $\gcd(e,\operatorname{phi}(n))$ tương đương với (2).

Tại sao luôn chọn $e=2^k+1$ không phải $2^k$?

Không phải lúc nào chúng ta cũng chọn $e$ của hình thức $2^k+1$. Ví dụ $e=37$ khá phổ biến (xem cái này). Chúng tôi luôn chọn $e$ lẻ trong RSA vì nếu không thì điều kiện $\gcd(e,p_i-1)=1$ không thể đáp ứng cho $p_i>2$, bởi vì $2$ là số nguyên tố chẵn duy nhất.

Nếu một người sử dụng thậm chí $e$, đó không phải là RSA. Đó có thể là hệ thống mật mã Rabin.