0

我正在寻找一个输入 0、1、2、3....N 的函数。它的结果应该是相同的输入数组，只是“随机”排列。结果必须是唯一的，因此所有这些都是生成的。现在，我知道/不介意对于所有 0、1、....N 的列表，将输出相同的结果。这是意料之中的，很好，我只希望结果是随机输入的。

我发现了这个功能：

function perm( x )
{
    return x * 833 % N;
}

其中 833 可以是任何大的素数。这会产生不错的结果，但它们总是具有重复模式。参见 N = 16：0 3 6 9 12 15 2 5 8 11 14 1 4 7 10 13

想象一下它看起来像 3 个鲨鱼鳍。基本上我的问题是，我如何制作一个函数来完成我所描述的但更混乱的洗牌？

4

2 回答 2

4

线性同余算法将始终显示该线性模式。你可能更想要一个块密码。参见例如here和这个相关问题

你的小长度，一个更实用的解决方案将是一个预先生成的排列表（如建议的另一个答案 - 你相当粗鲁地拒绝并被删除）。

于 2013-04-30T18:20:28.877 回答
0

如果数组适合内存，那么您可能需要使用Fisher-Yates shuffle。那是，

  1. 播种伪随机数生成器 (PRNG)
  2. 使用我称之为的索引遍历列表的每个元素i。
  3. 将出现在位置i的元素与位置≥<code>的另一个元素交换，我由PRNG随机（统一）选择。

对于小于几百万个元素的排列，这是一个非常好的解决方案。

如果数组不适合内存，那么您可能想要使用像块密码这样更高级的东西，正如@leonbloy 所建议的那样。这会带来一系列并发症......

作为排列的分组密码在密码学中自然出现。如果您有所有可能的 128 位字符串的秘密排列，那么您可以通过将消息分成 128 位块（必要时填充这些块）并将排列应用于每个块来加密消息。（我不是在谈论扰乱 128 位的位顺序，而是以任何可逆方式扰乱所有 128 位位串的集合。）对于密码学家来说，不能以任何方式对排列进行逆向工程是很重要的，因为这会破坏加密。无论您个人是否关心对您的排列进行逆向工程，如果您想通过已建立的加密文献中的分组密码生成随机排列，您将遇到由于密码安全性考虑而引起的复杂情况......

除非n您希望置换的元素数量恰好与密码的 (2 ^ blocksize) 一致，否则如何生成置换并不明显。如果没有一个聪明的想法，如果n不是 2 的幂，那么你就不走运了。更糟糕的是，最常见且已建立的分组密码具有固定的分组大小。（例如，AES 的块大小为 128 位，适用于对 2^128 个元素进行排列。）

n当不是 2 的幂时采用分组密码的一种潜在策略称为循环游走。将输入的整数从区间[0, n - 1]嵌入到较大的区间中[0, 2 ^ block_size]并应用分组密码。如果结果在期望的区间之外[0, n - 1]，则重复应用分组密码，直到结果落在范围内。但是一个可用的实现仍然需要一些工作......

自行车步行的平均效率是 n / 2 ^ blocksize。举例来说，如果n是 200 万并且我们使用 AES，那么效率是无穷小的5.9e-33，并且返回任何结果都需要很长时间。因此，使用具有可变长度块大小的密码实际上很重要。然后理想情况下选择块大小为最小整数，使得n≤（2 ^块大小），效率将大于50％......

在密码学中，更大的块大小往往更安全，并且大多数可变长度的块密码具有相当大的最小块大小。这是因为小块大小的密码容易受到更多攻击。事实上，在密码学中是否存在一个有效且理论上合理的、具有小块大小的块密码似乎是一个悬而未决的问题。如果我们n的大小约为 2^30，但唯一可用的块密码的最小块大小为 64，那么我们的效率将非常糟糕......

NIST 批准的一种合适的解决方案是 FF3，由于存在小块大小的漏洞，该解决方案已被修订为 FF3-1。（虽然这是一个小的改进，但 FF3-1 没有理论上的保证，因此它可能存在其他类似的漏洞。）

基于以上所有考虑，以下是自行车步行的快速 Python 实现。

from typing import Callable, Optional


def cycle_walk(i: int, n: int, cipher: Callable[[str], str]) -> int:
    working_digits = len(int_to_bin(n - 1))
    i_as_str = int_to_bin(i, num_digits=working_digits)
    out_candidate_str = cipher(i_as_str)
    out_candidate_int = int(out_candidate_str, 2)
    if out_candidate_int >= n:
        return cycle_walk(out_candidate_int, n, cipher)
    else:
        return out_candidate_int


def int_to_bin(i: int, num_digits: Optional[int] = None) -> str:
    """Convert an integer to a binary string of 0s and 1s."""
    assert i >= 0
    s = bin(i)[2:]
    if num_digits is not None:
        assert len(s) <= num_digits
        s = s.zfill(num_digits)
    return s

这些功能旨在与FF3-1 的此实现兼容。我们创建密码如下：

from ff3 import FF3Cipher

key = "EF4359D8D580AA4F7F036D6F04FC6A94"
tweak = "D8E7920AFA330A73"

cipher = FF3Cipher(key, tweak, radix=2).encrypt

您可以将上面的键和调整视为 PRNG 种子。

最后，我们计算一个置换索引如下：

cycle_walk(i=42, n=1_100_003, cipher=cipher)  # 295427

有了n这么小，实际上仍然可以计算完整的排列表并验证它是一个排列：

# This will take several minutes to generate the full permutation table.
permutation = [cycle_walk(i, 1_100_003, cipher) for i in range(1_100_003)]

# Verify that all the numbers are within the correct range.
assert [] == [i for i in permutation if not 0 <= i < len(permutation)]

# Verify that there are no duplicates.
assert len(set(permutation)) == len(permutation)

免责声明：

  • 我不是密码学家。如果您需要生成加密安全排列，请与专家讨论。
  • 我的回答只是一个下午好奇的结果。我不太了解文献，所以可能有一些我不知道的更简单的已知方法。如果有，请告诉我！
于 2021-09-19T17:02:36.883 回答