Полиалфавитные шифры: история и развитие

Введение

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

История

В работе Аль Калкашанди (1355–1418), основанной на более ранней работе Ибн аль-Дурайима (1312–1359), содержалось первое опубликованное обсуждение подстановки и перестановки шифров, а также первое описание полиалфавитного шифра, в котором каждой букве открытого текста присваивается более одного заместителя. Однако утверждается, что полиалфавитные шифры могли быть разработаны арабским криптологом Аль Кинди (801–873) за столетия до этого. Шифр Альберти, созданный Леоном Баттистой Альберти около 1467 года, был ранним полиалфавитным шифром. Альберти использовал смешанный алфавит для шифрования сообщения, но при желании переключался на другой алфавит, указывая это включением в шифротекст прописной буквы или числа. Для этого шифрования Альберти использовал декодирующее устройство – свой шифровальный диск, который реализовывал полиалфавитную подстановку со смешанными алфавитами. Иоганн Тритемий – в своей книге Polygraphiae libri sex (Шесть книг о полиграфии), опубликованной в 1518 году после его смерти, – изобрел полиалфавитный шифр с прогрессивным ключом, названный шифром Тритемия. В отличие от шифра Альберти, который переключал алфавиты через случайные интервалы, Тритемий переключал алфавиты для каждой буквы сообщения. Он начал с tabula recta – таблицы, представляющей собой квадрат с 26 буквами (хотя Тритемий, писавший на латыни, использовал 24 буквы). Каждый алфавит был сдвинут на одну букву влево от предыдущего, и начинался снова с A после достижения Z (см. таблицу). Идея Тритемия заключалась в шифровании первой буквы сообщения с использованием первого сдвинутого алфавита, так что A становилось B, B – C и т.д. Вторая буква сообщения шифровалась с использованием второго сдвинутого алфавита и так далее. Шифровальный диск Альберти реализовывал ту же схему. Он имел два алфавита: один на неподвижном внешнем кольце, а другой – на вращающемся диске. Буква шифровалась путем поиска этой буквы на внешнем кольце и кодирования ее буквой, находящейся под ней на диске. Диск начинался с A под B, и пользователь поворачивал диск на одну букву после шифрования каждой буквы. Шифр был тривиальным для взлома, а аппаратная реализация Альберти не намного сложнее. Прогрессия ключа в обоих случаях была плохо скрыта от злоумышленников. Даже реализация полиалфавитного шифра Альберти была довольно легкой для взлома (прописная буква – важная подсказка для криптоаналитика). На протяжении последующих нескольких сотен лет значимость использования множества алфавитов подстановки оставалась незамеченной почти всеми. Разработчики полиалфавитных шифров, по-видимому, сосредотачивались на сокрытии выбора нескольких таких алфавитов (повторяя их по мере необходимости), а не на повышенной безопасности, которую можно было бы получить, используя множество алфавитов и не повторяя ни один из них. Принцип (особенно неограниченные дополнительные алфавиты подстановки Альберти) был крупным прорывом – самым значительным за несколько сотен лет с момента разработки частотного анализа. Разумная реализация была бы (и, когда она была достигнута, оказалась) значительно сложнее для взлома. Только в середине XIX века (в секретных работах Бэббиджа во время Крымской войны и в публичной публикации Фридриха Касиски, примерно эквивалентной его работе, несколько лет спустя) криптоанализ хорошо реализованных полиалфавитных шифров достиг каких-либо успехов. См. исследование Касиски.

The work of Al Qalqashandi (1355–1418), based on the earlier work of Ibn al Durayhim (1312–1359), contained the first published discussion of the substitution and transposition of ciphers, as well as the first description of a polyalphabetic cipher, in which each plaintext letter is assigned more than one substitute. However, it has been claimed that polyalphabetic ciphers may have been developed by the Arab cryptologist Al Kindi (801–873) centuries earlier. The Alberti cipher by Leon Battista Alberti around 1467 was an early polyalphabetic cipher. Alberti used a mixed alphabet to encrypt a message, but whenever he wanted to, he would switch to a different alphabet, indicating that he had done so by including an uppercase letter or a number in the cryptogram. For this encipherment Alberti used a decoder device, his cipher disk, which implemented a polyalphabetic substitution with mixed alphabets. Johannes Trithemius—in his book Polygraphiae libri sex (Six books of polygraphia), which was published in 1518 after his death—invented a progressive key polyalphabetic cipher called the Trithemius cipher. Unlike Alberti's cipher, which switched alphabets at random intervals, Trithemius switched alphabets for each letter of the message. He started with a tabula recta, a square with 26 letters in it (although Trithemius, writing in Latin, used 24 letters). Each alphabet was shifted one letter to the left from the one above it, and started again with A after reaching Z (see table). Trithemius's idea was to encipher the first letter of the message using the first shifted alphabet, so A became B, B became C, etc. The second letter of the message was enciphered using the second shifted alphabet, etc. Alberti's cipher disk implemented the same scheme. It had two alphabets, one on a fixed outer ring, and the other on the rotating disk. A letter is enciphered by looking for that letter on the outer ring, and encoding it as the letter underneath it on the disk. The disk started with A underneath B, and the user rotated the disk by one letter after encrypting each letter. The cipher was trivial to break, and Alberti's machine implementation not much more difficult. Key progression in both cases was poorly concealed from attackers. Even Alberti's implementation of his polyalphabetic cipher was rather easy to break (the capitalized letter is a major clue to the cryptanalyst). For most of the next several hundred years, the significance of using multiple substitution alphabets was missed by almost everyone. Polyalphabetic substitution cipher designers seem to have concentrated on obscuring the choice of a few such alphabets (repeating as needed), not on the increased security possible by using many and never repeating any. The principle (particularly Alberti's unlimited additional substitution alphabets) was a major advance—the most significant in the several hundred years since frequency analysis had been developed. A reasonable implementation would have been (and, when finally achieved, was) vastly harder to break. It was not until the mid 19th century (in Babbage's secret work during the Crimean War and Friedrich Kasiski's generally equivalent public disclosure some years later), that cryptanalysis of well implemented polyalphabetic ciphers got anywhere at all. See Kasiski examination.