Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
p{st =s/t, = t(k)} = rn,k = I ,т.
Отсюда по формуле Байеса получаем
Pfik) ^ 1
----------------, К = 1,01. (9)
134
Шифры гаммирования
С ростом т чтение в колонках становится затруднительным, а при т = п и при условии, что при шифровании использовалась случайная равновероятная гамма, каждая колонка содержит все знаки алфавита, ни одному из которых нельзя отдать предпочтения. Поэтому в последовательности колонок можно прочитать любой текст, то есть нет возможности получить информацию об истинном сообщении.
Пример (использования неисправности в реализации шифра Бернама)
Рассмотрим шифр гаммирования, определяемый уравнением (4), называемый шифром Вернама. Узел реализации такого шифра можно представить схемой, изображенной на рис. 19. На этой схеме кружочками обозначены узлы сложения по модулю 2 битов открытого текста с соответствующими битами гаммы. Знаки открытого текста и знаки гаммы представляются при этом 5-мерными двоичными векторами.
Рис. 19
В случае обрыва одного из “проводков”, идущих от источника гаммы, последовательность знаков гаммы будет со-
135
І лава 6
держать лишь половину возможных своих значений. Соответствующая координата в любом 5-мерном векторе гаммы будет равна нулю. В случае обрыва двух или большего числа “проводков” векторы гаммы будут содержать два или большее число нулевых координат. Число возможных знаков гаммы будет сокращаться вдвое при каждом обрыве. Таким образом, подобная неисправность схемы приводит к постановке задачи, указанной в предыдущем пункте. В рассматриваемом случае подобную неисправность можно обнаружить по шифртексту.
Покажем, как это сделать при условии, что “исправная” гамма является случайной и равновероятной. Будем при этом рассматривать позначные модели открытого текста, гаммы и шифртекста, то есть считать, что они являются реализациями случайных независимых испытаний полиномиальных схем с соответствующими распределениями вероятностей р(А), r(A), s(А) на знаках открытого текста, гаммы и шифртекста. Естественно также условиться, что распределения р(А) и 7(A) являются независимыми. При этом распределение s( А) определяется формулой
*оо= ?/>(*)-Кг)» о°)
(х,г)
у=х@/
где X — знак открытого текста, у — знак гаммы, у — знак шифртекста.
Итак, в нашем случае алфавитом открытого текста, шифрованного текста и гаммы является множество
А = {(ах,а2,аъ,а^,аь): а, е Z2,/ = 1,5},
образующее абелеву группу относительно операции ® покоординатного сложения векторов по модулю 2. При обрыве,
136
Шифры гаммирования
например, первого соединения (на рис. 19 обрыв указан символом “ / “) возможные знаки гаммы образуют подмножество
В = {(0,р2,р„р4,р5): Pj є Z2,у = 2,5},
являющееся подгруппой группы (А,0). Точно так же и при любых других обрывах множество знаков гаммы образует подгруппу В группы (А,0).
Теорема. При использовании равновероятной гаммы векторы, принадлежащие одному смежному классу группы А по подгруппе В, встречаются в гиифртексте с равными вероятностями.
Доказательство. Разложим группу А = {ах,...,ап} в левые смежные классы по подгруппе В = (^19...Ьт }:
A = Bv(g2®B)v...v(gr®B)9 (11)
где gi є A9 і = 2,/, — представители соответствующих
смежных классов, и рассмотрим один из смежных классов H = в этом разложении. Пусть для удобства
H — g®B. Ясно, что числа t9m9n связаны равенством n = t-m.
Выберем нумерацию элементов множеств В и H в соответствии с равенством
^ hk=g®bk (12 при к = \,т.
Так как В само является группой, при любых і,кє\,т найдется такое /є 1, т, для которого выполняется равенство
13'
tлава 6
b, =bk ®bj-
(13)
Заметим, попутно, что в группах А и В каждый элемент является обратным для самого себя.
Легко видеть, что если в (13) индекс і пробегает все значения от 1 до т, то (при фиксированном к) и индекс j пробегает то же множество значений.
Вычислим вероятность s(hk) появления знака hk смежного класса H в шифртексте. В связи с условием равновероятности знаков гаммы, а также в соответствии с (10) - (13) имеем:
При этом мы воспользовались тем очевидным свойством, что в случае обрыва знаки гаммы по-прежнему будут иметь одинаковые вероятности.
Отсюда следует, что вероятность s(hk ) не зависит от к и
совпадает с s(hi) для любого / = I9m , что и требуется. Теорема доказана.
Доказанная теорема позволяет определить по шифртексту характер произошедшей неисправности. Для этого с использованием частотных свойств используемого кода (например, МТК-2 или др.), аналогичных частотам букв в открытом тек-
138
Шифры гаммирования
сте, можно подсчитать значения вероятностей знаков смежных классов gt® B9 і = \9t, из разложения (11) по формуле
где а є g( ® В. Этот подсчет может быть проведен для любых комбинаций обрывов. Теперь остается определить частоты символов шифртекста и сравнить их с рассчитанными заранее эталонными диаграммами. Сравнение выявит характер неисправности, и задача восстановления открытого текста будет сведена к чтению в колонках.
