Испытания шифров
Начинают взлом шифров обыкновенно со статистических испытаний текста шифровки, что дает общие данные об их стойкости на начальном этапе анализа. Так как цель криптографии состоит в том, чтобы преобразовать открытый текст в шифровку, смысл которой недоступен незаконному получателю информации, то можно в идеале представить шифровальную систему, как "черный ящик", вход и выход которого взаимонезависимы, так как для установления ключа, согласующего входной текст с шифром, потребуется перебор всех допустимых вариантов. Если пространство поиска ключа очень велико и невозможно с помощью имеющихся вычислительных средств проверить каждый ключ за ограниченное разумное время, то шифр является вычислительно безопасным. Надлежит сделать следующие важные замечания.
1. Текст и шифр лишь кажутся независимыми, по-
тому что имеются детерминированные алгорит-
мы, отображающие их друг в друге - шифрова-
ния и расшифрования. Однако, предположив
независимость текста и его шифровки, пытаются
ее опровергнуть, беря пары выборок {текст,
шифр} и вычисляя их статистику. Так можно
заменить криптографическую стойкость шифра
на статистическую безопасность и считать, что
шифр статистически безопасен, если пары вы-
борок {текст, шифр} статистически независимы.
Одно из испытаний заключается в установлении
статистической связи изменения шифровки при
изменении символов и бит в исходном тексте
или ключе. Это испытание дает меру "эффекта
размножения" ошибок в шифре, который счита-
ется хорошим лишь в том случае, если малей- шие изменения исходного текста или ключа вле-
кут большие изменения шифровки. Смысл такого
рода тестов состоит в том, что безопасная система
обязательно безопасна и статистически.
2. Статистические испытания являются единствен-
ной стратегией испытаний больших криптогра-
фических систем с секретным ключом, постро-
енных в виде чередующихся слоев блоков заме-
ны и перестановок, как блоки вносящие нели-
нейность в системах Lucifer и DES. Это объяс-
няется трудностью составления уравнений, свя-
зывающих вход и выход системы, которые мож-
но было бы решать другими методами. В крип-
тографических системах, не имеющих таких бло-
ков, например, в системах RSA и ЭльГамаля,
уравнения, связывающие вход и выход, являют-
ся частью самой криптографической системы,
поэтому легче сосредоточить внимание на ана-
лизе этих уравнений.
3. Статистические проверки являются, пожалуй,
единственным общим и быстрым методом выяв-
ления плохих шифров. Вместо того, чтобы тра-
тить много времени на их аналитическую про-
верку, чтобы в конце концов убедиться в том,
что они не стойкие криптографически, с помо-
щью статистики можно быстро определить, за-
служивает ли эта система дальнейшей проверки.
Так, алгоритм FEAL-4 был сначала вскрыт
обычным методом криптоанализа, и независимо
от этого было показано, что он является стати-
стически слабым.
Важное значение для статистических испытаний имеет случайность текста шифровки конечной длины. Практическую меру случайности такой последовательности ввели Лемпел и Зив, авторы общеупотребимого алгоритма сжатия данных, применяемого во всех архиваторах IBM PC. Она указывает, на сколько можно сжать последовательность при использовании алгоритма Лемпела-Зива. Практически, если текст шифровки сжимается одним из архиваторов больше, чем на 10%, то шифровальная система очевидно не состоятельна. Если сжатие шифра оказалось меньше этой величины, то... все может быть. Отметим, что алгоритмам архивирования удается сжимать даже случайные последовательности символов, хотя сжатие в этом случае не превышает единиц процентов. Столь пространное описание статистического подхода к криптоанализу дано потому, что в этой главе ему будет уделено мало внимания, а вскрытие шифров будет показано лишь с точки зрения аналитического подхода. Итак, рассмотрим наиболее употребительные виды атак на некоторые известные уже шифры.