От аль-Кинди до Керкгоффса
На Хабре уже вышло несколько десятков статей, рассказывающих о старинных шифрах и классической криптографии. Например, «Как закалялась сталь», «Элементарные шифры», «История первых шифров» или «Итальянский след». Интересующиеся могут легко найти и другие, это не трудно. В большинстве из них читателю наверняка встретятся моноалфавитные шифры типа шифра Цезаря, другие варианты шифров замены, перестановки или композиционные шифры. Когда только задумал написать эту статью, я решил представить в ней некоторые интересные оригинальные шифры, о которых ещё никто не писал на Хабре или же они были упомянуты буквально несколькими строками. С одной стороны, эта задача может показаться тривиальной, поскольку в криптологии за сотни лет накопилось множество самых разнообразных шифров, но такое впечатление обманчиво. Хотя книг и статей по истории криптографии очень много, большая их часть так или иначе описывает одни и те же шифры, и это печально. Десятки похожих описаний шифров Цезаря, Виженера, Плейфера (на самом деле Уитстона), Отендорфа и других постепенно переходят к диску Альберти и цилиндру Джефферсона, от которых уже рукой подать до Энигмы и её потомков. В любом случае чем тривиальней кажется материал, тем интересней сделать из него то, что не потеряется в ленте и вызовет какой-то положительный фидбэк. Ну что же, трудности созданы, осталось их героически преодолеть.
Сегодня криптология неразрывно связана с математикой, и чем дальше, тем больше. Текущие и разрабатываемые методы как криптографии, так и криптоанализа, используют всё более сложные алгоритмы и разделы математики, отчего порой небезосновательно кажется, что порог входа в криптологию очень высок, но это не совсем так. Конечно, без хоть какой-то математической базы сегодня в этой сфере делать совсем нечего, однако так было не всегда. Первые способы тайной передачи информации заключались в сокрытии самого сообщения. Эти методы не являются частью криптологии, сегодня их называют стеганографией. Очень приблизительно и грубо практика криптологии делится на две эпохи. Первая связана с периодом, когда основные инструменты шифрования и взлома кодов возникли из анализа языка, то есть больше относились к лингвистике, чем к математике. При этом большее внимание уделялось шифрованию отдельного сообщения. Вторую эпоху следует отсчитывать от начала военного использования телеграфа и заявления Огюста Керкгоффса о том, что необходимо сосредоточиться на криптографических системах, а не на отдельных секретных сообщениях, то есть по факту полностью отказаться от ручного шифрования сообщений.
Пожалуй, первые серьёзные попытки внедрения математики для взлома кодов предпринимались арабскими учёными ещё с VIII века. Это неудивительно, поскольку в те времена впереди планеты всей во многих областях и в математике, в частности, были именно они. Одновременно разрабатывались и новые методы шифрования для противодействия попыткам математического взлома кодов. Есть мнения, что бурное развитие отдельных наук и ремёсел в арабском мире было напрямую связано с исламскими религиозными запретами. В отличие от других вероисповеданий в исламе изобразительное искусство не получило широкого распространения и многие творческие порывы направлялись на другие области, в основном на литературу, каллиграфию, философию, астрономию и математику.
Аль-Кинди
Так ещё в VIII веке известный арабский учёный аль-Кинди написал трактат о дешифровке криптографических сообщений и составил первую известную таблицу частотности букв языкового алфавита, что также позволяет считать его отцом математической статистики. Его трактат является старейшей известной книгой по криптологии, опередившей любую другую более чем на 300 лет. Но совершенствование криптоанализа не остановилось на том, что впоследствии стало называться частотным анализом. Аль-Кинди также описал некоторые тонкости, позволяющие более эффективно проводить количественный и качественный анализ зашифрованных сообщений, исследуя множество вариантов шифрования, в том числе частые или невозможные ассоциации букв, идентификацию вероятных слов типа имён собственных или устойчивых выражений.
Такое систематическое изучение особенностей языка зародилось в процессе кодификации арабского языка, который был фундаментальным фактором культурного и административного объединения завоёванных территорий от долины Инда до Пиренейского полуострова. Желание усвоить все предыдущие знания потребовало обширной работы по переводу текстов с санскрита, греческого, сирийского и персидского языков, в том числе и часто встречавшихся зашифрованных вариантов. Это привело к написанию многочисленных трактатов по языковому анализу. Тот же лингвистический контекст привёл к созданию учёными основ алгебры, задуманной как труд по литературной классификации проблем естественного арабского языка. Именно эти работы стали одними из первых связей между криптологией и математикой. Такие политические и культурные императивы послужили основой для развития школы арабской криптологии, которая процветала примерно до XIV века.
Другой арабский учёный также отметился на криптологическом поприще. Ибн Дунайнир первым описал шифрование с использованием арифметики десятично-взвешенного числового алфавита. При этом применялась арабская алфавитная запись чисел — «абджадия» или «Хисаб аль-джамаль».
Несмотря на свою важность, этот метод шифрования был упущен из виду аль-Кинди в его трактате по криптоанализу несмотря на то, что он наверняка знал о нём. Этот достаточно старый метод шифрования, хорошо известный арабам на раннем этапе их цивилизации и позже практиковавшийся в других языках, таких как иврит, и представляет собой простую замену, при которой каждая буква заменяется одним символом во всей криптограмме. Однако учёный пошёл немного дальше и предложил интересную концепцию композиции в десятичном числовом алфавите, зависящем от площади с использованием общепринятых в то время единиц измерения. Подобные шифры сегодня называются композиционными, то есть предложенный составной метод шифрования делал криптограмму похожей на крестьянский финансовый земельный реестр. Она составлялась путём представления букв в виде размеров участков земли, имитируя внешнее подобие покупки, продажи или иных подобных сделок. Такое представление способствует сокрытию шифра и ещё больше затрудняет его криптоанализ.
Второй интересный метод сокрытия информации, который предложил ибн Дунайнир, заключался в кодировании сообщений посредством дактильной азбуки с использованием абджадии. В этом случае буквы заменяются числами, передаваемыми путем сгибания пальцев в определённой форме. Такой вид тайной связи часто использовался посвящёнными в присутствии лиц, для чьих ушей передаваемая информация не предназначалась.
Метод ибн Дунайнира основывался на представлении предполагаемого числа с помощью относительных конфигураций пальцев. Хотя опять же, по сути, это простая замена, метод шифрования ибн Дунайнира интересен по своему содержанию и эффекту. Его важность обусловлена прежде всего тем фактом, что он также поддаётся численной обработке посредством простейших арифметических операций и способен принимать более сложные формы. Как это может быть, представляется следующей моделью:
Численная обработка позволяет повысить сложность криптоанализа. Стоит подчеркнуть, что хотя в настоящее время в алгоритмах шифрования используется гораздо более сложная численная обработка, этот метод в принципе лежит в основе многих алгоритмов современной криптографии.
Несмотря на то, что он опирался на работы своих предшественников, ибн Дунайнир выделяется даже среди арабских криптологов. Он продемонстрировал сложные методы шифрования, такие как совместная реализация транспозиции и замены, которая используется и сегодня в алгоритмах блочного шифрования типа DES (о нем я писал ранее). Учёный предлагал широко использовать стеганографические методы в совокупности с шифрованием на основе абджадии, а также некоторые варианты физических шифровальных устройств. Вообще стоит отметить, что самые ранние случаи использования математических методов шифрования в Европе датируются периодом правления короля Франции Генриха IV, а это около четырёхсот лет спустя.
Криптография и ранее использовалась для сокрытия сообщений различными цивилизациями, в том числе древнеегипетской, китайской, индийской, месопотамской, греческой и римской. Но ни в одной из них не было никакого криптоанализа, существовала только криптография. Так как криптология состоит из криптографии и криптоанализа, вполне серьёзно можно утверждать, что она впервые сформировалась в рамках арабской цивилизации. В дальнейшем некоторые арабские произведения попали в Европу во времена крестовых походов и позже, а с точки зрения криптологии средневековая Европа была менее развита, чем арабо-мусульманская цивилизация. Большинство европейских методов оставались рудиментарными ещё долгое время. Хотя и среди них попадались интересные экземпляры, например «мальтийский крест».
В таком варианте буквы заменялись заключающими их формами внутри восьмиконечного мальтийского креста. Рыцари были убеждены, что тайны, окружающей эти малоизвестные символы, достаточно, чтобы обеспечить конфиденциальность их посланий. Такой вариант шифрования является одним из вариантов геометрически простых шифров подстановки, семейство которых сегодня принято называть масонским шифром или pigpen. Это всё ещё простой моноалфавитный шифр, отличающийся от своих собратьев исключительно тем, что вместо букв или цифр используются геометрические символы, а не буквы. Похожим образом шифровали сообщения в романе Артура Конана Дойла «Пляшущие человечки». Использование символов на самом деле никак не усложняет криптоанализ, а учитывая определённую хайповость тамплиеро-массонов сегодня, таким шифром никого не удивишь, если никак его не усложнить. В википедии имеется достаточно подробная статья.
Конечно, долгое время большинство европейских методов шифрования не имело к математике никакого отношения и по большей части являлось полиалфавитными шрифтами замены. Один из самых известных базировался на tabula recta Иоганна Тритемия, эдаком творчески переработанном шифре Цезаря. Однако следующий виток развития европейской криптологии связан с именем Антуана Россиньоля и так называемыми «номенклаторами», самым известным из которых и стал шифр Россиньоля или Великий шифр. Хотя существовали и другие номенклаторы, большая часть из которых являлись омофоническими шифрами, шифр Россиньоля таковым не был. Он использовался французской армией и дипломатами почти двести лет. Множество французских архивных документов, зашифрованных этим шифром, оставались нерасшифрованными ещё долгое время после отказа от использования Великого шифра, пока в конце XIX века французский криптоаналитик Этьен Базери его не вскрыл.
Как я упоминал в начале статьи, практика криптологии грубо делится на два временных периода. Первый больше связан с лингвистикой, шифрами замены и концентрацией на шифровании отдельного сообщения, а второй с формированием понятия о криптосистемах и отказом от ручного шифрования. Огюст Керкгоффс в 1883 году издал труд «Военная криптография», в котором описал свои взгляды на проектирование криптографических систем. Там же он и сформулировал свой принцип, который широко используется в современной криптографии, но это, как говорится, совсем другая история.
Так, шаг за шагом криптографические системы пришли к сложным механическим устройствам, а также к математическому анализу их работы, хотя по-настоящему криптология стала академической дисциплиной только после массового внедрения компьютеров и сетей, о чём вкратце я писал в прошлой статье. В любом случае даже несмотря на то, что времена классической криптографии давно прошли есть ещё много интересных историй, так или иначе связанных с криптологией, и многие из них не уступят захватывающему детективу. Продолжение следует…
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
