Первая страница / Теория / Кодирование / Криптография /

Исторический очерк

История криптографии насчитывает не одно тысячелетие. Уже в исторических документах Египта и Месопотамии имеются сведения о системах и способах составления шифрованного письма. Мы расcкажем о некоторых наиболее известных древних шифрах.

Атбаш

Некоторые фрагменты библейских текстов зашифрованы с помощью шифра, который назывался атбаш. Правило зашифрования состояло в замене i-й буквы алфавита буквой с номером n − i + 1, где n — число букв в алфавите. Происхождение слова атбаш объясняется принципом замены букв. Это слово составлено из букв Алеф, Тае, Бет, Шит, то есть первой и последней, второй и предпоследней букв древнесемитского алфавита.

Сцитала

Упрощение письма стимулировало развитие криптографии. В Древней Греции криптография уже широко использовалась в разных областях деятельности, в особенности в государственной сфере. В Спарте в V–IV веках до н. э. использовалось одно из первых шифровальных приспособлений — Сцитала. Это был жезл цилиндрической формы, на который наматываласть полоска пергамента. Вдоль оси цилиндра на пергамент построчно записывался текст, после этого лента сматывалась с жезла и передавалась адресату, который имел точно такую же Сциталу. Такой способ шифрования осуществлял перестановку букв в сообщении, ключом к которому служил диаметр Сциталы. Метод вскрытия этого шифра приписывается Аристотелю. Он предложил заточить конусом длинный брус и, обернув вокруг него ленту, начать сдвигать ее по конусу от малого диаметра до самого большого. В том месте, где диаметр конуса совпадал с диаметром Сциталы буквы складывались в слоги и слова. После этого оставалось только изготовить жезл нужного диаметра.

Табличка Энея

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

Квадрат Полибия

Квадрат полибия
 12345
1ABCDE
2FGHI,JK
3LMNOP
4QRSTU
5VWXYZ

Греческий писатель Полибий использовал систему сигнализации, которая была широко принята как метод шифрования. Он записывал буквы алфавита в квадратную таблицу и заменял их координатами: парами чисел (ij), где i — номер строки, j — номер столбца. Применительно к латинскому алфавиту квадрат Полибия имеет следующий вид.

Пары (ij) передавались с помощью факелов. Например, для передачи буквы О нужно было взять 3 факела в правую руку и 4 факела — в левую.

Шифровальный диск

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

Шифровальный диск представлял собой пару соосных дисков разного диаметра (см. рисунок). Больший из них — неподвижный, его окружность разделена на 24 равных сектора, в которые вписаны 20 букв латинского алфавита в их естественном порядке и 4 цифры (от 1 до 4). При этом из 24-буквенного алфавита были удалены 4 буквы, без которых можно было обойтись, подобно тому, как в русском языке обходятся без Ъ, Ё, И. Меньший диск — подвижный, по его окружности, разбитой также на 24 сектора, были вписаны все буквы смешанного латинского алфавита.

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

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

Для этой цели на внешнем диске имелись цифры. Альберти составил код, состоящий из 336 кодовых групп, занумерованных от 11 до 4444. Каждому кодовому обозначению соответствовала некоторая законченная фраза. Когда такая фраза встречалась в открытом сообщении, она заменялась соответствующим кодовым обозначением, а с помощью диска цифры зашифровывались как обычные знаки открытого текста, превращаясь в буквы.

Таблица Тритемия

Богатым на новые идеи в криптографии оказался XVI век. Многоалфавитные шифры получили развитие в вышедшей в 1518 г. первой печатной книге по криптографии под названием «Полиграфия». Автором книги был один из самых знаменитых ученых того времени аббат Иоганнес Тритемий. В этой книге впервые в криптографии появляется квадратная таблица. Шифралфавиты записаны в строки таблицы один под другим, причем каждый из них сдвинут на одну позицию влево по сравнению с предыдущим.

Тритемий предлагал использовать эту таблицу для многоалфавитного зашифрования самым простым из возможных способов: первая буква текста шифруется первым алфавитом, вторая буква — вторым и т. д. В этой таблице не было отдельного алфавита открытого текста, для этой цели служил алфавит первой строки. Таким образом, открытый текст, начинающийся со слов HUNC CAVETO VIRUM …, приобретал вид HWPF GFBMCZ FUEIB …

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

Первый шифр с паролем

В 1553 г. Джованни Баттиста Белазо предложил использовать для многоалфавитного шифра буквенный, легко запоминаемый ключ, который он назвал паролем. Паролем могло служить слово или фраза. Пароль периодически записывался над открытым текстом. Буква пароля, расположенная над буквой текста, указывала на алфавит таблицы, который использовался для зашифрования этой буквы. Например, это мог быть алфавит из таблицы Тритемия, первой буквой которого являлась буква пароля. Однако Белазо, как и Тритемий, использовал в качестве щифралфавитов обычные алфавиты.

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

Воскресить смешанные алфавиты, которые применял Альберти, и объединить идеи Альберти с идеями Тритемия и Белазо в современную концепцию многоалфавитной замены выпало на долю итальянца Джованни де ла Порта. Ему было 28 лет, когда он в 1563 г. опубликовал книгу «О тайной переписке». По сути, эта книга являлась учебником по криптографии, содержащим криптографические познания того времени.

Порта предложил использовать квадратную таблицу с периодически сдвигаемым смешанным алфавитом и паролем. Он советовал выбирать длинный ключ. Впервые им был предложен шифр простой биграммной замены, в котором пары букв представлялись одним специальным графическим символом. Они заполняли квадратную таблицу размеров 20×20, строки и столбцы которой занумерованы буквами алфавита:

A B C D E F G H I L M N O P Q R S T U Z

Шифрование осуществляется при помощи лозунга, который пишется над открытым текстом. Буква лозунга определяет алфавит (заглавные буквы первого столбца), расположенная под ней буква открытого текста ищется в верхнем или нижнем полуалфавите и заменяется соответствующей ей буквой второго полуалфавита. Например, фраза, начинающаяся словами HUNC CAVETO VIRUM …, будет зашифрована при помощи лозунга DE LA PORTA в XFHP YTMOGA FQEAS.

Шифр Виженера

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

Первая строка служит алфавитом открытого текста, а первый столбец — алфавитом ключа. Для зашифрования открытого сообщения (To = t1t2…) Виженер предлагал в качестве ключевой последовательности (Γ) использовать само сообщение (To) с добавленной к нему в качестве первой буквы (to) известной отправителю и получателю. Последовательности букв подписывались друг под другом:

Γ  = tot1t2ti−1
To = t1t2t3ti
______________
Tш = s1s2s3si

При этом пара букв, стоящих друг под другом в Γ и Тo, указывала, соответственно, номера строк и столбцов таблицы, на пресечении которых находится знак si шифрованного текста (Tш). Например, фраза HUNC CAVETO VIRUM…, использованная в предыдущих примерах, и начальная буква Р дают шифртекст YCHP ECUWZH IDAMG.

Во втором варианте Виженер предлагал в качестве ключевой последовательности использовать шифрованный текст:

Γ  = sos1s2si−1
To = t1t2t3ti
______________
Tш = s1s2s3si

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

Поворотная решетка

Кардано принадлежит идея поворотной решетки как средства шифрования. Изначально обычная решетка представляла собой лист из твердого материала, в котором через неправильные интервалы сделаны прямоугольные вырезы высотой для одной строчки и различной длины. Накладывая эту решетку на лист писчей бумаги, можно было записывать в вырезы секретное сообщение. После этого, сняв решетку, нужно было заполнить оставшиеся свободные места на листе бумаги неким текстом, маскирующим секретное сообщение. Подобным стеганографическим методом маскировки сообщения пользовались многие известные исторические лица, например кардинал Ришелье во Франции и русский дипломат и писатель А. Грибоедов. Так, Ришелье использовал прямоугольник размера 7×10. Для длинных сообщений прямоугольник использовался несколько раз. Прорези трафарета размещались в позициях: (1, 8), (2, 9), (3, 6), (4, 5), (4, 6). (5, 1), (5, 6), (5, 7), (5, 9), (6, 2), (6, 10), (7, 9), (7, 10).

Текст выглядит как невинное любовное письмо, однако используя трафарет Ришелье, получит зловещую команду: «YOU KILL AT ONCE».

(Содержание раздела) Дальше >

Воробьева Е., Лукьянова А.