Извлечение начального начального значения PRNG?

Question

Я недавно прочитал, что вы можете предсказать результаты PRNG, если вы:

1. Знать, какой алгоритм используется.
2. Имеют последовательные точки данных.

Можно ли вычислить начальное число, используемое для ГСЧП, только из точек данных?

Answer 1

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

Answer 2

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

Например, типичный return seed=(seed*A+B)%N имеет обратную величину return seed=((seed-B)/A)%N.

Answer 3

Теоретически это всегда возможно, если вам «позволено» перебором всех возможных значений для начального числа, и если у вас достаточно точек данных, то есть только одно начальное число, которое могло бы произвести такой вывод.Если PRNG был посеян со временем, и вы примерно знаете, когда это произошло, то это может быть очень быстро, так как не так много правдоподобных значений, которые можно попробовать.Если PRNG был заполнен данными из действительно случайного источника, имеющего 64 бита энтропии, то этот подход невозможен в вычислительном отношении.

Существуют ли другие методы, зависит от алгоритма.Например, выполнение этого для Blum Blum Shub эквивалентно целочисленной факторизации, которая, как правило, считается сложной вычислительной проблемой.Другие, более быстрые PRNG могут быть менее «безопасными» в этом смысле.Любой PRNG, используемый для криптографических целей, например, в потоковом шифре, в значительной степени нуждается в неизвестном способе сделать это.