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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приведем пример второго исторического шифра - шифра перестановки. Выберем целое положительное число, скажем, 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 и порядок расположения чисел в нижнем ряду двухстрочной записи.

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

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

Открытый текст выписывается в прямоугольную таблицу из п строк и m столбцов. Предполагается, что длина текста t < n-m (в противном случае оставшийся участок текста шифруется отдельно по тому же шифру). Если t строго меньше n-m , то оставшиеся пустые клетки заполняются произвольным набором букв алфавита. Шифртекст выписывается по этой таблице по заранее оговоренному «маршруту» - пути, проходящему по одному разу через все клетки таблицы. Ключом шифра являются числа n, m и указанный маршрут.

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

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

ДИСК Энея

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

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

Гектор, Эней! На вас, воеводы, лежит наипаче

Бремя забот о народе троянском; отличны вы оба

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

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

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

Первое из них - так называемый «диск Энея». Его принцип был прост.

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

ЛИНЕЙКА Энея

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

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

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

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

КНИЖНЫЙ шифр

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

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

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

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

	А	В	С	D	Е
А	А	в	с	D	Е
В	F	G	н	I	К
С	L	м	N	О	Р
D	Q	R	S	Т	U
Е	V	W	X	Y	Z

Шифруемая буква заменялась на координаты квадрата, в котором она записана. Так, В заменялась на АВ, F на ВА, R на DB и т. д. При расшифровании каждая такая пара определяла соответствующую букву сообщения. Заметим, что секретом в данном случае является сам способ замены букв. Ключ в этой системе отсутствует, поскольку используется фиксированный алфавитный порядок следования букв.

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

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

Т Н	Е	А	В
L С	D	F	G
I К	М	N	0
Р Q	R	S	и
V W	X	Y	Z

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

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

	1	2	3	4	5
1	Е	К	Т	L	В
2	Н	У	А	D	и
3	М	S	G	С	V
4	F	Р	Q	R	W
5	О	Y	X	Z	N

Зашифруем по нему слово «THE APPLE». Получим шифрованный текст:

13.21.11.23.42.42.14.11. (*)

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

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

1321112342421411 (**)

Полученная последовательность цифр сдвигается циклически влево на один шаг:

3211123424214111

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

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

SEKCDHFE (***)

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

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

Если же в тексте (***) будет искажена четвертая буква (буква С заменена, например, на К), то в расшифрованном тексте будет уже два искажения: THE HIPLE, что уже затрудняет восстановление исходного сообщения. Аналогично обстоит дело с ошибками вида «пропуск букв». Пусть в тексте (***) пропущена буква С. Шифртекст примет вид: SEKDHFE, или

32.11.12.24.21.41.11.

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

ШИФР Чейза

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

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

	1	2	3	4	5	6	7	8	9	0
1	X	и	А	С	0	N	Z	L	Р	ф
2	в	Y	F	м	@	Е	G	J	Q	со
3	D	К	S	V	н	R	W	Т	I	>ь

Ключом шифра является порядок расположения букв в таблице. При шифровании координаты букв выписываются вертикально. Например, слово PHILIP приобретает вид:

133131

959899

Чейз предложил ввести еще один ключ: заранее оговоренное правило преобразования нижнего ряда цифр. Например, число, определяемое этим рядом, умножается на 9:

959899x9=8639091

получаем новую двухстрочную запись:

1	3	3	1	3 1
6	3	9	0	9 1

Эта двухстрочная запись вновь переводится в буквы согласно таблице; при этом первое число (8) нижнего ряда определяет букву первой строки. Шифртекст приобретает следующий вид:

LN Slip IX (**)

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

При расшифровании полученная последовательность (**) переводится в двухстрочную запись:

(1) 1	3	3	1	3 1
8 6	3	9	0	9 1

Нижний ряд делится на 9:

8639091:9 = 959899,

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

Однако предложение Чейза не нашло поддержки. Причины: заметное усложнение процесса шифрования - расшифрования, а также особая чувствительность шифра к ошибкам (искажениям в шифртексте). В этом читатель сможет убедиться самостоятельно. Кроме того, использование в качестве ключа любого числа (кроме 9) может порождать недоразумения как при шифровании, так и при расшифровании.

ТЮРЕМНЫЙ шифр

Интересно отметить, что в несколько изменённом виде шифр Полибия дошёл до наших дней и получил своеобразное название «тюремный шифр». Для его использования нужно только знать естественный порядок расположения букв алфавита (как в указанном выше примере квадрата Полибия для английского языка). Стороны квадрата обозначаются не буквами (ABCDE), а числами (12345). Число 3, например, передаётся путём тройного стука. При передаче буквы сначала «отстукивается» число, соответствующее строке, в которой находится буква, а затем номер соответствующего столбца. Например, буква «F» передаётся двойным стуком (вторая строка) и затем одинарным (первый столбец).

С применением этого шифра связаны некоторые исторические казусы. Так, декабристы, посаженные в тюрьму после неудавшегося восстания, не смогли установить связь с находившимся в «одиночке» князем Одоевским. Оказалось, что князь (хорошо образованный по тем временам человек) не помнил естественного порядка расположения букв в русском и французском алфавитах (другими языками он не владел). Декабристы для русского алфавита использовали прямоугольник размера 5x6 (5 строк и 6 столбцов) и редуцированный до 30 букв алфавит.

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

МАГИЧЕСКИЕ квадраты

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

В квадрат размером 4 на 4 (размеры могли быть и другими) вписывались числа от 1 до 16. Его магия состояла в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному и тому же числу - 34.

Впервые эти квадраты появились в Китае, где им и была приписана некоторая «магическая сила». Приведем пример:

16	3	2	13
5	10	11	8
9	6	7	12
4	15	14	1

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

16У	3И	2Р	13Д
53	10Е	11Г	8Ю
9С	6Ж	7А	12О
4Е	15Я	14Н	1П

После этого шифрованный текст записывается в строку: УИРДЗЕГЮСЖАОЕЯНП

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

ИСТОРИЧЕСКИЕ КНИГИ по криптографии

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

В 1412 году Шехаб аль Кашканди написал 14-ти томную энциклопедию «Шауба аль Аша». В этой работе имеется раздел о криптографии «Относительно сокрытия в буквах тайных сообщений». В нем дано систематическое описание различных шифров замены и перестановки. Здесь же приводится и криптоанализ этих шифров на основе подсчета частотности букв в арабском языке по тексту Корана; развиваются методы дешифрования, базирующиеся на разночастотности букв. В работе Кашканди предлагается семь систем шифрования (повторяющих неопубликованные идеи его предшественника Ибн ад-Дурахийма):

- одна буква может заменять другую;

- можно писать слово в обратном порядке, например, слово «Мухаммед» (МХМД - в арабском алфавите, состоящем из согласных) примет вид ДМХМ;

- можно переставлять в обратном порядке чередующиеся буквы слов;

- заменять буквы на цифры в соответствии с принятой заменой арабских букв на числа. Тогда слово «Мухаммед» превращается в 40+8+40+4 (М=40, Х=8, Д=4). При этом криптограмма выглядит как перечень каких-то цифр;

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

- можно заменять каждую букву именем какого-либо человека;

- при шифровании можно использовать словарь замены, описывающий положения луны, названия стран (в определенном порядке), названия фруктов, деревьев и т. д.

В этой же книге Кашканди пишет о частотном методе дешифрования шифра простой замены: «Если вы хотите разгадать сообщение, которое вы получили в зашифрованном виде, то прежде всего начинайте подсчет букв, а затем сосчитайте, сколько раз повторяется каждый знак, и подведите итог в каждом отдельном случае...».

Арабы первыми обратили внимание на возможность использования стандартных слов и выражений для дешифрования. Так, первый широко известный среди арабов филолог восьмого века Абу аль-Ахмади, дешифровав криптограмму на греческом языке, которую переслал ему византийский император с просьбой о дешифровании, так объяснил свой метод: «Я сказал себе, что письмо должно начинаться со слов «Во имя Бога» или как-нибудь в этом роде. Итак, я составил на основе этого первые буквы, и все оказалось правильным». На основе открытого им метода дешифрования он написал книгу «Китаб аль-Маумма» («Книга тайного языка»).

Однако в последующем столетии криптография у арабов деградировала. В 1600 году марокканский султан Ахмед аль-Мансур направил английской королеве Елизавете посла с целью заключения союза против Испании. Посол отправил султану зашифрованную депешу, которая попала в руки к арабам. Ее дешифрование длилось 15 лет, и в связи с успешным завершением работы арабы воздали хвалу Аллаху. Ибн ад-Дурахийм решил бы эту загадку за несколько часов.

Выдающийся арабский ученый и философ XI-XII веков, поэт Омар Хайям в своих произведениях нередко обращался к тайнописи. Вот одно из его произведений («Рубай»):

Все что видишь ты, - видимость только одна, Только форма - а суть никому не видна. Смысл этих картинок понять не пытайся -Сядь спокойно в сторонке и выпей вина!

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

В XIV-XV веках клерк тайной канцелярии папской курии Чикко Симо-нетти написал книгу о тайнописи. В ней он изложил усовершенствованные шифры замены, в том числе и шифр многозначной замены, в котором одной и той же букве (гласной) соответствует несколько шифробозначений. Симонет-ти обслуживал герцогов Сфорца, олигархов Милана, дешифруя для них перехваченные депеши. Он разработал 13 правил дешифрования шифров простой замены, которые изложил в рукописи на трех кусках пергамента.

Секретарь антипапы Клементия VII Габриель де Лавинда в XV веке написал «Трактат о шифрах» (первый европейский учебник по криптографии), в котором изложил метод дешифрования шифров замены, основанный на подсчете частот букв, и описал шифры пропорциональной замены. В последнем шифре буквам алфавита ставилось в соответствие несколько шифробозначе-ний, причем их количество было пропорционально частоте появления буквы в текстах итальянского языка.

Наиболее крупного успеха в развитии криптографии в то время достиг Леон Альберти, человек универсального таланта, архитектор и математик. В 1466 году он представил в папскую канцелярию трактат о шифрах, написанный по заказу папы римского, в котором провел анализ частот букв, исследовал шифры замены и перестановки, затронул вопросы стойкости шифров. Замеченная Альберти разночастотность появления букв в осмысленных текстах дала толчок изучению синтаксических свойств письменных сообщений. При этом основное внимание обращалось на наиболее часто встречающиеся буквы. В русском языке первые десять наиболее частых букв породили несколько неудобное для чтения слово «сеновалитр» (внутри этого слова частотные «приоритеты» букв не соблюдаются). В английском языке из частых букв составлена фраза «a sin to err» («грех ошибаться») В итальянском языке среди наиболее частых букв встречаются в подавляющем большинстве гласные буквы. Не в этом ли секрет «певучести» итальянского языка?

Полное же упорядочение букв литературного русского языка в порядке убывания частот их появления в текстах имеет следующий вид:

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

ЧЕРНЫЕ кабинеты. РОЛЬ КРИПТОГРАФИИ

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

XVII-XVIII века вошли в историю криптографии как эра «черных кабинетов» - специальных государственных органов по перехвату, перлюстрации и дешифрованию переписки (в первую очередь, дипломатической).

В штат «черных кабинетов» входили криптографы - дешифровалыцики,

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

Представляет интерес следующая созвучная оценка роли криптографии, высказывавшаяся уже в XX веке. Известный американский исследователь в,области истории спецслужб, Флетчер Прат, в книге «Секретно и срочно» утверждает: «Престолы, королевства и битвы выигрывались или проигрывались в зависимости от знания тайнописи». Здесь безусловно присутствует элемент преувеличения роли криптографии в развитии исторических событий, но фактом является то, что криптография играла и сейчас играет заметную роль в принятии государственных решений в области политики, дипломатии, воен-f..-,;-ного дела и т. д. У Прата нашлись сторонники. Крупнейший исследователь истории криптографии Д. Кан (США), иллюстрируя влияние криптографии на развитие политических событий в мире, утверждает: «В самом деле, не будет большим преувеличением заявить, что образование коммунистической державы, а это является, пожалуй, самым главным событием современной истории, стало возможным в значительной степени в результате дешифрования секретной переписки царской России». При этом имеются в виду успехи немецких дешифровалыциков. Германия была заинтересована в развале России как главного противника в войне. Один из реальных путей достижения этой цели заключался в поддержке российских революционеров. Поэтому результаты дешифровальной работы использовались для поддержки российских противников царского режима. Что же касается успехов немецких дешифровалыциков, то министр иностранных дел Германии времен I Мировой войны Циммерман вспоминал: «В те немногие мгновения дешифровалыцики держали историю в своих руках». В наше время Д. Кан утверждает: «Криптография является наиболее важной формой разведки в современном мире. Она дает ,,.'. намного больше и намного более достоверной информации, чем шпионаж ...»

Криптоанализ

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

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

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

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

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

Атака c известным открытым текстом

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

Атака выборочного открытого текста

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

Атака адаптивно-выбранного открытого текста

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

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

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

Дешифровальщик может выбирать различные символы текста для дешифрования и имеет доступ к расшифрованному открытому тексту. Задача состоит в выводе шифра. Эта атака, прежде всего, применима к обще-ключевым алгоритмам. Атака выбранного зашифрованного текста в некоторых случаях эффективна против симметричного алгоритма. (Атака выбранного открытого текста и атака выбранного зашифрованного текста вместе называются атака выбранного текста)

Атака выборного шифра

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

Метод "резиновой дубинки"

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

Дешифрование шифра простои замены.

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

1) В осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, при этом относительные частоты букв в различных текстах одного языка близки между собой. То же самое можно сказать и о частотах пар, троек букв открытого текста;

2) Любой естественный язык обладает так называемой избыточностью, что позволяет с большой вероятностью «угадывать» смысл сообщения, даже если часть букв в сообщении не известна.

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

1	а - 0,062	12	л - 0,035	23	ц - 0,004
2	6-0,014	13	м- 0,026	24	ч- 0,012
3	в - 0,038	14	н - 0,053	25	ш - 0,006
4	г -0,013	15	о - 0,090	26	щ - 0,003
5	д - 0,025	16	п - 0,023	27	ы- 0,016
6	е,ё - 0,072	17	р - 0,040	28	ъ,ь- 0,014
7	ж - 0,077	18	с - 0,045	29	э - 0,003
8	3-0,016	19	т - 0,Q53	30	ю - 0,006
9	и - 0,062	20	у -0,021	31	я -0,018
10	и -0,010	21	ф - 0,002	32	- 0,175
11	к - 0,28	22	х - 0,009

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

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

О,Е,А,И,Н,Т,С,Р,В,Л,К,М,Д,П,У,Я,3,Ы,Б,Ь,Г,Ч,Й,Х,Ж,Ю,Ш,Ц,Щ,Э,Ф.

Как запомнить первые 10 наиболее частых букв? Помните, как запоминают основные цвета в физике? Надо запомнить фразу Каждый охотник желает знать, где живет фазан. Первые буквы слов фразы указывают на основные цвета. В криптографии надо запомнить слово СЕНОВАЛИТР - в нем все 10 наиболее частых букв.

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

Английский язык	е- 12,75	t-9,25	г -8,50	i - 7,75	h - 7,75	о - 7,50
Французский язык	е- 17,75	а - 8,25	s-8,25	i - 7,25	n - 7,25	r-7,25
Немецкий язык	е- 18,50	п - 1 1.,50	i - 8,00	г - 7,50	s - 7,00	a - 5,00
Арабский язык	а -17,75
Греческий язык	а -14,25
Японский язык	р- 15,75
Латинский язык	а -11,00
Малайский язык	а -20,25
Санскрит	а -31,25

Частоты знаков алфавита зависят не только от языка, но и от характера текста. Так в тексте по криптографии будет повышена вероятность букв Ф, Ш (из-за часто встречающихся слов «шифр», «криптография»). В математическом тексте скорее всего будет завышена частота буквы Ф (из-за слов «функция», «функционал» и т. п.).

В стандартных текстовых файлах наиболее частым был символ «пробел», в ехе-файлах наиболее часто встречается символ 0, в текстах, написанных в текстовом процессоре ChiWriter, удобном для оформления математических текстов, на первое место вышел символ "\" - backslash .

Частотная диаграмма является устойчивой характеристикой текста. Из теории вероятностей следует, что при достаточно слабых ограничениях на вероятностные свойства случайного процесса справедлив закон больших чисел, т. е. относительные частоты у знаков сходятся по вероятности к значениям их вероятностей P_k:

.

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

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

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

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

Аналогичная картина наблюдается и для пар соседних букв (биграмм) открытого текста (наиболее частая биграмма русского открытого текста - СТ). Однако для получения устойчивой картины длина последовательности должна быть существенно больше. На сравнительно небольших отрезках открытого текста эта картина как-то смазана. Более устойчивой характеристикой биграмм является отсутствие в осмысленном тексте некоторых биграмм, как говорят, наличие запретных биграмм, имеющих вероятность, равную практически 0.

Видели ли Вы когда-нибудь в открытом тексте биграммы ЪЬ, «гласная» Ь, «пробел» Ь? Знание и использование указанных особенностей открытого текста значительно облегчает дешифрование шифра перестановки и замены.

Дешифрование шифра простой замены! Рассмотрим пример дешифрования шифра простой замены (Учебное пособие «Принципы и методы защиты информации», Проскурин Г.В.). Пусть у нас имеется следующий шифртекст.

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

Работу следует начать с подсчета частот символов в шифрованном тексте.

После того как проведен подсчет, упорядочим символы по убыванию частот.

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

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

При достаточно большой длине шифртекста, для того чтобы из шифрованного текста получить открытый, достаточно заменить bt на О, Ь2 на Е, Ь3 на А и т. д.

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

Что нам остается - угадывать замену. При этом мы должны все-таки учитывать статистические особенности открытого текста. В шифртексте через пробел скорее всего обозначается пробел, через букву О скорее всего обозначена О или А, через Е - О, Е, А, через А - Е, А или И и т.д.

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

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

Таблица не приводится из-за своей громоздкости, она приведена в Приложении 3.

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

В колонках наиболее вероятных замен буквы, отвечающие правильным обратным заменам, должны быть обозначены как заглавные. Прочитавоткрытый текст, Вы убедитесь, что он представляет собой несколько предложений из книги Дориченко С.А. и Ященко В.В. «25 этюдов о шифрах»,М.,1994.

Для дешифрования в автоматизированном режиме прежде всего надо завести в память компьютера словарь русского языка.

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

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

Blog

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

Содержание