整数的对称双射算法

Question

我需要一种算法，可以将一个 32 位有符号整数一对一映射（即无冲突）到另一个 32 位有符号整数。

我真正关心的是足够的熵，以便函数的输出看起来是随机的。基本上我正在寻找一种类似于 XOR 密码的密码，但它可以生成更任意的输出。安全性并不是我真正关心的，尽管默默无闻才是。

出于澄清目的进行编辑：

1. 算法必须是对称的，以便我可以在没有密钥对的情况下反转操作。
2. 该算法必须是双射的，每个 32 位输入数字必须生成一个 32 位唯一数字。
3. 函数的输出必须足够模糊，仅向输入添加一个就会对输出产生很大的影响。

预期结果示例：

F(100) = 98456
F(101) = -758
F(102) = 10875498
F(103) = 986541
F(104) = 945451245
F(105) = -488554

就像 MD5 一样，改变一件事可能会改变很多事情。

我正在寻找一个数学函数，因此手动映射整数对我来说不是一个解决方案。对于那些询问的人来说，算法速度并不是很重要。

Answer 1

使用任何 32 位分组密码！根据定义，分组密码以可逆的方式将其范围内的每个可能的输入值映射到唯一的输出值，并且根据设计，在没有密钥的情况下很难确定任何给定值将映射到什么。只需选择一个密钥，如果安全性或模糊性很重要，请将其保密，然后使用密码作为转换。

要将这个想法扩展到非 2 次方范围，请参阅我的帖子 使用分组密码进行安全排列。

解决您的具体问题：

1. 该算法确实是对称的。我不确定“在没有密钥对的情况下反转操作”是什么意思。如果您不想使用密钥，请对随机生成的密钥进行硬编码并将其视为算法的一部分。
2. 是的 - 根据定义，分组密码是双射的。
3. 是的。如果不是这样的话，它就不是一个好的密码。

Answer 2

下面的论文为您提供了 4 或 5 个映射示例，为您提供了函数而不是构建映射集： www.cs.auckland.ac.nz/~john-rugis/pdf/BijectiveMapping.pdf

Answer 3

如果您的目标只是获得粗略大小的数字的看似随机的排列，那么还有另一种可能的方法：将数字集减少为素数。

形式的映射

然后您可以使用f(i) = (i * a + b) % p

，如果 p 确实是素数，则这将是所有 a != 0 和所有 b 的双射。对于较大的 a 和 b 来说，它看起来相当随机。

例如，在我偶然发现这个问题的情况下，我使用 1073741789 作为小于 1 << 的数字范围的素数。 30. 这使我只丢失 35 个数字，这对我来说没问题。

我的编码是 then

((n + 173741789) * 507371178) % 1073741789

，解码是

(n * 233233408 + 1073741789 - 173741789) % 1073741789

注意 507371178 * 233233408 % 1073741789 == 1，所以这两个数字是模 1073741789 的数字域的逆数（您可以使用扩展欧几里德算法计算出这些字段中的逆数）。

我相当随意地选择了 a 和 b，我只是确保它们大约是 p 大小的一半。

Answer 4

我将尝试通过一个更简单的示例来解释我的解决方案，然后可以轻松地将其扩展到您的大型示例。

假设我有一个 4 位数字。有 16 个不同的值。将其视为一个四维立方体：
_{（来源：ams.org）}
。

每个顶点代表这些数字之一，每一位代表一个维度。因此它基本上是 XYZW，其中每个维度只能具有值 0 或 1。现在假设您使用不同顺序的维度。例如 XZYW。现在每个顶点的数量都改变了！

您可以对任意数量的维度执行此操作，只需排列这些维度即可。如果您不关心安全性，那么这对您来说可能是一个不错的快速解决方案。另一方面，我不知道输出是否足够“模糊”以满足您的需求，当然在完成大量映射之后，映射可以反转（这可能是优点或缺点，具体取决于您的需求。）

Answer 5

除了生成随机查找表之外，您还可以使用函数组合：

• XOR
• 对称位排列（例如移位 16 位，或翻转 0-31 至 31-0，或翻转 0-3 至 3-0、4-7到 7-4，...)
• 更多？

Answer 6

您可以使用随机生成的查找表吗？只要表中的随机数是唯一的，您就可以获得双射映射。但它不是对称的。

针对所有 32 位值使用一个 16 GB 查找表可能不切实际，但您可以对高位字和低位字使用两个单独的 16 位查找表。

PS：我认为你可以生成一个对称双射查找表，如果这很重要的话。该算法将从一个空的 LUT 开始：

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

选择第一个元素，为其分配随机映射。要使映射对称，也分配逆数：

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

选择下一个数字，再次分配随机映射，但选择尚未分配的数字。 （即在本例中，不要选择 1 或 3）。重复此操作直至 LUT 完成。这应该生成随机双射对称映射。

Answer 7

取一个数，乘以9，取反数，除以9。

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

应该足够晦涩了！

编辑：它不是 0 结尾整数的双射

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

您可以随时添加特定规则，例如：
取一个数，除以 10 x 倍，乘以 9，逆数字，除以 9，乘以 10^x。

所以

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

它有效！

编辑2：为了更加晦涩，您可以添加任意数字，并在最后减去。

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129

Answer 8

这是我的简单想法：
正如 PeterK 提出的那样，您可以移动数字的位，但您可以为每个数字进行不同的位排列，并且仍然能够破译它。

密码是这样的：
将输入数字视为位数组 I[0..31]，将输出视为 O[0..31]。
准备一个由 64 个随机生成的数字组成的数组 K[0..63]。这将是你的钥匙。
从第一个随机数 (I[K[0] mod 32]) 确定的位置取出输入数字的位，并将其放在结果的开头 (O[0]< /代码>）。现在要决定将哪个位放置在 O[1] 处，请使用之前使用过的位。如果为0，则使用K[1]生成I中要取的位置，如果为1，则使用K[2]（简单来说就是跳过一个随机数）。

现在这效果不太好，因为你可能会两次使用相同的位。为了避免这种情况，请在每次迭代后重新对位进行编号，并忽略已使用的位。要生成获取 O[1] 的位置，请使用 I[K[p] mod 31]，其中 p 为 1 或 2，具体取决于位 O[0]，因为还剩下 31 位，编号从 0 到 30。

为了说明这一点，我举一个例子：

我们有一个 4 位数字，和 8 个随机数：25, 5 , 28, 19, 14, 20, 0, 18.

I: 0111    O: ____
    _

25 mod 4 = 1，所以我们将取位置为 1 的位（从 0 开始计数）

I: 0_11    O: 1___
     _

我们刚刚取了一位值为 1 的位，所以我们随机跳过一个数字并使用 28。还剩下 3 位，因此为了计算位置，我们取 28 mod 3 = 1。我们取剩余位的第一个（从 0 开始计数）：

I: 0__1    O: 11__
   _

我们再次跳过一个数字，并取 14。14 mod 2 = 0，所以我们取第 0 位：

I: ___1    O: 110_
      _

现在没关系，但前一位是 0，所以我们取 20。 20 mod 1 = 0：

I: ____    O: 1101

就是这样。

破译这样的数字很容易，只需做同样的事情即可。放置代码第一位的位置从密钥中得知，接下来的位置由先前插入的位确定。

显然，这具有仅移动位的所有缺点（例如 0 变为 0，MAXINT 变为 MAXINT），但似乎很难找到某人如何在不知道密钥的情况下加密该数字，而密钥必须是秘密的。

Answer 9

如果您不想使用正确的加密算法（可能出于性能和复杂性原因），您可以使用更简单的密码，例如 维吉尼亚密码。该密码实际上被描述为le chiffre indéchiffrable（法语，意为“牢不可破的密码”）。

下面是一个简单的 C# 实现，它根据相应的键值来移动值：

void Main()
{
  var clearText = Enumerable.Range(0, 10);
  var key = new[] { 10, 20, Int32.MaxValue };
  var cipherText = Encode(clearText, key);
  var clearText2 = Decode(cipherText, key);
}

IEnumerable<Int32> Encode(IEnumerable<Int32> clearText, IList<Int32> key) {
  return clearText.Select((i, n) => unchecked(i + key[n%key.Count]));
}

IEnumerable<Int32> Decode(IEnumerable<Int32> cipherText, IList<Int32> key) {
  return cipherText.Select((i, n) => unchecked(i - key[n%key.Count]));
}

当输入稍有变化时，该算法不会在输出中产生较大的变化。但是，您可以使用另一个双射运算而不是加法来实现此目的。

Answer 10

在一张大纸上画一个大圆圈。从圆顶部顺时针方向，等间距地写入从 0 到 MAXINT 的所有整数。逆时针写入从 0 到 MININT 的所有整数，再次等距。请注意，MININT 位于圆圈底部的 MAXINT 旁边。现在在一张硬卡片的两面复制这个图形。将硬卡通过两者的中心固定在圆圈上。选择一个旋转角度，任何你喜欢的角度。现在您有了一个 1-1 映射，它可以满足您的一些要求，但可能还不够模糊。松开卡，将其围绕一个直径（任何直径）翻转。重复这些步骤（以任何顺序），直到获得满意的双射。

如果您一直密切关注，那么用您喜欢的语言对其进行编程应该不难。

澄清以下评论：如果您仅将卡片旋转到纸张上，那么方法就像您抱怨的一样简单。但是，当您翻转卡片时，映射并不等于任何 m 的 (x+m) mod MAXINT。例如，如果您不旋转卡片并将其围绕直径翻转到 0（位于钟面顶部），则 1 映射到 -1，2 映射到 -2，依此类推。 (x+m) mod MAXINT 仅对应于卡片的旋转。

Answer 11

将数字一分为二（16 个最高有效位和 16 个最低有效位），并将两个 16 位结果中的位视为两副牌中的牌。混合套牌，将一张套牌压入另一套牌中。

因此，如果您的初始数字是 b31,b30,...,b1,b0 您最终会得到 b15,b31,b14,b30,...,b1,b17,b0,b16 。它实施起来很快而且很快，反之亦然。

如果您查看结果的十进制表示形式，该系列看起来相当晦涩难懂。

您可以手动映射 0 ->最大值和最大值-> 0 以避免它们映射到自身。