Русская Википедия:Полиалфавитный шифр
Полиалфавитный шифр (многоалфавитный шифр) — это совокупность шифров простой замены, которые используются для шифрования очередного символа открытого текста согласно некоторому правилу.
Суть полиалфавитного шифра заключается в циклическом применении нескольких моноалфавитных шифров к определённому числу букв шифруемого текста. Предположим, что имеется некоторое сообщение x1 , x2 , x3 , …, xn , …, x2n, …, которое необходимо зашифровать, а также для использования полиалфавитного шифра взяли n моноалфавитных шифров. В данном случае к первой букве применяется первый моноалфавитный шифр, ко второй букве — второй, к третьей — третий, …, к n-ой букве — n-ый, а к (n+1)-ой вновь первый, и так далее, пока все сообщение не будет зашифровано. Таким образом, получается довольно-таки сложная последовательность, вскрыть которую сложнее нежели моноалфавитный шифр. Важным эффектом, достигаемым при использовании полиалфавитного шифра, является маскировка частот появления тех или иных букв в тексте, чего лишены шифры простой замены.
Исторические сведения
История криптоанализа берет своё начало с моноалфавитных шифров. Данный шифр обеспечивал необходимую секретность передаваемым сообщениям до тех пор, пока развитие частотного криптоанализа не разрушило его стойкость. Первым слабость таких шифров к частотному криптоанализу показал ещё в IX веке арабский философ и математик Аль-Кинди в своем труде «Манускрипт о дешифровке криптографических сообщений»[1]. В Европе моноалфавитные шифры пользовались большой популярностью вплоть до XV века. Ярким примером ненадежности этого шифра послужила казнь Марии Стюарт в 1587 году. Доказательством заговора против английской королевы Елизаветы стало расшифрованное Томасом Фелиппесом письмо Марии Стюарт к Энтони Бабингтону[1].
Таким образом, возникла потребность в создании более совершенного способа защиты информации, и на смену моноалфавитным шифрам пришли полиалфавитные. В шестидесятых годах XV века итальянский учёный и архитектор Леон Баттиста Альберти (Шаблон:Lang-it), стремясь получить устойчивый к частотному криптоанализу шифр, одним из первых начал применять вместо одного секретного алфавита два или более, переходя от одного к другому по некоторому правилу[2]. Однако довести эту систему до полноценной предстояло его последователям[3].
Значительного результата достиг немецкий монах Иоганн Тритемий (Шаблон:Lang-lat). Согласно его методу очередная буква заменяется символом из собственного шифралфавита, причем каждый следующий алфавит получается из предыдущего путём сдвига на одну букву. Совокупность этих шифров сдвига, записанных по порядку один под другим, называется таблицей Тритемия[4].
В 1553 году итальянец Джованни Баттиста Белласо (Шаблон:Lang-it) в брошюре «Шифр синьора Джованни Белласо» (Шаблон:Lang-it) предложил усовершенствовать данный метод с помощью введения ключевого слова. Буквы этого слова последовательно записываются над шифруемым текстом, таким образом, каждая буква ключа указывает на определенный шифралфавит из таблицы Тритемия[5].
В то же время итальянский врач и учёный Джамбаттиста делла Порта (Шаблон:Lang-it) поставил под сомнение надежность полиалфавитных шифров. Анализируя методы шифрования, предложенные Тритемием и Белласо, он выявил некоторые закономерности, с помощью которых разработал способы вскрытия данных шифров. Однако Порта не смог распространить свои наблюдения на полиалфавитные шифры в целом, в связи с чем данный вид шифрования продолжил считаться надежным на протяжении следующих трехсот лет[5].
Следующим значимым представителем истории развития описываемых шифров считается французский криптограф Блез де Виженер (Шаблон:Lang-fr). Опираясь на труды своих предшественников, он разработал способ шифрования схожий с предложенным ранее Джованни Белласо. Основное отличие заключалось в том, как выбирается шифралфавит для очередной буквы. Виженер предложил использовать в качестве ключа какой-либо другой открытый текст. Данный метод шифрования, известный в наше время как шифр Виженера, он привел в своей работе «Трактат о шифрах» (Шаблон:Lang-fr) в 1585 году[4].
Несмотря на стойкость к криптоанализу того времени, полиалфавитные шифры долгое время не получали широкого распространения в связи со сложностью их использования. Для повседневных целей обычных людей было достаточным использование моноалфавитных шифров, а для военных и дипломатических целей государство большое внимание уделяло скорости и простоте шифрования. Для этого применялись некие промежуточные шифры, вскрытие которых требовало больше усилий по сравнению с моноалфавитными шифрами, но при этом их использование было проще полиалфавитных[3].
С развитием «Черных кабинетов» в странах Европы в XVIII веке все шифры моноалфавитной замены потеряли всякую надежность. Этот факт способствовал вынужденному переходу к использованию полиалфавитных шифров. Другой причиной популяризации более сложного вида шифрования стало развитие телеграфа и возникшая необходимость в защите сообщений от перехвата.[3]
В 1863 году Фридрих Касиски (Шаблон:Lang-de) нашел способ вскрытия шифра Виженера с коротким кодовым словом, использование которого было наиболее распространено. В случае, когда шифрование производилось с помощью соразмерного с открытым текстом ключа, кодовая фраза может быть подобрана при условии, что она состоит из осмысленных слов. Попытки изобрести новый стойкий к взлому шифр долгое время не приводили к успеху, поэтому криптографы придумывали такие реализации существующих полиалфавитных шифров, чтобы избежать их вскрытия с помощью метода Касиски и метода подбора кодового слова[3][4]. Например, майор армии США Джозеф Моборн (Шаблон:Lang-en) в конце Первой мировой войны изобрел шифрблокнот одноразового назначения. На каждую страницу блокнота записывалась последовательность из сотен случайных букв, которая использовалась в качестве одноразового ключа для шифруемого сообщения. Также создавался идентичный блокнот, с помощью которого осуществлялась дешифровка получателем сообщения. После использования соответствующая страница каждого блокнота уничтожалась. Однако многие реализации не получили широкого применения в связи со сложностями их использования[6].
На рубеже XIX века Томас Джефферсон (Шаблон:Lang-en) предпринял попытку механизировать процесс шифрования, создав одну из первых роторных машин (известную также как цилиндр Джефферсона), которая позволила облегчить использование полиалфавитных шифров замены. Наибольшее распространение роторные машины получили в XX веке[4][7]. Такие машины обеспечивали повышенную степень криптостойкости и увеличивали скорость шифрования, что было особенно важно во время военных действий. Среди наиболее известных роторных систем можно выделить немецкую машину «Enigma», американское устройство «Sigaba», а также машину «Турех», которая родом из Великобритании. С появлением ЭВМ в 1940-х гг. стало возможным вскрытие роторных криптосистем. Со временем полиалфавитные шифры отошли на второй план, а на смену им пришли новые более надежные методы шифрования[2].
Криптоанализ полиалфавитных шифров
Метод Касиски
Взлом полиалфавитного шифра в 1863 году в своей книге «Тайнопись и искусство дешифрования»(Шаблон:Lang-de) описал отставной офицер прусской армии Фридрих Касиски (Шаблон:Lang-de). Данный метод применим для шифров с коротким ключевым словом, так как основан на поиске повторяющихся последовательностей символов в шифротексте. Длина ключа определяет количество вариантов, которыми может быть зашифрована одна и та же последовательность в открытом тексте. Таким образом, можно предположить, что количество букв между повторяющимися последовательностями в шифротексте кратно длине кодового слова. Далее криптоаналитик определяет вероятное число символов в кодовом слове путём подбора общих делителей для всех интервалов между повторениями. На заключительном этапе первоначальный шифротекст рассматривается как несколько моноалфавитных шифров, к которым применяется частотный криптоанализ[3][8].
Этот метод взлома полиалфавитного шифра был разработан ещё в 1854 году Чарльзом Бэббиджем (Шаблон:Lang-en). Однако в связи с тем, что он не опубликовал результаты своего труда, об этом стало известно только в XX веке. Именно поэтому такого рода способ дешифровки связывают с именем Фридриха Касиски, а также носит название «Метод Касиски»[3].
Индекс совпадений
В 1920 году была опубликована выдающаяся монография под названием «Индекс совпадения и его применение в криптоанализе» (Шаблон:Lang-en)[9]. Её автором является известный криптоаналитик того времени Уильям Фридман (Шаблон:Lang-en). Он заинтересовался поиском способа вскрытия шифра Виженера со случайным длинным ключом[10]. В своем анализе он впервые обратился к статистическим методам, рассмотрев текст, как единый объект с взаимосвязанными элементами. Благодаря работам Фридмана появилось понятие «индекса совпадений», а криптоанализ обогатился средствами из категории статистических исследований[9].
Пример применения
В качестве примера зашифруем фразу «divert troops to east ridge» с помощью шифра Виженера, используя ключевое слово «WHITE». Изначально буквы кодового слова поочередно записываются над открытым текстом. Ключевое слово повторяется до того момента, пока каждой букве шифруемого сообщения не будет соответствовать определенная буква используемого ключа. Далее для получения шифротекста воспользуемся квадратом Виженера. Каждой букве ключевого слова ставится в соответствие строка, начинающаяся с той же буквы. Таким методом определяется шифралфавит, которым будет зашифрована каждая буква открытого текста. То есть для шифрования первого символа «d» используется 23-я строка квадрата Виженера. Следующий этап — нахождение буквы, которая стоит на пересечении столбца, начинающегося с «d», и соответствующей ей строкой-шифралфавитом. В данном случае это буква «Z», она и является первым символом шифротекста. Аналогичным образом поступаем с каждой буквой исходной фразы[3].
Чтобы расшифровать полученное сообщение, необходимо проделать те же действия, что и при зашифровке, с одним лишь отличием: теперь буква, которая находится на пересечении строки-шифралфавита и столбца, начинающегося с искомой буквы открытого текста, известна[3].
Примечания
Литература
- Книга:Kahn, D.: The Codebreakers
- Шаблон:Книга
- Шаблон:КнигаШаблон:Недоступная ссылка
- Шаблон:Книга
- Шаблон:Книга
