Полиалфавитный шифр

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

Суть полиалфавитного шифра заключается в циклическом применении нескольких моноалфавитных шифров к определённому числу букв шифруемого текста. Предположим, что имеется некоторое сообщение x₁ , x₂ , x₃ , …, x_n , …, x_2n, …, которое необходимо зашифровать, а также для использования полиалфавитного шифра взяли n моноалфавитных шифров. В данном случае к первой букве применяется первый моноалфавитный шифр, ко второй букве — второй, к третьей — третий, …, к n-ой букве — n-ый, а к (n+1)-ой вновь первый, и так далее, пока все сообщение не будет зашифровано. Таким образом, получается довольно-таки сложная последовательность, вскрыть которую сложнее нежели моноалфавитный шифр. Важным эффектом, достигаемым при использовании полиалфавитного шифра, является маскировка частот появления тех или иных букв в тексте, чего лишены шифры простой замены.

Исторические сведения

Одно из писем Энтони Бабингтона, 1586 год

История криптоанализа берет своё начало с моноалфавитных шифров. Данный шифр обеспечивал необходимую секретность передаваемым сообщениям до тех пор, пока развитие частотного криптоанализа не разрушило его стойкость. Первым слабость таких шифров к частотному криптоанализу показал ещё в IX веке арабский философ и математик Аль-Кинди в своем труде «Манускрипт о дешифровке криптографических сообщений». В Европе моноалфавитные шифры пользовались большой популярностью вплоть до XV века. Ярким примером ненадежности этого шифра послужила казнь Марии Стюарт в 1587 году. Доказательством заговора против английской королевы Елизаветы стало расшифрованное Томасом Фелиппесом письмо Марии Стюарт к Энтони Бабингтону.

Таким образом, возникла потребность в создании более совершенного способа защиты информации, и на смену моноалфавитным шифрам пришли полиалфавитные. В шестидесятых годах XV века итальянский учёный и архитектор Леон Баттиста Альберти (итал. Leone Battista Alberti), стремясь получить устойчивый к частотному криптоанализу шифр, одним из первых начал применять вместо одного секретного алфавита два или более, переходя от одного к другому по некоторому правилу. Однако довести эту систему до полноценной предстояло его последователям.

Значительного результата достиг немецкий монах Иоганн Тритемий (лат. Iohannes Trithemius). Согласно его методу очередная буква заменяется символом из собственного шифралфавита, причем каждый следующий алфавит получается из предыдущего путём сдвига на одну букву. Совокупность этих шифров сдвига, записанных по порядку один под другим, называется таблицей Тритемия.

La cifra del. Sig. Giovan Bastista Belaso, 1553

В 1553 году итальянец Джованни Баттиста Белласо (итал.  Giovan Battista Bellaso) в брошюре «Шифр синьора Джованни Белласо» (итал.  «La cifra del. Sig. Giovan Battista Belaso») предложил усовершенствовать данный метод с помощью введения ключевого слова. Буквы этого слова последовательно записываются над шифруемым текстом, таким образом, каждая буква ключа указывает на определенный шифралфавит из таблицы Тритемия.

Квадрат Виженера (tabula recta). Используется в процессе шифрования и дешифрования

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

Следующим значимым представителем истории развития описываемых шифров считается французский криптограф Блез де Виженер (фр.  Blaise de Vigenère). Опираясь на труды своих предшественников, он разработал способ шифрования схожий с предложенным ранее Джованни Белласо. Основное отличие заключалось в том, как выбирается шифралфавит для очередной буквы. Виженер предложил использовать в качестве ключа какой-либо другой открытый текст. Данный метод шифрования, известный в наше время как шифр Виженера, он привел в своей работе «Трактат о шифрах» (фр. «Traicté des Chiffres») в 1585 году.

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

С развитием «Черных кабинетов» в странах Европы в XVIII веке все шифры моноалфавитной замены потеряли всякую надежность. Этот факт способствовал вынужденному переходу к использованию полиалфавитных шифров. Другой причиной популяризации более сложного вида шифрования стало развитие телеграфа и возникшая необходимость в защите сообщений от перехвата.

В 1863 году Фридрих Касиски (нем.  Friedrich Wilhelm Kasiski) нашел способ вскрытия шифра Виженера с коротким кодовым словом, использование которого было наиболее распространено. В случае, когда шифрование производилось с помощью соразмерного с открытым текстом ключа, кодовая фраза может быть подобрана при условии, что она состоит из осмысленных слов. Попытки изобрести новый стойкий к взлому шифр долгое время не приводили к успеху, поэтому криптографы придумывали такие реализации существующих полиалфавитных шифров, чтобы избежать их вскрытия с помощью метода Касиски и метода подбора кодового слова. Например, майор армии США Джозеф Моборн (англ.  Joseph Mauborgne) в конце Первой мировой войны изобрел шифрблокнот одноразового назначения. На каждую страницу блокнота записывалась последовательность из сотен случайных букв, которая использовалась в качестве одноразового ключа для шифруемого сообщения. Также создавался идентичный блокнот, с помощью которого осуществлялась дешифровка получателем сообщения. После использования соответствующая страница каждого блокнота уничтожалась. Однако многие реализации не получили широкого применения в связи со сложностями их использования.

Цилиндр Джефферсона

На рубеже XIX века Томас Джефферсон (англ.  Thomas Jefferson) предпринял попытку механизировать процесс шифрования, создав одну из первых роторных машин (известную также как цилиндр Джефферсона), которая позволила облегчить использование полиалфавитных шифров замены. Наибольшее распространение роторные машины получили в XX веке. Такие машины обеспечивали повышенную степень криптостойкости и увеличивали скорость шифрования, что было особенно важно во время военных действий. Среди наиболее известных роторных систем можно выделить немецкую машину «Enigma», американское устройство «Sigaba», а также машину «Турех», которая родом из Великобритании. С появлением ЭВМ в 1940-х гг. стало возможным вскрытие роторных криптосистем. Со временем полиалфавитные шифры отошли на второй план, а на смену им пришли новые более надежные методы шифрования.

Криптоанализ полиалфавитных шифров

Основная статья: Криптоанализ полиалфавитных шифров

Метод Касиски

Взлом полиалфавитного шифра в 1863 году в своей книге «Тайнопись и искусство дешифрования»(нем. «Die Geheimschriften und die Dechiffrirkunst») описал отставной офицер прусской армии Фридрих Касиски (нем. Friedrich Kasiski). Данный метод применим для шифров с коротким ключевым словом, так как основан на поиске повторяющихся последовательностей символов в шифротексте. Длина ключа определяет количество вариантов, которыми может быть зашифрована одна и та же последовательность в открытом тексте. Таким образом, можно предположить, что количество букв между повторяющимися последовательностями в шифротексте кратно длине кодового слова. Далее криптоаналитик определяет вероятное число символов в кодовом слове путём подбора общих делителей для всех интервалов между повторениями. На заключительном этапе первоначальный шифротекст рассматривается как несколько моноалфавитных шифров, к которым применяется частотный криптоанализ.

Этот метод взлома полиалфавитного шифра был разработан ещё в 1854 году Чарльзом Бэббиджем (англ. Charles Babbage). Однако в связи с тем, что он не опубликовал результаты своего труда, об этом стало известно только в XX веке. Именно поэтому такого рода способ дешифровки связывают с именем Фридриха Касиски, а также носит название «Метод Касиски».

Уильям Фридман

Индекс совпадений

В 1920 году была опубликована выдающаяся монография под названием «Индекс совпадения и его применение в криптоанализе» (англ. «Index of Coincidence and Its Applications in Cryptography»). Её автором является известный криптоаналитик того времени Уильям Фридман (англ. William Frederick Friedman). Он заинтересовался поиском способа вскрытия шифра Виженера со случайным длинным ключом. В своем анализе он впервые обратился к статистическим методам, рассмотрев текст, как единый объект с взаимосвязанными элементами. Благодаря работам Фридмана появилось понятие «индекса совпадений», а криптоанализ обогатился средствами из категории статистических исследований.

Пример применения

Квадрат Виженера. Синим цветом выделены используемые шифралфавиты, определяемые ключевым словом «WHITE». Зелёным цветом выделен открытый алфавит.

В качестве примера зашифруем фразу «divert troops to east ridge» с помощью шифра Виженера, используя ключевое слово «WHITE». Изначально буквы кодового слова поочередно записываются над открытым текстом. Ключевое слово повторяется до того момента, пока каждой букве шифруемого сообщения не будет соответствовать определенная буква используемого ключа. Далее для получения шифротекста воспользуемся квадратом Виженера. Каждой букве ключевого слова ставится в соответствие строка, начинающаяся с той же буквы. Таким методом определяется шифралфавит, которым будет зашифрована каждая буква открытого текста. То есть для шифрования первого символа «d» используется 23-я строка квадрата Виженера. Следующий этап — нахождение буквы, которая стоит на пересечении столбца, начинающегося с «d», и соответствующей ей строкой-шифралфавитом. В данном случае это буква «Z», она и является первым символом шифротекста. Аналогичным образом поступаем с каждой буквой исходной фразы.

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

Литература

• David Kahn. The Codebreakers — The Story of Secret Writing. — New York: Charles Scribner's Sons, 1967. — 473 с. — ISBN 0-684-83130-9.
• Сингх С. Книга шифров:тайная история шифров и их расшифровки = The Code Book: The Secret History of Codes and Code-breaking / пер. с англ. А. Галыгин. — Москва: АСТ, Астрель, 2009. — Т. 2. — 447 с. — ISBN 978-5-17-038477-8.
• Fred Cohen. A Short History of Cryptography // Introductory Information Protection. — 1987. — ISBN 1-878109-05-7. (недоступная ссылка)
• Яковлев А. В., Безбогов А. А., Родин В. В., Шамкин В. Н. Криптографическая защита информации. — Тамбов: Издательство ТГТУ, 2006. — 140 с. — 100 экз. — ISBN 5-8265-0503-6.
• Алферов А. П., Зубов А. Ю. , Кузьмин А. С., Черёмушкин А. В. Основы криптографии / под ред. Т. А. Денисовой. — 2-е. — Москва: Гелиос АРВ, 2002. — 480 с. — 3000 экз. — ISBN 5-85438-025-0.