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