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

Потребность разработки полиалфавитных шифров возникла в 850 году после работы Аль-Кинди «Трактат о дешифровке криптографических сообщений». Совместно с методами криптографии появились и методы криптоанализа. Оба направления изучают одни и те же объекты, но с разных сторон.

История создания полиалфавитного шифра

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

Далее некоторые доработки, основываясь на работах Альберти, сделал немецкий аббат Иоганн Тритемий, автор первой печатной книги по криптографии изданной в 1518 году «Полиграфия». Над шифром также потрудился итальянский учёный Джованни Порта, который помимо создания шифров также занимался и взломом полиалфавитных шифров. Когда Порта было 28 лет (1563), он написал свою книгу «О тайной переписке», в которой описал все известные системы шифров.

Окончательный вид шифру, над которым трудились на протяжении столетия в разное время Альберти, Тритемий и Порта, предал французский дипломат Блез де Виженер. Сегодня этот полиалфавитный шифр всем известен как шифр Виженера. В силу своей работы Виженеру приходилось постоянно сталкиваться с шифровками, но вплотную заняться изучением криптографии у него не было времени до выхода на пенсию. Так в 1586 году Виженер представил комиссии Генриха III во Франции окончательный вариант шифра. Известный писатель и математик Чарльз Лютвидж Доджсон назвал шифр Виженера невзламываемым в своей статье «Алфавитный шифр» (англ. The Alphabet Cipher); таковым этот шифр считали ещё 300 лет.

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

Криптоанализ шифра Виженера

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

Шифр Виженера достаточно прост для использования в полевых условиях, особенно если применяются шифровальные диски. Например, конфедераты использовали медный шифровальный диск для шифра Виженера в ходе Гражданской войны в США. Послания Конфедерации были далеки от секретных, и их противники регулярно взламывали сообщения. Основной уязвимостью командования Конфедерации было то, что они использовали только три ключевых словосочетания: «Manchester Bluff», «Complete Victory» и — так как война подходила к концу — «Come Retribution».

Анализ Бэббиджа и Касиски

С разницей в несколько лет над разработкой метода дешифровки работали математики Чарльз Бэббидж и Фридрих Касиски. Результаты их работ почти одинаковые, за исключением того, что Касиски дал строгую формулировку взлома шифра Виженера, тогда как взлом Бэббиджа остался только на страницах его дневника.

Бэббидж

Английский математик Чарльз Бэббидж был разносторонне развитой личностью, работал во многих областях науки и техники. К тому времени, когда он взялся за шифр Виженера, многие криптоаналитики уже отказались от попыток его дешифровать. Толчок к исследованию дал спор с дантистом из Бристоля Дж. Твейтсом в 1854 году. Последний утверждал, что создал новый шифр, который невозможно взломать, и пытался его запатентовать. Бэббидж утверждал, что данный шифр уже существует несколько столетий. Процесс спора привел Бэббиджа к заключению, что нужно попытаться вскрыть шифр Виженера.

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

Успеха во взломе шифра Виженера Бэббидж добился в том же 1854 году, однако не опубликовал своих изысканий, и об открытии никто не узнал. Этот факт стал известен только в XX веке, когда ученые разбирали многочисленные заметки Бэббиджа. Имеется две версии, почему Бэббидж не объявил о своем достижении. Первая версия заключается в том, что британская секретная служба потребовала от Бэббиджа сохранения в тайне своей работы, поскольку она давала Британии явное преимущество над Россией — её противником в Крымской войне. Вторая версия состоит в том, что «была у него такая привычка — бросать незавершенными значительные и многообещающие начинания и не сообщать о своих открытиях».

Касиски

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

Анализ Фридмана

Полковник Фэбиан после начала войны США против Германии передал свою криптографическую лабораторию правительству в распоряжение. Уильям Фредерик Фридман отвечал за подготовку разведывательных войск, а одним из его ассистентов была его жена — криптограф Элизабет Фридман. К концу 1917 года Фридманом уже был заложен фундамент в виде 7 монографий по криптографии, который стал толчком для более важных открытий. Так, в 1920 году выходит работа The Riverbank Publications, которая считается основополагающей в этой дисциплине. В этом же году выходит одна из самых важных публикации в истории криптографии The Index of Coincidence and Its Applications in Cryptography. В этой работе Фридман вводит понятие «индекс совпадений» и предлагает методику расчёта совпадений. В смежных публикация Фридман описывает метод определения периода гаммы в шифре Виженера, а также представляет бесключевой метод дешифрирования при использовании неравновероятной гаммы (тест Фридмана, 1925). Это была первая успешная демонстрация вероятностно-статистических методов в криптографии.

Литература

• Кан, Дэвид. Взломщики кодов = The Codebreakers: The Story of Secret Writing / Перевод А. Ключевского. — М.: Центрполиграф, 2000. — 186 с. — ISBN 5-227-00678-4.
• Сингх, Саймон. Книга шифров: Тайная история шифров и их расшифровки = The Code Book / Перевод А. Галыгина. — М.: ООО «Издательство Астрель», 2006. — С. 62—110. — 447 с. — ISBN 978-5-271-14453-0.
• Kahate, Atuk. Cryptography and Network Security. — 8th ed. — Tata McGraw-Hill Publishing Company Ltd, 2006. — P. 36, 58. — ISBN 0-07-049483-5.

Ссылки

• Alberti, Leone Battista. De Componendis Cyfris  (неопр.). Ars Cryptographica (1466). — Оригинальный текст (лат.). Дата обращения: 2 июня 2013. Архивировано 2 июня 2013 года.