Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии

Шифры гаммирования

лением к каждому его элементу числа ^(/,7*) (по модулю п ),

имеет нулевой относительный сдвиг с У/ .

Пусть У® 9У* 1 — результаты зашифрования

У^ каждой из простых замен (18). Несложно вычислить вза­

имные индексы

м ц г ^ г ; 1), 0 < 5 < п - 1 , ! < / < / < / /

(всего, таким образом, имеется С'2 • п значений). Для этого

воспользуемся формулой, полученной из (19):

п- 1

Если я равно ^ (относительному сдвигу У^ и У ^ \

то взаимный индекс совпадения должен быть (для английско-

го языка) близок к 0,066, так как относительный сдвиг У/ и

„Л		, то взаимный индекс
У*	равен нулю. Если же я Ф^

совпадения должен колебаться в пределах 0,032 4- 0,045. Используя изложенный метод, мы сможем связать систе­

мой уравнений относительные сдвиги различных пар столб-

цов У^ и У^ . В результате останется 26 вариантов для клю-

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

Следует отметить, что предложенный метод будет эф­ фективным для не слишком больших значений // . Это объ-

151

/лава 6

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

§ 6.6. Ошибки шифровальщика

Предположим, что при шифровании текста Т = /^2.../,

модульной гаммой Г —у ху 2—/1 произошел сбой и был про­

пущен (или повторен) некоторый т-значный отрезок гаммы

(или открытого текста) УкУк+\—Ук+т-\ (соответственно

1к*к+\—*к+т-\)- Э™ могло произойти, например, в случае, ко­

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

Рассмотрим случай, когда в результате сбоя оказывается пропущенным отрезок открытого текста. Тогда криптоанали­ тик противника будет иметь два шифрованных текста:

^1 = ( 1 + У\’—>*к-\ + У к -1 ’ *к+т + У к ’- ’ (1 + У1-т>

8 2 =(\ + У 1 + У к - ] ’ *к + У к ’ —>*1 +У1-

Теперь можно выделить следующие два фрагмента в 51,

и 82:

= *к+т + У к ’" - ’ *1-т + У 1-2т’

(22)

^ 2 ^к+т Ук+т

У 1-т '

152

Шифры гаммирования

Распишем отрезки открытых текстов в виде последова­ тельности т-грамм:

Т	~ 0 к ’ ""> ^к+ т -\ )’			к+т	к+ 2т -\ )’**• ?
	------------------V	у--------------------	'-4------------------------		у ---------------------	/
Т	~~ ^ к + т	>'” ^ к + 2 т - \ )>••• •
	-------------------V	^-------------------		/
Так же распишем отрезок гаммы:
^	~ (У к 9***9У к+т-1 (У к+т ’•**> У к+ 2т -\					'	*
	4----------------	у-----------------	' 4-------------------		у -------------------
		Го			У\
Тогда соответствующие отрезки 5,					и 82 можно представить
в виде суммы т-грамм:
		*^1 ~*\ +У09*2 +У\’-">						^23^
		$2	+У\>*2		У2’**•’
где векторы складываются покоординатно по модулю п.
Теперь можно выразить разность 82 —8Х:
	&	= $2 “	^1 =	У 1	Уо> У 2 ~ У \ > — •			(2 4 )
Пусть 5 = ^ ,$ 2,.... Тогда с помощью (24) образуем по­
следовательность
	<5*—	•1")5,29»У| “Ь‘5'2				,
					I

которая, в силу очевидного равенства ^ Ии = / , —у0, имеет

и=1
ВИД
8 = Г о ~ Г о >Г1 ~ Г 0 ’ Г 2 - Г о — •	(2 5 >

153

I лава Ь

Наконец, находим разность 8 Х= 5) - 5 , которая, с уче­

том (25), имеет вид

5 , = 7\ + У о,12 + Уо><з + Уо> - •

(2 6 )

Последовательность (26) представляет собой результат

зашифрования отрезка открытого текста Тх =^+т^А :+т+1 >•••

периодической гаммой

^1 ~~ У к ->Ук+\ > -"> У к+ т -\> У к > У к+ \’‘” >У к+ т -\>—

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

Нетрудно убедиться в том, что и три другие ошибки (в комбинации: пропуск/повтор отрезка гаммы/открытого тек­ ста) также приводят к задаче вскрытия шифра Виженера. Кроме того, легко установить характер такой ошибки непо­ средственно по текстам двух имеющихся в распоряжении криптоаналитика шифртекстов.

Контрольные вопросы

1.В чем слабость шифра гаммирования с неравновероятной гаммой?

2.Является ли надежным шифрование литературного текста с помощью модульного гаммирования, использующего гамму, два знака которой имеют суммарную вероятность, совпадающую с суммарной вероятностью остальных зна­ ков? Почему?

3.Почему наложение на открытый текст гаммы, представ­ ляющей собой периодическую последовательность не­ большого периода, не дает надежной защиты?

154

Шифры гаммирования

4.Почему недопустимо использовать дважды одну и ту же гамму (даже случайную и равновероятную!) для зашиф­ рования разных открытых текстов?

5.Почему в качестве гаммы нецелесообразно использовать текст художественного произведения? Можете ли Вы

предложить метод вскрытия такого шифра?

6. Можно ли по шифртексту получить приближения для вероятностей знаков гаммы?

7.В чем состоит тест Казисии?

8. Назовите основные этапы работы по вскрытию шифра Виженера.

9.Каким образом рассчитывается индекс совпадения для реального языка?

10.Из каких простых замен «состоит» шифр гаммирования (как многоалфавитный шифр)?

155

Глава 7

Надежность шифров

§ 7.1. Энтропия и избыточность языка

Рассмотренные нами модели отражают лишь поверхност­ ные свойства открытых текстов. Более глубокие свойства тек­ стов изучаются методами теории информации, разработанной К. Шенноном. Речь идет о “количестве информации”, содер­ жащейся в сообщении. Для выяснения этого необходимо вве­ сти разумную меру количества информации.

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

прирост информации = устраненной неопределенности,

на основании которой неопределенность и информация долж­ ны измеряться одной и той же мерой.

К такому выводу можно прийти на примере эксперимента со случайным бросанием монеты. Какова неопределенность того, что в результате очередного бросания монеты выпадет “орел”? Если монета дефектна и при бросании всегда выпада­ ет орлом, никакой неопределенности нет — наоборот, есть полная определенность: обязательно выпадет орел. Макси­ мальной же неопределенность будет, очевидно, в случае, ко­ гда монета не имеет дефектов, т. е. с равными вероятностями выпадают обе ее стороны.

Результат бросания монеты можно трактовать иначе. Ес­ ли монета всегда выпадает орлом, то при проведении очеред­ ного эксперимента мы не получим никакой информации: мы

156

Надежность шифров

заранее знали об исходе эксперимента. Другими словами, ко­ личество информации, извлекаемой из эксперимента, равно нулю. Максимальным количество получаемой информации будет, очевидно, в случае когда «орел» и «решка» равноверо­ ятны.

Пример количественной меры неопределенности случай­ ного эксперимента дает теоретическая физика — такой мерой служит энтропия. Применительно к независимым испытани­ ям случайной величины % с распределением вероятностей

4 = (1)

энтропия Н (^ ) определяется формулой

п

(2)

Единицу измерения энтропии вероятностной схемы пред­ лагает так называемая теорема кодирования [Ягл73], утвер­ ждающая, что любой исход можно закодировать символами О и 1 так, что полученная длина кодового слова будет сколь угодно близка сверху к Н {%) . На основании этого единицей количества информации естественно считать 1 бит. Напри­ мер, количество информации, получаемое при бросании мо­ неты, равно 1 бит, так как орел можно закодировать единицей,

а решку — нулем.
Легко	видеть,	что если р ^ Х / п	при всех / = 1,л, то
Н 0 =	= 1о§ 2 п . Кроме того, в общем случае имеет ме­
сто неравенство Н		( > О, причем Н (	= 0 в том и только в
том случае, когда		р ( = 1 для некоторого / и р ] = 0 для всех

У * * -

157

[ лава 7

Мерой среднего количества информации, приходящейся на одну букву открытого текста языка Л (рассматриваемого как источник случайных текстов), служит величина Н А, на­ зываемая энтропией языка Л . Естественно вычислять ее по­

следовательными приближениями: Н 0, Н х, где Н х — эн­

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

а1 в открытом тексте. Для английского языка, Н 0 » 4,70,

Н х = Н ( ^ ) «4,14. В качестве следующего, более точного

приближения, энтропия вероятностного распределения би­ грамм, деленная на 2 (нас интересует энтропия на знак). В общем случае следует взять энтропию вероятностной схемы на г-граммах, деленную на г. Соответствующие вычисления

для английского языка дают отношения	Н 2
	----- «3,56,
	2

ц

® 3,30, и так далее. Исследования показывают, что с рос-

Н г

том г отношение —- стремится к некоторому пределу. Этот

г

предел и принимается за определение энтропии Н А языка

Л 5:

Я Л = Н ш ^ .	(3)
Г—>00 у»

При этом формула

5 Существование предела (3) строго доказывается для стационарных эргодических источников сообщений.

158

надежность шифров

(4)

1о§2 п

определяет избыточность языка КА.

Термин “избыточность языка” возник в связи с тем, что максимальная информация, которую в принципе могла бы нести каждая буква сообщения, равна Н 0 = 1о§0п (где п —

число букв в алфавите). Как было отмечено выше, так было бы в случае, если буквы сообщения появлялись случайно и равновероятно. В то же время средняя энтропия буквы в от­ крытом тексте значительно меньше и, следовательно, буква несет меньше информации, чем 1о§^ п . Величина

1о§а п - Н х характеризует, таким образом, неиспользованные возможности в передаче информации с помощью текста, а

отношение
\оёап - Н к	^
1о§2 п	1о§2 п

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

К. Шеннон предложил оригинальный метод оценивания отношения Н г/ г для осмысленных текстов с позиции меры неопределенности опыта, состоящего в угадывании г-й буквы текста, при условии, что предшествующие его буквы извест­ ны [Ягл73]. Эксперимент по угадыванию г-й буквы текста легко может быть поставлен. Для этого достаточно выбрать осмысленный отрезок открытого текста длины г —1 и пред­ ложить кому-либо угадать следующую букву. Подобный опыт может быть повторен многократно, при этом сложность уга­ дывания г -й буквы может быть оценена с помощью среднего

159

/лава /

значения числа попыток Рг9 требующихся для нахождения

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

есть что отвечающая им величина	Н г/ г практически	уже
достигла своего предельного значения Н А.
Исходя из этих рассуждений,	К. Шеннон произвел	ряд

подобных экспериментов, в которых г принимало значения 1,15 и 100. При этом он обнаружил, что отгадывание сотой буквы по 99 предшествующим заметно более просто, чем уга­ дывание 15-й буквы по 14 предыдущим. Опыты показали, что

с ростом г величина	Н г/ г	убывает вплоть до г « 3 0 , а при
дальнейшем росте г она уже практически не меняется.
Согласно исследованиям Б. Б. Пиотровского				[Ягл73],
имеют место следующие приближения величины Н л :
Т аб л и ц а 8
		Яд
	(бит/букву)		(в процентах)
Русский		Франц.	Русский	Франц.
	язык	язык	язык	язык
Язык в целом	1,37	1,40	72,6	70,6
Разговорная	1,40	1,50	72,0	68,4
речь		1,38	76,2
Литературный	1,19			71,0
текст		1,22	83,4
Деловой текст	0,83			74,4

160