Серверные решения →Теория

Полиалфавитные криптосистемы

Шифруемся

Октябрь 27, 2020 Зюзин Владислав
Куприков Олег

8 минут чтения

Полиалфавитный шифр – это криптосистема, в которой используется несколько моноалфавитных шифров. Поэтому нам необходимо иметь как минимум 2 таблицы и шифрование текста происходит следующим образом. Первый символ шифруется с помощью первой таблицы, второй символ – с помощью второй таблицы и так далее.

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

Моноалфавитные шифры были популярны вплоть до конца 16 века, так как практически все научились их вскрывать. Необходимо было что-то менять и поэтому в 1585 году был создан шифр Виженера. С этого началась новая эпоха в истории криптографии, которая называется период полиалфавитных шифров, хотя попытки создать подобные криптосистемы были и раньше за пол века до этого, но ничего серьёзного из этого не получилось.

Шифр Гронсфельда

Данный шифр представляет собой модификацию шифра Цезаря и по своей структуре похож на шифр Виженера.

Принцип работы. Берём к примеру текст «РАБОТА» и ключ, например - «136». Ключ в данном случае не одно число, а набор цифр, для понимания можно представить в виде «1,3,6» и не важно какой длины. Далее каждой букве исходного текста присваиваем по 1 цифре ключа, например «Р(1) А(3) Б(6) О(1) Т(3) А(6)» и каждому символу исходного текста прибавляем значение ключа по методу Цезаря. Получается зашифрованный текст «СГЖПХЁ».

При расшифровании проделываем ту же логику, как при расшифровании по методу Цезаря.

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

Шифр Виженера является самым популярным полиалфавитным шифров за всю историю.

Для начала создаётся квадрат Виженера.

Ключом в данном методе может быть любой длины и состоять из любых символов, которые есть в таблице 3. Например возьмём ключ «ШИНА» и исходный текст «РАБОТА».

Проделываем то же самое, что и при шифре Гронсфельда, к каждой букве исходного текста записываем исходную букву ключа – «Р(Ш) А(И) Б(Н) О(А) Т(Ш) А(И)». Согласно таблице 3 по диагонали находим букву исходного текста, а по вертикали находим букву ключа, их пересечение является зашифрованной буквой, таким образом проделываем для всех букв и шифруем текст, получается «СЙППКЙ».

Чтобы расшифровать нам нужно точно так же под каждой буквой закрытого текста записываем букву ключа - «С(Ш) Й(И) П(Н) П(А) К(Ш) Й(И)». По вертикали находим букву ключа и по этой строке находим зашифрованную букву, пересечение с буквой по горизонтальной строки – буква исходного текста, расшифровывает и получаем исходный текст.

Атака методом индекса совпадений

В данном случае рассмотрим криптоанализ шифра Виженера, его так же можно применять и к шифру Гронсфельда. Нижеприведённый метод криптоанализа называется методом индекса совпадений.

Атака методом индекса совпадений состоит из 2 шагов:

1. Определяет длину ключевого слова
2. Дешифрование текста

Рассмотрим каждый из этапов:

1. Для того, чтобы найти длину ключа воспользуемся методом индекса совпадений.

ИС = 0,0553

Индекс совпадений – это константа, вероятность того, что две наугад выбранные буквы в нормальном осмысленном произвольном русском тексте будут одинаковые.То есть вероятность, что две наугад выбранные буквы будут одинаковые, равна 5,53%.

При атаке на шифротекст необходимо ориентироваться именно на эту вероятность.

Если имеет шифротекст, зная о нём только то, что он зашифрован шифром Виженера, определяем длину ключа.

В шифре Виженера ключом выступает любая последовательность цифр, начиная с 2, потому что если была бы 1 буква, то это просто шифр Цезаря.

Итак, начиная с минимума, предполагаем, что длина ключа составляет 2 символа и проверяем это. Выбираем из шифротекста каждую вторую букву, начиная с первой и выписываем отдельно полученную строку. Предполагаемую длину ключа обозначаем k=2, а количество символов в этой строке за L. Далее из алфавита берём каждую букву и считаем для неё индекс совпадений, то есть берём определённую букву и подсчитываем сколько раз она встретилась в этой строке шифротекста (это число обозначаем – n), и так для всех букв. Далее высчитываем индекс совпадений по формуле

ИС = n(n-1)/L(L-1)

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

2. Вычислив длину ключевого слова возвращаемся к шифротексту.

Разбиваем текст на количество символов символов в ключе, например, при длине ключа k=3, делим текст на 3 части. В первую часть будет входить каждая третья буква, начиная с первой, во вторую часть – каждая третья буква, начиная со второй, и третья часть – каждая третья буква, начиная с третьей. После этого выписываем отдельно каждую часть. Отдельная часть представляет собой обычный шифр Цезаря. Далее дешифруем каждую часть методом частотного криптоанализа. Находим самую частую букву каждой части шифротекста, сравниваем её с буквой «О», так как она в русском алфавите самая частая и сравниваем шифрованную букву с буквой «О». Вычисляем разницу позиций между ними – в ответе получим число, равное ключу и дешифруем с помощью него по шифру Цезаря первую часть шифротекста. Такие же действия проделываем и для остальных частей, затем восстанавливаем части дешифрованного шифротекста и получаем исходный текст.

Автокорреляционный метод

Данный метод проще в реализации, чем метод индекса совпадений, но последовательность действий точно такая:

1. Определение ключа
2. Дешифрование текста

Имея шифротекст, необходимо посчитать количество букв в нём. Желательно весь шифротекст записать в одну строку, затем сделать копию и разместить под ней же.

Как и в случае с методом индекса совпадением предполагаем для начала минимальную длину ключа, то есть k=2. Затем в копии строки шифротекста убираем первые два символа и дописываем их в конец строки. Далее ищем количество совпадающих букв между этими двумя строками и находим долю количества совпадений от общего количества символов в тексте по формуле:

Y = n/L

• Y - Доля количества совпадений
• n – количество совпадений
• L – количество символов в шифротексте

Полученное значение сравниваем со значением контанты индекса совпадений, так же – если это значение намного отличается, предполагаем длину ключа k=3 и делаем ту же процедуру до тех пор, пока доля количества совпадений будет близка к константе индекса совпадений.

После нахождения длины ключа проделываем то же самое, что и в методе индекса совпадений и дешифруем текст.

Шифр Тритемиуса

Шифр Тритемиуса позиционируется усиленным шифром Цезаря и описывается формулой:

C = (m+s(p))modN

• C - номер зашифрованного символа в алфавите
• m - номер символа открытого текста в алфавите
• n - количество символов в алфавите
• s(p) - это ключ, который представляет собой математическую функцию, например: s(p) = 2p+const
  • p - порядковый номер символа в исходном тексте
  • const - любое число, которое задаётся в ручную

Точно так же, как в шифре Цезаря каждый символ, перед тем, как шифровать, будет переводится в число, согласно определённой таблице.

Первое, что нужно сделать – пронумеровать все символы в исходном тексте, то есть каждый символ получается свой номер в зависимости от своей позиции в тексте. Шифрование происходит посимвольно.

Расшифрование происходит похожим способом и описывается формулой:

C = (m-s(p))modN

Шифр для своего времени очень неплох, потому что не смотря на свою простоту, то есть самая сложная часть – это выбрать функцию s(p). Он демонстрирует достаточно высокий криптоустойчивости, то есть не уступает ни шифру Виженера, ни шифру Гросфельда.

Книжный шифр

Книжный шифр – не является популярным шифром среди старых шифров, но при грамотном подходе к использованию, обеспечивает криптостойкость на порядки выше, чем шифр Виженера и Гронсфельда. Это симметричный шифр, в котором в качестве ключа используется любая книга на выбор, и процесс шифрования происходит посимвольно.

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

Чтобы получатель смог расшифровать полученное сообщение должен обладать точно такой же книгой. Поочередно смотрит комбинацию и находит её в данной книге и расшифровывает полученное сообщение. Недостаток этого шифра – это непрактичность и трудоёмкость при шифровании и расшифровании.