Exponentiația modulară cu un index public poate fi considerată o permutare sigură?
Voi presupune că ideea de permutare este $f_{(n,e)}:\ x\mapsto x^e\bmod n$ cu impar $n>2$, ciudat $e>1$, și $x$ în decor $\{0,1,\ldots n-2,n-1\}$ mai putin un subset de $\{0,1,n-1\}$.
$f_{(n,e)}$ este o permutare când $n$ este fără pătrat, și $e$ este coprim cu $\varphi(n)$.
Când $n$ are $k$ factori primi (distinți), $f$ are $3^k$ puncte staţionare: oricare $x$ cu $x\bmod p\in\{0,1,p-1\}$ pentru fiecare prim $p$ împărțind $n$. Asta include întotdeauna $0$, $1$, și $n-1$, motiv pentru care este posibil să dorim să le eliminăm.
Dacă $2^i+3$ este prim (adică pentru $i$ în A057732), și $e$ este coprim cu $2^i+2$, atunci $g_{(i,e)}:\ x\mapsto((x+2)^e-2)\bmod(2^i+3)$ este o permutare a $[0,2^i)$ (care se mapează cu ușurință la setul de $i$-bit șiruri de biți), cu cele trei puncte fixe evidente eliminate. Probabil vrem și noi $e>i$, și poate dori $e$ de greutate Hamming redusă. Exemple în care această construcție ar putea fi utilă: $(i,e)=(30,65)$, sau $(i,e)=(784.1025)$. Ultimul este o permutare de 98 de octeți care este destul de rapid de evaluat. Există un suport hardware bun în unele medii cripto.
Permutarea este ușor inversabilă atunci când factorizarea lui $n$ este public: facem ca în RSA, asta e mai rău $\log_2(n)/\log_2(e)$ mai costisitoare decât permutarea directă.
Este sigur? Depinde de utilizare. Tine $f_{(n,e)}(x)f_{(n,e)}(y)\bmod n=f_{(n,e)}(x\,y\bmod n)$, ceea ce face acea permutare $f_{(n,e)}$ foarte special, și există proprietăți analogice pentru $g_{(i,e)}$. Astfel, nu avem un înlocuitor bun pentru o permutare aleatorie în toate cazurile de utilizare a acestora, dar asta ar putea fi atunci când este combinat cu XOR pentru câteva runde într-o primitivă cripto simetrică.
