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

Псевдослучайная битовая последовательность должна, по возможности, не отличаться от по-настоящему случайной. Необходимо, чтобы в ней число единиц примерно совпадало с числом нулей, а половина всех "полосок" (подряд идущих идентичных компонентов последовательности) имела длину I. одна четвертая — длину 2, одна восьмая — длину 4 и т. д. Кроме только что перечисленных, существует еще ряд общепринятых тестов, которые позволяют проверить, действительно ли данная последовательность является псевдослучайной.

Созданию хороших генераторов псевдослучайных последовательностей уделяется достаточно большое внимание в математике. В настоящее время удается порождать последовательности с периодом порядка 2000—3000 бит. Проблема в том, что все генераторы псевдослучайных последовательностей при определенных условиях дают предсказуемые результаты и корреляционные зависимости. А это как раз то, чего ждут от псевдослучайных последовательностей криптоаналитики, чтобы предпринять эффективную атаку на криптосистемы, где эти последовательности используются.

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

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

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

Последовательность называется no-настоящему случайной, если ее нельзя воспроизвести. Это означает, что если запустить генератор по-настоящему случайных последовательностей дважды при одном и том же входе, то на его выходе получатся разные случайные последовательности. Основная трудность состоит в том, чтобы суметь отличить случайную последовательность от неслучайной. Если несколько раз зашифровать строку символов с помощью криптографического алгоритма, соответствующего ГОСТ 28147-89, то получится последовательность, очень напоминающая по-настоящему случайную. Чтобы доказать ее неслучайность, другого способа, кроме аренды АНБ соответствующих вычислительных мощностей и программы вскрытия. не существует. Однако вряд ли ваше предложение об аренде будет воспринято там всерьез.

Плохие ключи

Когда отправитель сам выбирает ключ, с помощью которого он шифрует свои сообщения, его выбор обычно оставляет желать лучшего. Например, Петр Сергеевич Иванов скорее предпочтет использовать в качестве ключа Ivanov, чем &7)g*. И вовсе не потому, что он принципиально не желает соблюдать элементарные правила безопасности. Просто свою фамилию Иванов помнит гораздо лучше, чем абракадабру из шести произвольно взятых символов. Однако тогда сохранить свою переписку в тайне ему не поможет и самый стон кий алгоритм шифрования в мире, особенно если используемые Ивановым ключи всегда совпадают с именами его ближайших родственников и записывает он эти ключи на клочках бумаги, которые наклеивает на компьютер. В ходе хорошо организованной атаки методом тотального перебора квалифицированный криптоанатитик не будет опробовать все ключи последовательно, один за другим. Он сначала проверит те из них, которые хоть что-то значат для Иванова. Такая разновидность атаки методом тотального перебора наливается товарной атакой, поскольку в ходе нее противник использует словарь наиболее вероятных ключей. В этот словарь обычно входят:

Имя, фамилия, отчество, инициалы, год рождения и другая личная информация, имеющая отношение к данному человеку. Например, при словарной атаке против Петра Сергеевича Иванова в первую очередь следует проверить PSI, PSIPSI, PIVANOV, Pivanov, psivanov, peteri, pete I, IvanovP, peterivanov, Peter-Ivanov и т. д.
Словарная база данных, составленная из имен людей, героев мультфильмов и мифических животных, ругательств, чисел (как цифрами, так и прописью), названий художественных фильмов, научно-фантастических романов, астероидов, планет и цветов радуги, общепринятых сокращении и т. д. В общей сложности для одного конкретного человека такая база данных насчитывает более 60 тыс. словарных единиц.
Слова, которые получены путем внесения различных изменений в словарную базу данных, составленную на предыдущем этапе. Сюда относятся обратный порядок написания слова, замена в нем латинских буки о, l, z, s на цифры 0 , 1, 2 и 5 соответственно, использование слова во множественном числе и т. д. Это даст дополнительно еще около миллиона словарных единиц для опробования в качестве возможного ключа к шифру.
Слова, полученные с помощью замены строчных букв на заглавные. Такой замене в принципе может подвергаться любое число букв. Например. вместе со словом Ivanov будут проверяться слова iVanov, ivAnov, ivaNov, ivanOv, ivanoV, IVanov, IvAnov, IvaNov, IvanOv, IvanoV и т. д. Однако. вычислительная мощь современных компьютеров позволяет проверять только одно-, двух- и трехбуквенные замены строчных букв на заглавные.
Слова на различных иностранных языках. Хотя компьютерные пользователи в основном работают с англоязычными операционными системами (DOS, UNIX, Windows и другими), существуют локализованные версии распространенных операционных систем, в которых допускается использование другого языка. Это означает, в качестве ключа на вход программы шифрования может быть подана любая фраза на родном языке ее пользователя. Следует также учитывать, что ключ может быть транслитерирован с любого языка (например, с русского или китайского) на английский и затем в таком виде введен в программу шифрования.
Пары слов. Поскольку количество вероятных пар слов, из которых может состоять криптографический ключ, слишком велико, на практике криптоаналитики обычно ограничиваются словами из трех и четырех букв.
Случайные ключи

Хороший ключ представляет собой случайный битовый вектор. К примеру. если его длина составляет 56 бит, то это значит, что в процессе его генерации с одинаковой вероятностью может получиться любой из 2 56 (2 в степени 56) возможных ключей. Источником случайных ключей обычно служит либо природный случайный генератор (хорошей аналогией такого генератора является маленький ребенок, который только что научился ходить, — временные интервалы между его падениями абсолютно случайны). Кроме того, источником случайного ключа может быть криптографически надежный генератор псевдослучайных битовых последовательностей. Лучше, чтобы процесс генерации ключей был автоматизирован. Если под рукой нет компьютера для запуска программы, реализующей псевдослучайный генератор, или ваш ребенок давно уже вышел из младенческого возраста, можно бросать монетку или игральную кость.

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

Во всех алгоритмах шифрования имеются так называемые нестойкие ключи. Это означает, что некоторые из ключей к шифру являются менее надежными, чем остальные. Поэтому при генерации ключей нужно автоматически проверять их на стойкость и генерировать новые вместо тех, которые эту проверку не прошли. К примеру, в DES-алгоритме имеются всего 24 нестойких ключа из общего количества 2 56 , и следовательно вероятность наткнуться на нестойкий ключ пренебрежимо мала. Кроме того, откуда криптоаналитику знать, что для зашифровывания конкретного сообщения или файла был применен именно нестойкий ключ? А сознательный отказ от использования нестойких ключей дает противнику дополнительную информацию о вашей криптосистеме, что нежелательно. С другой стороны, проверка ключей на нестойкость достаточно проста, чтобы ею пренебрегать.

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

Пользоваться случайными ключами не всегда удобно. Иногда ключ требуется сохранить в памяти, а запомнить 36f9 67аЗ f9cb d931 человеку не так-то просто. В этом случае для генерации можно использовать некое правило, которое будет очевидно для вас, но недоступно для постороннего. Два варианта такого правила:

Составьте ключ из нескольких слов, разделенных знаками препинания. Например, очень просто и надолго запоминаются ключи типа Yankee'Go home.
Используйте в качестве ключа сочетание букв, которые представляют собой акроним более длинного слова. К примеру, броское название немецкого вина Liebenfraumilch позволяет путем отбрасывания гласных букв и добавления восклицательного знака сгенерировать ключ Lbnfrmlch!.
Пароль

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

Пароль следует выбирать достаточно длинным, чтобы полученный в результате его преобразования ключ был случайным. Из теории информации известно, что в предложении на английском языке каждая буква содержит примерно 1,3 бита информации. Тогда, чтобы получить 64-бтный ключ, пароль должен состоять примерно из 49 букв, что соответствует английской фразе из 10 слов.

Необходимо, чтобы при желании пароль было легко вспомнить, и в то же время требуется, чтобы он был достаточно уникален. Цитата из Козьмы Пруткова, которая у всех на слуху, вряд ли подойдет, поскольку его сочинения имеются в форме, доступной для воспроизведения на компьютере, и следовательно, могут быть использованы в словарной атаке. Лучше воспользоваться творчеством малоизвестного поэта или драматурга, процитировав его с ошибками. Большего эффекта можно добиться, если в цитате, использованной для генерации ключа, будут присутствовать иностранные слова. Идеально подходят для этой цели незатейливые ругательства — их вам не придется записывать, чтобы запомнить. Достаточно шарахнуть себя по пальцу молотком, и пароль автоматически придет вам в голову. Надо только сдержаться и не произнести его вслух, чтобы не подслушали посторонние.