Начальное число и его длина. Начальное число для генератора псевдослучай-
ных чисел сродни криптографическому ключу системы шифрования; начальное
число должно выбираться равномерно и храниться в секрете от любого противни-
ка. Еще один важный момент, очевидный из обсуждения атак методом перебора,
заключается в том, что s должно быть достаточно длинным, чтобы невозможно
было перечислить все возможные начальные числа. В асимптотическом смысле
это предусматривается посредством задания длины начального числа равного па-
раметру безопасности, чтобы поиск методом полного перебора всех возможных
начальных чисел требовал экспоненциального времени. На практике же началь-
ное число должно быть достаточно длинным, чтобы было невозможно перепро-
бовать все возможные начальные числа в пределах некоторых временных границ.
О существовании генераторов псевдослучайных чисел. Существуют гене-
раторы псевдослучайных чисел? Безусловно, кажется, что создать их достаточно
сложно, и кто-то справедливо может задаваться вопросом, существует ли какой-
либо алгоритм, соответствующий определению 3.14. Хотя мы не знаем, как без-
оговорочно доказать существование генераторов псевдослучайных последователь-
ностей, у нас есть веские основания верить, что они существуют. Например, они
могут быть созданы при достаточно слабом допущении, что существуют необра-
тимые функции (что верно, если некоторые задачи, как разложение больших чисел
на множители, сложны). Мы подробнее обсудим это в Г лаве 7. Также мы имеем
несколько практических конструкций, потенциально возможных генераторов псев-
дослучайных последовательностей, называемых поточными шифрами, для кото-
рых неизвестны эффективные дистинкторы. (Позднее мы представим более силь-
ные примитивы, называемые блочными шифрами.) Далее мы сделаем обобщенный
обзор поточных шифров и обсудим конкретные поточные шифры в Г лаве 6.
Достарыңызбен бөлісу: |