Атака на шифр. Стойкость шифра

Материал из Saratov FIO Wiki
Перейти к: навигация, поиск

Атака на шифр. Стойкость шифра.

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

• противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов;

• противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты;

• противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровать и дешифровать любую информацию.

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

В криптографии принято работать с универсальным алфавитом, состоящим из двоичных слов некоторой длины. Двоичное слово длины n - это набор из n нулей и единиц. Соответствующий алфавит состоит из 2n символов. Выбор такого алфавита объясняется многими соображениями. При использовании компьютеров удобно представлять информацию в виде последовательностей нулей и единиц. Это, в частности, обусловливается тем, что в компьютере используются элементы, которые могут находиться в одном из двух состояний. Одно из них обозначается «0», а другое «1». С другой стороны, слова в любом алфавите можно легко перевести в двоичные слова. Пусть пробел между словами считается отдельной буквой (обозначение: __ ). Рассмотрим, например, телеграфный код - старое техническое применение двоичной системы счисления. Он состоит тоже из 32 символов - двоичных слов длины 5. Сопоставим каждой букве двоичное слово длины 5 следующим образом: __ → 00000, А→ 00001, Б → 00010, В→ 00011, Г → 00100, Д → 00101, …, Ю →11110, Я → 11111.

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

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

Таким образом, двоичные слова и двоичные последовательности - типовые объекты в криптографии. Теперь можно ответить на вопрос: Возможен ли абсолютно стойкий шифр? Клодом Шенноном было доказано существование такого шифра. Это, так называемая, лента однократного использования.

Основные требования к ленте однократного использования:

1) полная случайность ключа;

2) равенство длины ключа и длины открытого текста;

3) однократность использования ключа.


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

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

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

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

• мысленно встать в положение противника и пытаться с его позиций атаковать шифр;

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

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

Нет, для некоторых шифров можно сразу, даже не зная ключа, восстановить открытый текст по шифрованному.

Эту мысль удобнее проиллюстрировать на примере шифра замены, для которого уже разработаны методы вскрытия.

Шифр замены преобразует открытый текст в шифрованный по следующему правилу: каждая буква x заменяется на букву g(x). Вскрытие шифра основано на двух закономерностях:

1) в осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, а действие подстановки g «переносит» эту закономерность на шифрованный текст;

2) любой естественный язык обладает так называемой избыточностью, что позволяет с большой вероятностью угадывать смысл сообщения, даже если часть букв в сообщении неизвестна.

Для вскрытия шифра простой замены поступают следующим образом. Составляют таблицу частот встречаемости букв в шифртексте. Считают, что при замене частоты x и g(x) совпадают. Последовательно перебирая различные варианты, пытаются либо прийти к противоречию с законами русского языка, либо получить читаемые куски сообщения. Далее, по возможности, продлевают читаемые куски либо по смыслу, либо по законам русского языка.