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

11

ГЛАВА 1. ИСТОРИЧЕСКИЙ ОЧЕРК РАЗВИТИЯ КРИПТОГРАФИЧЕСКИХ СРЕДСТВ И МЕТОДОВ ЗА­ ЩИТЫ ИНФОРМАЦИИ

Д. Канн: «... История криптографии ... - это история человечества».

Понятие «безопасность»охватывает широкий круг интересов как отдельных лиц, так и целых государств. Во все исторические времена существенное внимание уделя­ лось проблеме информационной безопасности, обеспечению защиты конфиденциаль­ ной информации от ознакомления с ней конкурирующих групп. Недаром великий психолог Вильям Шекспир в «Короле Лире» изрёк: «Чтоб мысль врага узнать, сердца вскрывают, а не то что письма».

Параграф 1.1 Криптографические средства с древнего времени

Существовали три основных способа защиты информации.

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

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

Идея экзотической защиты секретных текстов (в том числе и с применени­ ем симпатических чернил) дошла до наших дней. А. Толстой в известном произведении «Гиперболодд инженера Гарина» описал способ передачи со­ общения путем его записи на спине посыльного - мальчика. Во время П Ми­

12

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

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

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

1

ШИФР Гая Юлия Цезаря

\

Вкриптографии древних времен использовались два вида шифров: замена

иперестановка.

Историческим примером шифра замены является шифр Цезаря (I век до н. э.), описанный историком Древнего Рима Светонием. Гай Юлий Цезарь ис­ пользовал в своей переписке шифр собственного изобретения. Применитель­ но к современному русскому языку он состоял в следующем. Выписывался алфавит: А, Б, В, Г, Д, Е ,...; затем под ним выписывался тот же алфавит, но с циклическим сдвигом на 3 буквы влево:

А Б В Г Д Е Ё З К ^ И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ъ Ь Э Ю Я Г Д Е Ё Ж З И Й К Л МНОП Р С Т У Ф X Ц ЧШ Щ ЫЪ Ь Э Ю Я А Б В

При зашифровании буква А заменялась буквой Г, Б заменялась на Д, В - Е и так далее. Так, напри­ мер, слово «РИМ» превращалось в слово «УЛП».

Получатель сообщения «УЛП» искал эти буквы в нижней строке и по буквам над ними восстанавливал исходное слово «РИМ». Ключом в шифре Цезаря является величина сдвига 2-й нижней строки алфавита. Преемник Юлия Цезаря - Цезарь Август использовал тот же шифр, но с ключом - сдвиг 1. Слово «РИМ» он в этом случае зашифровал бы в буквосочетание «СЙН»

Гай Юлий Цезарь

13

Естественное развитие шифра Цезаря очевидно: нижняя строка двух­ строчной записи букв алфавита может быть с произвольным расположением этих букв. Если в алфавитном расположении букв в нижней строке существует'всего 33 варианта ключей (число букв в русском алфавите), то при их про­ извольном расположении число ключей становится огромным. Оно равно 33! (33 факториал), т.е. приблизительно десять в тридцать пятой степени. Этот момент очень важен. Если противник догадался или получил сведе­ ния об используемом шифре (а шифры используются длительное время), то он может попробовать перебрать все варианты возможных секретных ключей при дешифровании перехваченной криптограммы. В современных условиях такой перебор в шифре Цезаря доступен ученику 5-6 классов средней школы. Но перебор 33! вариантов ключей занял бы даже при ис­ пользовании современных ЭВМ столетия. Едва ли найдется дешифро­ вальщик, который даже в наши дни выбрал бы этот путь дешифрования. Однако во времена Цезаря, когда царила всеобщая неграмотность населе­ ния, сама возможность увидеть осмысленное сообщение за «абракадаб­ рой», даже составленной из знакомых букв, казалась неосуществимой.

Во всяком случае, древнеримский историк Светоний не приводит фактов дешифрования переписки Цезаря. Напомним, что сам Цезарь всю жизнь ис­

пользовал один и тот же ключ (сдвиг - 3). Этим шифром он пользовался, в частности, для обмена посланиями с Цицероном.

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

14

Фрагмент шифрованного послания имел следующий вид:

Соответствующий открытый текст: «Гш Ьеге АЬе 51апеу» («Я здесь Аб Слени»), Использован шифр простой замены букв на фигурки людей; флажок в руках означает конец слова.

ШИФР перестановки

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

1	2	3	4	5
3	2	5	1	4

Эта конструкция носит название подстановки, а число 5 называется ее степенью.

Зашифруем фразу «СВЯЩЕННАЯ РИМСКАЯ ИМПЕРИЯ». В этой фразе 23 буквы. Дополним её двумя произвольными буквами (например, Ь, Э) до ближайшего числа, кратного 5, то есть 25. Выпишем эту дополненную фразу без пропусков, одновременно разбив её на пятизначные группы:

СВЯЩЕ ННАЯР ИМСКА ЯИМПЕ РИЯЬЭ Буквы каждой группы переставим в соответствии с указанной двухётроч-

ной записью по следующему правилу: первая буква встаёт на третье место, вторая - на второе, третья - на пятое, четвёртая - на первое и пятая - на чет­ вёртое. Полученный текст выписывается без пропусков:

ЩВСЕЯЯННРАКМИАСПИЯЕМЬИРЭЯ При расшифровании текст разбивается на группы по 5 букв и буквы пере­

ставляются в обратном порядке: 1 на 4 место, 2 на 2, 3 на 1,4 на 5 и 5 на 3. Ключом шифра является выбранное число 5 и порядок расположения чисел в нижнем ряду двухстрочной записи.

Прибор Сцитала.

Упрощенное современное изобрете­ ние

15

ПРИБОР Сцитала

Одним из первых физических приборов, реализующих шифр перестанов­ ки, является так называемый прибор Сцитала. Он был изобретён в древней «варварской» Спарте во времена Ликурга (V в. до н. э.). Рим быстро восполь­ зовался этим прибором. Для зашифрования текста использовался цилиндр за­ ранее обусловленного диаметра. На цилиндр наматывался тонкий ремень из пергамента, и текст выписывался построчно по образующей цилиндра (вдоль его оси). Затем ремень сматывался и отправлялся получателю сообщения. По­ следний наматывал его на цилиндр того же диаметра и читал текст по оси ци­ линдра. В этом примере ключом шифра являлся диаметр цилиндра и его дли­ на, которые, по существу, порождают двухстрочную запись, аналогичную указанной выше.

Шифр «Сцитала» реализует один из вариантов так называемого сегодня «шифра маршрутной перестановки». Смысл этого шифра заключается в сле­ дующем.

Открытый текст выписывается в прямоугольную таблицу из п строк и т столбцов. Предполагается, что длина текста 1: < п т (в противном случае ос­ тавшийся участок текста шифруется отдельно по тому же шифру). Если X строго меньше п-ш , то оставшиеся пустые клетки заполняются произвольным набором букв алфавита. Шифртекст выписывается по этой таблице по заранее

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

Втакой трактовке шифр «Сцитала» приобретает следующий вид. Пусть

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

16

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

Были и другие способы защиты информации, разработанные в античные времена.

ДИСК Энея

Одно из первых исторических имен, которое упоминается в связи с криптографией, это имя Энея - легендарного полководца, защитника Трои, друга богатыря Гектора. Гомер в «Илиаде» (VIII век до н. э.) указывает, что Эней был сыном богини Афродиты и смертного человека. В битве под Троей Эней был тяжело ранен, и мать, спасая сына, также получила ранение. Пови­ нуясь долгу чести, Эней вступил в поединок с Геркулесом (Гераклом), хотя . отлично понимал безнадежность этого поединка для себя. На этот раз его спас от смерти союзник троянцев морской бог Посейдон.

Гомер дает следующую характеристику Гектору и Энею:

Гектор, Эней! На вас, воеводы, лежит наипаче Бремя забот о народе троянском; отличны вы оба

В каждом намерении вашем, сражаться ли нужно, иль мыслить.

Согласно преданиям, Эней был посвящен в древнегреческую Мистерию. При посвящении он спускался в ад; гарпии предсказали ему падение Трои.

В области тайнописи Энею принадлежат два изобретения.

Первое из них - так называемый «диск Энея». Его принцип был прос^. На диске диаметром 10-15 см и толщиной 1-2 см высверливались отвер­

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

17

ЛИНЕИКА Энея

Идея Энея была использована в создании и других оригинальных шифров замены. Например, в одном из вариантов вместо диска использовалась линейка с числом отверстий, равных количеству букв алфавита. Каждое отверстие обозначалось своей буквой; буквы по отверстиям располагались в произвольном порядке. К линейке была прикреплена катушка с намотанной на неё ниткой. Рядом с катушкой имелась прорезь. При шифровании нить протягивалась через прорезь, а затем через отверстие, соответствующее первой букве шифруемого текста, при этом на нити завязывщюя узелок в месте прохождения ее через отверстие; затем нить возвращалась в прорезь и аналогично зашифровывалась вторая буква текста

Инициация в Мистерию. Эней в аду

ит. д.

После окончания шифрования нить извлекалась и передавалась по­ лучателю сообщения. Тот, имея идентичную линейку, протягивал нить через прорези отверстий, опре­ деляемых узлами, и восстанавливал исходный текст по буквам отверстий. Это устройство получило название «линейка Энея». Шифр, реализуемый линейкой Энея, является одним из примеров шифра замены: в нем бук­ вы заменяются на расстояния между узелками н& нитке. Ключом шифра являлся порядок расположения букв по отверстиям в линейке. Посторон­ ний, получивший нить (даже имея линейку, но без нанесённых букв), не сможет прочитать передаваемое со­

общение. Жрица мистерий

18

УЗЕЛКОВОЕ письмо

Аналогичное «линейке Энея» так называемое «узелковое письмо» («ки­ пу») получило распространение у индейцев Центральной Америки. Свои со­ общения они также передавали в виде нитки, на которой завязывались разно­ цветные узелки, определявшие содержание сообщения.

КНИЖНЫЙ шифр

Заметным вкладом Энея в криптографию является предложенный им так называемый книжный шифр, описанный в сочинении «Об обороне укреплён- ' ных мест». Эней предложил прокалывать малозаметные дырки в книге или в другом документе над буквами секретного сообщения. Интересно отметить, что в первой мировой войне германские шпионы использовали аналогичный шифр, заменив дырки на точки, наносимые симпатическими чердилами на буквы газетного текста.

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

КВАДРАТ Полибия

Ещё одно изобретение древних греков - так называемый квадрат Поли­ бия, (Полибий - греческий государственный деятель, полководец, историк, III век до н. э.). Применительно к современному латинскому алфавиту из 26 букв шифрование по этому квадрату заключалось в следующем. В квадрат разме­ ром 5x5 клеток выписываются все буквы алфавита, при этом буквы I, .1 не различаются (I отождествляется с буквой I):

	А	. В	с	Б	Е
А	А	В	с	О	Е
в.	Р	С	н	I	К
с	Ь	М	N	О	Р
ц	<3	Я	8	Т	И

ЕV \У X V 2

Шифруемая буква заменялась на координаты квадрата, в котором она за­ писана. Так, В заменялась на АВ, Р на ВА, В на БВ и т. д. При расшифрова­

19

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

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

Здесь, однако, появилось и некоторое неудобство. Произвольный порядок букв трудно запомнить, поэтому пользователю шифра было необходимо по­ стоянно иметь при себе ключ - квадрат. Появилась опасность тайного озна­ комления с ключом посторонних лиц. В качестве компромиссного решения был предложен ключ - пароль. Легко запоминаемый пароль выписывался без повторов букв в квадрат; в оставшиеся клетки в алфавитном порядке выписы­ вались буквы алфавита, отсутствующие в пароле. Например, пусть паролем является слово «ТНЕ ТАВЬЕ». Тогда квадрат имеет следующий вид:

Т	Н	Е	А	В
В	С	В Т		о
I	К	М	N	О
Р	<}	К	3	В
V	XV	X	У	2

Такой квадрат уже не нужно иметь при себе. Достаточно запомнить ключ - пароль. Заметим кстати, что таким же образом можно запомнить поря­ док расположения букв при использовании «линейки Энея», а также шифра обобщенной замены Ю. Цезаря (при произвольном расположении букв в нижней строке). Интересное усиление шифра Полибия было предложено од­ ним криптографом-любителем уже в XIX веке. Смысл этого усложнения по­ ясним на примере.

Пусть имеется следующий квадрат Полибия:

	1	2		3	4	5
1	Е /	К		т	Ь	В
2	Н	1	/	А	В	в
3	м	8		О	с	V
4	р	Р		С!	к.	XV
5	О	У		X	ъ	N

Зашифруем по нему слово «ТНЕ АРРЬЕ». Получим шифрованный

текст:

_________________________13.21.11.23.42.42.14.11. (*)

20

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

Усложненный вариант заключается в следующем. Полученный первичный шифртекст (*) шифруется вторично. При этом он выписывается без разбие­ ния на пары:

1321112342421411 (**) Полученная последовательность цифр сдвигается циклически влево на

один шаг:

3211123424214111 Эта последовательность вновь разбивается в группы по два:

\32Л1.12.34.24.21.41.11.

ипо таблице заменяется на окончательный шифртекст:

ЗЕКСОНРЕ (***) Количество ключей в этом шифре остается тем же (25!), но он уже значи­

тельно более стоек. Заметим, что этот шифр уже не является шифром простой замены (буква Е открытого текста переходит в различные буквы: К, Е; буква Р - в буквы Б, Н).

Был подмечен и негативный момент. Если в шифре простой замены шиф­ ртекст будет написан с одной ошибкой (например, в тексте (*) вместо четвер­ той буквы 23 будет написано 32), то расшифрованный текст будет содержать лишь одну ошибку: ТНЕ ЗРРЬЕ, что легко исправляется получателем сооб­ щения.

Если же в тексте (***) будет искажена четвертая буква (буква С заменена, например, на К), то в расшифрованном тексте будет уже два искажения: ТНЕ Н1РЬЕ, что уже затрудняет восстановление исходного сообщения. Аналогич­ но обстоит дело с ошибками вида «пропуск букв». Пусть в тексте (***) про­ пущена буква С. Шифртекст примет вид: ЗЕКЛЭНРЕ, или

32.11.12.24.21.41.11.

После расшифрований получим: ТНЕ 1РЬЕ, то есть наряду с пропуском буквы в расшифрованном тексте имеется и искажение другой буквы. При пропуске в (***) первой буквы при расшифровании получим: ЕЕ АРРЬЕ.

ШИФР Чейза

В середине XIX века американец П. Э. Чейз предложил следующую мо­ дификацию шифра Полибия.

Выписывается прямоугольник размера 3x10; буквы латинского алфавита дополняются знаком @ и греческими буквами X, (о <р:

4