Вспомните, что вскрытие грубой силой обычно является вскрытием с использованием известного открытого текста, для этого нужно немного шифротекста и соответствующего открытого текста . Если вы предполагаете, что наиболее эффективным способа взлома алгоритма является вскрытие грубой силой - большое допущение -то ключ должен быть достаточно длинным, чтобы сделать вскрытие невозможным . Насколько длинным?
Скорость вскрытия грубой силой определяется двумя параметрами : количеством проверяемых ключей и скоростью проверки одного ключа. Большинство симметричных алгоритмов в качестве ключа могут использ о-вать в качестве ключа любую битовую последовательность фиксированной длины. Длина ключа DES составляет 56 бит, всего может быть 256 возможных ключей. Длина ключей для ряда алгоритмов, обсуждаемых в этой книге, равны 64 битам, всего может быть 2м возможных ключей. Другие алгоритмы используют 128-битовые ключи.
Скорость, с которой может быть проверен каждый ключ, имеет менее важное значение . Для проводимого анализа я предполагаю, что скорость проверки ключа для каждого алгоритма примерно одинакова. В действ и-тельности скорость проверки одного алгоритма может быть в два, три или даже десять раз выше чем другого . Но так как для тех длин ключей, для которых мы проводим поиск, время поиска в миллионы раз больше, чем время проверки одного ключа, небольшие отличия в скорости проверки не имеют значения.
В криптологической среде большинство споров по поводу вскрытия грубой силой сконцентрированы вокруг алгоритма DES. В 1977 году Уитфилд Диффи и Мартин Хеллман [497] сформулировали условия существования специализированной машины по взлому DES. Эта машина состоит из миллионов микросхем, каждая из кот о-рых проверяет миллион ключей в секунду. Такая машина за два часа сможет проверить 256 за 20 часов. При вскрытии алгоритма с 64-битовым ключом проверка всех 2м потребует 214 дней.
Задача вскрытия грубой силой как будто специально придумана для параллельных процессоров . Каждый процессор проверяет подмножество пространства ключей. Процессорам не нужно обмениваться между собой информацией, единственным используемым сообщением будет сообщение, сигнализирующее об успехе . Не требуется и доступ к одному участку памяти. Сконструировать машину с миллионом процессоров, каждый из кот о-рых работает независимо от других, нетрудно.
Сконструировать машину для взлома грубой силой Майкл Винер решил [1597, 1598]. (Он сконструировал машину для DES, но анализ может быть выполнен почти для всех алгоритмов.) Он разработал специализированные микросхемы, платы и стойки, оценил затраты и сделал вывод, что за миллион долларов можно постр о-ить машину, которая сможет взломать 56-битный ключ DES key в среднем за 3.5 часа (и наверняка за 7 часов). Соотношение стоимость/скорость является линейным. Для ряда длин ключей эти значения обобщены в 6-й. Вспомните о законе Мура: мощь вычислительных средств приблизительно каждые 18 месяцев . Это означает, что затраты будут уменьшаться на порядок каждые пять лет, и то, что в 1995 году стоит миллион долларов, в 2000 году будет стоить около 100000 долларов. Еще более упростить процесс вычислений могла бы конвейер и-зация [724].
Для 56-битовых ключей эти суммы оказываются вполне по карману большинству крупных корпораций и многим криминальным организациям. Военные бюджеты большинства промышленно развитых стран могут позволить взламывать и 64-битные ключи. Вскрытие 80-битного ключа все еще за пределами возможного, но если текущая тенденция сохранится, то через каких-нибудь тридцать лет все может измениться .
Конечно, нелепо прогнозировать компьютерную мощь на 35 лет вперед. Технологические прорывы, популярные в научной фантастике, могут сделать эти прогнозы смешными . С другой стороны, неизвестные в настоящее время физические ограничения могут сделать эти прогнозы нереально оптимистичными . В криптографии умнее быть пессимистом. Применение в алгоритме 80-битного ключа кажется недостаточно дальновидным . Используйте ключ, длина которого, по меньшей мере, 112 бит.