从带有秘密的字符串集中生成随机密码。随机不是很随机

Question

我需要一个基本的密码短语生成器，它使用一组单词列表，每个单词对应密码短语中的每个位置。

 def generate(self) -> str:
        passphrase = "%s-%s-%s-%s-%s%s%s" % (
            self.choose_word(self.verbs),
            self.choose_word(self.determiners),
            self.choose_word(self.adjectives),
            self.choose_word(self.nouns),
            self.choose_word(self.numbers),
            self.choose_word(self.numbers),
            self.choose_word(self.numbers),
        )

从中选择的列表包含 100 个形容词、9 个限定词、217 个名词、67 个动词和数字 1-9，并且使用 Secrets.choice 进行选择

    def choose_word(cls, word_list: List[str]) -> str:
        return secrets.choice(word_list)

理论上，我认为这将使我的密码数量低于 130 亿个。不过，我编写了一个测试用例，生成 10,000 个密码短语，并通过对生成的密码短语序列进行成员资格检查来检查它们是否都是唯一的

def test_can_generate_10000_passphrases_without_collision(passphrase: Passphrase):
    generated_passphrases = []
    for i in range(10000):
        generated_passphrase = passphrase.generate()
        assert generated_passphrase is not None and len(generated_passphrase) > 10
        assert generated_passphrase not in generated_passphrases
        generated_passphrases.append(generated_passphrase)

    assert len(generated_passphrases) == 10000

但是，测试并没有反映我预期的重复概率。使用 pytest-repeat，我将此测试设置为运行 10,000 次，在我终止进程之前，它在 4145 次运行中失败/生成了 24 次重复密码。在每种情况下，测试的输出都会被截断，但显示在生成的短语集中“”找到了选定的密码短语，并且该短语每次都不同。

我在这里并没有具体的问题，似乎我误解了一些东西，要么我的概率计算错误，我需要在列表中添加更多单词，要么关于序列检查中的测试正在做更宽松的事情符合我的预期。

我从 random.choices 切换到 Secrets.choices，我尝试在运行之间重新实例化密码生成器类，尝试添加检查密码是否为空（因为空字符串总是匹配），并且还尝试运行进出docker 容器认为可能有什么东西扰乱了随机性。

Answer 1

问题的性质

我们首先断言 k 维列表之间存在 1 对 1 映射 长度为 ℓ₁,...,ℓ_k 的列表和整数的索引 范围 [0,...,Π(ℓ₁,...,ℓ_k)-1]，其中 Π 表示 一组值的乘积。

以下 python 类显示了执行该映射的数学实现。

class Mapping:

  def __init__(self, dimensions):
    self.dimensions = dimensions
    self.n_dimensions = len(dimensions)
    self.cumulative = dimensions.copy()
    self.cumulative.append(1)
    for i in range(1, self.n_dimensions):
      idx = self.n_dimensions - i
      self.cumulative[idx] *= self.cumulative[idx+1]
    self.capacity = self.cumulative.pop(0)
    self.capacity *= self.cumulative[0]

  def indices_to_int(self, indices):
    result = 0
    for i in range(self.n_dimensions):
      result += indices[i] * self.cumulative[i]
    return result

  def int_to_indices(self, index):
    indices = [None] * self.n_dimensions
    for i in range(self.n_dimensions):
      indices[i] = index // self.cumulative[i]
      index -= indices[i] * self.cumulative[i]
    return indices

将其与一小组索引一起使用可以非常清楚地显示一对一映射。 此代码：

list_lengths = [2,3,4]
map = Mapping(list_lengths)

int_set = range(map.capacity)
for number in int_set:
  index_list = map.int_to_indices(number)
  print(number, index_list, map.indices_to_int(index_list))

产生下面给出的结果。输出由左列中的一个整数组成，该整数映射到列表 索引值位于中心。该列表随后被映射回原始列表 整数来演示映射的 1 对 1 性质。

0 [0, 0, 0] 0
1 [0, 0, 1] 1
2 [0, 0, 2] 2
3 [0, 0, 3] 3
4 [0, 1, 0] 4
5 [0, 1, 1] 5
6 [0, 1, 2] 6
7 [0, 1, 3] 7
8 [0, 2, 0] 8
9 [0, 2, 1] 9
10 [0, 2, 2] 10
11 [0, 2, 3] 11
12 [1, 0, 0] 12
13 [1, 0, 1] 13
14 [1, 0, 2] 14
15 [1, 0, 3] 15
16 [1, 1, 0] 16
17 [1, 1, 1] 17
18 [1, 1, 2] 18
19 [1, 1, 3] 19
20 [1, 2, 0] 20
21 [1, 2, 1] 21
22 [1, 2, 2] 22
23 [1, 2, 3] 23

这意味着您尝试从以下位置生成元素的独特组合的问题 一组列表相当于在明确定义的范围内生成一组唯一的整数值。 列表长度为

[2,3,4]

，即

range(2*3*4)

。对于您的实际问题， 适用范围为

range(100*9*217*67*10*10*10)

，即

range(13_085_100_000)

。

您可能会认为，如果从 130 亿的池中取出大小为 10_000 的样本 整数，获得重复项的机会接近于零。 生日 问题，也称为生日悖论，告诉我们事实并非如此。当您对值进行采样时 独立地，每个附加样本都有避免 all 值的任务 已经采样过的。回避的概率一开始很高，但小于 1，并且随着回避概率的增加而减小 采样值的数量增加并成倍增加（由于独立采样），因此所有这些值的概率 同时相互错过的概率惊人地迅速减少到零。事实证明 一年有 365 天（忽略闰年），得到的概率 当您介绍第 23 个人时，一个或多个重复生日已超过 1/2 到小组。当你达到 57 人时，有两个或更多人的概率 生日相同的人超过 0.99。

13_085_100_000的池大小比365大得多，但逻辑工作原理相同 方式。以下程序显示，样本大小为 10_000 个整数值， 通过分析得出的具有一个或多个重复值的概率为 约0.00381。我们预计 10_000 个此类实验中至少有 38 个 一份重复。样本量为 135_000 时，重复的概率超过 0.5。

import fractions

pool_size = fractions.Fraction(13_085_100_000)  # use big-integer rational arithmetic
samp_size = 10_000
p_no_duplicates = fractions.Fraction(1)  # no duplicates when one item in the room...
numerator = fractions.Fraction(pool_size + 1)

# ...so start with the second item.
for i in range(2, samp_size): # i is number of items currently in the room
  p_no_duplicates *= fractions.Fraction(numerator - i) / pool_size
print("For " + str(samp_size) + " items and a pool size of " +
  str(pool_size) + ", P(Duplicate) = " + str(1.0 - p_no_duplicates))

# For 10000 items and a pool size of 13085100000, P(Duplicate) = 0.0038127078842439266

一个可能的解决方案

一个可能的解决方案是使用Python的

random.sample()

，它可以进行无替换采样。这意味着 一旦选择了一个值，它就会从剩余候选池中删除。 （这会改变池中所有剩余值的概率，因此这“不是”独立抽样。） 在整个过程之前不会出现重复的情况 池已被采样。 使用 random.sample() 将保证唯一的整数，然后可以将其映射到 一组独特的索引，可用于构建您的密码短语组。以下使用

[2,3,4]

索引说明了这一点 从前面的例子来看：

import random

# list_lengths = [100,9,217,67,10,10,10]
list_lengths = [2,3,4]
map = Mapping(list_lengths)

int_set = random.sample(range(map.capacity), map.capacity)
for number in int_set:
  index_list = map.int_to_indices(number)
  print(number, index_list, map.indices_to_int(index_list))

这将唯一地生成所有索引集，但顺序是随机的。
切换 

list_lengths

分配行上的注释并设置样本大小 到 10_000 以获得

index_list

中唯一索引的随机子样本。