Дешифрование шифра гаммирования при некачественной гамме

Пусть I некоторый алфавит буквы которого упорядочены в естественном порядке. Запись i+i`=i`` будем понимать как модульное сложение номеров букв из {1,2,…,|I|-1,0}по модулю |I|. То есть, записывая уравнения, связанные с гаммированием мы отождествляем буквы с их номерами в алфавите.

Предположим, что в качестве знаков гаммы в шифре гаммирования могут быть лишь знаками i, i`ÎI, то есть уравнения образования шифртекста b₁,b₂,…, b_T имеют вид a_j+g_j=b_j, jÎ{1,2,…,N} (можно сказать, что в данном примере используют всего 1 бит гаммы).

В этом случае восстановление открытого текста a₁,a₂,…, a_N по шифртексту b_j не вызывает труда. Действительно, по известному шифртексту выпишем колонки букв (переведя их в положительные вычеты)

b1 – i	b2 –i	……		bN –i
b1 -i`	b2 –i`	……		bN –i`

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

К	Ш	И	П	Ш	О	Л	Ш	А	Э	И	Ж
В	Р	А	З	Т	Ж	Г	Р	Ш	Ф	А	Я

Прочитали слово КРИПТОГРАФИЯ?

Если бы для зашифрования использовалось 4 буквы, то глубина колонки была бы равна 4. Если используется полная гамма – для русского языка все 32 знака, то глубина колонок равна 32 и Вы можете в ней прочитать любой текст.

Предположим, что гамма шифрования принимает все значения, но с разными вероятностями. В этом случае для дешифрования также существуют определенные подходы. Один из них заключается в чтении в колонках, где порядок (сверху вниз) в колонке возможных открытых букв aÎI определен убыванием (точнее, не возрастанием) вероятностей

Р(a/b)=P(a,b)/p(b)=

при известной фиксированной букве b. Здесь (p(a),aÎI) – вероятностное распределение букв открытого текста, (q(c), cÎI) – вероятностное распределение на знаках гаммы.

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

Предположим, что при решении криптографической задачи (например, определения открытого текста при перекрытии шифра, или при использовании некачественной гаммы наложения в шифре гаммирования) удалось для каждой неизвестной буквы построить множество букв среди которых она находится, то есть на каждом месте построить колонку размером (глубиной) h допустимых вариантов букв, среди которых заведомо находится истинная буква. Используя читаемость открытого текста, можно попытаться выбрать из каждой колонки одну букву так, чтобы полученный текст был осмысленным. Если нарисовать колонки букв и отметить в колонках истинные буквы, то процесс чтения будет иметь визуально зигзагообразный характер. Для малых значений глубины h найти открытый текст описанным выше образом не составляет труда. Если глубина h велика, то среди возможных открытых текстов, которые можно прочесть зигзагообразным чтением, могут быть ложные тексты. Как определить критическую глубину h₀, при которой можно считать, что открытый текст все еще остается единственным?

Пусть

n=32 – количество букв в алфавите,

H(n)=H (дв.ед.)/log₂n – энропия на букву по основанию n,

L – длина сообщения,

h – глубина колонки.

Ниже будет показано, что существует h₀, что при h<h₀ зигзагообразное чтение дает единственный открытый текст, а при h>h₀ существует много ложных открытых текстов.

Итак, мы имеем:

1. всего последовательностей из L знаков – N=n^L,

2. среди этих последовательностей – M=n^H(n) осмысленных текстов (свойство «равнораспределенности»),

3. из L колонок глубины h можно получить K=h^L любых последовательностей.

Проведем сначала прикидочный расчет. Будем считать, что каждая последовательность из K=h^L последовательностей получена выборкой из равновероятного распределенияна множестве всех последователностей длины L букв алфавита. Вероятность получения при таком выборе открытого текста приблизительно равна М/N. При К испытаниях среднее чило получаемых открытых текстов равно КМ/N= h^L n^H(n)/ n^L. Это число равно единицы (один открытый текст в колонках единственный) при h₀=n^1-H(n). Для русского литературного языка n=32, H(n)=1/5, h₀=32^4/5=16.

Математическая модель. Будем считать, что в колонках всегда содержится истинный осмысленный текст. При составлении любой последовательности из букв, содержащихся в колонках, мы как бы производим выборку без возвращения объема K-1 из множества N-1, в котором M-1 -»белых» шаров (осмысленных текстов) и N-M «черных» шаров (нечитаемых текстов). Какова вероятность P(m) того, что будет выбрано m «белых» шаров, т.е. m осмысленных текстов?

Мы имеем случай гипергеометрического распределения и

P(m)= .

Нас интересует случай m=0, т.е. вероятность того, что в колонках содержится только один осмысленный текст:

P(0)=

Произведем асимптотический анализ этой формулы в предположении, что длина сообщения L . Очевидно, что при этом M,K так, что , или, в других обозначениях, . Воспользуемся формулой Стирлинга

m!= .

Тогда нетрудно показать, что

P(0)= =

= .

Отсюда нетрудно видеть, что если , то вероятность единственности зигзагообразного чтения стремиться к единице, а при – к нулю. Величину критической глубины зигзагообразного чтения можно положить равной h₀=n^1-H(n).