WikiDer > Шифр Виженера

Шифр Виженера назван в честь Блез де Виженера (на фото), хотя Джован Баттиста Беллазо изобрел его еще до того, как Виженер описал свой автоключ шифр.

Репродукция Конфедерацияс шифровальный диск используется в американская гражданская война на выставке в Национальный криптологический музей

В Шифр Виженера (Французское произношение:[viʒnɛːʁ]) является методом шифрование алфавитный текст, используя ряд переплетенных Шифры Цезаряна основе букв ключевого слова. Он использует форму полиалфавитная замена.^[1][2]

Впервые описано Джован Баттиста Беллазо в 1553 году шифр легко понять и внедрить, но он сопротивлялся всем попыткам его взломать до 1863 года, три века спустя. Это заслужило описание le chiffre unéchiffrable (Французский для «неразборчивого шифра»). Многие люди пытались реализовать схемы шифрования, которые по сути являются шифрами Виженера.^[3] В 1863 г. Фридрих Касиски был первым, кто опубликовал общий метод расшифровки шифров Виженера.

В 19 веке схему ошибочно приписали Блез де Виженера (1523–1596), и поэтому приобрела свое нынешнее название.^[4]

История

Первое хорошо задокументированное описание полиалфавитного шифра было сделано Леон Баттиста Альберти около 1467 г. и использовал металл шифровальный диск для переключения между шифралфавитами. Система Альберти переключала алфавиты только после нескольких слов, и переключатели указывались записью буквы соответствующего алфавита в зашифрованном тексте. Позже, Йоханнес Тритемиус, в его работе Полиграфии (который был завершен в виде рукописи в 1508 году, но впервые опубликован в 1518 году),^[5] изобрел tabula recta, критический компонент шифра Виженера.^[6] В Шифр Тритемияоднако предоставил прогрессивную, довольно жесткую и предсказуемую систему переключения между шифралфавитами.^{[примечание 1]}

В 1586 году Блез де Виженер опубликовал тип полиалфавитного шифра, названный автоключ шифр - потому что его ключ основан на исходном открытом тексте - в суде Генрих III Франции.^[7] Однако шифр, теперь известный как шифр Виженера, первоначально описан Джован Баттиста Беллазо в его книге 1553 года La cifra del Sig. Джован Баттиста Беллазо.^[8] Он построил на tabula recta Тритемия, но добавил повторяющийся «контрзнак» ( ключ), чтобы переключать шифралфавиты каждую букву. В то время как Альберти и Тритемиус использовали фиксированный шаблон замен, схема Белласо означала, что шаблон замен можно легко изменить, просто выбрав новый ключ. Ключи обычно представляли собой отдельные слова или короткие фразы, заранее известные обеим сторонам или передаваемые «вне диапазона» вместе с сообщением. Таким образом, метод Белласо требовал надежной защиты только для ключа. Поскольку получить короткую ключевую фразу относительно легко, например, в предыдущем частном разговоре, система Bellaso была значительно более безопасной.^{[нужна цитата]}

В 19 веке изобретение шифра Беллазо было ошибочно приписано Виженера. Дэвид Кан в своей книге Взломщики кодов посетовал на эту неправильную атрибуцию, заявив, что история «проигнорировала этот важный вклад и вместо этого назвала регрессивный и элементарный шифр для него [Виженера], хотя он не имел к этому никакого отношения».^[9]

Шифр Виженера приобрел репутацию исключительно надежного шифра. Известный писатель и математик Чарльз Лютвидж Доджсон (Льюис Кэрролл) назвал шифр Виженера нерушимым в своей статье 1868 года "Алфавитный шифр»в детском журнале. В 1917 г. Scientific American описал шифр Виженера как «невозможный для перевода».^[10][11] Эта репутация была незаслуженной. Чарльз Бэббидж известно, что он взломал один из вариантов шифра еще в 1854 году, но не опубликовал свою работу.^[12] Касиски полностью взломал шифр и опубликовал эту технику в 19 веке, но даже в 16 веке некоторые опытные криптоаналитики могли иногда взламывать шифр.^[9]

Криптографическая логарифмическая линейка использовалась в качестве вспомогательного средства для расчетов в швейцарской армии с 1914 по 1940 год.

Шифр Виженера достаточно прост, чтобы быть полевым шифром, если он используется вместе с шифровальными дисками.^[13] В Конфедеративные Штаты Америки, например, использовал латунный шифр-диск для реализации шифра Виженера во время американская гражданская война. Сообщения Конфедерации были далеко не секретными, и Союз регулярно взламывал их сообщения. На протяжении всей войны руководство Конфедерации в первую очередь полагалось на три ключевые фразы: «Манчестер Блафф», «Полная победа» и, когда война подошла к концу, «Приходи возмездие».^[14]

Шифр Вернама, ключ которого - до тех пор, пока сообщение не станет одноразовый блокнот, теоретически неразрывный шифр.^[15] Гилберт Вернам пытался восстановить взломанный шифр (создав шифр Вернама-Виженера в 1918 году), но технология, которую он использовал, была настолько громоздкой, что ее было невозможно реализовать.^[16]

Описание

Квадрат Виженера или стол Виженера, также известный как tabula recta, может использоваться для шифрования и дешифрования.

В Шифр цезаря, каждая буква алфавита сдвигается на некоторое количество разрядов. Например, в шифре Цезаря сдвига 3, А станет D, B станет E, Y станет B и так далее. Шифр Виженера имеет несколько последовательных шифров Цезаря с разными значениями сдвига.

Для шифрования можно использовать таблицу алфавитов, называемую tabula recta, Площадь Виженера или Стол Виженера. В нем 26 раз написан алфавит в разных строках, каждый алфавит циклически сдвинут влево по сравнению с предыдущим алфавитом, что соответствует 26 возможным шифрам Цезаря. На разных этапах процесса шифрования шифр использует другой алфавит из одной из строк. Алфавит, используемый в каждой точке, зависит от повторяющегося ключевого слова.^{[нужна цитата]}

Например, предположим, что простой текст быть зашифрованным

ATTACKATDAWN.

Человек, отправляющий сообщение, выбирает ключевое слово и повторяет его до тех пор, пока длина не совпадет с открытым текстом, например, ключевое слово "LEMON":

ЛИМОНЛЕМ

Каждая строка начинается с ключевой буквы. Остальная часть строки содержит буквы от A до Z (в порядке смещения). Хотя показано 26 строк ключей, код будет использовать столько ключей (разных алфавитов), сколько уникальных букв в строке ключей, здесь всего 5 ключей: {L, E, M, O, N}. Для следующих друг за другом букв сообщения будут взяты последовательные буквы ключевой строки, и каждая буква сообщения будет зашифрована с использованием соответствующей ключевой строки. Выбирается следующая буква ключа, и эта строка перемещается, чтобы найти заголовок столбца, соответствующий символу сообщения. Буква на пересечении [key-row, msg-col] - это зашифрованная буква.

Например, первая буква открытого текста, А, в паре с L, первая буква ключа. Следовательно, строка L и столбец А квадрата Виженера, а именно L. Точно так же для второй буквы открытого текста используется вторая буква ключа. Буква в строке E и столбец Т является Икс. Остальной открытый текст зашифровывается аналогичным образом:

Расшифровка выполняется путем перехода к строке в таблице, соответствующей ключу, нахождения позиции буквы зашифрованного текста в этой строке и последующего использования метки столбца в качестве открытого текста. Например, в строке L (от LEMON), зашифрованный текст L появляется в столбце А, которая является первой буквой открытого текста. Далее в ряду E (от LEMON), зашифрованный текст Икс находится в столбце Т. Таким образом Т это вторая буква открытого текста.

Алгебраическое описание

Виженера также можно описать алгебраически. Если буквы А–Z принимаются числа 0–25 (${ Displaystyle А , { widehat {=}} , 0}$, ${ Displaystyle B , { widehat {=}} , 1}$и т. д.), и выполняется сложение по модулю 26, шифрование Виженера ${ displaystyle E}$ используя ключ ${ displaystyle K}$ можно записать как

${ displaystyle C_ {i} = E_ {K} (M_ {i}) = (M_ {i} + K_ {i}) { bmod {2}} 6}$

и расшифровка ${ displaystyle D}$ используя ключ ${ displaystyle K}$ так как

${ displaystyle M_ {i} = D_ {K} (C_ {i}) = (C_ {i} -K_ {i} +26) { bmod {2}} 6,}$

в котором ${ Displaystyle М = М_ {1} точки М_ {п}}$ это сообщение, ${ Displaystyle C = C_ {1} точки C_ {n}}$ это зашифрованный текст и ${ Displaystyle К = К_ {1} точки К_ {п}}$ ключ, полученный повторением ключевого слова ${ Displaystyle lceil п / м rceil}$ времена, когда ${ displaystyle m}$ длина ключевого слова.

Таким образом, используя предыдущий пример, чтобы зашифровать ${ Displaystyle А , { widehat {=}} , 0}$ с ключевой буквой ${ Displaystyle L , { widehat {=}} , 11}$ расчет приведет к ${ Displaystyle 11 , { widehat {=}} , L}$.

${ Displaystyle 11 = (0 + 11) { bmod {2}} 6}$

Следовательно, чтобы расшифровать ${ Displaystyle R , { widehat {=}} , 17}$ с ключевой буквой ${ Displaystyle E , { widehat {=}} , 4}$, расчет приведет к ${ Displaystyle 13 , { widehat {=}} , N}$.

${ Displaystyle 13 = (17-4) { bmod {2}} 6}$

В общем, если ${ displaystyle Sigma}$ это алфавит длины ${ displaystyle ell}$, и ${ displaystyle m}$ - длина ключа, можно записать шифрование и дешифрование Виженера:

${ displaystyle C_ {i} = E_ {K} (M_ {i}) = (M_ {i} + K _ {(я { bmod {m}})}) { bmod { ell}},}$

${ displaystyle M_ {i} = D_ {K} (C_ {i}) = (C_ {i} -K _ {(i { bmod {m}})}) { bmod { ell}}.}$

${ displaystyle M_ {i}}$ обозначает смещение я-й символ открытого текста ${ displaystyle M}$ в алфавите ${ displaystyle Sigma}$. Например, взяв 26 английских символов в качестве алфавита ${ Displaystyle Sigma = (А, В, С, ldots, X, Y, Z)}$, смещение A равно 0, смещение B равно 1 и т. д. ${ displaystyle C_ {i}}$ и ${ displaystyle K_ {i}}$ похожи.

Криптоанализ

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

Основная слабость шифра Виженера - повторяющийся характер его ключ. Если криптоаналитик правильно угадывает длину ключа, зашифрованный текст можно рассматривать как переплетенный Шифры Цезаря, которые легко разбиваются по отдельности. В Касиски экспертиза и Тест Фридмана может помочь определить длину ключа (см. ниже: § Экзамен Касиски и § Тест Фридмана).

Касиски экспертиза

В 1863 г. Фридрих Касиски был первым, кто опубликовал успешную общую атаку на шифр Виженера.^[17] Более ранние атаки полагались на знание открытого текста или использование узнаваемого слова в качестве ключа. У метода Касиски таких зависимостей не было. Хотя Касиски первым опубликовал отчет об атаке, ясно, что другие знали об этом. В 1854 г. Чарльз Бэббидж был побужден взломать шифр Виженера, когда Джон Холл Брок Туэйтс представил «новый» шифр в Журнал Общества искусств.^[18][19] Когда Бэббидж показал, что шифр Туэйтса был, по сути, просто еще одним воссозданием шифра Виженера, Туэйтс бросил вызов Бэббиджу: учитывая исходный текст (из шекспировской Буря : Акт 1, сцена 2) и его зашифрованную версию, он должен был найти ключевые слова, которые Туэйтс использовал для зашифровывания исходного текста. Бэббидж вскоре нашел ключевые слова: «два» и «вместе». Затем Бэббидж зашифровал тот же отрывок из Шекспира, используя разные ключевые слова, и предложил Туэйтсу найти ключевые слова Бэббиджа.^[20] Бэббидж никогда не объяснял метод, который он использовал. Исследования записей Бэббиджа показывают, что он использовал метод, позже опубликованный Касиски, и предполагают, что он использовал этот метод еще в 1846 году.^[21]

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

Ключ: ABCDABCDABCDABCDABCDABCDABCDPlaintext: КРИПТОISSHORTFORКРИПТОГРАФИКА Шифрованный текст: CSASTPKVSIQUTGQUCSASTPIUAQJB

В зашифрованном тексте легко заметить повторение, поэтому тест Касиски будет эффективным.

Расстояние между повторениями CSASTP равно 16. Если предполагается, что повторяющиеся сегменты представляют одни и те же сегменты открытого текста, это означает, что длина ключа составляет 16, 8, 4, 2 или 1 символ. (Все факторы расстояния - возможные длины ключей; ключ длины один - это просто Шифр цезаря, и его криптоанализ намного проще.) Поскольку длины ключей 2 и 1 нереально короткие, нужно пробовать только длины 16, 8 или 4. Более длинные сообщения делают тест более точным, потому что они обычно содержат больше повторяющихся сегментов зашифрованного текста. Следующий зашифрованный текст состоит из двух повторяющихся сегментов:

Шифрованный текст: VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR

Расстояние между повторениями VHVS равно 18. Если предполагается, что повторяющиеся сегменты представляют одни и те же сегменты открытого текста, это означает, что длина ключа составляет 18, 9, 6, 3, 2 или 1 символ. Расстояние между повторениями QUCE составляет 30 знаков. Это означает, что длина ключа может составлять 30, 15, 10, 6, 5, 3, 2 или 1 символ. Взяв пересечение Из этих наборов можно с уверенностью заключить, что наиболее вероятная длина ключа - 6, поскольку 3, 2 и 1 нереально короткие.

Тест Фридмана

Тест Фридмана (иногда известный как тест каппа) был изобретен в 1920-х гг. Уильям Фридман, кто использовал индекс совпадения, который измеряет неравномерность частот букв шифра для взлома шифра. Зная вероятность ${ displaystyle kappa _ {p}}$ что любые две случайно выбранные буквы исходного языка совпадают (около 0,067 для моноблок Английский) и вероятность совпадения для равномерного случайного выбора из алфавита ${ displaystyle kappa _ {r}}$ (1/26 = 0,0385 для английского языка) длину ключа можно оценить следующим образом:

${ displaystyle { kappa _ {p} - kappa _ {r}} over { kappa _ {o} - kappa _ {r}}}$

от наблюдаемой частоты совпадений

${ displaystyle kappa _ {o} = { frac { sum _ {i = 1} ^ {c} n_ {i} (n_ {i} -1)} {N (N-1)}}}$

в котором c размер алфавита (26 для английского), N длина текста и п₁ к п_c наблюдаемый зашифрованный текст частота букв, как целые числа.

Однако это только приближение; его точность возрастает с увеличением размера текста. На практике было бы необходимо попробовать различные длины ключей, близкие к оценочной.^[22] Лучшим подходом к шифрам с повторяющимся ключом является копирование зашифрованного текста в строки матрицы с таким количеством столбцов, как предполагаемая длина ключа, а затем вычисление среднего индекс совпадения каждый столбец рассматривается отдельно. Когда это делается для каждой возможной длины ключа, наивысший средний I.C. то соответствует наиболее вероятной длине ключа.^[23] Такие тесты могут быть дополнены информацией из экзамена Kasiski.

Частотный анализ

Как только длина ключа известна, зашифрованный текст можно переписать в такое количество столбцов, причем каждый столбец соответствует одной букве ключа. Каждый столбец состоит из открытого текста, зашифрованного одним Шифр цезаря. Клавиша Цезаря (сдвиг) - это просто буква клавиши Виженера, которая использовалась для этого столбца. Используя методы, подобные тем, которые используются для взлома шифра Цезаря, можно обнаружить буквы в зашифрованном тексте.

Улучшение экзамена Касиски, известное как Kerckhoffs', сопоставляет частоты букв каждого столбца с частотами сдвига открытого текста, чтобы определить ключевую букву (сдвиг Цезаря) для этого столбца. Как только каждая буква в ключе известна, все, что нужно сделать криптоаналитику, - это расшифровать зашифрованный текст и раскрыть открытый текст.^[24] Метод Керкхоффа неприменим, если таблица Виженера была зашифрована, а не с использованием обычных алфавитных последовательностей, но проверка Касиски и тесты на совпадения все еще могут использоваться для определения длины ключа.

Ключевое устранение

Шифр Виженера с нормальными алфавитами по существу использует арифметику по модулю, которая является коммутативной. Следовательно, если длина ключа известна (или угадана), вычитание зашифрованного текста из самого себя, смещения на длину ключа, приведет к вычитанию простого текста из самого себя, также смещенному на длину ключа. Если какое-либо «вероятное слово» в открытом тексте известно или может быть угадано, его самовычитание может быть распознано, что позволяет восстановить ключ путем вычитания известного открытого текста из зашифрованного текста. Удаление ключа особенно полезно для коротких сообщений. Например, используя Лев как ключ ниже:

Затем вычтите зашифрованный текст из себя со сдвигом длины ключа 4 для Лев.

Что почти эквивалентно вычитанию открытого текста из себя тем же сдвигом.

Что алгебраически представлено для ${ Displaystyle я в [1, п-м]}$ так как:

${ displaystyle { begin {align} (C_ {i} -C _ {(i + m)}) { bmod { ell}} & = (E_ {K} (M_ {i}) - E_ {K} (M _ {(i + m)})) { bmod { ell}} & = ((M_ {i} + K _ {(i { bmod {m}})}) { bmod { ell }} - (M _ {(i + m)} + K _ {((i + m) { bmod {m}})}) { bmod { ell}}) { bmod { ell}} & = ((M_ {i} + K _ {(i { bmod {m}})}) - (M _ {(i + m)} + K _ {((i + m) { bmod {m}}) })) { bmod { ell}} & = (M_ {i} + K _ {(i { bmod {m}})} - M _ {(i + m)} - K _ {((i + m) { bmod {m}})}) { bmod { ell}} & = (M_ {i} -M _ {(i + m)} + K _ {(i { bmod {m}} )} - K _ {((i + m) { bmod {m}})}) { bmod { ell}} & = (M_ {i} -M _ {(i + m)} + K_ { (i { bmod {m}})} - K _ {(i { bmod {m}})}) { bmod { ell}} & = (M_ {i} -M _ {(i + m )}) { bmod { ell}} конец {выровнено}}}$

В этом примере слова БРАУНФОКС известны.

Этот результат ОМАЗ соответствует буквам с 9-й по 12-ю в приведенных выше более крупных примерах. Известный раздел и его местонахождение проверяются.

Вычесть ПРОСМОТРЕТЬ из этого диапазона зашифрованного текста.

Это дает окончательный результат - раскрытие ключа. Лев.

Варианты

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

Если используются несколько ключей, эффективная длина ключа является наименьшим общим кратным длинам отдельных ключей. Например, с помощью двух клавиш ИДТИ и КОТ, длина которого равна 2 и 3, получается эффективная длина ключа 6 (наименьшее общее кратное 2 и 3). Это можно понять как точку, в которой обе клавиши совпадают.

Шифрование дважды, сначала ключом ИДТИ а затем с ключом КОТ это то же самое, что и однократное шифрование ключом, полученным путем шифрования одного ключа другим.

Это демонстрируется шифрованием ATTACKATDAWN с участием IOZQGH, чтобы получить тот же зашифрованный текст, что и в исходном примере.

Если длины ключей относительно простые, эффективная длина ключа растет экспоненциально по мере увеличения длины отдельных ключей. Это особенно верно, если каждая длина ключа индивидуально проста. Например, эффективная длина ключей 2, 3 и 5 составляет 30 символов, а длина ключей из 7, 11 и 13 символов - 1001. Если эта эффективная длина ключа больше, чем зашифрованный текст, он обеспечивает такую ​​же невосприимчивость к тестам Фридмана и Касиски, что и вариант с действующим ключом.

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

Шифровальное колесо Конфедерации, захваченное при сдаче Мобил, Алабама, в мае 1865 г. - Национальный криптологический музей

Виженер фактически изобрел более сильный шифр, автоключ шифр. Название «шифр Виженера» стало ассоциироваться с более простым полиалфавитным шифром. Фактически, эти два шифра часто путали, и оба иногда назывались le chiffre unéchiffrable. Бэббидж фактически взломал гораздо более сильный автоключевой шифр, но Касиски, как правило, приписывают первое опубликованное решение полиалфавитных шифров с фиксированным ключом.

Простым вариантом является шифрование с использованием метода дешифрования Виженера и дешифрование с использованием шифрования Виженера. Этот метод иногда называют «Вариант Бофорта». Он отличается от Шифр Бофорта, создан Фрэнсис Бофорт, который похож на Vigenère, но использует немного измененный механизм шифрования и таблицу. Шифр Бофорта - это обратный шифр.

Несмотря на кажущуюся силу шифра Виженера, он так и не получил широкого распространения в Европе. Шифр Гронсфельда - это вариант, созданный графом Гронсфельдом (Josse Maximilaan van Gronsveld урожденная ван Бронкхорст); он идентичен шифру Виженера, за исключением того, что в нем используется всего 10 различных шифралфавитов, соответствующих цифрам от 0 до 9). Ключ Гронсфельда 0123 такой же, как ключ Виженера в ABCD. Шифр Гронсфельда усилен, потому что его ключ не является словом, но он ослаблен, потому что в нем всего 10 шифровальных алфавитов. Это шифр Гронсфельда, который стал широко использоваться в Германии и Европе, несмотря на его слабые места.

Смотрите также

• Роджер Фронтенак (Нострадамус расшифровщик катрена, 1950)

использованная литература

Цитаты

Источники

• Бойтельшпахер, Альбрехт (1994). "Глава 2". Криптология. перевод с немецкого Дж. Криса Фишера. Вашингтон, округ Колумбия: Математическая ассоциация Америки. С. 27–41. ISBN 0-883-85504-6.
• Сингх, Саймон (1999). "Глава 2: Le Chiffre Indéchiffrable". Кодовая книга. Якорная книга, Случайный дом. ISBN 0-385-49532-3.
• Хелен Ф. Гейнс (18 ноября 2014 г.). Криптоанализ: исследование шифров и их решение. Курьерская корпорация. п. 117. ISBN 978-0-486-80059-2.
• Мендельсон, Чарльз Дж (1940). "Блез де Виженер и" Шифр ​​Карре "'". Труды Американского философского общества. 82 (2).

Заметки

внешние ссылки

Статьи

• История шифра от Cryptologia
• Базовый криптоанализ при H2G2
• «Конспект лекций по классической криптологии» включая объяснение и вывод теста Фридмана