S 5 Генерация ДсеаДослучаИных чисел 61

последовательности, было бы предпочтительнее из каждого г,-оставлять только несколько битов информации. \

Другой аспект взаимосвязи между свойствами случайных последовательностей и криптографией еще более интересен. Даже самые лучшие криптосистемы были бы бесполезны, если бы криптоаналитик мог угадывать используемый в них ключ (причем это замечание в одинаковой степени относится как к криптосистемам с секретным, так и к криптосистемам с открытым ключом). И по всей видимости, не существует лучшего способа предотвратить эту угрозу, чем выбирать ключ действительно случайным образом. Ведь именно отсутствие случайности в «телеграфных ключах» как раз и было главной причиной раскрытия Энигмы (Enigma) [187, 303]. В качестве простейшего примера рассмотрим одноразовый шифр, который уже был описан в § 3.2. Как мы там отмечали, эта криптосистема обладает совершенной секретностью, если только ее ключ действительно выбиргьется случайно, но в то же время может быть без особого труда раскрыта, если ключом в ней будет открытый текст на английском языке. Напомним, что основное неудобство одноразовых шифров заключается в том, что их ключи должны быть не только случайными, но также иметь в точности такую же длину, как и само шифруемое сообщение, и при этом использоваться только один раз.

В режиме обратной связи по выходу (OFB), который описан в § 3.5, криптография и случайность прекрасно объединяются: в нем для генерации псевдослучайной последовательности на основе двух коротких исходных векторов (к и So, из которых только к секретно) используется криптосистема, и полученная.таким образом последовательность применяется как одноразовый ключ для шифрования реальных сообщений открытого текста. Преимущество подобного подхода состоит в том, что секретный ключ к HciMHoro короче, чем открытый текст, и может быть использован повторно столько раз, сколько вы этого захотите, поскольку So при этом все равно каждый раз меняется (напомним, что sq задается в открытом виде как часть шифртекста, так что для обеспечения соответствующей стойкости необходимо лишь однажды передать начальный ключ к и все). Неизбежной пдатой за использование такого короткого ключа является, конечно, поте-

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

Скажем, что псевдослучайный генератор является криптографически сильным, если последовательность, которую он вырабатывает из (секретного) короткого начального двоичного вектора, является по существу точно такой же, как и по-настоящему случайная последовательность, применяемая для той цели, для которой она используется в одноразовом шифре. Под словами «по существу точно такой же» мы понимаем, что никакое практически легкоосуществимое вычисление не может позволить криптоаналитику получить какую бы то ни было информацию об открытом тексте после перехвата его шифртекста (за исключением разве что с пренебрежимо малой вероятностью). Другими словами, он ведет себя точно так же, как если бы был совершенно секретным по Шеннону, до тех пор, пока для его криптоанализа не будет затрачено невообразимо большое количество времени. Подобные генераторы могут использоваться для реализации криптосистем с секретным ключом, если обе стороны договорились об исходном секретном векторе, который они собираются использовать, при условии что никогда не будут использовать один и тот же такой исходный вектор дважды. Намного менее очевидно, что криптографически сильные псевдослучайные генераторы могут быть использованы и при реализации криптосистем с открытым ключом, но в следующем параграфе мы покажем, что такое тоже возможно.

Первый шаг к обоснованию криптографически сильных генераторов был сделан Эди Шамиром [316]. Впоследствии Мануэлем Блюмом и Сильвио Микэли в [57] было введено ключевое понятие псевдослучайных генераторов - так называемая непредикативность влево - когда криптоаналитик, который знает, как работает генератор, но не знает, какой исходный вектор используется при его работе, для того чтобы угадать первый бит, выработанный генератором, не может найти ничего лучшего, чем после анализа всей сгенерированной в результате последовательности, подбросить жребий (если, конечно, ему при этом анализе не слишком повезет, или если он не окажется в состоянии проделать практически невыполнимые вычисления). Как и обычно.

мы не знаем, существуют ли подобные генераторы, но первый кандидат на такой генератор был предложен Блюмом и Микэли [57}, которые доказали, что их генератор является непредикативным влево в предположении, что вычисление дискретных логарифмов является практически трудноосуществимым. То, что введение понятия непредикативности генераторов влево было вполне уместно, установил Эндрю Яо, доказав, что .пюбой такой генератор является криптографически сильным [364]. Наконец, Леонид Левин дал необходимые и достаточные условия для существования подобных генераторов [250]. См. также [219, 211].

Сейчас мы приведем описание более простого и в вычислительном отношении более эффективного кандидата на криптографически сильный псевдослучайный генератор, который известен как BBS-генератор, названный так в честь Леоноры Блюм, Мануэля Блюма и Майка Шуба [49]. Он основывается на нашем втором кандидате на однонаправленную функцию с потайным ходом, который был преставлен в § 1. Напомним, что п называется целым числом Блюма, если оно является произведением двух различных простых чисел р и q, оба из которых сравнимы с числом 3 по модулю 4. Напомним также, что в данном случае функция возведения в квадрат по модулю п является перестановкой квадратичных вычетов по модулю числа п, и считается, что она является однонаправленной функцией с потайным ходом, так как было доказано, что трудность ее обращения (то есть вычисления примитивных квадратных корней по модулю п) вычислительно эквивалентна разложению п на множители. В предположении, что факторизация числа п является трудной задачей, может быть доказана даже более сильная теорема: для почти всех квадратичных вычетов у по модулю п, то есть у = х mod п, к наилучшей (из всех возможных) выполнимой оценке того, каким должен быть первый значащий разряд х, приводит лишь подбрасывание жребия [349, 350, 8, 117]. Другими словами, оказывается, что практически трудно не только вычислить сам примитивный квадратный корень, но даже получить вероятностную информацию о его первом значащем бите (наподобие следующей: «Я не убежден, но мне все-таки кажется, что этот бит больше похож на нуль, чем на единицу»).

Теперь мы готовы описать BBS-генератор и доказать, что при