Phép lũy thừa mô-đun với chỉ mục công khai có thể được coi là hoán vị an toàn không?
Tôi sẽ cho rằng suy nghĩ hoán vị là $f_{(n,e)}:\ x\mapsto x^e\bmod n$ với số lẻ $n>2$, số lẻ $e>1$, và $x$ trong bộ $\{0,1,\ldots n-2,n-1\}$ trừ đi một số tập con của $\{0,1,n-1\}$.
$f_{(n,e)}$ là một hoán vị khi $n$ Là vuông miễn phí, và $e$ là nguyên tố cùng với $\varphi(n)$.
Khi nào $n$ có $k$ (riêng biệt) thừa số nguyên tố, $f$ có $3^k$ điểm cố định: bất kỳ $x$ với $x\bmod p\in\{0,1,p-1\}$ cho mọi số nguyên tố $p$ phân chia $n$. Điều đó luôn luôn bao gồm $0$, $1$, và $n-1$, đó là lý do tại sao chúng tôi có thể muốn xóa chúng.
Nếu $2^i+3$ là số nguyên tố (nghĩa là đối với $i$ Trong A057732), và $e$ là nguyên tố cùng với $2^i+2$, sau đó $g_{(i,e)}:\ x\mapsto((x+2)^e-2)\bmod(2^i+3)$ là một hoán vị của $[0,2^i)$ (dễ dàng ánh xạ tới tập hợp $i$-bit bitstrings), với ba điểm cố định rõ ràng đã bị loại bỏ. Chắc chúng tôi cũng muốn $e>i$, và có thể muốn $e$ trọng lượng Hamming thấp. Ví dụ về việc xây dựng đó có thể hữu ích: $(i,e)=(30,65)$, hoặc $(i,e)=(784,1025)$. Cái sau là hoán vị 98 byte, khá nhanh để đánh giá. Có hỗ trợ phần cứng tốt trong một số môi trường tiền điện tử.
Hoán vị dễ dàng nghịch đảo khi phân tích thành nhân tử $n$ là công khai: chúng tôi làm như trong RSA, điều đó còn tệ hơn về $\log_2(n)/\log_2(e)$ tốn kém hơn so với hoán vị trực tiếp.
Điều đó có an toàn không? Nó phụ thuộc vào việc sử dụng. Nó giữ $f_{(n,e)}(x)f_{(n,e)}(y)\bmod n=f_{(n,e)}(x\,y\bmod n)$, mà làm cho hoán vị đó $f_{(n,e)}$ rất đặc biệt và có thuộc tính tương tự cho $g_{(i,e)}$. Do đó, chúng tôi không có sự thay thế tốt cho một hoán vị ngẫu nhiên trong tất cả các trường hợp sử dụng của những trường hợp này, nhưng điều đó có thể xảy ra khi kết hợp với XOR trong một vài vòng trong một số nguyên hàm tiền điện tử đối xứng.
