08-10-2023
Потребность разработки полиалфавитных шифров возникла в 850 году после работы Аль-Кинди «Трактат о дешифровке криптографических сообщений». Совместно с методами криптографии появились и методы криптоанализа. Оба направления изучают одни и те же объекты, но с разных сторон.
Шифр простой замены долгое время был достаточен для обеспечения секретности. Но к началу XV века, когда многие криптоаналитики того времени уже легко взламывали любые сообщения с шифром простой замены, нужно было искать более надежное шифрование. Разработкой более стойкого шифра занялся художник, композитор, поэт и философ Леон Баттист Альберти. С подачи своего друга Леонардо Дато, служащего секретарем у папы Римского, Альберти заинтересовала идея создания нового шифра. В своей книге «Трактат о шифрах» (1466) Альберти предложил использовать для шифрования не один шифроалфавит, а два или более. При шифровании один шифроалфавит сменял другой[1].
Далее некоторые доработки, основываясь на работах Альберти, сделал немецкий аббат Иоганн Тритемий, автор первой печатной книги по криптографии изданной в 1518 году «Полиграфия». Над шифром также потрудился итальянский ученный Джованни Порта, который помимо создания шифров также занимался и взломом полиалфавитных шифров. Когда Порта было 28 лет (1563), он написал свою книгу «О тайной переписке», в которой описал все известные системы шифров.
Окончательный вид шифру, над которым трудились на протяжении столетия в разное время Альберти, Тритемий и Порта, предал французский дипломат Блез де Виженер. Сегодня этот полиалфавитный шифр всем известен как шифр Виженера. В силу своей работы Виженеру приходилось постоянно сталкиваться с шифровками, но вплотную заняться изучением криптографии у него не было времени до выхода на пенсию. Так в 1586 году Виженер представил комиссии Генриха III во Франции окончательный вариант шифра. Известный писатель и математик Чарльз Лютвидж Доджсон назвал шифр Виженера невзламываемым в своей статье «Алфавитный шифр» (англ. The Alphabet Cipher); таковым этот шифр считали ещё 300 лет.
Шифр Виженера всё же не пользовался столь высокой популярностью, как шифр замены. И тому была следующая причина: для пользования шифром Виженера без современных компьютеров и специализированной техники необходимо было тратить часы для расшифровки и шифровки сообщений. Потому пользовались популярностью так называемые омофонические шифры, которые были более просты в использовании, хотя и не так надёжны, как шифр Виженера.
Шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому. Это представление было опровергнуто после того, как Касиски полностью взломал шифр в XIX веке, хотя известны случаи взлома этого шифра некоторыми опытными криптоаналитиками ещё в XVI веке.
Шифр Виженера достаточно прост для использования в полевых условиях, особенно если применяются шифровальные диски. Например, конфедераты использовали медный шифровальный диск для шифра Виженера в ходе Гражданской войны в США. Послания Конфедерации были далеки от секретных, и их противники регулярно взламывали сообщения. Основной уязвимостью командования Конфедерации было то, что они использовали только три ключевых словосочетания: «Manchester Bluff», «Complete Victory» и — так как война подходила к концу — «Come Retribution».
С разницей в полвека над разработкой метода дешифрации трудились сначала Чарльз Бэббидж, затем Фридрих Касиски. Результаты их работ почти одинаковые, за исключением того, что Касиски дал строгую формулировку взлома шифра Виженера, тогда как взлом Бэббиджа остался только на страницах его дневника.
Наиболее любопытная фигура в криптоанализе XIX века, пожалуй, является Чарльз Бэббидж, английский гений, известный как разработчик прототипа современного компьютера. Бэббидж был разносторонне развитой личностью, он имеет научные достижения во многих областях науки и техники. Но его достижения в криптографии остались без внимания, наверное потому что как гений он редко доводил свои начинания до финала.
Также как и Альберти, Бэббиджа в криптографию привел его друг астроном Джон Гершель. После признания Бэббиджа в Лондоне, как искусного криптоаналитика, он стал получать различные заказы. Он помог расшифровать записи первого королевского астронома Англии, разгадывал шифр жены Карла I, участвовал в судебных разбирательствах. Все его работы он использовал в своей книге «Основные принципы дешифрования»: в ней должны были содержаться все виды шифров, и каждому прилагался пример дешифровки и упражнение читателю. К сожалению, книга не вышла в печать.
К тому времени когда Бэббидж взялся за шифр Виженера, многие криптоаналитики отказались от попыток его дешифровать. Толчок к исследованию дал спор с дантистом из Бристоля Холом Бруком Твейтсом. Твейтс утверждал, что создал новый шифр, который невозможно взломать, и пытался его запатентовать. Бэббидж в свою очередь утверждал, что данный шифр уже существует несколько столетий. Процесс спора привел Бэббиджа к заключению, что нужно попытаться вскрыть шифр Виженера.
Сложность шифра заключается в том, что каждая буква может быть закодирована несколькими буквами нового алфавита — следовательно, и изначально одинаковые слова могут выглядеть по-разному. Но если слово в тексте встречается несколько раз, то существует вероятность того, что шифрокод этого слова в некоторых случаях будет одинаковым. На этом предположении Бэббидж начал свою работу. И сделал всё то же, что и присвоено Касиски, только ничего не запатентовал.
Помимо того, что Бэббидж просто поленился закончить свой труд, есть ещё две версии того, почему этого он не сделал. Первая версия заключается в том, что Бэббидж сделал свое открытие вскоре после того, как разразилась крымская война. Это открытие давало Британии явное преимущество над Россией, её противником. Вполне возможно, что британская секретная служба потребовала от Бэббиджа, чтобы он сохранил свою работу в секрете, тем самым обеспечив себе девятилетнюю фору перед остальным миром.
Вторая же версия немного корыстная, но всё же это версия. Сейчас всем известна компания денежных переводов Western Union, которая существовала также и в XIX веке. Денежные переводы передавались телеграммами и шифровались шифром Виженера. Бэббидж как раз в то время взломал шифр Виженера. Почему он утаил свое открытие? Возможно, он как-то этим воспользовался? Ответы на эти вопросы мы не знаем. Как не знаем, что открывают и как этим пользуются наши современные «Бэббиджи».
В 1863 году Касиски опубликовал свою 95-страничную книгу по криптографии «Тайнопись и искусство дешифрования» (нем. Die Geheimschriften und die Dechiffrierkunst, в которой изложил свою методику взлома шифра Виженера. Данная публикация была в то время единственная, в которой описывались алгоритмы взлома полиалфавитных шифров. Её можно считать отправной точкой, в истории взлома данного типа шифров. Алгоритм взлома сегодня известен как метод Касиски. Как и большинство великих людей, Фридрих Касиски умер, не осознавая, какой прорыв он совершил.
Спустя годы историки обнаружили схожесть алгоритмов, записанных в дневниках Бэббиджа, и метода Касиски.
Полковник Фэбиан после начала войны США против Германии передал свою криптографическую лабораторию правительству в распоряжение. Уильям Фредерик Фридман отвечал за подготовку разведывательных войск, а одним из его ассистентов была его жена — криптограф Элизабет Фридман. К концу 1917 года Фридманом уже был заложен фундамент в виде 7 монографий по криптографии, который стал толчком для более важных открытий. Так, в 1920 году выходит работа The Riverbank Publications, которая считается основополагающей в этой дисциплине. В этом же году выходит одна из самых важных публикации в истории криптографии The Index of Coincidence and Its Applications in Cryptography. В этой работе Фридман вводит понятие «индекс совпадений» и предлагает методику расчёта совпадений. В смежных публикация Фридман описывает метод определения периода гаммы в шифре Виженера, а также представляет бесключевой метод дешифрирования при использовании неравновероятной гаммы (тест Фридмана, 1925). Это была первая успешная демонстрация вероятностно-статистических методов в криптографии[2].
Криптоанализ полиалфавитных шифров.