Криптографические методы защиты информации

Лекции

2. ИСТОРИЯ КРИПТОГРАФИИ

 

2.1. Введение.

2.2. Наивная криптография.

2.3. Формальная криптография.

2.4. Математическая криптография.

Вопросы для самопроверки.

 

2.1. Введение

 

В истории развития криптографии можно выделить три этапа [11]:

- наивная криптография;

- формальная криптография;

- математическая криптография.

 

2.2. Наивная криптография

 

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

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

[43] Точное время возникновения этих способов обмена тайной информацией теряется в глубине веков, и установить его невозможно. Историки полагают, что первые протокриптографические приемы появились в Древнем Египте около 4 тыс. лет назад. Писцы, составлявшие жизнеописания правителей, стремились придать стандартным иероглифам необычный вид на монументах и гробницах, чтобы сообщить надписям менее обыденный и более почтительный стиль. Жрецы пользовались этим же приемом при переписывании религиозных текстов, чтобы те выглядели для мирян загадочнее и внушительнее. Такие «переводы» становились все менее понятными простому люду, который в результате оказывался во все большей зависимости от жрецов.

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

Рис.2.1. Розеттский камень1

Более явные криптологические примеры дошли до нас от цивилизаций Месопотамии — от вавилонян, ассирийцев, халдеев, использовавших особую систему письма — клинопись. В 1500 г. до н. э. на глиняной табличке был записан тщательно охраняемый рецепт глазури для гончарных изделий. Знаки, определяющие необходимые ингредиенты, были намеренно перемешаны. Таким образом, мы имеем право утверждать, что эта табличка является самой ранней известной секретной записью.

Примерно с 500 г. до н. э. в Индии также широко применялись секретные записи, в частности в донесениях шпионов и текстах, предположительно использовавшихся Буддой. Методы засекречивания включали в себя фонетическую замену, когда согласные и гласные менялись местами, использование перевернутых букв и запись текста под случайными углами. Различные индийские трактаты, ярким примером которых является «Артхашастра» (около 321—300 гг. до н. э.), показывают, что индийцы были хорошо знакомы со способами сокрытия информации. Согласно «Камасутре», классическому произведению об эротике и других видах наслаждений, написанному Ватсьяяной около IV в. до н.э., владение приемами составления секретного письма (наряду с музыкой, кулинарией и шахматами) является одним из 64 искусств, которыми должны владеть женщины.

Рис.2.2. Фрагмент «Камасутры»

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

С VIII века н. э. развитие криптографии происходит в основном в арабских странах. Считается, что арабский филолог Халиль аль-Фарахиди первым обратил внимание на возможность использования стандартных фраз открытого текста для дешифрования. Он предположил, что первыми словами в письме на греческом языке византийскому императору будут «Во имя Аллаха», что позволило ему прочитать оставшуюся часть сообщения. Позже он написал книгу с описанием данного метода — «Китаб аль-Муамма» («Книга тайного языка») [17]. В 855 г. выходит «Книга о большом стремлении человека разгадать загадки древней письменности» арабского учёного Абу Бакр Ахмед ибн Али Ибн Вахшия ан-Набати, одна из первых книг о криптографии с описаниями нескольких шифров, в том числе с применением нескольких алфавитов. Также к IX веку относится первое известное упоминание о частотном криптоанализе — в книге Аль-Кинди «Манускрипт о дешифровке криптографических сообщений». В 1412 г. выходит 14-томная энциклопедия Шихаба ал-Калкашанди «Субх ал-Ааша», один из разделов которой «Относительно сокрытия в буквах тайных сообщений» содержал описание семи шифров замены и перестановки, частотного криптоанализа, а также таблицы частоты появления букв в арабском языке на основе текста Корана. В словарь криптологии арабы внесли такие понятия как алгоритм и шифр.

Рис.2.3. Фрагмент первой страницы «Манускрипта о дешифровке криптографических сообщений» Аль-Кинди

В древние времена широкое применение нашли различные простейшие криптографические устройства.

Греческим поэтом Архилохом, жившим в VII веке до н.э., упоминается устройство под названием сцитала (греч. σκυτάλη - жезл). Достоверно известно, что сцитала использовалась в войне Спарты против Афин в конце V века до н. э. Оно представляет собой цилиндр (иногда жезл командующего) и узкую полоску пергамента, обматывавшуюся вокруг него по спирали, на которой в свою очередь писалось сообщение [17].

Рис.2.4. Сцитала

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

Другим широко известным криптографическим устройством защиты информации был «диск Энея» - инструмент для защиты информации, придуманный Энеем Тактиком в IV веке до н.э. Устройство представляло собой диск диаметром 13-15 см и толщиной 1-2 см с проделанными в нём отверстиями, количество которых равнялось числу букв в алфавите. Каждому отверстию ставилась в соответствие конкретная буква. В центре диска находилась катушка с намотанной на неё ниткой [17].

Рис.2.5. Диск Энея

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

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


1Розеттский камень - плита из гранодиорита, найденная в 1799 г. в Египте возле небольшого города Розетта (теперь Рашид), недалеко от Александрии, с выбитыми на ней тремя идентичными по смыслу текстами, в том числе двумя на древнеегипетском языке и одним на древнегреческом языке. Древнегреческий был хорошо известен лингвистам, и сопоставление трёх текстов послужило отправной точкой для расшифровки египетских иероглифов.

 

2.3. Формальная криптография

 

Этап формальной криптографии (конец XV – начало XX вв.) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации.

К концу XIV в. между итальянскими городами-государствами в переписке уже применялись «номенклаторы»2 (лат. nomen — «имя» и calator — «раб», «слуга»). Они состояли из кодовых обозначений для слогов, слов и имен, а также алфавитов шифрозамен. Вплоть до XIX в. номенклаторы оставались самой широко используемой системой сокрытия содержания сообщений [43].

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

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

Рис.2.6. Фрагмент первой страницы «Трактата о шифрах» Леона Баттисто Альберти

Однако флорентийский учёный так и не смог оформить своё открытие в полную работающую систему, что было сделано уже его последователями (Блез Вижинер).

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

Рис.2.7. Первый печатный труд по криптографии - «Полиграфия» Иоганна Трисемуса [Национальный музей криптографии, США]

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

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

В 1863 г. Фридрих Касиски (англ. Friedrich Kasiski) опубликовал метод, впоследствии названный его именем, позволявшим быстро и эффективно вскрывать практически любые шифры того времени, в т.ч. полиалфавитные. Метод состоял из двух частей - определение периода шифра и дешифровка текста с использованием частотного криптоанализа.

Рис.2.8. Титульный лист «Тайнописи и искусства дешифрования» Фридриха Касиски

В 1883 г. голландец Огюст Керкгоффс3 опубликовал труд под названием «Военная криптография» (фр. «La Cryptographie Militaire»). В нём он описал шесть требований, которым должна удовлетворять защищённая система. Хотя к некоторым из них стоит относиться с подозрением, стоит отметить труд за саму попытку:

1. шифр должен быть физически, если не математически, невскрываемым;

2. система не должна требовать секретности, на случай, если она попадёт в руки врага;

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

4. зашифрованный текст должен (без проблем) передаваться по телеграфу;

5. аппарат для шифрования должен быть легко переносимым, работа с ним не должна требовать помощи нескольких лиц;

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

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

Рис.2.9. Титульный лист брошюры «Военная криптография» Огюста Керкгоффса

В 1920 г. вышла монография американского криптографа российского происхождения Уильяма Ф. Фридмана «Индекс совпадения и его применение в криптографии» (англ. «Index of Coincidence and Its Applications in Cryptography»). Работа вышла в открытой печати, несмотря на то, что была выполнена в рамках военного заказа. Двумя годами позже Фридман ввёл в научный обиход термины криптология и криптоанализ [13].

Рис.2.10. «Индекс совпадения и его применение в криптографии» Уильяма Фридмана

Криптография оказала влияние и на литературу. Упоминания о криптографии встречаются ещё во времена Гомера и Геродота, хотя они описывали искусство шифрования в контексте различных исторических событий. Первым вымышленным упоминанием о криптографии можно считать роман «Гаргантюа и Пантагрюэль» французского писателя XVI века Франсуа Рабле, в одной из глав которого описываются попытки чтения зашифрованных сообщений. Упоминание встречается и в «Генрихе V» Шекспира. Впервые как центральный элемент художественного произведения криптография используется в рассказе «Золотой жук» Эдгара Аллана По 1843 г. В нём писатель не только показывает способ раскрытия шифра, но и результат, к которому может привести подобная деятельность - нахождение спрятанного сокровища. Одним из лучших описаний применения криптографии является рассказ 1903 г. Артура Конан Дойля «Пляшущие человечки». В рассказе великий сыщик Шерлок Холмс сталкивается с разновидностью шифра, который не только прячет смысл написанного, но, используя символы, похожие на детские картинки, скрывает сам факт передачи секретного сообщения. В рассказе герой успешно применяет частотный анализ, а также предположения о структуре и содержании открытых сообщений для разгадывания шифра.

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

               
Энигма 1
(Германия)
  М-209
(США)
  Коралл
(СССР)

Рис.2.11. Шифровальные устройства [en.wikipedia.org, www.cryptomuseum.com]

Успешные криптоатаки на подобного рода криптосистемы стали возможны только с появлением ЭВМ.


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

3Огюст Керкгоффс (Auguste Kerckhoffs, 1835 - 1903 гг.) - голландский лингвист и криптограф, профессор Парижской высшей школы коммерции во второй половине XIX века. В русских источниках встречаются разные переводы фамилии - Керкхофф, Кирхгоф, Керкгоффс, Керхофс, Керкхоффс. Полное имя, полученное при крещении, - Жан Вильгельм Губерт Виктор Франсуа Александр Огюст Керкгоффс фон Ниувенгоф [17, 43].

 

2.4. Математическая криптография

 

После Первой мировой войны правительства стран засекретили все работы в области криптографии. К началу 1930-х годов окончательно сформировались разделы математики, являющиеся основой для будущей науки: общая алгебра, теория чисел, теория вероятностей и математическая статистика. К концу 1940-х годов построены первые программируемые счётные машины, заложены основы теории алгоритмов, кибернетики. Тем не менее, в период после Первой мировой войны и до конца 1940-х годов в открытой печати было опубликовано совсем немного работ и монографий, но и те отражали далеко не самое актуальное состояние дел. Наибольший прогресс в криптографии достигается в военных ведомствах.

Ключевой вехой в развитии криптографии является фундаментальный труд Клода Шеннона «Теория связи в секретных системах» (англ. Communication Theory of Secrecy Systems) - секретный доклад, представленный автором в 1945 г., и опубликованный им в «Bell System Technical Journal» в 1949 г. В этой работе, по мнению многих современных криптографов, был впервые показан подход к криптографии в целом как к математической науке.

Рис.2.12. Сборник со статьей «Теория связи в секретных системах» Клода Шеннона

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

В 1967 г. выходит книга Дэвида Кана «Взломщики кодов». Хотя книга не содержала сколько-нибудь новых открытий, она подробно описывала имеющиеся на тот момент результаты в области криптографии, большой исторический материал, включая успешные случаи использования криптоанализа, а также некоторые сведения, которые правительство США полагало всё ещё секретными. Но главное - книга имела заметный коммерческий успех и познакомила с криптографией десятки тысяч людей. С этого момента начали понемногу появляться работы и в открытой печати.

Рис.2.13. Обложка первого издания «Взломщиков кодов» Дэвида Кана

Примерно в это же время Хорст Фейстель переходит из Военно-воздушных сил США на работу в лабораторию корпорации IBM. Там он занимается разработкой новых методов в криптографии и разрабатывает ячейку Фейстеля, являющуюся основой многих современных шифров, в том числе шифра Lucifer, ставшего прообразом шифра DES – бывшего стандарта шифрования США, первого в мире открытого государственного стандарта на шифрование данных. На основе ячейки Фейстеля были созданы и другие блочные шифры, в том числе TEA (1994 г.), Twofish (1998 г.), IDEA (2000 г.), а также бывший (ГОСТ 28147-89) и действующий (ГОСТ 34.12-2015) российские стандарты шифрования.

В 1976 г. публикуется работа Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» (англ. «New Directions in Cryptography»). Данная работа открыла новую область в криптографии, теперь известную как криптография с открытым ключом. Также в работе содержалось описание алгоритма Диффи - Хеллмана - Меркла, позволявшего сторонам сгенерировать общий секретный ключ, используя открытый канал связи.

Рис.2.14. Начало статьи «Новые направления в криптографии» Уитфилда Диффи и Мартина Хеллмана

Хотя работа Диффи-Хеллмана создала большой теоретический задел для открытой криптографии, первой реальной криптосистемой с открытым ключом считают алгоритм RSA (названный по имени авторов - Рон Ривест (R. Rivest), Ади Шамир (A. Shamir) и Леонард Адлеман (L. Adleman)). Опубликованная в августе 1977 г., работа позволила сторонам обмениваться секретной информацией, не имея заранее выбранного секретного ключа. Стоит отметить, что и алгоритм Диффи - Хеллмана - Меркла, и RSA были впервые открыты в английских спецслужбах, но не были ни опубликованы, ни запатентованы из-за секретности.

В России для шифрования с открытым ключом стандарт отсутствует, однако для электронной цифровой подписи (органически связанной с шифрованием с открытым ключом) принят ГОСТ Р 34.10-2001 (ГОСТ Р 34.10-2012), использующий криптографию на эллиптических кривых.

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

Относительно новым методом является вероятностное шифрование. Вероятностное шифрование предложили Шафи Гольдвассер (Goldwasser) и Сильвио Микэли (Micali). Шифрование было названо «вероятностным» в связи с тем, что один и тот же исходный текст при шифровании с использованием одного и того же ключа может преобразовываться в совершенно различные шифротексты. При использовании криптосистем с открытым ключом существует возможность подбора открытого текста сопоставлением перехваченного шифротекста с результатом шифрования. Вероятностное шифрование позволяет на порядки увеличить сложность такого вида атаки.

Чарльз Беннет (Charles Bennet) и Жиль Брассард (Gilles Brassard), опираясь на работу Стивена Уиснера (Stephen Wiesner), разработали теорию квантовой криптографии, которая базируется скорее на квантовой физике, нежели на математике. Процесс отправки и приёма информации выполняется посредством объектов квантовой механики (например, при помощи электронов в электрическом токе, или фотонов в линиях волоконно-оптической связи). Основанная на принципах квантовой механики, эта система, в отличие от обычной криптографии, теоретически позволяет гарантированно защитить информацию от злоумышленника, даже если тот обладает самой современной технологией и неограниченными вычислительными мощностями. На данный момент, разрабатываются только прототипы квантовых криптосистем.

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

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

 

Вопросы для самопроверки

 

1. Назовите основные этапы развития криптографии.