идентичных компьютера, и оба они подсчитают одно и то же. Компьютер может находиться только в огран и-ченном числе состояний (очень большом, но все же ограниченном) , и выдаваемый результат всегда будет строго определяться исходными данными и текущим состоянием компьютера . Это значит, что любой генератор случайных чисел на компьютере (по меньшей мере, на конечном автомате), по определению, периодичен. А все, что периодично, по определению, предсказуемо . А все, что предсказуемо, не может быть случайным . Для настоящего генератора случайных чисел нужно подавать на вход что-нибудь случайное, компьютер же не может обеспечить это требование.

Псевдослучайные последовательности

Лучшее, что может сделать компьютер - это генератор псевдослучайных последовательностей Что это

такое? Многие пытались дать его формальное определение, но я уклонюсь от этого. Псевдослучайная послед о-вательность - это что-то, выглядящее как случайное . Период последовательности должен быть достаточно в е-лик, поэтому конечная последовательность разумной длины - которая в действительности и используется - не периодична. Если вам нужен миллиард случайных бит, не пользуйтесь генератором последовательности, повт о-ряющейся каждые шестнадцать тысяч бит. Эти относительно короткие непериодические подпоследовательности должны быть, насколько это возможно, неотличимы от случайных последовательностей . Например, в них должно быть примерно одинаковое количество единиц и нулей, около половины серий (последовательностей одинаковых бит) должны быть единичной длины , четверть - состоять из двух бит, восьмая часть - из трех, и т.д. Эти последовательности должны быть несжимаемы . Распределение длин серий для нулей и единиц должно быть одинаковым [643, 863, 99, 1357]. Эти свойства могут быть измерены опытным путем и затем сравнены с ожидаемыми статистически с помощью статистики хи-квадрат. Для наших целей генератор последовательн ости считается псевдослучайным, если он обладает следующим свойством :

1. Он выглядит случайно. Это означает, что он проходит все тесты на случайность, которые нам удалось найти. (Начните с приведенных в [863].)

Множество усилий было затрачено на создание хороших псевдослучайных последовательностей на компь ю-тере. Обсуждение генераторов в большом количестве можно найти в академической литературе вместе с ра з-личными тестами на случайность. Все эти генераторы периодичны (этого невозможно избежать), но, если их период 2256 и выше, они могут быть использованы в самых серьезных приложениях .

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

Криптографически безопасные псевдослучайные последовательности

Криптографические приложения предъявляют к генератору псевдослучайных последовательностей более высокие требования по сравнению с другими приложениями . Криптографическая случайность не ограничивае т-ся статистической случайностью, хотя и включает ее . Чтобы последовательность была криптографически безопасной псевдослучайной последовательностью, она должна обладать следующим свойством :

2. Она непредсказуема. Должно быть очень трудно (с точки зрения применения вычислительных мо щ-ностей) предсказать, каким будет следующий случайный бит, даже если полностью известен алгоритм или устройство, генерирующее последовательность, и все предыдущие биты потока.

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

Как и любой криптографический алгоритм, генераторы криптографически безопасных псевдослучайных п о-следовательностей представляют собой предмет вскрытия . Так же как криптографический алгоритм, может быть взломан и генератор криптографически безопасных псевдослучайных последовательностей . Создание устойчивых к вскрытию генераторов является основой криптографии .

Настоящие случайные последовательности

Теперь мы вторгаемся в область, принадлежащую философам . Существует ли такая вещь как случайность? Что такое случайная последовательность? Как узнать, что последовательность случайна? Является ли "101110100" более случайной чем "l01010101"? Квантовая механика убеждает нас в том, что в реальном мире существует настоящая случайность. Но как сохранить эту случайность в предопределенном мире компьютерных микросхем и конечных автоматов?

В сторону философию, с нашей точки зрения генератор последовательности действительно случаен, если он обладает третьим свойством:

3. Создаваемая им последовательность не может быть уверенно воспроизведена. Если вы запускаете г е-

нератор случайных чисел дважды с одним и тем же входом (по крайней мере, насколько это в челов е-ческих силах), то вы получите две совершенно независимые случайные последовательности.

Выход генератора, удовлетворяющего всем трем приведенным требованиям, будет достаточно хорош для одноразового блокнота, генерации ключа и других криптографических применений, требующих генерации де й-ствительно случайных последовательностей . Трудность в том, чтобы понять, действительно ли последовател ь-ность случайна? Если я повторно зашифрую строку, используя DES и заданный ключ, я получу хороший, выглядящий случайным образом результат, вы не сможете сказать, что он не случаен, пока вы не наймете взло м-щика DES из NSA.

Глава 3

Основные протоколы 3.1 Обмен ключами

Общепринятой криптографической техникой является шифрование каждого индивидуального обмена соо б-щениями отдельным ключом. Такой ключ называется сеансовым, так как он используется для единственного отдельного сеанса обмена информацией. В разделе 8.5 говорится о том, что сеансовые ключи полезны, так как время их существования определяется длительностью сеанса связи . Передача этого общего сеансового ключа в руки обменивающихся информацией представляет собой сложную проблему .

Обмен ключами с помощью симметричной криптографии

Этот протокол предполагает, что пользователи сети, Алиса и Боб, получают секретный ключ от Центра ра с-пределения ключей (Key Distribution Center, KDC) [1260] - Трента наших протоколов. Перед началом протокола эти ключи уже должны быть у пользователей . (Протокол игнорирует очень насущную проблему доставки этих секретных ключей, предполагается, что ключи уже у пользователей, и Мэллори не имеет о них никакой инфо р-мации.)

(1) Алиса обращается к Тренту и запрашивает сеансовый ключ для связи с Бобом.

(2) Трент генерирует случайный сеансовый ключ. Он зашифровывает две копии ключа: одну для Алисы, а другую - для Боба. Затем Трент посылает обе копии Алисе.

(3) Алиса расшифровывает свою копию сеансового ключа.

(4) Алиса посылает Бобу его копию сеансового ключа.

(5) Боб расшифровывает свою копию сеансового ключа.

(6) Алиса и Боб используют этот сеансовый ключ для безопасного обмена информацией.

Этот протокол основан на абсолютной надежности Трента, для роли которого больше подходит заслуж и-вающая доверия компьютерная программа, чем заслуживающий доверия человек. Если Мэллори получит до ступ к Тренту, скомпрометированной окажется вся сеть. В его руках окажутся все секретные ключи, выделенные пользователям Трентом, он сможет прочесть все переданные сообщения, которые ему удалось перехватить, и все будущие сообщения. Ему останется только подключиться к линиям связи и подслушивать зашифрованный поток сообщений.

Другой проблемой такой системы является то, что Трент потенциально является ее узким местом. Он должен участвовать в каждом обмене ключами. Если с ним что-то случится, это разрушит всю систему.

Обмен ключами, используя криптографию с открытыми ключами

Базовая смешанная криптосистема обсуждалась в разделе 1.5. Для согласования сеансового ключа Алиса и Боб применяют криптографию с открытыми ключами, а затем используют этот сеансовый ключ для шифров а-ния данных. В некоторых реализациях подписанные ключи Алисы и Боба доступны в некоторой базе данных . Это значительно облегчает протокол, теперь Алиса, даже если Боб о ней никогда не слышал, может безопасно послать Бобу сообщение:

(1) Алиса получает открытый ключ Боба из KDC.

(2) Алиса генерирует случайный сеансовый ключ, зашифровывает его открытым ключом Боба и посылает его Бобу.

(3) Боб расшифровывает сообщение Алисы с помощью своего закрытого ключа.

(4) Алиса и Боб шифруют свой обмен информацией этим сеансовым ключом.

Вскрытие "человек-в-середине"

В то время, как Ева не может сделать ничего лучшего, чем пытаться взломать алгоритм с открытыми кл ю-чами или выполнить вскрытие с использованием только шифротекста , у Мэллори гораздо больше возможностей. Он не только может подслушать сообщения Алисы и Боба, но и изменить сообщения, удалить сообщения и создать совершенно новые . Мэллори может выдать себя за Боба, сообщающего что-то Алисе, или за Алису, сообщающую что-то Бобу. Вот как будет выполнено вскрытие:

(1) Алиса посылает Бобу свой открытый ключ. Мэллори перехватывает его и посылает Бобу свой собстве н-ный открытый ключ.