Существуют модернизации этого способа вскрытия, предполагающие, что Мэллори пошлет Бобу сообщение, отличное от того, которое он желает перехватить . Никогда не подписывайте произвольных сообщений от других людей и не передавайте результаты дешифровки произвольных сообщений иным людям .

Обнаружение вскрытия, основанного на возвращении сообщения

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

(1)Алиса подписывает сообщение.

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

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

(4)Боб проверяет подпись Алисы.

Вскрытия криптографии с открытыми ключами

Во всех подобных протоколах криптографии с открытыми ключами я не рассказал , как Алиса получает открытый ключ Боба. Подробно этот вопрос описан в разделе 3.1, но о нем стоит упомянуть и здесь.

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

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

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

2.8. Генерация случайных и псевдослучайных последовательностей

Почему даже в книге по криптографии снова эти докучливые рассуждения о генерации случайных чисел? Генератор случайных чисел встроен в каждый компилятор, обычный вызов функции. Почему бы не использ о-вать его? К сожалению, эти генераторы случайных чисел почти наверняка недостаточно безопасны для крипт о-графии и, возможно, даже не совсем случайны . Большинство из них весьма плохи .

Генераторы случайных чисел на самом деле совсем не случайны, потому что им и не нужно быть такими . Для большинства приложений, например, компьютерных игр, требуется так мало случайных чисел, что их н е-случайность вряд ли будет заметна. Однако, криптография очень чувствительна к свойствам генераторов сл у-чайных чисел. Примените плохой генератор, и у вас появятся таинственные корреляции и странные результаты [1231, 1238]. Если ваша безопасность зависит от генератора случайных чисел, таинственные корреляции и странные результаты являются абсолютно не тем, чего бы вы желали добиться.

Проблема в том, что генератор случайных чисел не создает случайной последовательности . Он, возможно, не выдает ничего даже отдаленно напоминающего случайную последовательность . Конечно, невозможно создавать на компьютере что-то по настоящему случайное. Дональд Кнут приписывал фон Нейману следующие слова: "Каждый, кто занимается арифметическими методами получения случайных чисел, определенно грешит " [863]. Компьютеры - это детерминированные бестии: закладывается известный материал, выполняются полностью предсказуемые действия, и что-то отличное выползает с другого конца. Подача одного и того же на вход в двух различных случаях приведет к одному и тому же результату . Заложите одинаковые исходные данные в два

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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