Трактат о шифрах

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

История создания

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

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

Трактат видного представителя итальянского Возрождения Леона Баттиста Альберти, посвящённый рассматриваемой теме, можно считать первым в истории источником для изучения новых подходов к криптографии.

Альберти — первый представитель новых идей в этой области. Он широко известен как яркий представитель итальянского Ренессанса, круг его интересов очень обширен. Он прослужил более 30 лет в папской канцелярии, что и заинтересовало его криптографией. К числу его работ относится трактат «О принципах шифров». Рукопись содержится в ватиканских архивах. Был осуществлён английский, итальянский перевод этого сочинения. Вместе с книгой, представленной на выставке в Мантуе, посвященной 590-летию со дня рождения Альберти, в декабре 1994 года был выпущен CD, содержащий историческое вступление, текст 12 сохранившихся рукописей сочинения и его переводы на различные языки.

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

Итак, в трактате содержатся как сведения о криптографии, так и о криптологии. Сам Альберти строго не разделял эти понятия. Однако в самом начале книги он описывает исследования не столько важные для шифрования, сколько для криптоанализа. Речь идёт о частотности различных гласных и согласных латинского языка, а также о частотности биграмм и положении гласных и согласных латинского языка. Альберти отметил, что на какой-либо латинской книге соотношение гласных к согласным будет 300 к 100.

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

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

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

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

И наконец, Альберти приводит свой собственный шифр.

Описание

«Диск Альберти» состоял из двух дисков — внешнего неподвижного (на нём были нанесены латинские буквы в алфавитном порядке и цифры 1, 2, 3, 4) и подвижного внутреннего диска, на котором буквы были переставлены. Диски крепились на одной оси так, чтобы внутренний мог вращаться. Окружность каждого диска разделена на 24 равные клетки. Скольжение алфавитов находится под контролем ключевых букв, включённых в тело криптограммы. Для того, чтобы расшифровать сообщение, написанное с использованием дисков Альберти, вы должны были иметь соответствующий алфавит на вашем внутреннем диске.

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

Ключом данного шифра являлся порядок расположения букв на внутреннем диске и его начальное положение относительно внешнего диска. Другим изобретением Альберти стали коды, он предложил заменять на упорядоченные двух-, трёх- и четырёх цифровые комбинации слоги, слова и целые предложения (всего таких комбинаций 336). После этого цифры перешифровывались многоалфавитной заменой. Как видим, диск — механическое устройство для осуществления простой замены. Изобретение такого устройства ещё не поясняет, почему Альберти признают отцом западноевропейской криптологии. Главная заслуга Альберти — использование не одного, а нескольких алфавитов, что затрудняет частотный анализ. Переключение с одного на другой алфавит Альберти предлагал делать через каждые 3-4 слова. Это делается поворотом внутреннего диска в ту или другую сторону на определённое число делений. Сигналом такого переключения служила заглавная буква. Без этой причины заглавные буквы в тексте не имели места быть. Сначала Альберти использовал два алфавита, потом больше. Таким образом, Альберти одним из первых выдвинул идею «двойного шифрования» — текст, полученный в результате первого шифрования, подвергался повторному шифрованию другим шифром. Идеи Альберти использовались при создании шифрмашин в первой половине XX века, некоторые из них использовались в разных странах до 1980-х годов.

Шифр Альберти не является периодическим. В XVI веке Джованни Баттиста делла Порта использовал систему ключевых слов для реализации шифра, который может рассматриваться как изменение шифра Альберти. Одно ключевое слово используется для формирования перестановки алфавита, другое ключевое слово используется, чтобы определить последовательность для нескольких алфавитов. Это техника, которая была названа «двойной шифр» была более точно описана как многоалфавитная. Техника перестановки Порта была основана на 2-мерной таблице, для примера вот вариант таблицы Порта на основе 26-символьного алфавита:

                                             Эквивалент внешнего диска:
                                  a b c d e f g h i j k l m n o p q r s t u v w x y z
                                0 A L B E R T I C P H D F G H J K M N O S U V W X Y Z
                                1 Z A L B E R T I C P H D F G H J K M N O S U V W X Y
                             N  2 Y Z A L B E R T I C P H D F G H J K M N O S U V W X
                             u  3 X Y Z A L B E R T I C P H D F G H J K M N O S U V W
                             m  4 W X Y Z A L B E R T I C P H D F G H J K M N O S U V
                             b  5 V W X Y Z A L B E R T I C P H D F G H J K M N O S U
                             e  6 U V W X Y Z A L B E R T I C P H D F G H J K M N O S
                             r  7 S U V W X Y Z A L B E R T I C P H D F G H J K M N O
                                8 O S U V W X Y Z A L B E R T I C P H D F G H J K M N
                             o  9 N O S U V W X Y Z A L B E R T I C P H D F G H J K M
                             f 10 M N O S U V W X Y Z A L B E R T I C P H D F G H J K
                               11 K M N O S U V W X Y Z A L B E R T I C P H D F G H J
                             S 12 J K M N O S U V W X Y Z A L B E R T I C P H D F G H
                             h 13 H J K M N O S U V W X Y Z A L B E R T I C P H D F G
                             i 14 G H J K M N O S U V W X Y Z A L B E R T I C P H D F
                             f 15 F G H J K M N O S U V W X Y Z A L B E R T I C P H D
                             t 16 D F G H J K M N O S U V W X Y Z A L B E R T I C P H
                             s 17 H D F G H J K M N O S U V W X Y Z A L B E R T I C P
                               18 P H D F G H J K M N O S U V W X Y Z A L B E R T I C
                               19 C P H D F G H J K M N O S U V W X Y Z A L B E R T I
                               20 I C P H D F G H J K M N O S U V W X Y Z A L B E R T
                               21 T I C P H D F G H J K M N O S U V W X Y Z A L B E R
                               22 R T I C P H D F G H J K M N O S U V W X Y Z A L B E
                               23 E R T I C P H D F G H J K M N O S U V W X Y Z A L B
                               24 B E R T I C P H D F G H J K M N O S U V W X Y Z A L
                               25 L B E R T I C P H D F G H J K M N O S U V W X Y Z A

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

Открытие нового класса шифров — шифров многоалфавитной замены — могло иметь важнейшее значение для совершенствования криптографических методов, однако сочинение Альберти не получило широкого распространения. Единственным неитальянским писателем XVI века, упоминавшим в своей работе трактат Альберти, был французский дипломат Блез де Виженер. Сведения о том, что Альберти действительно создал такой трактат, казались утерянными вплоть до второй половины XIX века, когда английский исследователь Р. Браун установил на основании изучения рукописей венецианских архивов, что Альберти действительно изобрёл новую систему шифрования.

Пример с использованием шифра Альберти

В качестве примера этого шифра зашифруем сообщение «this is a test of alberti» с помощью приведенной выше таблицы.

Начнём с написания второго ключевого слова, CATWALK, неоднократно под текстом.

                                                   this is a test of alberti
                                                   CATW AL K CATW AL KCATWAL

Теперь замените буквы ключевого слова с их числовым эквивалентом, где А = 0, В = 1, C = 2 и т. д.

                                    t--h--i--s  i--s  a  t--e--s--t  o--f  a--l--b--e--r--t--i
                                    2  0 19 22  0 11 10  2  0 19 22  0 11 10  2  0 19 22  0 11

Следующий символ, соответствующий координатам, определяется характером текста и значением индекса, (то есть (t, 2) = N, (h, 0) = C и т. д.)

                                                    this is a test of alberti
                                                    NCKW PC M NRZX JU MHLFVSX

Сообщение изменено до неузнаваемости. Также следует отметить, что частотный анализ не имеет смысла, поскольку, без соответствующих букв h, s, t и i оба были переведены на соответствующие буквы С и X, соответственно.

Расшифровка сообщений

Чтобы расшифровать тайное послание, выпишите зашифрованные символы и соответствующие им сдвиги.

                                    N--C--K--W  P--C  M  N--R--Z--X  J--U  M--H--L--F--V--S--X
                                    c--a--t--w  a--l  k  c--a--t--w  a--l  k--c--a--t--w--a--l
                                    2  0 19 22  0 11 10  2  0 19 22  0 11 10  2  0 19 22  0 11

Теперь вы можете посмотреть символы в таблице выше, чтобы получить исходное сообщение.

                                                    this is a test of alberti

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

Значение

Следует проанализировать ещё две особенности рассуждений Альберти о криптографии.

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

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

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