4
$\begingroup$

Secure permutation can be used in Sponge and Duplex constructions to build hash functions and encryption. To potentially use them in public-key cryptography, some arithmetic properties is desired.

Can modular exponentiation with a public index be considered a secure permutation? What public attacks are available? Are there constructions proven to be insecure?

$\endgroup$
4
$\begingroup$

Can modular exponentiation with a public index be considered a secure permutation?

I'll assume the permutation thought is $f_{(n,e)}:\ x\mapsto x^e\bmod n$ with odd $n>2$, odd $e>1$, and $x$ in the set $\{0,1,\ldots n-2,n-1\}$ less some subset of $\{0,1,n-1\}$.

$f_{(n,e)}$ is a permutation when $n$ is square-free, and $e$ is coprime with $\varphi(n)$.

When $n$ has $k$ (distinct) prime factors, $f$ has $3^k$ stationary points: any $x$ with $x\bmod p\in\{0,1,p-1\}$ for every prime $p$ dividing $n$. That always include $0$, $1$, and $n-1$, which is why we may want to remove them.

If $2^i+3$ is prime (that is for $i$ in A057732), and $e$ is coprime with $2^i+2$, then $g_{(i,e)}:\ x\mapsto((x+2)^e-2)\bmod(2^i+3)$ is a permutation of $[0,2^i)$ (which easily maps to the set of $i$-bit bitstrings), with the three obvious fixed points removed. We probably also want $e>i$, and may want $e$ of low Hamming weight. Examples where that construction might be useful: $(i,e)=(30,65)$, or $(i,e)=(784,1025)$. The later is a 98-byte permutation that's reasonably fast to evaluate. There is good hardware support in some crypto environments.

The permutation is easily invertible when the factorization of $n$ is public: we do as in RSA, that's at worse about $\log_2(n)/\log_2(e)$ more costly than the direct permutation.

Is that secure? It depends on the usage. It holds $f_{(n,e)}(x)f_{(n,e)}(y)\bmod n=f_{(n,e)}(x\,y\bmod n)$, which makes that permutation $f_{(n,e)}$ very special, and there's analog property for $g_{(i,e)}$. Thus we do not have a good substitute for a random permutation in all use cases of these, but that might do when combined with XOR for a few rounds in some symmetric crypto primitive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.