Как определить начальные значения генератора псевдослучайных чисел, если задана последовательность?

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

$x_{n+1}=(aX_n+c) \bmod m$

Если мне дают весь период (или, по крайней мере, большую смежную подпоследовательность этого), как я могу восстановить параметры и которые произвели эту последовательность? Я ищу общий метод, который сможет определить начальные параметры, если известен генератор псевдослучайных чисел. $a,c,m$ $x_0$

random-number-generation inverse-problem Пол
источник

Что именно известно? Из смежного последующего вы не можете сказать, где последовательность началась

, если элементы не проиндексированы в последовательности. Если

известно, то

легко обнаруживаются.

x_{0}

$x_0$

m

$m$

a

$a$

c

$c$

hardthth

Ответы:

См. Статью « Как взломать линейный конгруэнтный генератор» , Haldir («Reverse Engineering Team», декабрь 2004):

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

Документ включает в себя исходный код «доказательства концепции», написанный на C, с использованием NTL Виктора Шупа для арифметики повышенной точности.

hardmath
источник

Это была отличная статья! :) Знаете ли вы о более общем методе, который может применяться к другим генераторам случайных чисел, а не только к линейным конгруэнтным?

Павел

@Paul: Конечно, можно найти ГСЧ, которые легко «решаются» по своим параметрам по достаточным выходным данным (обратная задача), но может показаться, что чем лучше ГСЧ (более случайный вид выхода), тем сложнее обратный проблема была бы. Решение случая LCG связано с определенными размерными эффектами кластеризации, которые хорошо известны, делая пары сгенерированных значений неравномерно распределенными. Для получения дополнительной информации см. Проект криптографически

стойкого