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

91

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

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

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

Основные понятия теории автоматов.

Определение. Три конечных множества 1,3,0 и два семейства ото­ бражений (8|)*еь (РОшь 51:8—>3, Р;: 8—> 0,1е 1 называют конечным автоматом

(конечным автоматом Мили) и обозначают через А=(1,8,0,(50,61,(РО|бг)- Полагают, что автомат моделирует работу многих дискретных уст­

ройств, при этом множество I называют входным алфавитом автомата, 8 - множеством состояний, О - выходным алфавитом автомата функции (бО^ь (РОы называют, соответственно, частичными функциями переходов и выхо­ дов автомата. Автомат А функционирует в дискретном времени 1е {1,2,...}. При входной последовательности 3=11,12,..., у е I и начальном состоянии 8=81 €8 автомат вырабатывает последовательность состояний Ам(8,3 )=81,8г,...

(последовательно находится в состояниях 8ь$2,...) и выходную последова­ тельность А(8,3)=у1,у2,.... Правила получения этих последовательностей та­ ковы:

82=6ц81 - образ 81 при отображении 5ц, 8,+1=5у8^ е {1 ,2,...}, У1=Рп8| - образ 81 при отображении Рп, у}=Ру8^ ]е { 1,2,,..},

В случае Р1=Рг для любых 1,Ге1 автомат А называют автоматом Му­

ра.

Автономным конечным автоматом называют двойку конечных мно­ жеств 8,0 и два отображения: 6: 8-»8 и А.:3-»0 и обозначают через

А=(8,0,8,А,). В ряде случаев используют и другое определение: Автомат А=(1,8,0, (8|)|€1, (РОы) называют автономным в случае, когда |1|=1.

Для автомата определяют его граф переходов: совокупность точек на плоскости, обозначенных состояниями автомата, некоторые из которых со­ единены ориентированным ребром (стрелкой —»). На ребре, соединяющем состояние 8 с ставятся две пометки: Ну , где 1 и у определены из соотноше­ ний 818=3', Р|8=у. Переход из состояния в состояние по стрелкам называется

путем, в графе переходов автомата. Путь определяет последовательность со­

/

92

стояний Ам(з,3) и выходную последовательность А(з,3), отвечающую вход­ ной последовательности 3 автомата А и его начальному состоянию 8|=8е$.

Отметим, что задание семейства отображений (61)161, ((РОиО равно­ сильно заданию отображения 6: 1x8—>3, 5(1,8)=б1(8) (аналогично, Р: 1х8-»0 , Р(1,8)=Р1(8)). В связи с чем чаще автомат А определяют тремя множествами 1,8,0 и двумя отображениями 6, Р: А=(1,8,0-, 6, Р).

Обозначим через I* множество всех слов конечной длины в алфавите I. Автомат А с начальным состоянием 8задает отображение (рд,51*—Ю*, именно, для З е 1*

фА>5(3)=А(8,3).

Такие отображения называются конечно-автоматными или просто автомат­ ными.

При фиксированных множествах I, 8, 0 автомат задается отображе­ ниями 6, р. При моделировани функционирования шифратора, или его крип­

тосхемы конечным автоматом начальные состояния автомата моделируют

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

Шифрующий автомат. Понятие шифрующего автомата трактуется

неоднозначно.

Первое определение состоит в том, что шифрующий автомат есть

множество автоматов А(г), геК. с начальными состояниями 8(г)е8(г). Такое

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

Второе определение шифрующего автомата состоит в том, что автомат А=(1,8,0 ,(б1)1б1,(Р1)1б1) является шифрующим автоматом, если его автомат­ ные отображения фА,51*—Ю* , 8е 8 являются инъективными отображениями.

Такое определение согласуется с определением шифра (Х,К,У,Г) в том смысле что в качестве отображений Гх берутся автоматные инъективные отображения.

Для большей общности, иногда второе определение обобщают. Имен­ но, рассматривают автоматы, у которых 1=Гх@, где Г - алфавит внешней

•части ключа, часть ключа: у=у1 ,у2,...уЬ, у)еГ; @ - алфавит открытого текста. При фиксированых частях ключа уеГь и з е 8 требуют инъективность отобра­

жения @ь в О1, то есть при входных различных последовательностях вида

93

3=(а 1 ,у1),(а2,у2),...(аЬ,уЬ) и 3'= (а'1,у1), (а'2,у2),...(а'Ь,уЬ) требуют, чтобы А(8,3)*А(8,3') при любом натуральном Ь,

Выясним условия, при которых автомат А=(1,8,ОД(3) является шиф­ рующим автоматом, то есть автоматные отображения фд>51*—>0 * , з<=3 явля­

ются инъективными отображениями. Для отображения (3:1x8—>0 обозначим через р5отображение I в О: р8(1)=р(1,8). Через 35обозначим множество состоя­ ний автомата А, содержащее 8и все состояния з'е 8, достижимые из 8 в графе переходов автомата А, то есть для которых есть пути из 8 в з . На множестве 88определен подавтомат А8=(1,88,0,8,Р) автомата А (здесь ограничения ото­

бражений 5, Р обозначены теми же буквами). С использованием введенных определений несложно доказывается

УТВЕРЖДЕНИЕ. Автоматное отображение <рА,81*-»0* , з е 8 являет­ ся инъективным тогда и только тогда, если при каждом состоянии 8' из 88

отображение р8инъективно.

В третьем определении под шифрующим автоматом понимают авто­ мат, моделирующий устройство шифрования, либо некоторого его блока. В таком понимании устройство шифрования моделируют автоматом А=(1,8,О,(60;€1,(р|)ы), у которого отображения (бО^ 3 в 8 являются биекциями

8 в 8. Такие автоматы обычно называют перестановочными. Часто гам­

мообразующее устройство шифратора называют шифрующим автоматом.

Эквивалентность ключей шифрующего автомата. Определение. Состояния 8,8' автомата А называются неотличимыми,

если

А(8,3)=А(8',3)

при любом входном слове З е 1*.

Автомат А называется приведенным, если он не имеет различных

неотличимых состояний. I

Ключи 8,8' шифрующего автомата А называются эквивалентны­ ми, если 8,з' - неотличимые состояния автомата А.

Степенью различимости автомата А называется минимальное число К, при котором для любых 8, з' €8 из равенств А(з,3)=А(з',3) для всех З е Iя следуют равенства А (8,3')=А(8',3') для всех 3 ' е 1к‘!

Диаметром автомата А называют минимальное число Р, при котором для любого ее 8 каждое достижимое из 8 в графе перехоов автомата А состоя­ ние 8', 8Фз', достижимо путем длины, не превосходящей Э.

94

Параграф 1.4 Средства защиты информации в переходный пери­

од от древности к современности

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

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

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

По второму пути (уменьшение числа знаков, шифруемых по одной замене) пошли при создании поточных шифров замены.

Шифры многозначной замены (/Про/). Шифр многозначной замены задается таблицей,

А	Б	В	Г	д	Е	Ж	. . .
а1	61	в1	г1	д!	е1	ж1
а2	62	в2				ж2
аЗ

. . .

в которой каждой букве отвечает несколько символов шифртекста. Алфавит шифртекста по смыслу дела больше алфавита открытого текста. Шифроваль­ щик, зашифровывая открытый текст, должен выбрать для каждой буквы одно Из обозначений - например, А зашифровывается в а1, или в а2, и т. д. Данный шифр при грамотном использовании может значительно выровнять диаграм­

95

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

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

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

Блочный шифр «Два квадрата» (/Про/). Блочные шифры, в которых заменялись пары букв, применяли во время второй мировой войны немцы в низовых линиях связи. Они основаны на блочном шифре Плейфейра (у него был один квадрат). При шифровании открытый текст разбивался на блоки по две буквы

КР ИП ТО ГР АФ ИЯ Ключом являлись два квадрата, в которых записывался алфавит в произволь­ ном порядке.

					96
ы	Щ	э	ю	ь	ц	ю	э	ч	ь
м	б	г	д	е	е	м	н	о	ш
в	ж	И	з'	К	ж	л	К	п'	щ
л	с	н	О	п	б	в	а	г	д
а	т	р	У	Ф	Р	3	и	ф	я
X	ц	ч	ш	я	с	т	....Л	X	ы

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

ЖФКЗФБЕРРУЩР

Шифры типа! «Два квадрата» советским криптографам в годы войны удава­ лось дешифровывать, но это требовало значительных усилий и опыта. Преимуществом данных шифров перед кодами были.достаточная простота и быстрота зашифрования и расшифрования, отсутствие потребности в слова­ рях, простота в смене ключевых квадратов. Практически шифр «Два квадра­ та» является забытым шифром англичанина Чарльза Уинстона (1854 г.), кото­ рый назывался «двойным квадратом».

Блочные шифры (Продолжение).

Блочные шифры - это шифры простой замены с большей мощностью алфавита «открытого текста». Обычно к-граммы текста объявляются симво­ лами нового алфавита «открытого текста».

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

97

К

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

формации Ве(Р2)2к делится на два подблока Ь,К.е(Р2)к одинаковой длины, (Ь,К)=В, которые преобразуются по правилу

(Ь,К)-КП, Ь+Р(КД)), где Ке(Р2)к - ключ раунда шифрования, + покомпонентное сложение векто­

ров по модулю 2, а Р - произвольное фиксированное отображение (Р2)2к в (Р2)к. Многие блочные шифры построены на этом принципе и отличаются длиной к блоков, функцией Р, числом раундов шифрования.

Блочный шифр БЕЗ (/Про/).

Блочный шифр БЕЗ (Оа1а Епсгурбоп 51апдай) относится к числу наи­

более популярных. С точностью до перенумерации координат блоков откры­ того и шифрованного текста и ключа алгоритм БЕЗ имеет следующий вид. Открытый текст представляется в виде последовательности бит-нулей и еди­ ниц. В вычислительной машине информация хранится в виде 8-мерных дво­

ичных векторов - байт и поэтому представление их в битовом виде не встре­ чает трудностей. В процессе шифрования открытый текст разбивается на блоки по 64 бит и каждый блок заменяется по простой замене, т. е. если от­ крытый текст имеет вид: 0|,02,....,0(, где 0( - 64-мерные вектора, то шифро­ ванный текст имеет вид: 2 ], 2 2> ...., 2,, где 2, - тоже 64-мерные вектора, яв­

ляющиеся значениями взаимнооднозначной функции от открытого текста при фиксированном ключе к, 2=0^0,). Ключ шифратора БЕЗ - это последова­ тельность из 56 бит.

4 Зак. 5

98

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

Далее строятся блоки (С(1), 0(1)),........, (С(16), 0(16)).

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

С1,С2, ............,С28		Ф.^2, ...... Д28 ,
то заполнение (С(1),0(1))	будет получено сдвигом на 1 влево
Т(С1С2, ............,С28)=(С2, Сз,	,С28С1) ,	.........Д28)= (4г ^ 3 ,........Д28.Ф ) .

Таблица сдвигов является параметром алгоритма и имеет вид

1 ,1 ,2,2,2,2,2,2,1,2,2,2,2,2,2,1 .

Строка ключа К(1) получается из (С(1),0(1)) выбором некоторых 48 коорди­ нат. Таблица выбора задана, она одна и та же для всех итераций. Таким обра-

99

зом, на первом этапе из одного ключа в 56 бита получается 16 ключей К1, К2,..., К16 по 48 бит каждый. Эти ключи помещаются в ключевую таблицу К.

Замена вектора О из 64 битов открытого текста на вектор 2 - 6 4 бита шифро­ ванного текста получается путем более простых замен.

2=Р(К16) Р(К15)...Р(К1) О. Ртображение Р О в 2 удобно описать с помощью блок-схемы.

В схеме присутствуют накопители - фактически регистры, состоящие из ячеек памяти, в них хранятся бинарные вектора. На регистре указана его длина - размерность векторов.

Символом ® обозначим сумматор. На вход сумматора поступает два двоич­ ных вектора, а на выходе получается координатная сумма по модулю 2 этих

векторов. Суммой векторов 010010, 110100 будет вектор 100110.

В схеме ОЕ8 есть три преобразования: Е, 8 и Р. Преобразование Е

расширяет 32-мерный вектор в 48-мерный. Оно задается некоторой таблицей.

4*

Фактически символы из К2 переписываются в КЗ, некоторые из них по 2 раза.

Преобразования 31, 82, ....,38 (так называемые 8-блоки) преобразуют 6- битовые вектора в 4-х битовые вектора. Эти преобразования заданы 8 табли­ цами. В каждой таблице для всех 6-мерных 64 векторов указаны их образы 4- мерные вектора - их образы при преобразовании 8 блока.

Обращаем внимание, что преобразование 8 не просто перестановка и

выборка координат, а достаточно произвольная замена. Так в 81 вектор 0=(0,0,0,0,0,0) переходит в вектор 14=(1, 1, 1 , 0), вектор 1=(0, 0, 0, 0, 0, 1) в

вектор 4=(0, 1,0,0), а 2=(0, 0, 0, 0, 1, 0) в 13=(1,0, 1, 1). То есть отображение 8 - нелинейное.

Преобразование Р - это обычная перестановка координат 32-мерного вектора. Оно тоже задано таблицей.

Таким образом, преобразование Р(Кл) функционирует следующим об­ разом. Из накопителя К2 снимается заполнение, оно проходит через преобра­ зование Е, полученный в КЗ 48-мерный вектор суммируется с Ю. Результат записывается в К4. Заполнение К4 проходит через преобразования 8 блоков,

перестановку Р, складывается с содержимым накопителя К1. Окончательный результат преобразований записывается в К2, а предыдущее заполнение К2 выталкивается в первый регистр К1.

Далее процедура повторяется 16 раз, но каждый раз на вход поступает новая ключевая последовательность.

Зашифрование блока 0=(01,02) открытого текста можно описать уравнениями шифрования

2=(21,22)=(Н17,Н.б),

Н,+1=Н,.1 ® Р(К() Н(, Н0=О1, Нг=02.

Процедура расшифрования описывается уравнениямй 0 = (0 1,02)=(Н0,Н,), Н,.1=Н,+1еР(Ю )Н(, Нп=21, Н16=22.

Более удачное и подробное описание шифратора ЭЕ8 можно найти в книге

Ю.В. Романца, П.А. Тимофеева, В.Ф. Шаньгина «Защита информации в ком­ пьютерных системах и сетях. «Радио и связь», М., 1999 г.

Блочный шифр ГОСТ 28147 89 (/Про/). Российский аналог американско­ го стандарта шифрования БЕ8 - блочный шифр ГОСТ 2814789 имеет похо­

жую блок-схему