Генерация случайных парольных фраз из наборов строк с помощью secrets.random не является очень случайной

Характер проблемы

Начнем с утверждения, что существует отображение 1 к 1 между k-мерным списком индексы для списков длины ℓ₁,...,ℓ_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

Использование этого с небольшим набором индексов довольно четко показывает отображение 1 к 1. Этот код:

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).

Вы можете подумать, что если взять выборку размером 10_000 из пула в 13 миллиардов целые числа, вероятность получения дубликатов будет близка к нулю. день рождения Проблема , также известная как парадокс дня рождения, говорит нам об обратном. Когда вы выбираете значения независимо, каждая дополнительная выборка имеет задачу избежать всех значений которые уже были отобраны. Вероятности уклонения изначально высоки, но они меньше 1 и уменьшаются по мере того, как количество выбранных значений увеличивается и умножается (из-за независимой выборки), поэтому вероятность всех из них одновременное отсутствие друг друга удивительно быстро уменьшается до нуля. Оказывается что при 365 днях в году (без учета високосных лет) вероятность получить к тому моменту, когда вы представите 23-го человека, число одного или нескольких повторяющихся дней рождения превысит 1/2. в группу. К тому времени, когда вы достигнете 57 человек, вероятность наличия двух или более дни рождения которых совпадают, превышает 0,99.

Размер пула 13_085_100_000 намного больше, чем 365, но логика работает та же. способ. Следующая программа показывает, что при размере выборки 10_000 целочисленных значений: аналитически полученная вероятность наличия одного или нескольких повторяющихся значений равна около 0,00381. Мы ожидаем, что в 38 из 10 000 таких экспериментов будет по крайней мере один дубликат. При размере выборки 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)
  # Use index_list to generate a unique password 
  # from the lists of component elements.

Это создаст все наборы индексов уникальным образом, но в случайном порядке. Переключите комментарии к строкам назначения list_lengths и установите размер выборки. до 10_000, чтобы получить рандомизированную подвыборку уникальных индексов в index_list.