Blum Blum Shub PRG
Какова причина позади того, что генератор BBS только производит n младшие значащие биты или бит четности для каждого Xn, который это производит внутренне? Таким образом, если это производит полного Xn, которого это производит, там способ дифференцировать его от действительно случайной функции?
1 ответ
Обычный ответ на этот тип вопроса (почему использование только биты N самые низкоуровневые?) то, что это предотвращает утечку слишком большой информации о внутреннем состоянии PRNG.
Если Вы даете Вашему взломщику свое полное состояние X_n в двух последовательных состояниях, они могли бы легко(?) определить модуль и таким образом вычислить все будущие состояние PRNG.
Таким образом, учитывая значения = X_n и b = X _ (n+1), взломщик должен только найти M таким образом что b = a^2 модификация M. Целый a^2 больше, чем M, я думаю, что это должно быть легко сделать. Если M больше, чем a^2, то b = a^2 и взломщик должен продолжать просить числа, пока модуль не играет роли.