Стойкость шифра должна определяться только секретностью ключа. Если для генерации ключей используется нестойкий алгоритм, криптосистема будет нестойкой. Вскрытию подвергнется не сам шифр, а алгоритм генерации ключей.
Сокращенные ключевые пространства
Длина ключа в DES-алгоритме составляет 56 бит. В принципе, в качестве ключа может быть использован любой 56-битный вектор. На практике это правило часто не соблюдается. Например, широко распространенная программа шифрования файлов Norton Discreet, входящая в пакет Norton Utilities (версии 8.0 или более младшей версии), который предназначен для работы в операционной системе DOS, предлагает пользователю программную реализацию DES-алгоритма. Однако при вводе ключа разрешается подавать на вход программы только те символы, старший бит представления которых в коде ASCII равен нулю. Более того, пятый бит в каждом байте введенного ключа является отрицанием шестого бита, и в нем игнорируется младший бит. Это означает, что мощность ключевого пространства сокращается до каких-то жалких 2 40 ключей. Таким образом из-за плохой процедуры генерации ключей программа Norton Discreet реализует алгоритм шифрования, ослабленный в десятки тысяч раз по сравнению с настоящим DES-алгоритмом.
В табл. 6.6 приведено количество возможных ключей в зависимости от раз-личных ограничений на символы, которые могут входить в ключевую последовательность. Табл. 6.7 содержит сложность атаки методом тотального перебора при условии, что перебор ведется со скоростью 1 млн ключей в секунду.
Таблица 6.6. Количество возможных ключей в зависимости от ограничений на символы ключевой последовательности
| Символы ключа | 4 байта | 5 байт | 6 байт | 7 байт | 8 байт |
| Строчные буквы (26) | 4,7*10 5 | 1,3*10 7 | 3,2*10 8 | 8,1*10 9 | 2,2*10 11 |
| Строчные буквы и цифры (36) | 1,8*10 6 | 6,1*10 7 | 2.3*10 9 | 7,9*10 10 | 2.9*10 12 |
| Буквы и цифры (62) | 1,6*10 7 | 9,3*10 8 | 5,8*10 10 | 3,6*10 11 | 2,3*10 14 |
| Печатаемые символы (95) | 8,2*10 7 | 7,8*10 9 | 7,5*10 11 | 7,1*10 13 | 6,7*10 15 |
| Все ASCII-символы | 4,4*10 9 | 1,2*10 10 | 2,9*10 14 | 7,3*10 16 | 1,9*10 19 |
Таблица 6.7. Сложность атаки методом тотального перебора при условии, что перебор ведется со скоростью 1 миллион ключей в секунду
| Символы ключа | 4 байта | 5 байт | 6 байт | 7 байт | 8 байт |
| Строчные буквы (26) | 0,6 сек. | 13 сек. | 6 мин. | 2,3ч. | 2,5 дн. |
| Строчные буквы и цифры (36) | 1,8 сек. | 2 мин. | 37 мин. | 23ч. | 34 дн. |
| Буквы и цифры (62) | 16 сек. | 16 мин. | 17ч. | 42 дн. | 7,0 лет |
| Печатаемые символы (95) | 1,5 мин. | 2,2ч. | 8,6 дн. | 2,3 лет | 211 лет |
| Все ASCII-символы | 1,3ч. | 14 дн. | 9,0 лет | 2400 лет | 590000 лет |
Из табл. 6.6 следует, что возможность опробовать 1 млн ключей в секунду позволяет в разумные сроки вскрывать 8-байтовые ключи из строчных букв и цифр, 7-байтовые буквенно-цифровые ключи, 6-байтовые ключи, составленные из печатаемых ASCII-символов, и 5-байтовые ключи, в которые могут входить любые ASCII-символы. А если учесть, что вычислительная мощь компьютеров увеличивается вдвое каждые полтора года, то для успешного отражения атаки методом тотального перебора в течение ближайшего десятилетия необходимо заблаговременно позаботиться о том. чтобы используемый ключ был достаточно длинным.
Плохие ключи
Когда отправитель сам выбирает ключ, с помощью которого он шифрует свои сообщения, его выбор обычно оставляет желать лучшего. Например, Петр Сергеевич Иванов скорее предпочтет использовать в качестве ключа Ivanov, чем &7)g\*. И вовсе не потому, что он принципиально не желает соблюдать элементарные правила безопасности. Просто свою фамилию Иванов помнит гораздо лучше, чем абракадабру из шести произвольно взятых символов. Однако тогда сохранить свою переписку в тайне ему не поможет и самый стон кий алгоритм шифрования в мире, особенно если используемые Ивановым ключи всегда совпадают с именами его ближайших родственников и записывает он эти ключи на клочках бумаги, которые наклеивает на компьютер. В ходе хорошо организованной атаки методом тотального перебора квалифицированный криптоанатитик не будет опробовать все ключи последовательно, один за другим. Он сначала проверит те из них, которые хоть что-то значат для Иванова. Такая разновидность атаки методом тотального перебора наливается товарной атакой, поскольку в ходе нее противник использует словарь наиболее вероятных ключей. В этот словарь обычно входят:
Случайные ключи
Хороший ключ представляет собой случайный битовый вектор. К примеру. если его длина составляет 56 бит, то это значит, что в процессе его генерации с одинаковой вероятностью может получиться любой из 2 56 возможных ключей. Источником случайных ключей обычно служит либо природный случайный генератор (хорошей аналогией такого генератора является маленький ребенок, который только что научился ходить, — временные интервалы между его падениями абсолютно случайны). Кроме того, источником случайного ключа может быть криптографически надежный генератор псевдослучайных битовых последовательностей. Лучше, чтобы процесс генерации ключей был автоматизирован. Если под рукой нет компьютера для запуска программы, реализующей псевдослучайный генератор, или ваш ребенок давно уже вышел из младенческого возраста, можно бросать монетку или игральную кость.
Использование хорошего генератора случайных чисел является очень важным моментом при генерации криптографических ключей, однако не следует слишком много спорить о том, какой из этих генераторов является более случайным. Важнее применять стойкие алгоритмы шифрования и надежные процедуры работы с ключами. Если у вас появились сомнения относительно случайности при выборе ключа, можно использовать один из методов генерации ключей, описанных ниже в этой главе.
Во всех алгоритмах шифрования имеются так называемые нестойкие ключи. Это означает, что некоторые из ключей к шифру являются менее надежными, чем остальные. Поэтому при генерации ключей нужно автоматически проверять их на стойкость и генерировать новые вместо тех, которые эту проверку не прошли. К примеру, в DES-алгоритме имеются всего 24 нестойких ключа из общего количества 2 56 , и следовательно вероятность наткнуться на нестойкий ключ пренебрежимо мала. Кроме того, откуда криптоаналитику знать, что для зашифрования конкретного сообщения или файла был применен именно нестойкий ключ? А сознательный отказ от использования нестойких ключей дает противнику дополнительную информацию о вашей криптосистеме, что нежелательно. С другой стороны, проверка ключей на нестойкость достаточно проста, чтобы ею пренебрегать.
Генерация открытых ключей гораздо более затруднена, чем генерация секретных ключей, поскольку открытые ключи должны обладать определенными математическими свойствами (например, должны быть результатом произведения двух простых чисел).
Пользоваться случайными ключами не всегда удобно. Иногда ключ требуется сохранить в памяти, а запомнить 36f9 67аЗ f9cb d931 человеку не так-то просто. В этом случае для генерации можно использовать некое правило, которое будет очевидно для вас, но недоступно для постороннего. Два варианта такого правила:
Пароль
Более привлекателен подход, при котором вместо отдельного слова используется достаточно длинное легко запоминающееся предложение на русском, английском или другом языке, которое преобразуется в ключ. Такое выражение в криптографии называется паролем. Для преобразования пароля в псевдослучайный битовый ключ можно воспользоваться любой однонаправленной хэш-функцией.
Пароль следует выбирать достаточно длинным, чтобы полученный в результате его преобразования ключ был случайным. Из теории информации известно, что в предложении на английском языке каждая буква содержит примерно 1,3 бита информации. Тогда, чтобы получить 64-бтный ключ, пароль должен состоять примерно из 49 букв, что соответствует английской фразе из 10 слов.
Необходимо, чтобы при желании пароль было легко вспомнить, и в то же время требуется, чтобы он был достаточно уникален. Цитата из Козьмы Пруткова, которая у всех на слуху, вряд ли подойдет, поскольку его сочинения имеются в форме, доступной для воспроизведения на компьютере, и следовательно, могут быть использованы в словарной атаке. Лучше воспользоваться творчеством малоизвестного поэта или драматурга, процитировав его с ошибками. Большего эффекта можно добиться, если в цитате, использованной для генерации ключа, будут присутствовать иностранные слова. Идеально подходят для этой цели незатейливые ругательства — их вам не придется записывать, чтобы запомнить. Достаточно шарахнуть себя по пальцу молотком, и пароль автоматически придет вам в голову. Надо только сдержаться и не произнести его вслух, чтобы не подслушали посторонние.
Несмотря на все сказанное, залогом наилучшей зашиты служит не шаманство при выборе пароля, а случайность полученного ключа. Хороший ключ — это случайный ключ, а значит, заранее будьте готовы к тому, что запомнить его наизусть будет очень трудно.
Стандарт ANSI X9.17
Американский национальный институт стандартов (ANSI) разработал метол генерации 64-битных ключей при помощи DES-алгоритма. Его основное назначение состоит в получении большого количества ключей для многократных сеансов связи. Вместо DES-алгоритма можно использовать любой другой стойкий алгоритм шифрования.
Пусть функция Е K (Р) осуществляет шифрование Р по DES-алгоритму на заранее заготовленном ключе К, который используется только для генерации секретных ключей. Пусть далее V 0 является начальным 64-битным значением, которое держится в тайне от противника, а Т i представляет собой отметку времени, когда был сгенерирован i-й ключ. Тогда очередной случайный ключ R i вычисляется с помощью преобразования:
R i = Е К (Е К (Т i ) Å V i )
Чтобы получить очередное значение V i , надо вычислить
V i = Е К (Е К (Т i ) Å R i )