В чем причина того, что генератор BBS выводит только n младших значащих бит или бит четности для каждого Xn, который он вырабатывает внутри? То есть, если он выводит полные Xn, которые он производит, есть ли способ отличить его от действительно случайной функции?
1 ответ
2
Обычный ответ на этот тип вопроса (зачем использовать только младший бит 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, и атакующий должен продолжать спрашивать цифры, пока модуль не вступит в игру.