2.2. Криптографическая стойкость шифров

Попытки противника по добыванию зашифрованной информации называют криптоатаками. В симметричных криптосистемах обычно рассматривают следующие криптоатаки:

Атака на основе шифртекста: криптоаналитик располагает шифртекстами отвечающими неизвестным открытым текстам различных сообщений. Требуется определить хотя бы одно из сообщений (или соответствующий ключ k_i), исходя из необходимого числа m криптограмм, или убедиться в своей неспособности сделать это. В качестве частных случаев возможно совпадение ключей k₁ = … = k_m или совпадение открытых текстов x₁ = … = x_m.

Атака на основе известного открытого текста: криптоаналитик располагает парами открытых и отвечающих им шифрованных текстов. Требуется определить ключ k_i для хотя бы одной из пар. В частном случае, когда k₁ = … = k_m, требуется определить ключ k или, убедившись в своей неспособности сделать это, определить открытый текст x_m+1 еще оджной криптограммы y_m+1 = E_k(x_m+1), зашифрованный на том же ключе.

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

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

Атаки на основе выбранных текстов считаются наиболее опасными. Иногда к указанным атакам добавляют и другие.

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

В криптографии различают два подхода к стойкости – теоретическую стойкость и практическую (или вычислительную) стойкость.

2.2.1. Теоретико-информационный подход к оценке криптостойкости шифров

Энтропия и избыточность языка

Свойства текстов изучаются методами теории информации, разработанной К. Шенноном. Ключевое понятие – энтропия, определяемая функцией от вероятностного определения и характеризующая количество неопределенности или информации в случайном эксперименте. Неопределенность и информация измеряются одной и той же мерой. Применительно к независимым испытаниям случайной величины  с распределением вероятностей

энтропия H() определяется формулой

Единицей количества информации считается 1 бит. При p_i = 1/n при всех , то

.

Мерой среднего количества информации, приходящейся на одну букву открытого текста языка  (рассматриваемого как источник случайных текстов), служит величина H_, называемая энтропией языка . вычисляется последовательными приближениями позначных моделей текста: H₁, H₂, … H_r.

Для каждого языка значение H_ стремится к определенному пределу (после r = 30 предел уже устанавливается):

.

при этом формула

определяет избыточность языка R_. Разговорные языки имеют весьма большую избыточность. Избыточность текста в 75% означает, что при оптимальном кодировании текста (например использование кодов Хаффмена, Фано или других) его можно сжать до четверти без потери информации.

Энтропию можно определить и по другому. Для n-буквенного алфавита число текстов длины L, удовлетворяющих статистическим ограничениям, равно (при достаточно больших L) не как это было бы, если бы мы имели право брать любые наборы из L букв, а всего лишь

По сути это приближенное число осмысленных текстов длины L для данного языка . Исходя из этого можно определить энтропию языка формулой

Расстояние единственности.

При дешифровании криптограмм может возникнуть ситуация, в которой несколько найденных ключей дают осмысленный текст. Так, криптограмму WNAJW, полученную при помощи шифра Цезаря, порождают два открытых текста RIVER и ARENA, отвечающих величинам сдвига (ключам) 5 и 11 соответственно. Из этих ключей один является истинным, а другой ложным. Найдем оценку для числа ложных ключей. Для этого рассмотрим связь между энтропиями вероятностных распределений P(X), P(K), P(Y), заданных на компонентах X, K, Y произвольного шифра _в см. лекция 2.

Назовем условную энтропию H(K / Y) неопределенностью шифра _в по ключу. Она измеряет среднее количество информации о ключе, которое дает шифртекст. Аналогично вводится неопределенность шифра по открытому тексту H(X / Y). Эти величины являются мерой теоретической стойкости шифра.

Минимально возможным значением неопределенности H(X/Y) является 0.

,

это возможно только в тех случаях, когда или для всех x, y, то есть если при некоторых x, y. Это означает, что по данному y можно получить существенную информацию об x, что свидетельствует о слабости шифра. Идеальной является ситуация когда H(X / Y) = H(X). Именно в этом случае шифр можно было бы назвать совершенным.

Связь между энтропиями компонент шифра дает формула неопределенности шифра по ключу:

полученная К. Шенноном. Эта формула позволяет получить оценку среднего числа ложных ключей.

Введем обозначение K(y) = {k  K : x  X, E_k(x) = y} – множество ключей, для каждого из которых y является результатом зашифрования некоторого осмысленного текста длины L. Если мы располагаем криптограммой y, то число ложных ключей равно |K(y)| - 1, так как лишь один из допустимых ключей является истинным. Определим среднее число ложных ключей к_L (относительно всех возможных шифртекстов длины L) формулой

.

Теорема. Для любого рассматриваемого шифра _в с равновероятными ключами при достаточно больших значениях L в алфавите из n букв имеет место неравенство

.

где R_ - избыточность данного языка.

Назовем расстоянием единственности для шифра _в натуральное число L₀, для которого ожидаемое число ложных ключей к_L равно нулю. По сути, расстояние единственности есть средняя длина шифртекста, необходимая для однозначного восстановления истинного ключа (без каких-либо временных ограничений на время его нахождения).

Непосредственно из предыдущего неравенства следует, что

откуда при к_L = 0 получаем и, следовательно,

Минимально возможное значение в этом неравенстве и принимается за L₀. Таким образом.

Например для шифра простой замены с параметрами n = 26, |K| = 26!, R_ = 0,5 (примерно соответствует английскому языку) получим оценку

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

Для совершенных шифров типа одноразовых блокнотов расстояние единственности L₀.

Теоретическая стойкость шифров

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

Априорная вероятность открытого текста – безусловная вероятность.

Апостериорная вероятность открытого текста – вероятность (по шифртексту) при условии использования соответствующего шифра.

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

Определение. Назовем шифр _в совершенным, если для любых x  X, y  Y выполняется равенство

p(x / y) = p_X(x).

Утверждение. Если шифр _в – совершенный, то

|X| ≤ |Y| ≤ |K|.

Теорема (К. Шеннон). Пусть _в – шифр, для которого |X| = |Y| = |K|. Тогда шифр _в – совершенный тогда и только тогда, когда выполняются два условия:

1. Для любых x  X, y  Y существует единственный ключ k  K, для которого

E_k(x) = y;

2. Распределение вероятностей P(K) – равномерное, то есть для любого ключа

По сути, теорема описывает шифры табличного гаммирования со случайными равновероятными ключами.