Можно ли считать модульное возведение в степень с общедоступным индексом безопасной перестановкой?
Я предполагаю, что мысль о перестановке $f_{(n,e)}:\ x\mapsto x^e\bmod n$ с нечетным $n>2$, странный $е>1$, и $х$ в наборе $\{0,1,\ldots n-2,n-1\}$ меньше некоторого подмножества $\{0,1,n-1\}$.
$f_{(n,e)}$ является перестановкой, когда $n$ является без квадратов, и $е$ взаимно прост с $\varphi(n)$.
Когда $n$ имеет $к$ (различные) простые факторы, $f$ имеет $3^к$ стационарные точки: любые $х$ с $x\bmod p\in\{0,1,p-1\}$ для каждого простого числа $р$ разделяющий $n$. Это всегда включает $0$, $1$, и $n-1$, поэтому мы можем захотеть их удалить.
Если $2^i+3$ является простым (то есть для $я$ в A057732), и $е$ взаимно прост с $2^i+2$, тогда $g_{(i,e)}:\ x\mapsto((x+2)^e-2)\bmod(2^i+3)$ является перестановкой $[0,2^i)$ (которое легко отображается на множество $я$-bit bitstrings) с удаленными тремя очевидными фиксированными точками. Мы, наверное, тоже хотим $е>я$, а может захотеть $е$ с малым весом Хэмминга. Примеры, где эта конструкция может быть полезна: $(я,е)=(30,65)$, или же $(i,e)=(784,1025)$. Последняя представляет собой 98-байтовую перестановку, которую достаточно быстро вычислить. В некоторых криптосредах имеется хорошая аппаратная поддержка.
Перестановка легко обратима, когда факторизация $n$ является общедоступным: делаем как в RSA, хуже примерно $\log_2(n)/\log_2(e)$ дороже, чем прямая перестановка.
Это безопасно? Это зависит от использования. Он держит $f_{(n,e)}(x)f_{(n,e)}(y)\bmod n=f_{(n,e)}(x\,y\bmod n)$, что делает эту перестановку $f_{(n,e)}$ очень особенный, и есть аналоговая собственность для $g_{(i,e)}$. Таким образом, у нас нет хорошей замены случайной перестановке во всех случаях их использования, но это может подойти в сочетании с XOR для нескольких раундов в каком-то симметричном криптопримитиве.
