В статье авторы рассматривают историю нематематической криптографии: от зарождения дисциплины до XIX века.
Ключевые слова: шифр, криптография, символ, алфавит, ключевое слово.
История криптографии насчитывает около 4 тысяч лет. Она, сама по себе — ровесница письменности. В некотором роде, саму письменность можно назвать криптографической системой. Эта дисциплина развивалась еще с рассвета первых цивилизаций, но лишь недавно, по историческим меркам, она стала наукой. Изначально, криптографические методы защиты информации применялись исключительно в военных целях, а сама же криптография не имела под собой прочного математического основания. В те времена дисциплина представляла собой несистематизированный набор данных, головоломок и наблюдений. Однако, именно эта «наивная» криптография стала прообразом современного ее вида, именно в древние времена были заложены основные идеи и методы шифрования. Так какова же была криптография в древности?
В этой статье рассмотрена история нематематической криптографии: от зарождения дисциплины до XIX века.
Целью этой статьи является углубленный анализ истории криптографии с древних времен до новейшего времени, и определение ее влияние и место в математике в целом.
Были поставлены следующие задачи: выяснить способы периодизации развития криптографии, проанализировать ее методы в разных периодах истории человечества. Также задачей статьи является описание самых значимых шифров и их влияние на развитие криптографии.
Криптография на заре цивилизации
Развитие криптографии неотделимо от развития письменности. Искусство тайнописи было известно еще жителям древнего мира: Шумерам, Индусам, Китайцам и Египтянам.
Так, например, среди 64 искусств письма, упоминаемых в древнеиндусских текстах, есть некоторые такие виды написания, которые мы можем смело назвать криптографическими преобразованиями. [1, 2, 3] Например, среди них есть метод, полагающий шифрующему писать знаки не по порядку, а вразброс по оговоренному правилу(история криптогафии носов).
Однако первым упоминанием об использовании криптографии принято считать манускрипт, прославляющий вельможу Хнумхотепа Второго, датированный 3900 годом до н. э. (англ. Khnumhotep II ) [4] [5] . В дальнейшем, криптография упоминается лишь в военном деле.
Шифры и Иудаизм. Шифр Атбаш.
Самым древним, из достоверно изученных, является шифр «Атбаш». Этот метод встречается в книге пророка Иеремии (VI век до н. э.). разберем этот шифр подробнее.
Атбаш — простейший шифр замены. Этимологически, название этого шифра происходит от четырех букв: алеф(первая буква алфавита), тау(последняя буква алфавита), бета(вторая буква алфавита) и шин(предпоследняя буква алфавита). Название намекает нам и на сам метод шифрования: первый символ заменяем на последний, второй — на предпоследний и т. д. Иначе:
a(1) =a(n), a(2) = a(n-1), …, a(i) = a(n-i+1), …, a(n) = a(1), где a(i) — некоторый элемент алфавита, n — количество символов в алфавите, а i = 1,2, …, n — порядковый номер символа в алфавите.
Криптография древней Греции
Далее, история криптографии закинет нас на самый юг Балканского полуострова, в древнегреческие полисы. Наиболее сильно криптография развивалась именно там. Исторической науке известно, что еще в 5–6 веке до н. э. в Спарте эта дисциплина уже была достаточно сильна развита. Именно там и появилось первое криптографическое устройство — сцитала. «Сциатала» с древнегреческого означает посох, длина и диаметр которого были ключом к дешифровке послания. В то же время древнегреческий полководец Эней Тактик изобрел сразу несколько техник криптографии и тайнописи: линейку Энея, диск Энея (позже, именно эта технология сослужит огромную службу европейцам эпохи просвещения, воскрешавшим криптографию). Более того, греческий полководец в сочинении «Об обороне укрепленных мест» описывает так называемый «книжный шифр». Позже, в 200 году до н. э. древнегреческий политик Полибий изобрел свой «магический квадрат». Опишем эти криптосистемы подробнее:
Сцитала
Сцитала представляла собой длинный стержень, на который наматывалась лента из пергамента. На ленту наносился текст вдоль оси скиталы, так, что после разматывания текст становился нечитаемым. Однако, мы можем представить ленту, с ее возможным конфигурациями, как массив данных, или же, как таблицу n×m, где n — количество строк, а n*m=l(длинна ленты).
Т. к. таблиц n×m мы можем составить ровно столько, сколько у l всего делителей, то задача по дешифровке сводится к разложению l на произведение простых чисел и подбор таких комбинаций этих простых чисел, которые бы делили l нацело. Тогда, мы получим множество (a(1), …, a(n)), для которых l = М{ a(1), …, a(n)}(общее кратное). В полученном множестве каждый a(i) — является количеством строк, а m(i) = l\ a(i) — количество столбцов. Таким образом, путем несложного перебора, мы получаем множество решений для заданной длинны ленты. Т. к. лента едва-ли превышает 1 м, то и количество подобных таблиц не будет превышать ~ 9 вариаций(исходя из того, что один символ занимает 1 см^2).
Важно отметить, что такую криптосистему можно, пускай и с оговоркой, назвать симметричной(нам не так важен метод шифрования, как важен диаметр цилиндра).
Простота в реализации и относительная надежность, которые можно назвать достоинством этой системы, перекрываются проблемой любого симметричного алгоритма: необходимость передачи ключей тайно.
Диск Энея
Это средство шифрования, представляющее собой диск, диаметром в 13–15 см и толщиной в 2 см. Между соответствующими некоторым буквам отверстиями протягивалась нитка. Таким образом, читающий мог получить сообщение и дешифровать его, потянув за нитку. Полученное сообщение осталось лишь записать в обратном порядке, чтобы получить открытый текст. Если же гонца с диском перехватят, то тот всегда мог выдернуть нитку из катушки в центре, уничтожив зашифрованное сообщение.
Линейка Энея
Этот криптографический инструмент (вероятно, первый в истории) представлял собой линейку с определенным положением отверстий на нем. Сама суть алгоритма — способность вычленить нужные символы из потока всех прочих. Линейка являет собой ключ, необходимый в двух экземплярах, для отправителя и получателя (потому, систему можно назвать системой симметричного шифрования).
Квадрат Полибия.
Спустя почти 400 лет, в 200 году до н.э был изобретен квадрат полибия. Это шифр замены, где алфавит представлялся в виде таблички, размером 5х5. В каждой клетке этого квадрата записывалась буква (что примечательно, в оригинальном варианте таблицы, одна ячейка всегда оставалось пустой), а каждой букве давался номер, состоящий из двух индексов, иначе говоря:
{N} — алфавит; i,j –индексы, a [ij] — буква, принадлежащая алфавиту, тогда, наш моноалфавитный шифр имеет вид следующей таблицы(для удобства, используем английский алфавит) (см. таблица 1):
Таблица 1
|
1 |
2 |
3 |
4 |
5 |
|
|
1 |
A |
B |
C |
D |
E |
|
2 |
F |
G |
H |
I\J |
K |
|
3 |
L |
M |
N |
O |
P |
|
4 |
Q |
R |
S |
T |
U |
|
5 |
V |
W |
X |
Y |
Z |
Общая формула шифрования:
a [ij] = ij;
PT = a(1),a(2)…a(k)
CT= ij(1),ij(2)…ij(k)
Ключом данной системы является сама таблица, представленная выше. Перед нами типичный пример моноалфавитного шифра замены, при том, достаточно стойкого (по меркам древних греков). Несмотря на то, что стойкость шифра обеспечивается секретностью ключа (как и с шифрами Энея), удобство такой записи в том, что нет необходимости создавать ключи в виде физического носителя. Более того, представленные закономерности не столь очевидны, как аналогичные у атбаша, что выделяет этот шифр из всех представленных выше.
Криптография в древнем Риме. Шифр Цезаря.
Далее, история нас забрасывает в древний Рим, к первому римскому императору Гаю Юлию Цезарю. Однако, нас не так интересует личность этого, безусловно, выдающегося полководца и правителя. Нас, как исследователей шифров древности, интересует именно одноименный шифр, который великий стратег описал в своих «Записках о Галльской войне».
Да-да, именно шифр Цезаря стал новой вехой в развитии криптографии. Остановимся подробнее на этом шифре. Это — моноалфавитный шифр замены, где каждая буква циклически сдвигается на некоторое количество символов вправо (сам Цезарь использовал шаг в три), иначе говоря: N — ключ (количество символов, на которое происходит сдвиг), a [i] — буква открытого текста, z [i] — буква шифротекста, а k — мощность алфавита.
Z [i] = a [i] +N(mod k);
A [i] = z [i] — N(mod k);
Представим алфавит в виде таблички, и зашифруем послание «Я люблю МИИТ» (см. таблица 2, 3):
Таблица 2
|
Буква |
А |
Б |
В |
Г |
Д |
Е |
Ё |
Ж |
З |
И |
Й |
|
Номер |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
Буква |
К |
Л |
М |
Н |
О |
П |
Р |
С |
Т |
У |
Ф |
|
Номер |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
|
Буква |
Х |
Ц |
Ч |
Ш |
Щ |
Ь |
Ы |
Ъ |
Э |
Ю |
Я |
|
Номер |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
Таблица 3
|
PT |
Я |
Л |
Ю |
Б |
Л |
Ю |
М |
И |
И |
Т |
|
Номера |
33 |
13 |
32 |
2 |
13 |
32 |
14 |
10 |
10 |
20 |
|
Номера(+7) |
7 |
20 |
6 |
9 |
20 |
6 |
21 |
17 |
17 |
27 |
|
СТ |
Ё |
Т |
Е |
З |
Т |
Е |
У |
П |
П |
Щ |
Получившееся сообщение: «ЁТЕЗТЕУППЩ».
Проблемой данного шифра можно выделить безопасность, основанную на секретности ключа, и слабую устойчивость к брутфорсу. Он выгодно выделяется своей простотой и, при том, надежностью, относительно многих других шифров. Сравнится по безопасности с ним может только квадрат полибия.
Далее, в течение всего периода существования Римской Империи о шифрах говорить не получится: многие документы утеряны, да и сама дисциплина особо не развивалась: хватало тех изобретений и открытий, которые сделали предшественники. Именно в таком стагнирующем положении вошла криптография в эпоху Средневековья.
Вывод
Все шифры античного периода делятся на два типа: шифра замены и шифр простейшей перестановки. К первым относятся: атбаш, шифр Цезаря, диск Энея и квадрат Полибия, к вторым же мы отнесем лишь Сциталу.
Обе категории этих шифров легко взломать: первая группа уязвима к частотному анализу, вторая группа уязвима к перебору данных в блоках.
Однако, многие из них так и не были взломаны во время жизни их создателей, что доказало их эффективность на тот период. Более того, именно эти шифры легли в фундамент криптографии и криптологии, и, как мы увидим позднее, стали прототипами шифров нового времени.
Криптография в Средние века
Криптография арабского мира.
Весь мир еще долго не могу оправиться от удара, полученного от крушения Западной Римской Империи. Вновь, криптография возвращается на радары историков лишь VIII веке, на этот раз, уже в арабских странах. Считается, что арабский филолог Халиль аль-Фарахиди первым обратил внимание на возможность использования стандартных фраз открытого текста для дешифрования. Он предположил, что первыми словами в письме на греческом языке византийскому императору будут «Во имя Аллаха», что позволило ему прочитать оставшуюся часть сообщения. Позже он написал книгу с описанием данного метода — «Китаб аль-Маумма» («Книга тайного языка»). В 855 году выходит «Книга о большом стремлении человека разгадать загадки древней письменности» арабского учёного Абу Бакр Ахмед бен-Али бен-Вахшия ан-Набати, одна из первых книг о криптографии с описаниями нескольких шифров, в том числе с применением нескольких алфавитов. Также к IX веку относится первое известное упоминание о частотном криптоанализе — в книге Ал-Кинди «Манускрипт о дешифровке криптографических сообщений».
В книге X века «Адаб аль-Куттаб» («Руководство для секретарей») ал-Сули есть инструкции по шифрованию записей о налогах, что подтверждает распространение криптографии в обычной, гражданской жизни
В 1412 году выходит 14-томная энциклопедия Шехаба ал-Кашканди «Шауба ал-Аша», один из разделов которой «Относительно сокрытия в буквах тайных сообщений» содержал описание семи шифров замены и перестановки, частотного метода криптоанализа, а также таблицы частотности букв в арабском языке на основе текста Корана.
Стоит отметить, что именно арабы внесли в словарь криптологии такие слова как «шифр» и «алгоритм».
К сожалению, состояние знания в Европе было плачевным: многие философские, алгебраические и иные произведения были, в том или ином виде, забыты и утрачены. Такая же учесть постигла криптографию: лишь изредка исторической науке доводилось находить хоть какие-то сведения о развитии этой дисциплины. Так, например, известно, что Карл Великий использовал свой собственный шифр, суть которого — замена некоторых символов при написании на специальные знаки. Известен так называемый «еврейский шифр», в котором замена букв осуществляется по подстановке, в которой нижняя строка образуется так: алфавит разбивается на две половины. Буквы второй половины пишутся под буквами первой половины в обратном порядке. Аналогично поступают с остальными буквами.
Криптография нового времени.
С бурным расцветом наук в итальянских городах-государствах, криптография вновь подняла свою голову. Шифры стали применяться не только государственными или религиозными деятелями, но и учеными (для защиты приоритета научных знаний). В 14 веке появляется книга Чикко Симонетти, сотрудника канцелярии папской курии. В этой книге описаны шифры замены, в которых гласным буквам ставятся в соответствие несколько знаков с целью выравнивания частот букв в шифртексте. Дано описание лозунгового шифра, в котором замена букв определяется так: под алфавитом пишутся различные буквы лозунга в порядке появления, а затем буквы, не появившиеся в лозунге. В 15 веке появляется книга Габриэля де Лавинда, секретаря Папы Клементия ХII, «Трактат о шифрах», в которой дается описание шифра пропорциональной замены. Шифр обеспечивает замену букв несколькими символами, пропорционально встречаемости букв в открытом тексте. Дается рекомендация заменять имена, должности, географические названия специальными знаками. В этот период в Милане применяется шифр, названный «Миланский ключ», представляющий собой значковый шифр пропорциональной замены.
Однако, значимую роль в становлении криптографии сыграл шифр, разработанный итальянским архитектором Леоном Баттистой Альберти в 1466 году. «Шифр, достойный королей», а именно так называл свое изобретение Альберти, идейно продолжил шифр Цезаря, сделав, при том, скачок в сторону многоалфавитных шифров. Рассмотрим его подробнее:
Шифрование текста производилось посредством двух скрепленных дисков, один из которых можно было крутить вокруг своей оси. На обоих дисках было по 24 символа (20 символов латинского алфавита + 4 цифры, от одного до 4), однако положение одного из них (относительно другого) можно было менять, тем самым чередуя алфавиты шифрования под каждый конкретный символ. Таким образом:
Пусть x(1)…x(n) — сообщение, состоящее из n символов, где каждый символ — x(i), а {k(i)} из t символов — множество ключей, а B — мощность алфавита, тогда
y(1) = x(1) + k(1)mod B…
y(n) = x(n) + k(t)mod B, t=\= n
Таким образом, через некоторое фиксированное количество символов, алфавит менялся, что затрудняло частотный криптоанализ. Ключом к шифру являлись: количество поворотов и шаг одного поворота.
Эту идею развил шифр Тритемия в 1518 году. Он предполагал тот же принцип многоалфавитной замены, однако, предлагал менять алфавит после каждого зашифрованного символа. Для этого он использовал специальную алфавитную таблицу (см. таблица 4):
Таблица 4
Пусть x(1)…x(n) — сообщение, состоящее из n символов, где каждый символ — x(i), а {k(i)} — множество ключей, совпадает с мощностью алфавита(B), тогда
y(1) = x(1) + k(1)mod B…
y(n) = x(n) + k(t)mod B,
Такое представление создавало еще больше препятствий криптологу: если Альберти менял алфавит раз в три-четыре слова, и закономерности в тексте выявлялись проще, то теперь отследить закономерности куда труднее.
В сущности, почти все последующие шифры данной эпохи были вариацией, или модернизацией модели Альберти.
Таблица делла Порты.
В XVI веке Джованни Баттиста делла Порта использовал систему ключевых слов для реализации шифра, похожего на шифр Альберти. Одно ключевое слово используется для формирования перестановки алфавита, другое ключевое слово используется, чтобы определить последовательность для нескольких алфавитов. Это техника, которая была названа «двойной шифр», а иначе — биграмма, является ярким примером многоалфавитного шифра замены.
Техника перестановки Порта была основана на 2-мерной таблице, для примера вот вариант таблицы Порта на основе 26-символьного алфавита.
В этом случае верхний регистр букв соответствует рандомизированному внутреннему алфавиту дисков, мы используем некоторое слово, как ключевое, чтобы формировать алфавит. Заглавные буквы соответствуют внешнему диску, а цифры на углу представляют индексы нескольких алфавитов, второе ключевое слово используется для обозначения последовательности индексов, использующихся для выбора строк в таблице. Для шифра типа Порта, ключ шифрования будет состоять из перестановки, приведённой в первой строке таблицы плюс сдвиг, который следует после каждой буквы текста. Каждое новое значение сдвига в методе Порта, или каждое новое «слово» во втором ключевом слове, означает новый алфавит шифротекста.
Сила шифра в том, что для шифрования используется сразу два параметра, потому, недоброжелателю необходимо иметь сообщение, суммарное длиной в 8000 символов, чтобы подвергнуть данный шифр частотному анализу.
Шифр Виженера
Еще одно важное усовершенствование многоалфавитных систем, состоящее в идее использования в качестве ключа текста самого сообщения или же шифрованного текста, принадлежит Джероламо Кардано и Блезу де Виженеру. Такой шифр был назван самоключом. В книге Виженера 'Трактат о шифрах» самоключ представлен следующим образом. В простейшем случае за основу бралась таблица Тритемия с добавленными к ней в качестве первой строки и первого столбца алфавитами в их естественном порядке. Позже такая таблица стала называться таблицей Виженера. Подчеркнем, что в общем случае таблица Виженера состоит из циклически сдвигаемых алфавитов, причем первая строка может быть произвольным смешанным алфавитом.
Пусть x(1)…x(n) — сообщение, состоящее из n символов, где каждый символ — x(i), а {k(i)} — ключевое слово, состоящее из w символов(<=B),тогда
y(1) = x(1) + k(1)mod B
…
y(n) = x(n) + k(w)mod B
Подведем итоги. Все шифры, представленные тут, являются вариациями шифра Альберти, потому и метод их анализа — тест Кассиски — является общим для всех.
Этап 1.
– Необходимо найти пары одинаковых подстрок в шифротексте
– Вычислить расстояние между их одинаковыми элементами
– Составить таблицу расстояний
– Выписываются делители расстояний
– Общие делители рассматриваются как возможные длины ключа
Этап 2.
– Шифротекст делится на группы, зашифрованные одни алфавитом
– Для каждой группы проводят частотный анализ, как для шифра простой замены.
Заключение
Криптография, как наука использования кодов и шифров для защиты секретов, начала свой отсчет тысячи лет назад. До последних десятилетий это была история того, что можно было бы назвать классической криптографией, то есть методов шифрования с использованием ручки и бумаги или, возможно, простых механических средств. Криптография возникла вместе с письменностью. Развитие криптографии шло параллельно с развитием криптоанализа — «взлома» кодов и шифров. Открытие и раннее применение частотного анализа для чтения зашифрованных сообщений иногда меняло ход истории.
Термин «криптография» далеко ушел от своего первоначального значения — «тайнопись», «тайное письмо».
Сегодня криптография — это дисциплина, изучающая способы защиты процессов информационного взаимодействия от целенаправленных попыток отклонить их от условий нормального протекания, основанные на криптографических преобразованиях, то есть преобразованиях данных по секретным алгоритмам. С давних времен вплоть до настоящего время важнейшей задачей криптографии является защита передаваемых по каналам связи или хранящихся в системах обработки информации данных от несанкционированного ознакомления с ними и от преднамеренного их искажения.
Литература:
- Основы Криптографии. / А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. —: Гелиос, 2005. — 5–53 c. — Текст: непосредственный.
- Криптография от папируса до компьютера. / В. Жельников. —: ABF, 1996. — 325 c. — Текст: непосредственный.
