Испытания шифров

adm  •  15 April, 2008

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

Текст и шифр лишь кажутся независимыми, потому что имеются детерминированные алгоритмы, отображающие их друг в друге - шифрования и расшифрования. Однако, предположив независимость текста и его шифровки, пытаются ее опровергнуть, беря пары выборок {текст, шифр} и вычисляя их статистику. Так можно заменить криптографическую стойкость шифра на статистическую безопасность и считать, что шифр статистически безопасен, если пары выборок {текст, шифр} статистически независимы. Одно из испытаний заключается в установлении статистической связи изменения шифровки при изменении символов и бит в исходном тексте или ключе. Это испытание дает меру "эффекта размножения" ошибок в шифре, который считается хорошим лишь в том случае, если малейшие изменения исходного текста или ключа влекут большие изменения шифровки. Смысл такого рода тестов состоит в том, что безопасная система обязательно безопасна и статистически.

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

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

Комментарии

Нет комментариев. Вы можете быть первым!

Оставить комментарий