Кpиптогpафия от папиpуса до компьютеpа

       

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


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

    


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

    

3. Статистические проверки являются, пожалуй,
     единственным общим и быстрым методом выяв-
     ления плохих шифров. Вместо того, чтобы тра-
     тить много времени на их аналитическую про-
     верку, чтобы в конце концов убедиться в том,
     что они не стойкие криптографически, с помо-
     щью статистики можно быстро определить, за-
     служивает ли эта система дальнейшей проверки.
     Так, алгоритм FEAL-4 был сначала вскрыт
     обычным методом криптоанализа, и независимо
     от этого было показано, что он является стати-
     стически слабым.

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


Содержание раздела