整数的对称双射算法

Question

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

我真正关心的是足够的熵，使得函数的输出看起来是随机的。基本上，我正在寻找一种类似于异或密码的密码，但可以生成更具任意性的输出。安全性并不是我真正关心的问题，尽管模糊性是。

为了澄清目的，编辑如下：

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

示例预期结果： F(100) = 98456 F(101) = -758 F(102) = 10875498 F(103) = 986541 F(104) = 945451245 F(105) = -488554

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

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

- Emre Yazici

---

你想让你的算法运行多快？ - Cyril Gandon

@Scorpi0 编码方式并不重要，解码速度应该更快，通常接受公钥加密速度相近的速度。 - Emre Yazici

@Scorpi0：算法必须是对称的，这样我才能反转该过程。我将以 PKI 速度作为衡量标准。 - Emre Yazici

@eyaici：如果编码函数是单射的，那么这个过程是可逆的。但是编码和解码函数必须要是同一个函数吗？这就是我理解中“对称”的意思。如果您所说的“对称算法”有其他含义，请澄清一下。 - Niki

在sci-comp SE上，有一个很好的回答，关于重复或接近重复的问题：随机访问随机排列。维基百科有关于伪随机排列和排列多项式的文章，其中包含一些其他的想法。如果你对模糊和“看起来洗牌”比安全性更感兴趣， - undefined

Answer 1

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

有关将此想法扩展到非2的幂次方范围的更多信息，请参见我在Secure Permutations with Block Ciphers上的帖子。

解决您的特定问题：

1. 该算法确实是对称的。我不确定您所指的“在没有密钥对的情况下反转操作”。如果您不想使用密钥，请硬编码一个随机生成的密钥并将其视为算法的一部分。
2. 是的 - 按定义，块密码是双射的。
3. 是的。如果不是这种情况，它就不是一个好的密码。

- Nick Johnson

---

是的，该算法是对称的，我的意思是我不想使用任何非对称解决方案（如果有的话），非对称密码使用不同的编码和解码密钥，这些密钥一起被称为“密钥对”。在您的建议下，我找到了一个32位块密码（可能是网络上唯一的一个），现在正在将其移植到另一种语言中，它看起来足够好：http://www.qualcomm.com.au/PublicationsDocs/skip32.c - Emre Yazici

啊，明白了。正如我的帖子所示，现有的密码可以缩短；TEA 可以被修改为 32 位块长度。我不会依赖这样的修改来保证加密安全性，但你似乎并不关心这个问题。 :) - Nick Johnson

当然，32位密钥的彩虹表只有16 GB大小，在第一次运行时就可以生成，因此可能永远不会在现代硬件上具有加密安全性。 - Jonathan Grynspan

以下是一些可能的密码，没有特定的顺序：Hasty Pudding密码、GDES、Simon、Speck、RC5。可能还有很多其他的。 - Artjom B.

Answer 2

如果您的目标仅是获得一个大致定义大小的数字集合的看似随机排列，那么还有另一种可能的方法：将数字集合减小为质数。

然后，您可以使用以下形式的映射：

f(i) = (i * a + b) % p 如果p确实是一个质数，则对于所有a≠0和所有b，这将是一个双射。对于较大的a和b，它看起来相当随机。

例如，在我的情况下，我使用1073741789作为质数，用于小于1 << 30的数字范围。这只让我失去了35个数字，这对我来说很好。

我的编码是：

((n + 173741789) * 507371178) % 1073741789

解码如下：

(n * 233233408 + 1073741789 - 173741789) % 1073741789

请注意，507371178 * 233233408 % 1073741789 == 1，因此这两个数字是模1073741789下的逆元素（您可以使用扩展欧几里得算法找到这些域中的逆元素）。

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

- John

---

不要“将数字集减少到一个质数”，而是要将数字集增加到一个质数！这会在两个方面搞乱你的双射：原始范围中的一些i有图像f(i)=j超出范围，而原始范围中的一些k有前像f(j)=k，其中j超出范围...但这两个问题正好抵消了！只需迭代f直到你在所需范围内。在我的例子中，f(f(i))=k，所以我们可以完全忽略j。我们可能需要执行f(f(f(f(i))))，但最终我们会回到范围内！ - undefined

这是因为排列具有循环，所以我们可以沿着循环骑行，直到回到原始范围（最坏情况下，我们回到i）。这将那些映射超出范围的i与那些原像超出范围的k连接在一起。这与将数字变为2的幂的思想类似，这样您就可以应用（如果需要，可以重复应用）一个分组密码 - 参见这个sci-comp SE帖子。 - undefined

@Silverfish 有意思，谢谢分享。 - undefined

Answer 3

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

- Björn

Answer 4

我将尝试用一个更简单的例子来解释我的解决方案，然后可以轻松地将其扩展到您的大型问题。假设我有一个4位数字，共有16个不同的值。把它看作是一个四维立方体:
_{(来源: ams.org)}
每个顶点代表其中一个数字，每个位代表一个维度。因此，它基本上是XYZW，其中每个维度只能具有值0或1。现在想象一下，您使用一个不同的维度顺序，例如XZYW。现在每个顶点都改变了它的数字!

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

- PeterK

---

这是否等同于将数字的各个位按照给定的模式进行简单地调换？无论如何，超立方体都很酷。 - Justin L.

是的，它是。超立方体示例仅用于解释，因为我认为实际上理解在多维空间中交换位所“做”的事情会很好。 - PeterK

我明白了。我以前从未见过多维被用作32位整数的类比，但确实很有趣。 - Justin L.

在n位值中交换位只会给出n!种可能性。你需要的是一个真正的排列，它可以给出(2^n)!种可能性。 - Todd Lehman

Answer 5

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

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

- Michel de Ruiter

---

正如我在问题中所写的那样，我需要任意外观的输出。我已经提到了异或方式，不是吗？ - Emre Yazici

当然可以，但我认为将异或与位排列结合起来可能会显得相对随意。无论在你的情况下意味着什么。 - Michel de Ruiter

是的，尝试位排列可以解决我的问题，但我正在寻找一个经过验证的已知方法，而不是自己实现，这就是为什么我在这里询问的原因。 - Emre Yazici

啊，那么我会像Nick Johnson提到的那样研究块加密。虽然有点难跟上，但是经过验证的方法。 - Michel de Ruiter

Answer 6

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

为所有32位值使用一个16 GB的查找表可能不太实际，但你可以使用两个分别用于高位和低位的16位查找表。

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

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

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

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

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

- Niki

---

使用查找表是一种确定的解决方案，但我需要一个数学解决方案。 - Emre Yazici

“数学解决方案”是什么意思？使用具有固定种子（例如密钥）的PRNG，您就可以得到一个数学解决方案。 - Niki

我的意思是更聪明的解决方案，映射2^32个整数既不划算也不可扩展。基本上我在寻找一个32位块密码（在32位情况下很少见），而我已经找到了它。 - Emre Yazici

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

- Cyril Gandon

---

如何处理溢出？将一个大的32位数字乘以9可能会导致一个大于2^32的数字。 - Niki

是的，在溢出方面有一些小问题，2147483647 <> 3647263599。该算法保证了对于集合10^N而言是双射映射，而不是2^N，这只是一个细节 :p - Cyril Gandon

正如我之前所述，我正在寻找一种可以生成任意外观输出的密码，但是您的解决方案会为连续数字生成类似的输出：123=>779，124=>679，125=>579... 对于我来说，模糊性是必须的，但不是唯一的问题。出于这个原因，我不使用简单的XOR密码或任何其他对称密码，它们可以生成更好的结果（就模糊性而言）。 - Emre Yazici

我在想，也许可以在倒置的数字上运行这个算法两次甚至更多次，比如10次，结果可能会很有趣。我会尝试编写一些代码！ - Cyril Gandon

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），但是似乎更难找到某人在不知道密钥的情况下如何加密该数字，而密钥必须保密。

- Michał Trybus

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]));
}

当输入稍有变化时，该算法不会在输出中产生大的偏移。但是，您可以使用另一种双射操作来代替加法以实现这一点。

- Martin Liversage

Answer 10

在一张大纸上画一个大圆。顺时针从圆的顶部等距离地写下从0到MAXINT的所有整数。再逆时针等间距地写下从0到MININT的所有整数。观察到MININT在圆底下方与MAXINT相邻。现在在硬纸板的两侧制作这个图形的副本。通过两个圆心将硬纸板固定在圆上。选择一个旋转角度，任何你喜欢的角度都可以。现在你有了一个符合你一些要求的一对一映射，但可能不太难懂。拆开卡片，在任意直径上翻转它。重复这些步骤（按任意顺序），直到你满意为止。

如果你一直在关注，用你喜欢的语言编程应该不难。

为澄清问题，针对以下评论：如果您只旋转卡片，那么方法就像您所抱怨的那样简单。然而，当您翻转卡片时，映射与任何m的(x+m) mod MAXINT都不等价。例如，如果您将卡片保持未旋转，并沿着0（位于时钟表面顶部）直径翻转它，则1将映射为-1，2将映射为-2，依此类推。(x+m) mod MAXINT仅对卡片的旋转对应。

- High Performance Mark

---

据我理解，您提到了一个函数，可以定义为f(x)=(x+m) mod MAXINT，其中0<m<MAXINT。然而，它具有非常简单的逻辑，输出很容易预测。正如我在问题中提到的，我不使用XOR密码，它可以使用特别选择的密钥生成更好的输出。 - Emre Yazici