Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии
.pdfШифры гаммирования
г Р о Р п -1 •••Р\ Л
Р = |
Р\ |
Ро - |
Рг |
|
|
|
|
|
р п-\ |
р п. 2 |
- Р о |
Такая матрица называется циркулянтом [Кос87]. В ней каждая строка получается циклическим сдвигом предыдущей
строки. Известно [Кос87], что определитель |Р| циркулянта
равен произведению
где {е0,...,еп_1}— множество всех корней степени п из 1 (в
поле комплексных чисел), причем
и-1
В том случае, когда Р | Ф 0, вектор г однозначно опре
деляется из соотношения
Г 1 = р - ‘ . Л |
(6) |
Приведем (без доказательства) формулу для Р 1
/ |
х0 |
X, |
... х и_, |
^ |
|
Р~1 = |
х п - \ |
х 0 |
- |
х п - 2 |
(7) |
|
Х[ х 2 - |
*0 |
) |
131
/ лава 6
где
Условие \Р Ф О можно проверить непосредственно по данному распределению вероятностей букв открытого текста.
Пользуясь (6) и (7), можно вычислить приближение г^
для г |
1 |
, подставляя вместо |
5 |
I |
в (6) вектор |
у |
I |
1 |
... , где |
|
|
|
= - |
V; — число вхождений символа / в шифрованный текст:
откуда
§6.3. Восстановление текстов, зашифрованных неравновероятной гаммой
Пример (использования шифра модульного гаммирова
ния)
Рассмотрим следующую постановку задачи. Пусть при использовании шифра модульного гаммирования в результа те, например, некоторой неисправности гаммообразующего
132
Шифры гаммирования
устройства, т.е. устройства, вырабатывающего гамму, в ней встречаются не все знаки. Предположим, далее, что гамма состоит лишь из знаков у]9...9у т, т <п , которые встречают
ся с вероятностями г 9...9гг соответственно. Будем также
предполагать, что исходный открытый текст является обыч ным литературным текстом. В этих условиях требуется де шифровать полученную криптограмму.
Заметим, что к подобной постановке задачи можно было прийти иначе. Выделив несколько знаков гаммы, имеющих достаточную суммарную вероятность, например 0,8, предпо ложим, что лишь они использовались при шифровании. Это предположение может привести к потере истинного варианта при построении некоторого метода вскрытия. Вероятность потери можно оценить при этом стандартными методами статистики.
При решении поставленной задачи примем во внимание, что в /-м такте шифрованию подлежала одна из следующих букв открытого текста:
',0) = * , - Г \ ’~ Л т) =з,-Гт> |
(8) |
где — буква шифртекста.
Поэтому знаки открытого текста следует искать в колон ках таблицы, изображенной на рис. 18:
Р и с .18
133
/лава 6
Отбирая по одному знаку из каждой колонки так, чтобы получился “читаемый” текст, мы получим возможность вос становить открытый текст.
Описанный метод относится к классу так называемых методов бесключевого чтения (когда открытый текст восста навливается без предварительного определения ключа) и на зывается методом чтения в колонках.
Метод чтения в колонках можно усовершенствовать за счет упорядочения букв в колонках. В самом деле, в каждом такте возможные знаки открытого текста
имеют априорные вероятности р (1),...,р (т), которые счита
ются известными. В нашем случае имеется также дополни тельная информация, а именно, известно, что произошло со бытие “ ^ =5 ”. При этом
р{а, = я/1, = {(к)} = гп , к = 1, т .
Отсюда по формуле Байеса получаем
------------ , К = 1,01. (9)
Теперь можно упорядочить вероятности (8) знаков от крытого текста в каждой колонке таблицы в соответствии с убыванием вычисленных апостериорных вероятностей. По ступив таким образом, мы поместим наиболее вероятные зна ки открытого текста в начало таблицы, чем облегчим чтение в колонках.
134
Шифры гаммирования
С ростом т чтение в колонках становится затруднитель ным, а при т —п и при условии, что при шифровании ис пользовалась случайная равновероятная гамма, каждая ко лонка содержит все знаки алфавита, ни одному из которых нельзя отдать предпочтения. Поэтому в последовательности колонок можно прочитать любой текст, то есть нет возмож ности получить информацию об истинном сообщении.
Пример (использования неисправности в реализации шифра Бернама)
Рассмотрим шифр гаммирования, определяемый уравне нием (4), называемый шифром Вернама. Узел реализации такого шифра можно представить схемой, изображенной на рис. 19. На этой схеме кружочками обозначены узлы сложе ния по модулю 2 битов открытого текста с соответствующи ми битами гаммы. Знаки открытого текста и знаки гаммы представляются при этом 5-мерными двоичными векторами.
Рис. 19
В случае обрыва одного из “проводков”, идущих от ис точника гаммы, последовательность знаков гаммы будет со-
135
I лава 6
держать лишь половину возможных своих значений. Соответ ствующая координата в любом 5-мерном векторе гаммы бу дет равна нулю. В случае обрыва двух или большего числа “проводков” векторы гаммы будут содержать два или боль шее число нулевых координат. Число возможных знаков гам мы будет сокращаться вдвое при каждом обрыве. Таким об разом, подобная неисправность схемы приводит к постановке задачи, указанной в предыдущем пункте. В рассматриваемом случае подобную неисправность можно обнаружить по шифр тексту.
Покажем, как это сделать при условии, что “исправная” гамма является случайной и равновероятной. Будем при этом рассматривать позначные модели открытого текста, гаммы и шифртекста, то есть считать, что они являются реализациями случайных независимых испытаний полиномиальных схем с соответствующими распределениями вероятностей р ( А ),
г ( А), 8 (А ) на знаках открытого текста, гаммы и шифр текста. Естественно также условиться, что распределения р(А) и г(А) являются независимыми. При этом распределе ние ?( А) определяется формулой
*(у)= ^ р М - г(г ), |
(10) |
(х,г)
у=х@ /
где х — знак открытого текста, у — знак гаммы, у — знак шифртекста.
Итак, в нашем случае алфавитом открытого текста, шиф рованного текста и гаммы является множество
А = {{ах, а 2, а ъ, а ^ , а ь) : а, е 2 2,/ = 1,5},
образующее абелеву группу относительно операции ® поко ординатного сложения векторов по модулю 2. При обрыве,
136
Шифры гаммирования
например, первого соединения (на рис. 19 обрыв указан сим волом “ / “) возможные знаки гаммы образуют подмножество
В = { ф , р 2, р ъ, р л, р 5): |
е 2 2,у = 2,5}, |
являющееся подгруппой группы |
(А,Ф) . Точно так же и при |
любых других обрывах множество знаков гаммы образует подгруппу В группы (Д ® ) .
Теорема. При использовании равновероятной гаммы векторы, принадлежащие одному смежному классу группы А по подгруппе В, встречаются в шифртексте с равными веро ятностями.
Д оказательство. Разложим группу А = {ах,...,ап} в ле
вые смежные классы по подгруппе В = {Ъх 9...Ьт}: |
|
Л = Д и ( я 2 е Я ) и . . . и ( * г Ф Д ), |
( 1 1 ) |
где §; е А, 1 = 2,1, — представители соответствующих
смежных классов, и рассмотрим один из смежных классов
Н = {к\,...,кт} |
в |
этом |
разложении. |
Пусть для |
удобства |
|
Н = § Ф В . Ясно, |
что |
числа (,т,п |
связаны |
равенством |
||
п = 1*т. |
|
|
|
|
|
|
Выберем нумерацию элементов множеств В |
и |
Н в со |
||||
ответствии с равенством |
|
|
|
|
||
_ |
|
|
Нк = ё ® Ъ к |
|
(12 |
|
при к = \ , т . |
|
|
|
|
|
|
Так как В само является группой, при любых |
г , к е \ , т |
|||||
найдется такое |
/ е 1, т , для которого выполняется равенство |
13'
|
(лава 6 |
ъ, = ьк ® V |
(13) |
Заметим, попутно, что в группах А и В каждый элемент явля ется обратным для самого себя.
Легко видеть, что если в (13) индекс / пробегает все зна чения от 1 до т , то (при фиксированном к) и индекс ] пробе гает то же множество значений.
Вычислим вероятность $(кк) появления знака кк смеж
ного класса Н в шифртексте. В связи с условием равноверо ятности знаков гаммы, а также в соответствии с ( 10) - (13) имеем:
При этом мы воспользовались тем очевидным свойством, что в случае обрыва знаки гаммы по-прежнему будут иметь оди наковые вероятности.
Отсюда следует, что вероятность з(кк ) не зависит от к и
совпадает с ^(к}) для любого / = \9тп, что и требуется. Теорема доказана.
Доказанная теорема позволяет определить по шифртексту характер произошедшей неисправности. Для этого с исполь зованием частотных свойств используемого кода (например, МТК-2 или др.), аналогичных частотам букв в открытом тек
138
Шифры гаммирования
сте, можно подсчитать значения вероятностей знаков смеж ных классов §{® В, г = 1,/, из разложения (1 1 ) по формуле
М8.ФВ)
где а е ® В . Этот подсчет может быть проведен для лю
бых комбинаций обрывов. Теперь остается определить часто ты символов шифртекста и сравнить их с рассчитанными за ранее эталонными диаграммами. Сравнение выявит характер неисправности, и задача восстановления открытого текста будет сведена к чтению в колонках.
Заметим, что вместо 5-мерных можно было рассматри вать и л-мерные векторы, п > 5. Предложенный метод рабо тает и в этом, более общем случае.
§ 6.4. Повторное использование гаммы
Как и раньше, мы предполагаем, что алфавит А откры тых текстов, гаммы и шифртекстов представляет собой мно жество чисел Ъп = {0,1,..., п —1} .
Пусть в распоряжении криптоаналитика оказались две криптограммы, полученные наложением одной и той же гам мы на два разных открытых текста:
8 { = Г| + Г ( т о А п ),
^2 = + Г ( т о й п ) ,
где
Рассмотрим возможности криптоаналитика по восстанов лению исходных открытых текстов.
/ лава 6
Прежде всего можно найти позначную разность
5 = 5| - 8 2 = Тх - Т 2(гпосЗгс).
Пусть 5 = 2,... • Тогда поставленная задача сводит ся к попытке подобрать пару открытых текстов, разность ко торых совпадает с известной последовательностью 5 . Будем в связи с этим говорить о разложении 8 на два составляю щих открытых текста. В случае когда данные тексты являют ся нормативными текстами, например, на русском, англий ском или другом языке, для решения последней задачи ис пользуется ряд подходов. Интуитивно понятно, что при дос таточной длине текстов маловероятна возможность множест венного представления данной последовательности $ в виде разности Т х—Т 2. Как правило, такое разложение бывает единственным. Здесь имеет место приблизительно такая же ситуация, как и при рассмотрении вопроса о расстоянии единственности (см. гл. 7).
Один из таких подходов (хорошо известных из истории криптографии) связан с использованием некоторого запаса слов или словоформ, часто встречающихся в открытых тек стах. Это могут быть, например, стандарты переписки, частые А:-граммы и т. п.
Предположим сначала, что одно из вероятных слов встре тилось в начале первого сообщения:
вероятное слово
В таком случае можно вычислить начало второго сообщения:
140