Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Двоичная последовательность называется псевдослучайной, если она выглядит как бессистемная и вероятностная, хотя на самом деле создавалась посредством вполне детерминированного процесса, который называется псевдослучайным генератором. Такие генераторы начинают свою работу с действительно случайной исходной последовательностью, называемой начальной, и детерминировано вырабатывают с ее помощью гораздо более длинную псевдослучайную последовательность. В этом смысле псевдослучайные генераторы можно рассматривать как своего рода распространителей случайности. В качестве энциклопедии по классической генерации псевдослучайных последовательностей и тестам, цель которых заключается в том, чтобы с их помощью иметь возможность отличать псевдослучайные последовательности от истинно случайных, мы рекомендуем [236].
Случайность и криптография вообще очень сильно взаимосвязаны. Ведь основная цель криптографических систем состоит в том, чтобы преобразовать неслучайные осмысленные открытые тексты в кажущуюся случайной беспорядочную мешанину символов. Эта способность криптосистем может быть использована для генерации псевдослучайных последовательностей следующим образом. Пусть Ек — некоторый алгоритм шифрования, и пусть а?о — произвольный открытый текст. Рассмотрим последовательность, которая определяется как г,-+1 = ?*(*>') для
i > 0. Если Ек вполне подходит для криптографических целей, то по всей видимости последовательность xi, xi, ... — является последовательностью без явных признаков системности (хотя совершенно очевидно, что она обязательно дблжна зацикливаться). Может быть, для того чтобы уменьшить корреляцию в этой
Генерация псевдослучайных чисел 61
последовательности, было бы предпочтительнее из каждого *,• оставлять только несколько битов информации. \
Другой аспект взаимосвязи между свойствами случайных последовательностей и криптографией еще более интересен. Даже самые лучшие криптосистемы были бы бесполезны, если бы криптоаналитик мог угадывать используемый в них ключ (причем это замечание в одинаковой степени относится как к криптосистемам с секретным, так и к криптосистемам с открытым ключом). И по всей видимости, не существует лучшего способа предотвратить эту угрозу, чем выбирать ключ действительно случайным образом. Ведь именно отсутствие случайности в «телеграфных ключах» как раз и было главной причиной раскрытия Энигмы (Enigma) [187, 303]. В качестве простейшего примера рассмотрим одноразовый шифр, который уже был описан в § 3.2. Как мы там отмечали, эта криптосистема обладает совершенной секретностью, если только ее ключ действительно выбирается случайно, но в то же время может быть без особого труда раскрыта, если ключом в ней будет открытый текст на английском языке. Напомним, что основное неудобство одноразовых шифров заключается в том, что их ключи должны быть не только случайными, но также иметь в точности такую же длину, как и само шифруемое сообщение, и при этом использоваться только один раз.
В режиме обратной связи по выходу (OFB), который описан в § 3.5, криптография и случайность прекрасно объединяются: в нем для генерации псевдослучайной последовательности на основе двух коротких исходных векторов (к и So', из которых только к секретно) используется криптосистема, и полученная_таким образом последовательность применяется как одноразовый ключ для шифрования реальных сообщений открытого текста. Преимущество подобного подхода состоит в том, что секретный ключ к намного короче, чем открытый текст, и может быть использован повторно столько раз, сколько вы этого захотите, поскольку so при этом все равно каждый раз меняется (напомним, что «о задается в открытом виде как часть шифртекста, так что для обеспечения соответствующей стойкости необходимо лишь однажды передать начальный ключ к и все). Неизбежной платой за использование такого короткого ключа является, конечно, поте-
62 Системы с открытым ключом
Глава 4
ря совершенной секретности. Хотя, в принципе, может быть, что этот режим обратной связи по выходу является ни чем иным, как принятием желаемой за действительную эвристикой.
Скажем, что псевдослучайный генератор является криптографически сильным, если последовательность, которую он вырабатывает из (секретного) короткого начального двоичного вектора, является по существу точно такой же, как и по-настоящему случайная последовательность, применяемая для той цели, для которой она используется в одноразовом шифре. Под словами «по существу точно такой же» мы понимаем, что никакое практически легкоосуществимое вычисление, не может позволить криптоаналитику получить какую бы то ни было информацию об открытом тексте после перехвата его шифртекста (за исключением разве что с пренебрежимо малой вероятностью). Другими словами, он ведет себя точно так же, как если бы был совершенно секретным по Шеннону, до тех пор, пока для его криптоанализа не будет затрачено невообразимо большое количество времени. Подобные генераторы могут использоваться для реализации криптосистем с секретным ключом, если обе стороны договорились об исходном секретном векторе, который они собираются использовать, при условии что никогда не будут использовать один и тот же такой исходный вектор дважды. Намного менее очевидно, что криптографически сильные псевдослучайные генераторы могут быть использованы и при реализации криптосистем с открытым ключом, но в следующем параграфе мы покажем, что такое тоже возможно.
