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

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

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

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

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

t_i⁽¹⁾=s_i – g₁,..., t_i^(m)=s_i – g_m, (8)

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

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

Рис.9

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

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

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

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

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

(9)

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

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

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

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

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

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

(10)

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

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

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

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

В={(0, b₂, b₃, b₄, b₅) : b_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. Предложенный метод рабо­тает и в этом, более общем случае.