algorithm - 整数的对称双射算法

Question

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

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

为澄清目的进行编辑：

该算法必须是对称的，这样我就可以在没有密钥对的情况下反转操作。
该算法必须是双射的，每个 32 位输入数字必须生成一个 32 位唯一数字。
函数的输出必须足够晦涩，只在输入中添加一个会对输出产生很大的影响。

预期结果示例：

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

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

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

score 34 · Accepted Answer

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

要将这个想法扩展到非 2 次幂范围，请参阅我在Secure Permutations with Block Ciphers上的帖子。

解决您的具体问题：

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

score 6 · Accepted Answer

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

假设我有一个 4 位数字。有 16 个不同的值。把它看成是一个四维立方体：（_来源：_ams.org_）。

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

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

score 5 · Accepted Answer

If your goal is simply to get a seemingly random permutation of numbers of a roughly defined size, then there is another possible way: reduce the set of numbers to a prime number.

Then you can use a mapping of the form

f(i) = (i * a + b) % p

and if p is indeed a prime, this will be a bijection for all a != 0 and all b. It will look fairly random for larger a and b.

For example, in my case for which I stumbled on this question, I used 1073741789 as a prime for the range of numbers smaller than 1 << 30. That makes me lose only 35 numbers, which is fine in my case.

My encoding is then

((n + 173741789) * 507371178) % 1073741789

and the decoding is

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Note that 507371178 * 233233408 % 1073741789 == 1, so those two numbers are inverse the field of numbers modulo 1073741789 (you can figure out inverse numbers in such fields with the extended euclidean algorithm).

I chose a and b fairly arbitrarily, I merely made sure they are roughly half the size of p.

score 5 · Accepted Answer

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

score 4 · Accepted Answer

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

异或
对称位排列（例如移位 16 位，或将 0-31 翻转为 31-0，或将 0-3 翻转为 3-0、4-7 至 7-4，...）
更多的？

score 1 · Accepted Answer

如果您不想使用正确的加密算法（可能出于性能和复杂性原因），您可以改用更简单的密码，例如Vigenère 密码。这种密码实际上被描述为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]));
}

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

score 1 · Accepted Answer

取一个数，乘以 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

W00t 它有效！

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

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

score 1 · Accepted Answer

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

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

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

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

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

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

选择下一个数字，再次分配一个随机映射，但选择一个尚未分配的数字。（即在这种情况下，不要选择 1 或 3）。重复直到 LUT 完成。这应该生成一个随机双射对称映射。

score 1 · Accepted Answer

这是我的简单想法：您可以像 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），但似乎更难找到某人如何在不知道密钥的情况下加密数字，这必须是秘密的。

score 0 · Accepted Answer

将数字分成两部分（16 个最高有效位和 16 个最低有效位），并将两个 16 位结果中的位视为两副牌中的牌。混合甲板迫使一个进入另一个。

因此，如果您的初始号码是b31,b30,...,b1,b0您最终得到b15,b31,b14,b30,...,b1,b17,b0,b16. 实施起来又快又快，反之亦然。

如果你看一下结果的十进制表示，这个系列看起来很模糊。

您可以手动映射 0 -> maxvalue 和 maxvalue -> 0 以避免它们映射到自己。

score 0 · Accepted Answer

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

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

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

algorithm - 整数的对称双射算法

11 回答 11

Related

Reference