УДК 003.26

ПОЛИАЛФАВИТНЫЕ КРИПТОСИСТЕМЫ

Зюзин Владислав Дмитриевич1, Большаков Василий Николаевич2, Кривдин Александр Дмитриевич3
1Московский технический университет связи и информатики, магистрант 1-ого курса
2Московский технический университет связи и информатики, студент 4-ого курса
3Московский технический университет связи и информатики, студент 4-ого курса

Аннотация
Полиалфавитная криптосистема - это криптосистема, в которой используется несколько моноалфавитных криптосистем.
Примерами таких криптосистем могут служить:
1) Шифр Гронсфельда
2) Шифр Виженера
3) Шифр Тремиуса
4) Книжный шифр
Также в статье представлены методы атак на полиалфавитные криптосистемы, такие как
1) Атака методом индекса совпадений
2) Автокорреляционный метод

Ключевые слова: , , , , , , , , , , , , , , ,


Рубрика: 01.00.00 ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Зюзин В.Д., Большаков В.Н., Кривдин А.Д. Полиалфавитные криптосистемы // Современные научные исследования и инновации. 2020. № 3 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2020/03/91568 (дата обращения: 20.03.2020).

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

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

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

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

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

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

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

 

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

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

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

Таблица. Квадрат Виженера

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

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

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

 

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

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

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

1) Определяет длину ключевого слова

2) Дешифрование текста

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

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

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

То есть вероятность, что две наугад выбранные буквы будут одинаковые, равна 5,53%.

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

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

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

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

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

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

 

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

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

1) Определение ключа

2) Дешифрование текста

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

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

Y – Доля количества совпадений

n – количество совпадений

L – количество символов в шифротексте

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

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

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

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

С – номер зашифрованного символа в алфавите

m – номер символа открытого текста в алфавите

N – количество символов в алфавите

s(p) – это ключ, который представляет собой математическую функцию, например:

p – порядковый номер символа в исходном тексте

const – любое число, которое задаётся в ручную

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

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

Рисунок. Шифр Тремиуса

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

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

 

Книжный шифр

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

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

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

Недостаток этого шифра – это непрактичность и трудоёмкость при шифровании и расшифровании.

Поделиться в соц. сетях

0

Библиографический список
  1. Полиалфавитный шифр // wikipedia.org URL: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D0%B0%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82%D0%BD%D1%8B%D0%B9_%D1%88%D0%B8%D1%84%D1%80 (дата обращения: 21.02.2020).
  2. Шифр Гронсфельда // wikipedia.org URL: https://ru.wikipedia.org/wiki/%D0%A8%D0%B8%D1%84%D1%80_%D0%93%D1%80%D0%BE%D0%BD%D1%81%D1%84%D0%B5%D0%BB%D1%8C%D0%B4%D0%B0 (дата обращения: 21.02.2020).
  3. Шифр Виженера // wikipedia.org URL: https://ru.wikipedia.org/wiki/%D0%A8%D0%B8%D1%84%D1%80_%D0%92%D0%B8%D0%B6%D0%B5%D0%BD%D0%B5%D1%80%D0%B0 (дата обращения: 22.02.2020).
  4. Шифр Тритемиуса // wikipedia.org URL: https://ru.wikipedia.org/wiki/%D0%A8%D0%B8%D1%84%D1%80_%D0%A2%D1%80%D0%B8%D1%82%D0%B5%D0%BC%D0%B8%D1%83%D1%81%D0%B0 (дата обращения: 22.02.2020).
  5. Книжный шифр // wikipedia.org URL: https://ru.wikipedia.org/wiki/%D0%9A%D0%BD%D0%B8%D0%B6%D0%BD%D1%8B%D0%B9_%D1%88%D0%B8%D1%84%D1%80 (дата обращения: 23.02.2020).


Количество просмотров публикации: Please wait

Все статьи автора «Зюзин Владислав Дмитриевич»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться:
  • Регистрация