Криптоанализ полиалфавитных шифров
Потребность разработки полиалфавитных шифров возникла в 850 году после работы Аль-Кинди «Трактат о дешифровке криптографических сообщений». Совместно с методами криптографии появились и методы криптоанализа. Оба направления изучают одни и те же объекты, но с разных сторон.
История создания полиалфавитного шифра
[править | править код]Шифр простой замены долгое время был достаточен для обеспечения секретности. Но к началу XV века, когда многие криптоаналитики того времени уже легко взламывали любые сообщения с шифром простой замены, нужно было искать более надёжное шифрование. Разработкой более стойкого шифра занялся художник, композитор, поэт и философ Леон Баттист Альберти. С подачи своего друга Леонардо Дато, служащего секретарем у папы Римского, Альберти заинтересовала идея создания нового шифра. В своей книге «Трактат о шифрах» (1466) Альберти предложил использовать для шифрования не один шифроалфавит, а два или более. При шифровании один шифроалфавит сменял другой[1].
Далее некоторые доработки, основываясь на работах Альберти, сделал немецкий аббат Иоганн Тритемий, автор первой печатной книги по криптографии изданной в 1518 году «Полиграфия». Над шифром также потрудился итальянский учёный Джованни Порта, который помимо создания шифров также занимался и взломом полиалфавитных шифров. Когда Порта было 28 лет (1563), он написал свою книгу «О тайной переписке», в которой описал все известные системы шифров.
Окончательный вид шифру, над которым трудились на протяжении столетия в разное время Альберти, Тритемий и Порта, предал французский дипломат Блез де Виженер. Сегодня этот полиалфавитный шифр всем известен как шифр Виженера. В силу своей работы Виженеру приходилось постоянно сталкиваться с шифровками, но вплотную заняться изучением криптографии у него не было времени до выхода на пенсию. Так в 1586 году Виженер представил комиссии Генриха III во Франции окончательный вариант шифра. Известный писатель и математик Чарльз Лютвидж Доджсон назвал шифр Виженера невзламываемым в своей статье «Алфавитный шифр» (англ. The Alphabet Cipher); таковым этот шифр считали ещё 300 лет.
Шифр Виженера всё же не пользовался столь высокой популярностью, как шифр замены. И тому была следующая причина: для пользования шифром Виженера без современных компьютеров и специализированной техники необходимо было тратить часы для расшифровки и шифровки сообщений. Потому пользовались популярностью так называемые омофонические шифры, которые были более просты в использовании, хотя и не так надёжны, как шифр Виженера.
Криптоанализ шифра Виженера
[править | править код]Шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому. Это представление было опровергнуто после того, как Касиски полностью взломал шифр в XIX веке, хотя известны случаи взлома этого шифра некоторыми опытными криптоаналитиками ещё в XVI веке.
Шифр Виженера достаточно прост для использования в полевых условиях, особенно если применяются шифровальные диски. Например, конфедераты использовали медный шифровальный диск для шифра Виженера в ходе Гражданской войны в США. Послания Конфедерации были далеки от секретных, и их противники регулярно взламывали сообщения. Основной уязвимостью командования Конфедерации было то, что они использовали только три ключевых словосочетания: «Manchester Bluff», «Complete Victory» и — так как война подходила к концу — «Come Retribution».
Анализ Бэббиджа и Касиски
[править | править код]С разницей в несколько лет над разработкой метода дешифровки работали математики Чарльз Бэббидж и Фридрих Касиски. Результаты их работ почти одинаковые, за исключением того, что Касиски дал строгую формулировку взлома шифра Виженера, тогда как взлом Бэббиджа остался только на страницах его дневника.
Бэббидж
[править | править код]Английский математик Чарльз Бэббидж был разносторонне развитой личностью, работал во многих областях науки и техники. К тому времени, когда он взялся за шифр Виженера, многие криптоаналитики уже отказались от попыток его дешифровать. Толчок к исследованию дал спор с дантистом из Бристоля Дж. Твейтсом в 1854 году. Последний утверждал, что создал новый шифр, который невозможно взломать, и пытался его запатентовать. Бэббидж утверждал, что данный шифр уже существует несколько столетий. Процесс спора привел Бэббиджа к заключению, что нужно попытаться вскрыть шифр Виженера.
Сложность шифра заключается в том, что каждая буква может быть закодирована несколькими буквами нового алфавита — следовательно, и изначально одинаковые слова могут выглядеть по-разному. Но если слово в тексте встречается несколько раз, то существует вероятность того, что шифрокод этого слова в некоторых случаях будет одинаковым. Исходя из этого предположения, Бэббидж начал свою работу.
Успеха во взломе шифра Виженера Бэббидж добился в том же 1854 году, однако не опубликовал своих изысканий, и об открытии никто не узнал. Этот факт стал известен только в XX веке, когда ученые разбирали многочисленные заметки Бэббиджа. Имеется две версии, почему Бэббидж не объявил о своем достижении. Первая версия заключается в том, что британская секретная служба потребовала от Бэббиджа сохранения в тайне своей работы, поскольку она давала Британии явное преимущество над Россией — её противником в Крымской войне. Вторая версия состоит в том, что «была у него такая привычка — бросать незавершенными значительные и многообещающие начинания и не сообщать о своих открытиях»[2].
Касиски
[править | править код]Независимо от Бэббиджа способ взлома шифра Виженера был найден Фридрихом Вильгельмом Касиски, который опубликовал его в 1863 год в книге «Die Geheimschriften und die Dechiffrirkunst» («Тайнопись и искусство дешифрования»). Данная публикация была в то время единственной, в которой описывались алгоритмы взлома полиалфавитных шифров. Её можно считать отправной точкой, в истории взлома данного типа шифров. Алгоритм взлома сегодня известен как метод Касиски.
Анализ Фридмана
[править | править код]Полковник Фэбиан после начала войны США против Германии передал свою криптографическую лабораторию правительству в распоряжение. Уильям Фредерик Фридман отвечал за подготовку разведывательных войск, а одним из его ассистентов была его жена — криптограф Элизабет Фридман. К концу 1917 года Фридманом уже был заложен фундамент в виде 7 монографий по криптографии, который стал толчком для более важных открытий. Так, в 1920 году выходит работа The Riverbank Publications, которая считается основополагающей в этой дисциплине. В этом же году выходит одна из самых важных публикации в истории криптографии The Index of Coincidence and Its Applications in Cryptography. В этой работе Фридман вводит понятие «индекс совпадений» и предлагает методику расчёта совпадений. В смежных публикация Фридман описывает метод определения периода гаммы в шифре Виженера, а также представляет бесключевой метод дешифрирования при использовании неравновероятной гаммы (тест Фридмана, 1925). Это была первая успешная демонстрация вероятностно-статистических методов в криптографии[3].
Примечания
[править | править код]- ↑ Alberti, 1466.
- ↑ Сингх С. Книга шифров: Тайная история шифров и их расшифровки. — М.: «Астрель», 2006.
- ↑ Кан, 2000, с. 111—115.
Литература
[править | править код]- Кан, Дэвид. Взломщики кодов = 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 года.