Криптографическая защита информации

4.5.3. Восстановление текстов, зашифрованных неравновероятной гаммой

Пример (использования шифра модульного гаммирования)

Рассмотрим следующую постановку задачи. Пусть при использовании шифра модульного гаммирования в результате, например, некоторой неисправности гаммообразующего устройства, т.е. устройства, вырабатывающего гамму, в ней встречаются не все знаки. Предположим, далее, что гамма состоит лишь из знаков ₁,...,_m, т < п, которые встречаются с вероятностями r_₁,...,r__m, соответственно. Будем также предполагать, что исходный открытый текст является обычным литературным текстом. В этих условиях требуется дешифровать полученную криптограмму.

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

При решении поставленной задачи примем во внимание, что в i-м такте шифрованию подлежала одна из следующих букв открытого текста:

t_i⁽¹⁾=s_i – ₁,..., t_i^(m)=s_i – _m, (8)

где s_i – буква шифртекста.

Поэтому знаки открытого текста следует искать в колонках таблицы, изображенной на рис. 9:

Рис.9

Отбирая по одному знаку из каждой колонки так, чтобы получился "читаемый" текст, мы получим возможность восстановить открытый текст.

Описанный метод относится к классу так называемых методов бесключевого чтения (когда открытый текст восстанавливается без предварительного определения ключа) и называется методом чтения в колонках.

Метод чтения в колонках можно усовершенствовать за счет упорядочения букв в колонках. В самом деле, в каждом такте возможные знаки открытого текста t⁽¹⁾=s – ₁,..., t⁽^m⁾=s – _m имеют априорные вероятности р_t₍₁₎,...,р_t₍_m₎, которые считаются известными. В нашем случае имеется также дополнительная информация, а именно, известно, что произошло событие "s_i = s". При этом

p{s_i=s/ t_i=t^(k)}= r__k, k=1,…,m.

Отсюда по формуле Байеса получаем

(9)

Теперь можно упорядочить вероятности (8) знаков открытого текста в каждой колонке таблицы в соответствии с убыванием вычисленных апостериорных вероятностей. Поступив таким образом, мы поместим наиболее вероятные знаки открытого текста в начало таблицы, чем облегчим чтение в колонках.

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

Пример (использования неисправности в реализации шифра Вернама)

Рассмотрим шифр гаммирования, определяемый уравнением (4), называемый шифром Вернама. Знаки открытого текста и знаки гаммы представляются при этом 5-мерными двоичными векторами.

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

Покажем, как это сделать при условии, что "исправная" гамма является случайной и равновероятной. Будем при этом рассматривать позначные модели открытого текста, гаммы и шифртекста, то есть считать, что они являются реализациями случайных независимых испытаний полиномиальных схем с соответствующими распределениями вероятностей р(А), r(A), s(A) на знаках открытого текста, гаммы и шифртекста. Естественно также условиться, что распределения р(А) и r(А) являются независимыми. При этом распределение s(A) определяется формулой

(10)

где х – знак открытого текста,  – знак гаммы, у – знак шифртекста.

Итак, в нашем случае алфавитом открытого текста, шифрованного текста и гаммы является множество

А={(а₁,а₂,а₃,а₄,а₅) :а_i Z₂, i=1,…,5},

образующее абелеву группу относительно операции  покоординатного сложения векторов по модулю 2. При обрыве, например, первого соединения возможные знаки гаммы образуют подмножество

В={(0, ₂, ₃, ₄, ₅) :_i Z₂, i=2,…,5},

являющееся подгруппой группы (А, ). Точно так же и при любых других обрывах множество знаков гаммы образует подгруппу В группы (А, ).

Разложим группу А = {а₁,…,а_n} в левые смежные классы по подгруппе В :

А=В (g₂B) …(g_rB), (11)

где g_i  A, i=2,…,r, – представители соответствующих смежных классов.

Теперь с использованием частотных свойств используемого кода (например, МТК-2 или др.), аналогичных частотам букв в открытом текcте, можно подсчитать значения вероятностей знаков смежных классов g_iB, i=1,…,r, из разложения (11) по формуле

где a  g_iB. Этот подсчет может быть проведен для любых комбинаций обрывов. Теперь остается определить частоты символов шифртекста и сравнить их с рассчитанными заранее эталонными диаграммами. Сравнение выявит характер неисправности, и задача восстановления открытого текста будет сведена к чтению в колонках.

Заметим, что вместо 5-мерных можно было рассматривать и n-мерные векторы, п > 5. Предложенный метод работает и в этом, более общем случае.

Содержание