Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

101

Ключом алгоритма является таблица К=(К1, К2,...,К8) из восьми 32мерных двоичных векторов. Основными узлами схемы являются накопители (регистры К.1 - К.5) длины. 32, сумматор по модулю 232, сумматор по модулю 2 (такой же как в ОЕЗ), 3 - блоки, подстановка сдвига Т. Подстановка Т в схеме ГОСТ осуществляет сдвиг заполнения регистра по циклу.

Сумматор по модулю 232 рассматривает поступающие на его вход 32-х битовое заполнение регистра К2 и 32 знака ключевой таблицы как два целых

числа (вектор трактуется как двоичная запись числа). С выхода сумматора снимается 32-х разрядный вектор - двоичная запись суммы по модулю 232 ,

поступивших на вход сумматора чисел. Восемь преобразований 3 заменяют поступающие на вход полубайты (4-х мерные вектора) йа другие полубайты по заданным таблицам..

Процедура шифрования в ГОСТ осуществляется следующим образом. Открытый текст разбивается на блоки по 64 бит. Каждый блок открытого тек­ ста0 =(0 1 ,0 2 ) шифруется по Шифру простой замены

2=(21,22)=Г(К,0),

	102
где преобразование Г задается рекуррентным соотношением
Н1+1=Н,., 0	0(К|((),Не), 1=1,2,......,32,
Н0=О1, Н,=02,
0 - покоординатное суммирование 32-мерных векторов в (Рг)32-
(21,22)=(Н зз,Нз2),
1(г)= 1, 2,	8, 1 , 2,	8, 1 , 2, ...,8, 8, 7,..., 1

О - преобразование (Р2)32 —> (Рг)32-

На вход преобразования в каждой итерации подается свой 32-мерный ключевой вектор. Первые 24 цикла подаются в прямой последовательности, а последние 8 циклов - в обратной. При преобразованиях О вектора у=(уо,...,Уз1) рассматриваются либо как последовательности из нулей и единиц, либо как двоичная запись целого числа (при суммировании по модулю 232),

У=Уо+2У1+22У2+ 2т'1Уз1.

Преобразование О (Р2)32 -» (Рг)32 имеет вид \у=0 (Кь и), где \у=Та8 ((К1+и) тоб 232), 8 - некоторое нелинейное преобразование У32 —>

Узг, при этом преобразовании	32-мерный вектор и представляется в виде
восьми 4-х мерных векторов	и=(иь ...., и8)
5(ии	,и8)=(51(1ц ),......., 88(и8))

8| : (Р2)4—>(Р2)4 - задается таблицей из 24=16 значений, Т8- подстановочная матрица типа сдвига

Т(ио, ,из1)=(и5(той32), и8+1(т0(132),...... . и31+.ч(тос1 32))- При каждой итерации преобразования О, как уже отмечалось выше, на

вход узла преобразования усложнения поступает 32 бита ключа. Поступают

они в следующем	порядке:
в 1	-ой итерации - 1-ая строка,
во	2-ой итерации - 2 строка,

в 8-ой итерации	-	8 строка,
в 9-ой	-	1 строка,
в 24-ой	-	8	строка^
в 25-ой	-	8	строка,
в 32-ой	-	1 строка.

То есть строки 3 раза проходятся в прямом направлении (24 итерации) и 1 раз - в обратном направлении (8 итераций). Результат этого преобразова­ ния записывается в регистры К.1 и К2 и является шифртекстом.

Сравнивая схемы ОЕ8 и ГОСТ, следует заметить, что они очень похо­

жи, но есть и отличия:

103

-в ГОСТе проводится в 2 раза большее число итераций, определяющих крип­ тографическую сложность результирующих преобразований;

-в ГОСТе существенно больше ключей (25б=6.4-1016вариантов ключевых ус­ тановок в БЕ8 и 2256= 6.4-1076 ключевых установок в ГОСТ).

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

Поточные шифры (/Про/).

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

Открытый „ Шифра­ Шифртекф'		Шифртекст Шифра­
текст	тор	тор
	Канал связи
Отправитель		Получатель

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

Описание поточных современных криптосхем можно найти в пособии: А.А. Варфоломеев, А.Е. Жуков, М.Ф. Пудовкина «Поточные криптосхемы. Основные свойства и методы анализа стойкости. М., 2000, 243 с., а также в гуляющей по Интернету одноименной книге.

Обычно поточный шифр удобно представить в виде трех блоков

104

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

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

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

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

1

105

Иногда в схеме присутствуют и некоторые несекретные параметры, называемые м а р ка нт а м и или синхропосылками. Делается это с той целью, чтобы усложнить задачу дешифрования. Если бы функционирование схемы зависело только от ключа, то все промежуточные последовательности (при отсутствии обратных связей) при, скажем, двукратном использовании ключа просто бы совпадали. Это - потенциальная криптографическая слабость. Терминч«синхропосылка» обычно применяется для электронных шифраторов, а «маркант» - для дисковых шифраторов, о которых пойдет речь ниже.

Дисковые шифраторы (/Про/).

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

Рь Рг> >Р(>.......

и шифрование открытого текста

1ь •••••••

будем проводить по правилу

У1 = Р1О1Х

,У« = Р.(1«),

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

«Энигма» (/Про/) в переводе означает «Загадка». Шифратор изобре­ тен в 1917 г. Эдваром Хеберном. Промышленная версия создана чуть позже берлинским инженером Артуром Кирхом (некоторые называют его Артуром Шербиусом). Активно шифратор «Энигма» и его модификации использова­ лись в годы второй мировой войны.

«Энигма» вначале представляла собой 4 вращающихся на одной оси барабана - диска.

106

Открытый текст Шифрованный

►

текст

I

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

В процессе шифрования на один из контактов левого диска поступал электрический импульс. Так как барабаны соприкасались контактами, то электрический импульс попадал на выход, проходя через четыре диска и пре­ терпевая четыре простые замены. Исполняющее устройство (пишущая ма­ шинка или перфоратор) фиксировало знак шифрованного текста в соответст­ вии с тем, на какой контакт выходного диска поступал электрический им­ пульс. Поскольку в каждый такт шифрования сдвигался на один шаг хотя бы один диск, подстановка - простая замена, по которой осуществлялось шифро­ вание, менялась для каждого символа открытого текста. Ключом шифратора, который сменялся каждый сеанс, являлся набор начальных угловых положе­ ний дисков. Долговременным ключом, он менялся очень редко, служили ком­ мутации дисков - соединения проводов внутри дисков. Для затруднения рас­ шифрования диски день ото дня переставлялись местами или менялись, т.е. 4 диска выбирались из комплекта, состоящего из 10-20 дисков. Для того чтобы не менять начальные установки на каждый сеанс связи, в некоторых сетях за­ крытой связ^1 использовался маркант. Делалось это следующим образом:

шифровальщик выбирал какую-то случайную начальную установку дисков. Далее шифровал на нем 4 заранее оговоренные буквы, например, АААА. Полученный шифрованный текст он не пересылал получателю, а использовал в

107

качестве начальной установки дисков прй шифровании. В начале шифрован­ ного текста проставлялся маркант - выбранные шифровальщиком случайные начальные установки.

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

2 1= Р 1(1)Р2([1/п]))Рз([1/п2])Р4([1/п3])0(,

где Р|(1) - подстановка, которая реализуется при повороте 1-го диска на I ша­

гов;

п- число символов в алфавите открытого текста;

[х]- целая часть х.

Очевидно, что Р|(1 + п)=Р1(1), если п - алфавит открытого текста или, что

то же самое, число угловых положений диска.

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

Шифратор Хагелин.

В качестве иллюстрации механических машин мы обсудим машину С- 36 известного разработчика криптографических машин Бориса Хагелина. Она известна также как М-209 Сопуейег и использовалась в армии США еще в начале пятидесятых годов. При описании шифратора Хагелин мы используем следующие работы.

1.Саломаа А. Криптография с открытым ключом. Пер. с англ.

А.А.Болотова и И.А. Вихлянцева под редакцией А.Е. Андреева и А.А. Боло­ това. М.: Мир, 1996.

2.Вагкег, \У.О. Сгур1апа1у813 о!" Ше На§еНп Сгур1о§гарЬ, Ае§еап

Рагк Ргезз, 1977.

3.Векег, Непгу апб Р1рег, Ргей. С1рЬег Зуз1етз. ТЬе Ркйесбоп оГ

Соттимсайопа. Могйтооб Воока, Бопбоп. 1982.

108

4.Э. КаЬп, ТЬе СоёеЬгеакегз: ТЬе 8югу оГ 8есге1 \УпПп§, №\у

Уогк: МастШап РиЪНзЫп§ Со., 1967.

5.ТесЬшса1 Мапиа1 Гог Сопуейег М-209.118 \Уаг ОерагЬпеп!:, 1942 (ЬИр://\у\у\у.гпапНше.ог§/с5р1500.Ь1ш).

На§еНп М-209

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

	Р ейтеры		Барабан с пронумерованными
			подвижными комбинационными
			линейками
Шестерня, продвигаемая
выдвинутыми комбинационными	_
линейками
Индикаторный диск,
на котором набираются
вводимые буквы
			Комбинационная линейка,
			\сдвинутая влево и ставш ая
			зубцом ш естерни
			с переменным
			числом зубцов
		Нерабочие\	Скошенная верхняя часть
			промежуточного рычага
Воспроизводящий диск,			гаммообразующиего колеса
с которого считы ваю тся
получающиеся в резул ьтате		и рабочие	Гаммообразующее
буквы		ш ти ф ты	колесо

Кинематическая схема М-209

1

109

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

Рассмотрим 6 х 27-матрицу М, элементами которой являются 0 и 1.

Потребуем также, чтобы в каждом из 27 столбцов матрицы М было не более двух единиц. Такие матрицы называются кулачковыми матрицами. Матрица

0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1

1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

М = 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0

является примером кулачковой матрицы.

Очевидно, что если V является 6-разрядной строкой из нулей и единиц,

то уМ (произведение вектора V на матрицу М) является 27-разрядной строкой с элементами из множества {0,1,2}. К примеру, если V= (1, 0,1,1, 0, 0), то

уМ = (0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 2, 1,1, 1, 0, 0, 0, 1, 1,1, 1, 1,2). (Здесь мы использовали матрицу М, написанную выше). Число эле­

ментов вектора уМ, о т л и ч н ы х о т нуля, называется числом выталкиваний зуб­

цов у относительно М. В нашем примере оно равно 16. Обычно, данное число является натуральным числом от 0 до 27

Пошаговая матрица конструируется следующим образом. Построим 6

последовательностей чисел из множества {0,1}. Эти последовательности имеют соответствующие длины 17, 19, 21, 23,25, 26 и начинаются с одной позиции.

К примеру,
0 1 1 0 0 0		1 0 0 0 0 0 0 0	1 1 0
01	1 1 1 1 0 0 0 0 0 0 0 0 0.0 0 0 0

0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1

1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1

есть ступенчатая матрица. В отличие от кулачковой матрицы, для ступенчатой матрицы нет ограничений на позиции единиц.

Пошаговая матрица генерирует бесконечную последовательность 6-

разрядных (строк) векторов следующим образом. Первые 17 векторов чита­ ются прямо из столбцов. Таким образом,

(0, 0, 0, 0, 1, 1) и (1 , 1, 0, 0, 0, 1)

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

			110
(0, 0, 0, 0, 0, 0)	(0,	0, 0, 0, 0,		0)	(1, 0, 0, 1, 0, 1)	(1,	0, 0, 0,0, 0)
(0, 1, 0, 0, 0, 0)	(0, 1,		0, 0,0,	0)	(0, 1, 0, 1, 0, 0)	(1,	1,	1, 0,0, 0)
(0, 1, 0, 0, 0, 0)	(0, 0,		0, 0, 1, 1)		(0, 0, 0, 0, 0, 1)	(0, 0,		0, 0,1, 1)
(0, 0, 0, 0, 0, 0)	(0,	0, 1, 0, 0,		0)	(0, 0, 0, 0, 0, 0)	(1, 0,		0, 0, 0, 0)
(1, 0, 0, 0, 0, 0)	(0, 0,		0, 0,0,	0)	(0, 0, 0, 1, 0, 0)	(1, 0, 0, 0,0, 0)
(1, 0, 0, 0, 0, 0)	(0, 0,		0, 0,0,	0)	(0, 0, 0, 1, 0, 0)	(1, 0, 0, 0,0, 0)
(1, 1, 0, 0, 0, 1)	(0,	1, 0, 1, 0, 0)			(0, 1, 0, 0, 0, 0)	(0,	1,	0,	0, 0, 0)
(0, 0, 1, 0, 0, 1)	(0,	0, 0, 1, 0,		0)	(0, 0, 0, 0, 0, 0)

Имея определенные кулачковую и ступенчатую матрицы, мы те­ перь можем сказать, как получается шифртекст. Для букв используют число­ вые коды: А получает номер 0, В получает номер 1 и т. д. Ъ получает номер

25.Сложение и вычитание чисел будет вестись по модулю 26.

'Обозначим через а 1-уЮ букву исходного сообщения, а через Ь — число выталкивании зубцов 1-го вектора, порожденного ступенчатой матри­

цей относительно кулачковой матрицы. Тогда а переводится в букву крипто­ текста

у=Ь-а-1.

Для примера рассмотрим исходное сообщение

аОУЕНКМЕЫТОРТНЕРЕОРЬЕВУТНЕРЕОРЬЕАШРСЖТНЕРЕОРЬЕ

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

6, 14,21,4, 17, 13, 12,4, 13, 19, 14,5, 19,7,4, 15,4, 14, 15, 11,4, 1,24,

19, 7,4, 15,4, 14, 15, 11,4, 0, 13, 3, 5, 14, 17, 19, 7, 4, 15,4, 14, 15, 11,4. Длина сообщения равна 47. Вычисляется число выталкивании зубцов

для первых 47 векторов,Ъорожденных ступенчатой матрицей. Это делается просто, так как первые 17 векторов можно увидеть непосредственно из этой матрицы, а остальные уже найдены выше. Числа выталкивании зубцов равны:

5,	10,	17,	16, 9, 9, 9, 7, 0, 0, 0, 0,				12, 0, 0,		18, 7, 0, 0,		18, 7, 9, 9,	19,	14, 9,	10,
	10, 0,0, 0, 7, 7, 0,			12, 7, 7,		12, 0, 9,	17,	19, 9,9, 5,		12, 0 .
	По формуле у=Ь-а-1 вычисляются числовые коды букв шифртекста:
	3, 2, 20, 4, 17, 21, 20, 21, 12, 6, 11, 6, 6, 18, 13, 17, 21, 11, 2, 21,
	4, 7, 20, 20,			1, 5, 15, 5, 11, 10, 14, 3, 6, 12, 8, 1, 18, 20, 6, 1,12, 3,
	4,20,		15,	0,	21.

Поэтому мы получаем следующий шифртекст:

ОСиЕКУЛУМОЕООЗЫКУЕСУЕНШВЕРРЕКОООМЮЗиОВМОЕиРАУ.

Три появления РЕОРЬЕ в исходном тексте шифруются как ВУЬСУЕ, РЕЬКСЮ и ОЕ11РАУ, тогда как 3 появления ТНЕ шифруются как ОЗИ, ЦВР и СВМ.

Дадим несколько дополнительных замечаний, касающихся машины С- 36. Роторы и клетки соответствуют ступенчатой и кулачковой матрицам. Лю­ бое переопределение ступенчатой матрицы осуществляется активизацией подхо’дящих штифтов в роторах. Аналогично, любое переопределение кулач­ ковой матрицы получается позиционированием зубцов.