带有公共索引的模幂可以被认为是安全的排列吗？

Question

安全置换可用于海绵状和双工结构，以建立哈希函数和加密。要在公钥密码学中使用它们，需要一些算术属性。

带有公共索引的模幂可以被认为是安全的排列吗？有什么公开攻击吗？有证明不安全的建筑吗？

Answer 1

带有公共索引的模幂可以被认为是安全的排列吗？

我假设置换思想是带有奇数n>2、奇数e>1和集合中的x的置换思想，\{0,1,\ldots n-2,n-1\}减去\{0,1,n-1\}的某些子集。

f_{(n,e)}是n是无平方时的置换，e是\varphi(n)的共变异。

当n有k (不同的)素因子时，f有3^k不动点:对于每一个素数p除以n的带有x\bmod p\in\{0,1,p-1\}的x。这通常包括0、1和n-1，这就是为什么我们可能要删除它们。

如果2^i+3是素数(即i in A057732)，而e与2^i+2是对等的，那么g_{(i,e)}:\ x\mapsto((x+2)^e-2)\bmod(2^i+3)是[0,2^i)的置换(很容易映射到i-bit位串集合)，并去掉三个明显的不动点。我们可能也要e>i，也可能要低汉明重量的e。该构造可能有用的示例：(i,e)=(30,65)或(i,e)=(784,1025)。后者是一个98字节的排列，计算起来相当快。在一些加密环境中有很好的硬件支持。

当n的因式分解是公开的时，置换是很容易可逆的:我们就像在\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组合几轮，就可以做到这一点。