Почему мы не объединяем генераторы случайных чисел?

Существует множество приложений, в которых используется генератор псевдослучайных чисел. Поэтому люди реализуют то, что, по их мнению, замечательно, но потом обнаруживают, что оно ошибочно. Нечто подобное произошло с генератором случайных чисел Javascript в последнее время. RandU намного раньше тоже. Есть также проблемы неподходящего начального посева для чего-то вроде Twister.

Я не могу найти примеров того, как кто-нибудь объединял два или более семейств генераторов с обычным оператором xor. Если у компьютера достаточно мощности для запуска таких вещей, как реализации java.SecureRandom или Twister, почему люди не объединяют их? ISAAC xor XORShift xor RandU должен быть довольно хорошим примером, где вы можете увидеть слабость одного генератора, смягчаемую другими. Это также должно помочь с распределением чисел в более высокие измерения, поскольку внутренние алгоритмы совершенно разные. Есть ли какой-то фундаментальный принцип, что их не следует объединять?

Если бы вы создали настоящий генератор случайных чисел, люди, вероятно, посоветовали бы вам объединить два или более источника энтропии. Мой пример отличается?

Я исключаю общий пример работы нескольких регистров сдвига с линейной обратной связью, поскольку они принадлежат к одному семейству.

IIRC (и это по памяти), бестселлер Rand 1955 года A Million Random Digits сделал нечто подобное. Прежде чем компьютеры стали дешевыми, люди выбирали случайные числа из этой книги.

Авторы генерировали случайные биты с электронным шумом, но это оказалось смещением (трудно сделать триггер, потраченный ровно столько же раз на триггер и флоп). Однако объединение битов сделало распределение намного более равномерным.

Конечно, вы можете комбинировать PRNG, как это, если хотите, при условии, что они посеяны независимо. Однако, это будет медленнее и, вероятно, не решит самые насущные проблемы людей.

На практике, если у вас есть потребность в очень высококачественном PRNG, вы используете хорошо проверенный PRNG с криптографической стойкостью, и вы засеиваете его истинной энтропией. Если вы сделаете это, ваш наиболее вероятный режим сбоя не является проблемой самого алгоритма PRNG; наиболее вероятный режим отказа - отсутствие адекватной энтропии (или, возможно, ошибки реализации). Использование нескольких PRNG не помогает в этом режиме отказа. Так что, если вы хотите очень качественный PRNG, вероятно, нет смысла их хранить.

В качестве альтернативы, если вам нужен статистический PRNG, который достаточно хорош для целей моделирования, обычно проблемой № 1 является либо скорость (очень быстрое генерирование псевдослучайных чисел), либо простота (не нужно тратить много времени на разработку или исследование). Xoring замедляет PRNG и делает его более сложным, поэтому он также не отвечает основным потребностям в этом контексте.

Пока вы проявляете разумную заботу и компетентность, стандартные PRNG более чем достаточно хороши, поэтому на самом деле нет никаких причин, по которым нам нужно что-то более изощренное (не нужно делать xor-ing). Если у вас нет даже минимального уровня обслуживания или компетенции, вы, вероятно, не собираетесь выбирать что-то сложное, например, занятие хорингом, и лучший способ улучшить ситуацию - это сосредоточиться на большей заботе и компетентности при выборе PRNG. а не на xor-ing.

Итог : по сути, трюк xor не решает проблемы, которые обычно возникают у людей при использовании PRNG.

Фактически, что-то о прорыве было только что объявлено, сделав именно это.

Профессор информатики Техасского университета Дэвид Цукерман и аспирант Эшан Чаттопадхьяй обнаружили, что «высококачественное» случайное число может быть получено путем объединения двух «некачественных» случайных источников.

Вот их статья: Явные экстракторы с двумя источниками и упругие функции

Предположим, что - псевдослучайная двоичная последовательность. То есть каждый X i является случайной величиной, поддерживаемой в { 0 , 1 } , а переменные X 1 , … , X n не обязательно являются независимыми. Мы можем думать о том, что эта последовательность генерируется следующим образом: сначала мы выбираем равномерно случайный ключ K , а затем используем некоторую функцию f ( K $X_1,\ldots,X_n$$X_i$$\{0,1\}$$X_1,\ldots,X_n$$K$$f(K)$ для генерации псевдослучайной последовательности.

Как измерить, насколько хороша псевдослучайная последовательность ? Хотя можно измерить, насколько хороша конкретная реализация (скажем, с помощью колмогоровской сложности), здесь я сосредоточусь на мерах, которые зависят от всего распределения случайной величины ( X 1 , … , X n ) . Одним из таких примеров является энтропия, но нам потребуются только два свойства нашей меры L : (большее L ( ⋅ ) означает более случайную последовательность)$X_1,\ldots,X_n$$(X_1,\ldots,X_n)$$L$$L(\cdot)$

• Если $y_1,\ldots,y_n$ является детерминированной последовательности (то есть, фиксированная последовательность) , то .$L(X_1 \oplus y_1, \ldots, X_n \oplus y_n) = L(X_1,\ldots,X_n)$

• Если - две независимые псевдослучайные последовательности, T ∈ { 0 , 1 } - независимый случайный бит, и → Z = → X $\vec{X^0},\vec{X^1}$$T \in \{0,1\}$$\vec{Z} = \vec{X^T}$ , то .$L(\vec{Z}) \geq \min(\vec{X^0},\vec{X^1})$

Первое свойство означает, что мера является инвариантной при переключении го бита. Второе свойство означает, что если мы смешаем два распределения → X , → $i$$\vec{X},\vec{Y}$ , то результат будет, по крайней мере, таким же хорошим, как и худший.

Любая разумная мера случайности будет удовлетворять первому свойству. Второе свойство удовлетворяется наиболее популярными мерами, такими как энтропия и минимальная энтропия H ∞ .$H$$H_\infty$

Теперь мы можем сформулировать и доказать теорему, показывающую, что XOR для двух псевдослучайных последовательностей всегда является хорошей идеей.

Теорема. Пусть - две независимые псевдослучайные последовательности одинаковой длины, и пусть $\vec{X},\vec{Y}$$L$ - допустимая мера случайности (одна удовлетворяет двум вышеуказанным условиям). Тогда

Доказательство. Предположим, что . Тогда X ⊕ Y является смесью распределений X ⊕ y , смешанных по распределению $L(X) \geq L(Y)$$X \oplus Y$$X \oplus y$$Y$ . Поскольку и смесь, по крайней мере, так же хороша, как и наихудшее распределение при смешивании, мы получаем L ( X ⊕ Y ) ≥ L ( X ) . $L(X \oplus y) = L(X)$$L(X \oplus Y) \geq L(X)$$~\square$

Эта теорема означает, что если вы XOR две псевдослучайные последовательности, сгенерированные с использованием двух независимых ключей, результат всегда будет по меньшей мере таким же хорошим, как и лучшая последовательность XORed, относительно любой допустимой меры случайности.

На практике, чтобы использовать два независимых ключа, мы, вероятно, расширяем один ключ до двух ключей псевдослучайным образом. Эти два ключа не являются независимыми. Однако, если мы используем «дорогой» способ расширения одного ключа на два ключа, мы ожидаем, что полученные два ключа будут «выглядеть» независимыми, и поэтому теорема будет «морально». В теоретической криптографии есть способы сделать это утверждение точным.

Должны ли мы тогда XOR два генератора псевдослучайных чисел? Если мы не ограничены скоростью, то это, безусловно, хорошая идея. Но на практике у нас есть ограничение скорости. Затем мы можем задать следующий вопрос. Предположим, что нам даны два PRNG, каждый с параметром который управляет временем работы (и, следовательно, мощностью) генератора. Например, T может быть длиной LFSR или количеством раундов. Предположим, что мы используем один PRNG с параметром T 1 , другой с параметром T 2 и XOR результат. Можно предположить, что T 1 + T 2 = t , так что общее время работы постоянно. Какой лучший выбор$T$$T$$T_1$$T_2$$T_1 + T_2 = t$$T_1,T_2$ ? Здесь есть компромисс, на который сложно ответить вообще. Может случиться так, что настройка намного хуже, чем ( t , 0 ) или ( 0 , t ) .$(t/2,t/2)$$(t,0)$$(0,t)$

Лучший совет здесь - придерживаться популярного PRNG, который считается сильным. Если вы можете сэкономить больше времени для генерации своей последовательности, сделайте XOR несколько копий, используя независимые ключи (или ключи, сгенерированные путем расширения одного ключа с использованием дорогого PRNG).

Я дам этому шанс, так как я достаточно обеспокоен советом, данным в некоторых других ответах.

Пусть - бесконечные битовые последовательности, сгенерированные двумя RNG (не обязательно PRNG, которые являются детерминированными после того, как известно начальное состояние), и мы рассматриваем возможность использования последовательности → X ⊕ → Y с надеждой на улучшение поведения в каком-то смысле. Есть много разных способов, которыми → X ⊕ → Y можно считать лучше или хуже по сравнению с каждым из → X и → Y ; Вот небольшая горстка, которая, я считаю, имеет смысл, полезна и согласуется с обычным употреблением слов «лучше» и «хуже»:$\vec{X},\vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X}$$\vec{Y}$

• (0) Вероятность истинной случайности последовательности увеличивается или уменьшается
• (1) Вероятность наблюдаемой неслучайности увеличивается или уменьшается (по отношению к некоторому наблюдателю, применяющему определенное количество проверки, предположительно)
• (2) Степень / очевидность наблюдаемой неслучайности увеличивается или уменьшается.

$\vec{X},\vec{Y}$$\varepsilon_X,\varepsilon_Y$$\vec{X} \oplus \vec{Y}$$\leq \varepsilon_X \varepsilon_Y \lt min\{\varepsilon_X,\varepsilon_Y\}$$\varepsilon_X,\varepsilon_Y$$\vec{X},\vec{Y}$

Однако (0) не представляет интереса для PRNG, поскольку в случае PRNG ни одна из рассматриваемых последовательностей не имеет шансов быть действительно случайной.

Поэтому для этого вопроса, который на самом деле касается PRNG, мы должны говорить о чем-то вроде (1) или (2). Так как они с точки зрения свойств и величин, таких как «наблюдаемый», «серьезный», «очевидный», «очевидный», мы сейчас говорим о колмогоровской сложности, и я не буду пытаться уточнить это. Но я пойду настолько далеко, что сделаю, надеюсь, неоспоримое утверждение, что с помощью такой меры «01100110 ...» (период = 4) хуже, чем «01010101 ...» (период = 2), что хуже, чем « 00000000 ... "(постоянный).

$\vec{X}$$\vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X} = \vec{Y}$$\vec{X} = \mathrm{not}(\vec{Y})$$\vec{X} \oplus \vec{Y}$$\vec{X}$$\vec{Y}$$\vec{X}$$\vec{Y}$$\vec{X} \oplus \vec{Y}$

Такая неожиданная зависимость оказывается действительно большой проблемой.

Пример того, что идет не так

Вопрос гласит: «Я исключаю общий пример нескольких регистров сдвига с линейной обратной связью, работающих вместе, поскольку они принадлежат к одному семейству». Но я собираюсь на время исключить это исключение, чтобы привести очень простой и понятный пример из жизни, который может пойти не так с XORing.

Моим примером будет старая реализация rand (), которая была в какой-то версии Unix около 1983 года. IIRC, эта реализация функции rand () имела следующие свойства:

• значение каждого вызова rand () составляло 15 псевдослучайных битов, то есть целое число в диапазоне [0, 32767).
• последовательные возвращаемые значения чередуются четно-нечетно-четно-нечетно; то есть младший значащий бит чередуется 0-1-0-1 ...
• $2^{15}$
• поэтому последовательность 15-битных возвращаемых значений rand () была периодической с периодом $2^{15}$

Мне не удалось найти исходный исходный код, но я предполагаю, что собрав воедино пару постов из https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A, которые он сделал именно следующее (код C), что согласуется с моей памятью о свойствах выше:

#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

Как можно себе представить, попытка использовать этот rand () различными способами привела к целому ряду разочарований.

Например, в какой-то момент я попытался смоделировать последовательность случайных бросков монет, многократно взяв:

rand() & 1

$i$$i-1$ «бесполезно» здесь; все, что мы действительно можем сказать, это то, что пронумерованные позиции битов были различной степени полезности / бесполезности.

Я также пробовал такие вещи, как дальнейшее скремблирование результатов или объединение значений XOR, возвращаемых из нескольких вызовов rand (). Конечно, XOR для пар последовательных значений rand () был катастрофой - он приводил ко всем нечетным числам! Для моих целей (а именно, для создания «очевидно случайной» последовательности бросков монет) результат XOR с постоянной четностью был даже хуже, чем чередующееся четно-нечетное поведение оригинала.

$\vec{X}$$s_X$$\vec{Y}$$s_Y$$\vec{X} \oplus \vec{Y}$ будет последовательностью либо всех четных, либо полностью нечетных чисел, что хуже, чем исходное чередующееся четное / нечетное поведение.

Другими словами, это пример, когда XOR ухудшил ситуацию в смысле (1) и (2), с помощью любой разумной интерпретации. Хуже и в нескольких других отношениях:

• (3) младший значащий бит XOR явно смещен, то есть имеет неравные частоты 0 и 1, в отличие от нумерованного положения бита на любом из входов, которые все несмещены.
• (4) На самом деле, для каждой позиции бита есть пары начальных чисел, для которых эта позиция бита смещена в результате XOR, и для каждой пары начальных чисел существуют (по крайней мере 5) позиции битов, которые смещены в XOR результат.
• $2^{14}$$2^{15}$ для оригиналов.

Ни одно из (3), (4), (5) не является очевидным, но все они легко проверяемы.

Наконец, давайте рассмотрим повторное введение запрета на PRNG из одной семьи. Проблема здесь, я думаю, заключается в том, что никогда не ясно, являются ли два PRNG «одного и того же семейства», до тех пор, пока / если кто-то не начнет использовать XOR и не заметит (или не заметит злоумышленник), что вещи стали хуже в смысле (1) и (2), то есть до тех пор, пока неслучайные паттерны в выходных данных пересекают порог от незамеченного к заметному / смущающему / катастрофическому, и в этот момент уже слишком поздно.

Я встревожен другими ответами здесь, которые дают безоговорочный совет «XOR не может навредить» на основе теоретических мер, которые, как мне кажется, плохо справляются с моделированием того, что большинство людей считают «хорошим» и «плохим» в отношении PRNGs в реальной жизни. Этот совет противоречит ясным и вопиющим примерам, в которых XOR ухудшает ситуацию, например, приведенному выше примеру rand (). Хотя вполне возможно, что относительно «сильные» PRNG могли последовательно отображать противоположное поведение, когда XORed к поведению игрушечного PRNG, который был rand (), тем самым делая XOR хорошей идеей для них, я не видел никаких доказательств в этом направлении, теоретических или эмпирически, поэтому мне кажется необоснованным предполагать, что это происходит.

Лично, будучи застигнутым врасплох XORing rand () в моей юности и бесчисленными другими неожиданными корреляциями в течение всей моей жизни, у меня нет особых оснований полагать, что результат будет другим, если я попробую подобную тактику снова. Вот почему я лично очень неохотно делаю XOR вместе с несколькими PRNG, если только не был проведен очень тщательный анализ и проверка, чтобы дать мне некоторую уверенность в том, что это может быть безопасно сделать для конкретных рассматриваемых RNG. Как потенциальное лекарство от того, когда у меня низкая уверенность в одном или нескольких отдельных PRNG, их XOR вряд ли увеличит мою уверенность, поэтому я вряд ли буду использовать его для этой цели. Я полагаю, что ответ на ваш вопрос заключается в том, что это широко распространенное мнение.

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Этот ответ строго о «мы не делаем это», а не «вот математическое доказательство того, почему он может или не может работать». Я не утверждаю, что XOR вводит (или нет) какие-либо криптографические уязвимости. Моя точка зрения заключается лишь в том, что опыт показывает нам, что даже самые простые схемы почти всегда приводят к непредвиденным последствиям, и именно поэтому мы их избегаем.

«Случайность» - это лишь верхушка айсберга, когда речь заходит о ГСЧ и ГСЧ. Есть и другие важные качества, например, однородность.

Представьте себе обычную игру в кости, которая сама по себе является неплохой ГСЧ. Но теперь допустим, что вам нужен диапазон 1-5 вместо 1-6. Первое, что приходит на ум, - это просто стереть лицо 6 и заменить его дополнительным 1. «Случайность» сохраняется (результаты по-прежнему действительно случайны), однако единообразие сильно страдает: теперь 1 в два раза чаще, чем другие результаты.

Объединение результатов от нескольких ГСЧ является аналогичным скользким уклоном. Например. простое добавление бросков в 2 кубика полностью уничтожает любую однородность, поскольку «7» теперь в 6 раз чаще, чем «2» или «12». Я согласен, что XOR выглядит лучше, чем сложение на первый взгляд, но в PRNG ничего не получается, как выглядит на первый взгляд.

Вот почему мы склонны придерживаться известных реализаций - потому что кто-то потратил кучу времени и денег на их исследование, и все недостатки хорошо известны, понятны и могут быть устранены. Когда вы развертываете свою собственную, вы потенциально создаете уязвимости, и вам следует приложить аналогичные усилия, чтобы доказать это. Как показывает пример добавления костей, комбинирование может не сильно отличаться от создания нового с нуля.

Безопасность - это цепочка, настолько сильная, насколько это слабый компонент. Эмпирическое правило в безопасности: когда вы объединяете две вещи, вы обычно получаете сумму недостатков, а не сумму сильных сторон.