Проблема стойкости криптосистемы

Вскрытие (взламывание) шифра — процесс получения защищаемой информации из шифрованного сообщения без знания примененного ши­фра. Попытку вскрытия шифра называют атакой на шифр.

Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра. Понятие стойкости шифра является центральным для криптогра­фии.

Важнейшим для развития криптографии был результат К. Шен­нона о существовании и единственности абсолютно стойкого шифра. Единственным таким шифром является какая-нибудь форма так на­зываемой ленты однократного использования, в которой открытый текст «объединяется» с полностью случайным ключом такой же дли­ны. Но абсолютно стойкий шифр оказался очень дорогим и непрактичным.

Понятно, что чаще всего для защиты своей информа­ции законные пользователи вынуждены применять неабсолютно стой­кие шифры. Такие шифры, по крайней мере теоретически, могут быть вскрыты. Вопрос толь­ко в том, хватит ли у противника сил, средств и времени для разработки и реализации соответствующих ал­горитмов. Обычно эту мысль выражают так: противник с неогра­ниченными ресурсами может вскрыть любой не­абсолютно стойкий шифр. На протяжении многих веков среди специалис­тов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра. Отец кибернетики Норберт Винер говорил: «Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит затраченных средств, усилий и времени...»

Как же должен действовать в этой ситуации законный пользова­тель, выбирая для себя шифр? Лучше всего, конечно, было бы дока­зать, что никакой противник не может вскрыть выбранный шифр, ска­жем, за 10 лет и тем самым получить теоретическую оценку стойкости. К сожалению, математическая теория еще не дает нужных теорем — они относятся к нерешенной проблеме нижних оценок вычислительной сложности задач.

Поэтому у пользователя остается единственный путь— получение практических оценок стойкости. Этот путь состоит из следующих эта­пов:

– понять и четко сформулировать, от какого противника мы соби­раемся защищать информацию; необходимо уяснить, что именно про­тивник знает или сможет узнать о системе шифра, а также какие силы и средства он сможет применить для его вскрытия;

– мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т.е. разрабатывать различные алгоритмы вскрытия шифра; при этом необходимо в максимальной мере обеспечить модели­рование сил, средств и возможностей противника;

– наилучший из разработанных алгоритмов использовать для прак­тической оценки стойкости шифра.

Здесь полезно для иллюстрации упомянуть о двух простейших мето­дах вскрытия шифра: случайное угадывание ключа (он срабатывает с маленькой вероятностью, зато имеет маленькую сложность) и перебор всех подряд ключей вплоть до нахождения истинного (он срабатывает всегда, зато имеет очень большую сложность). Отметим также, что не всегда нужна атака на ключ: для некоторых шифров можно сразу, даже не зная ключа, восстанавливать открытый текст по шифрованному.

Итак, стойкость конкретного шифра оценивается только путем все­возможных попыток его вскрытия и зависит от квалификации криптоана­литиков, атаку­ющих шифр. Такую процедуру иногда называют проверкой стойкости. Имеется несколько показателей криптостойкости, среди кото­рых: количество всех возможных ключей; среднее время, необходимое для кpиптоанализа.

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

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

В связи с вышесказанным рассмотрим основные понятия и задачи криптоанализа.