Криптография

Криптография в Древнем мире

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

 

Древний Египет

Первым известным применением криптографии принято считать использование специальных иероглифов около 4000 лет назад в Древнем Египте. Элементы криптографии обнаружены уже в надписях Старого и Среднего царств, полностью криптографические тексты известны с периода XVIII династии. Иероглифическое письмо, произошедшее от пиктографии, изобиловало идеограммами и в результате отсутствия огласовки дало возможность создавать фонограммы по принципу ребусов. Криптография египтян использовалась не с целью затруднить чтение, а вероятнее, со стремлением писцов превзойти друг друга в остроумии и изобретательности, а также с помощью необычности и загадочности, привлечь внимание к своим текстам. Одним из показательных примеров являются тексты прославления вельможи Хнумхотепа II (XIX в. до н. э.) найденные в хорошо сохранившейся гробнице № BH 3 в местности Бени-Хасан.

 

Скитала (сцитала)

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

Бесспорно известно, что скитала использовалась в войне Спарты против Афин в конце V века до н. э. Возможно также, что её упоминают поэты Архилох (VII век до н. э.) и Пиндар, хотя вероятнее, что в их стихах слово «скитала» использовано в своём первичном значении «посох».

Принцип её действия изложили Аполлоний Родосский (середина III века до н. э.) и Плутарх (около 45—125 н. э.), но сохранилось лишь описание последнего.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Диск Энея, линейка Энея, книжный шифр

С именем Энея Тактика, полководца IV века до н. э., связывают несколько техник шифрования и тайнописи.

Диск Энея представлял собой диск диаметром 10—15 см с отверстиями по числу букв алфавита. Для записи сообщения нитка протягивалась через отверстия в диске, соответствующим буквам сообщения. При чтении получатель вытягивал нитку, и получал буквы, правда, в обратном порядке. Хотя недоброжелатель мог прочитать сообщение, если перехватит диск, Эней предусмотрел способ быстрого уничтожения сообщения — для этого было достаточно выдернуть нить, закреплённую на катушке в центре диска.

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

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

 

 

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

Во II веке до н. э. в Древней Греции был изобретён квадрат Полибия. В нём буквы алфавита записывались в квадрат 5 на 5 (при использовании греческого алфавита одна ячейка оставалась пустой), после чего с помощью оптического телеграфа передавались номер строки и столбца, соответствующие символу исходного текста (на каждую букву приходилось два сигнала: число факелов обозначало разряд буквы по горизонтали и вертикали).

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

 

      1   2    3   4   5

 1  Α   Β   Γ   Δ   Ε

2  Ζ   Η   Θ   Ι   Κ

3  Λ   Μ   Ν  Ξ  Ο

4  Π   Ρ   Σ   Τ  Υ

5  Φ   Χ   Ψ  Ω    

 

Шифр Цезаря

Согласно свидетельству Светония, Цезарь использовал в переписке моноалфавитный шифр, вошедший в историю как Шифр Цезаря. Книгу о шифре написал грамматик Проб. В шифре Цезаря каждая буква алфавита циклически сдвигается на определённое число позиций. Величину сдвига можно рассматривать как ключ шифрования. Сам Цезарь использовал сдвиг на три позиции.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тайнописи

Кроме примитивных шифров в истории использовался и другой подход — полная

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

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

надпись было невозможно. Кроме этого, использовались специальные техники

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

Примером такой техники являются «вязанные руны», когда руны записываются

таким образом, что отдельные их элементы (например, вертикальные черты)

совпадают. Подобные системы часто использовались жрецами Северо-Западной

Европы вплоть до позднего Средневековья.

Множество вариантов тайнописи использовалось и на Руси. Среди них и простые 

моноалфавитные шифры (простая литорея, письмо в квадратах), замена

алфавита — тайнопись глаголицей, тайнопись греческой азбукой, а также особые

приёмы письма, например, монокондил. Наиболее ранние тексты с

использованием тайнописи относятся к XII веку.

Существует мнение, что в более поздний период тайнопись использовалась для

иконографии, например, при написании иконы XIV века«Донская Богоматерь».

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

декором, который был широко распространён как в древнерусской, так и,

например, в византийской иконописи.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Криптография от Средних веков до Нового времени

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

 

Развитие криптографии в арабских странах

С VIII века н. э. развитие криптографии происходит в основном в арабских странах.

Считается, что арабский филолог Халиль аль-Фарахиди первым обратил внимание

на возможность использования стандартных фраз открытого текста для

дешифрования. Он предположил, что первыми словами в письме на греческом

языке византийскому императору будут «Во имя Аллаха», что позволило ему

прочитать оставшуюся часть сообщения. Позже он написал книгу с описанием

данного метода — «Китаб аль-Муамма» («Книга тайного языка»).

В 855 году выходит «Книга о большом стремлении человека разгадать загадки

древней письменности» арабского учёного Абу Бакр Ахмед ибн Али Ибн Вахшия

ан-Набати, одна из первых книг о криптографии с описаниями нескольких шифров,

в том числе с применением нескольких алфавитов. Также к IX веку относится

первое известное упоминание о частотном криптоанализе — в книге Ал-Кинди 

«Манускрипт о дешифровке криптографических сообщений».

В книге X века «Адаб аль-Куттаб» («Руководство для секретарей») ас-Сули есть

инструкции по шифрованию записей о налогах, что подтверждает распространение

криптографии в обычной, гражданской жизни.

В 1412 году выходит 14-томная энциклопедия Ибн ал-Хаима «Субх ал-Ааша»,

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

В словарь криптологии арабы внесли такие понятия, как алгоритм и шифр.

 

 

Криптография эпохи Возрождения

Первой европейской книгой, описывающей использование криптографии, считается труд Роджера Бэкона XIII века «Послание монаха Роджера Бэкона о тайных действиях искусства и природы и ничтожестве магии» (лат. «Epistola Fratris Rog. Baconis, de secretis operibus artis et naturae et nullitate magiae»), описывающий, в числе прочего, применение 7 методов скрытия текста.

В XIV веке сотрудник тайной канцелярии папской курии Чикко Симонети пишет книгу о системах тайнописи, а в XV веке секретарь папы Климентия XII Габриэль де Левинда, родом из города Пармы, заканчивает работу над «Трактатом о шифрах».

Симеоне де Крема (Simeone de Crema) был первым (1401), кто использовал таблицы омофонов для сокрытия каждого гласного в тексте при помощи более чем одного эквивалента. Спустя более чем сто лет эти таблицы для успешной защиты от криптоаналитических атак использовал Эрнан Кортес.

Первая организация, посвятившая себя целиком криптографии, была создана в Венеции (Италия) в 1452 году. Три секретаря этой организации занимались взломом и созданием шифров по заданиям правительства. В 1469 году появляется шифр пропорциональной замены «Миланский ключ».

 

Отцом западной криптографии называют учёного эпохи Возрождения Леона Баттисту Альберти. Изучив методы вскрытия использовавшихся в Европе моноалфавитных шифров, он попытался создать шифр, который был бы устойчив к частотному криптоанализу. Трактат о новом шифребыл представлен им в папскую канцелярию в 1466 году. Альберти предложил вместо единственного секретного алфавита, как в моноалфавитных шифрах, использовать два или более, переключаясь между ними по какому-либо правилу. Однако флорентийский учёный так и не смог оформить своё открытие в полную работающую систему, что было сделано уже его последователями. Также Альберти предложил устройство из двух скреплённых в центре дисков, каждый из которых имел алфавит, написанный по краю, и мог поворачиваться относительного другого диска. Пока диски не двигаются, они позволяют шифровать с использованием шифра Цезаря, однако через несколько слов диски поворачиваются, и меняется ключ сдвига.

 

Очередной известный результат принадлежит перу германского аббата Иоганна Тритемия,

которого многие историки считают вторым отцом современной криптологии. В пятой книге

серии «Polygraphia», изданной в 1518 году, он описал шифр, в котором каждая следующая

буква шифруется своим собственным шифром сдвига. Его подход был улучшен Джованом

Баттистой Белласо (итал. Giovan Battista Bellaso), который предложил выбирать некоторое

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

ключевого слова используется для выбора конкретного шифра сдвига из полного набора

шифров для шифрования конкретной буквы, тогда как в работе Тритемия шифры

выбираются просто по циклу. Для следующего слова открытого текста ключ начинал

использоваться снова, так, что одинаковые слова оказывались зашифрованы одинаково.

Данный способ в настоящий момент известен как шифр Виженера. Кроме этого, Тритемий

первым заметил, что шифровать можно и по две буквы за раз — биграммами (хотя первый

биграммный шифр — Playfair — был предложен лишь в XIX веке). Позже, в XVII веке, член 

ордена иезуитов Атанасиус Кирхер провёл исследования лингвистических аспектов работ

Тритемия, результаты которых опубликовал в своей Polygraphia nova в 1663 году. Одним

из результатов стало создание «полиглотического кода на пяти языках», который мог

использоваться для шифрования и передачи сообщений на латинском, итальянском, 

французском, испанском и немецком языках, при этом декодирование могло

производиться на любом из указанных языков.

 

В 1550 году итальянский математик Джероламо Кардано, состоящий на службе у папы

римского, предложил новую технику шифрования — решётку Кардано. Этот способ

сочетал в себе как стеганографию (искусство скрытого письма), так и криптографию.

Затруднение составляло даже понять, что сообщение содержит зашифрованный текст,

а расшифровать его, не имея ключа (решётки) в то время было практически невозможно.

Решётку Кардано считают первым транспозиционным шифром или, как ещё называют,

геометрическим шифром, основанным на положении букв в шифротексте. Другой

транспозиционный шифр, намного более лёгкий, использовался в XVII веке при побеге

Джона Треваньона от сил Кромвеля, а также во время Второй мировой войны для

попыток передачи сведений офицерами захваченной немецкой подводной лодки в

письмах домой.

 

Фрэнсис Бэкон в своей первой работе 1580 года предложил двоичный способ кодирования

латинского алфавита, по принципу аналогичный тому, что сейчас используется в

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

каждой из букв, отправитель мог «спрятать» в тексте одного длинного сообщения короткое

секретное. Данный способ получил название «шифр Бэкона», хотя относится больше к 

стеганографии.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Самым известным криптографом XVI века можно назвать Блеза де Виженера. В своём трактате 1585 года он описал шифр, подобный шифру Тритемия, однако изменил систему выбора конкретного шифра замены для каждой буквы. Одной из предложенных техник было использование букв другого открытого текста для выбора ключа каждой буквы исходного текста. Описанный шифр известен как шифр Виженера и, при длине случайного ключа, равной длине открытого текста, является абсолютно стойким шифром, что было математически доказано много позже (в XX веке в работах Шеннона). Другая техника использовала результат шифрования для выбора следующего ключа — то, что впоследствии использует Фейстель и компания IBM при разработке шифра DES в 1970-х годах.

 

 

Криптография Второй мировой войны

Перед началом Второй мировой войны ведущие мировые державы имели электромеханические шифрующие устройства, результат работы которых считался невскрываемым. Эти устройства делились на два типа — роторные машины и машины на цевочных дисках. К первому типу относят «Энигму», использовавшуюся сухопутными войсками Германии и её союзников, второму — американскую M-209.

В СССР производились оба типа машин.

 

Германия: «Энигма», «Fish»

История самой известной электрической роторной шифровальной машины — «Энигма» — начинается в 1917 году — с патента, полученного голландцем Хьюго Кохом. В следующем году патент был перекуплен Артуром Шербиусом (англ.), начавшим коммерческую деятельность с продажи экземпляров машины как частным лицам, так и немецким армии и флоту.

Германские военные продолжают совершенствовать «Энигму». Без учёта настройки положения колец (нем. Ringstellung), количество различных ключей составляло 1016. В конце 1920-х — начале 1930-х годов, несмотря на переданные немецким аристократом Хансом Тило-Шмидтом данные по машине, имевшиеся экземпляры коммерческих вариантов, британская и французская разведка не стали браться за задачу криптоанализа. Вероятно, к тому времени они уже сочли, что шифр является невзламываемым. Однако группа из трёхпольских математиков так не считала и, вплоть до 1939 года, вела работы по «борьбе» с «Энигмой» и даже умела читать многие сообщения, зашифрованные «Энигмой» (в варианте до внесения изменений в протокол шифрования от декабря 1938 года). У одного из них, Мариана Реевского, зародилась идея бороться с криптографической машиной с помощью другой машины. Идея озарила Реевского в кафе, и он дал машине имя «Бомба» по названию круглого пирожного. Среди результатов, переданных британским разведчикам перед захватом Польши Германией, были и «живые» экземпляры «Энигмы», и электромеханическая машина «Bomba», состоявшая из шести спаренных «Энигм» и помогавшая в расшифровке (прототип для более поздней «Bombe» Алана Тьюринга), а также уникальные методики криптоанализа.

 

Дальнейшая работа по взлому была организована в Блетчли-парке, сегодня являющемся одним из предметов национальной гордости Великобритании. В разгар деятельности центр «Station X» насчитывал 12 тысяч человек, но, несмотря на это, немцы не узнали о нём до самого конца войны. Сообщения, расшифрованные центром, имели гриф секретности «Ultra» — выше, чем использовавшийся до этого «Top Secret» (по одной из версий, отсюда и название всей британской операции — «Операция Ультра»). Англичане предпринимали повышенные меры безопасности, чтобы Германия не догадалась о раскрытии шифра. Ярким эпизодом является случай с бомбардировкой Ковентри 14 ноября 1940 года, о которой премьер-министру Великобритании Уинстону Черчиллю было известно заранее благодаря расшифровке приказа. Однако Черчилль, опираясь на мнение аналитиков о возможности Германии догадаться об операции «Ультра», принял решение о непринятии мер к защите города и эвакуации жителей[89].

Война заставляет нас все больше и больше играть в Бога. Не знаю, как бы я поступил…

— Президент США Франклин Рузвельт о бомбардировке Ковентри

Хотя для СССР существование и даже результаты работы «Station X» секрета не представляли. Именно из результатов сообщений, дешифрованных в «Station X», СССР узнал о намечающемся «реванше» Гитлера за Сталинградскую битву и смог подготовиться к операции на Курском направлении, получившем названии «Курская дуга».

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

Однако с 1940 года высшее германское командование начало использовать новый метод шифрования, названный британцами «Fish». Для шифрования использовалось новое устройство «Lorenz SZ 40», разработанное по заказу военных. Шифрование основывалось на принципе одноразового блокнота (шифр Вернама, одна из модификаций шифра Виженера, описанная в 1917 году) и при правильном использовании гарантировало абсолютную криптостойкость (что было доказано позже в работах Шеннона). Однако для работы шифра требовался «надёжный» генератор случайной последовательности, который бы синхронизировался на передающей и принимающей стороне. Если криптоаналитик сумеет предсказать следующее число, выдаваемое генератором, он сможет расшифровать текст.

К сожалению для Германии, генератор, используемый в машинах «Lorenz SZ 40» оказался «слабым». Однако его взлом всё равно нельзя было осуществить вручную — криптоаналитикам из Блетчли-парка потребовалось создать устройство, которое бы перебирало все возможные варианты и избавляло бы криптоаналитиков от ручного перебора. Таким устройством стала одна из первых программируемых вычислительных машин «Colossus», созданная Максом Ньюменом (англ. Max Newman) и Томми Флауэрсом при участии Алана Тьюринга в1943 году (хотя некоторые источники указывают, что она была сделана для взлома «Энигмы»). Машина включала 1600 электронных ламп и позволила сократить время, требуемое на взлом сообщений, с шести недель до нескольких часов.