Блюм Блюм Шуб PRG

553

В чем причина того, что генератор BBS выводит только n младших значащих бит или бит четности для каждого Xn, который он вырабатывает внутри? То есть, если он выводит полные Xn, которые он производит, есть ли способ отличить его от действительно случайной функции?

1
"Блум Блум Шуб"? Это генератор случайных чисел или тонущий Стог? phenry 15 лет назад 2
@phenry: это генератор случайных чисел: http://en.wikipedia.org/wiki/Blum_Blum_Shub Thilo 15 лет назад 1

1 ответ на вопрос

2
Chris Johnsen

Обычный ответ на этот тип вопроса (зачем использовать только N битов самого младшего порядка?) Заключается в том, что он предотвращает утечку слишком большого количества информации о внутреннем состоянии PRNG.

Если вы дадите атакующему ваше полное состояние X_n в двух последовательных состояниях, они могут легко (?) Определить модуль и, таким образом, вычислить все будущие состояния PRNG.

То есть, учитывая значения a = X_n и b = X_ (n + 1), злоумышленнику нужно только найти M, такое что b = a ^ 2 mod M. Пока a ^ 2 больше, чем M, я думаю, что это должно быть легко сделать. Если M больше, чем ^ 2, то b = a ^ 2, и атакующий должен продолжать спрашивать цифры, пока модуль не вступит в игру.

Похожие вопросы