Математические алгоритмы в шифрах



В статье авторы приводят анализ отдельных симметричных шифров.

Ключевые слова: математика, алгоритм, шифр.

Мы живем в мире информации. Нас окружают книги, всемирная информационная сеть «интернет» и не только. Мы оплачиваем электронные счета, посещаем сайты в интернете, подписываем электронной подписью различные документы. Вся информация имеет статус открытого или закрытого доступа. Буквально каждый житель нашей планеты ежедневно сталкивается с шифрованием. Все то, что надо скрыть от большинства жителей засекречивается. Секретность информации осуществляется с помощью шифрования.

Наши персональные данные защищают с помощью различных шифров. Именно они обеспечивают безопасную передачу информации в различных сетях.

В современном мире человечество встречается с шифрованием практически постоянно. Но только немногие интересуются данной темой. Актуальность этой темы несомненна во все времена. Давайте познакомимся с этой темой поближе.

Рассмотрим небольшую часть симметричных шифров. Они подразделяются на два вида: шифры замены и шифры перестановки (табл. 1).

Таблица 1

Исследуемые симметричные шифры

Шифры замены	Шифры перестановки
Атбаш	по ключу
Цезаря	Двойной перестановки
Простая замена	Магический квадрат
Вижинера

1. Шифры замены

В представленных ниже «шифрах замены» символы исходного текста меняются на другие символы.

Шифр «Атбаш»

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

В России система шифрования «Атбаш» получила широкое распространение в 16–18 веках (табл. 2). Зашифрованные буквы записывались в обратном порядке от стандартной записи алфавита.

Таблица 2

Пример русского алфавита для шифрования методом «Атбаш»

Исходные буквы

А

Б

В

Г

Д

Е

Ё

Ж

3

И

Й

К

Л

М

Н

O

П

Зашифрованные буквы

Я

Ю

Э

Ь

Ы

Ъ

Щ

Ш

Ч

Ц

Х

Ф

У

Т

С

Р

П

Исходные буквы

Р

С

Т

У

Ф

X

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

Зашифрованные буквы

О

Н

М

Л

К

Й

И

З

Ж

Ё

Е

Д

Г

В

Б

А

Шифрование осуществляется по формуле:

i = n – i + 1, (1)

где i — номер буквы в алфавите, n — число букв в алфавите.

Например, исходный номер буквы «В» — 3. «В = 33–3+1=32». Таким образом, буква «В» заменена на «Э». Для примера использования зашифруем фразу: «Школа — источник знаний». Зашифрованная фраза: «Жфруя — цнмрзсцф чсясцх».

Шифр Цезарь

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

Таблица 3

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

Исходные буквы (х)

А

Б

В

Г

Д

Е

Ж

3

И

Й

К

Л

М

Н

O

П

Зашифрованные буквы (х 1 )

Г

Д

Е

Ж

3

И

Й

К

Л

М

И

0

П

Р

С

Т

Исходные буквы(х)

Р

С

Т

У

Ф

X

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

Зашифрованные буквы (х 1 )

У

Ф

X

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

А

Б

В

Если сопоставить каждому символу алфавита его порядковый номер, то шифрование (см. формулу (2)) и расшифрование (см. формулу (3)) можно выразить формулами:

х ₁ = х + k (2)

х = х ₁ — k, (3)

где х — символ открытого текста (исходные буквы), х ₁ — символ шифрованного текста (зашифрованные буквы), k — ключ (в шифре Цезаря ключ равен 3).

Пример шифрования:

исходная фраза: «Школа — источник знаний»

зашифрованная фраза: «Ынсог — лфхсърлн кргрлм» (ключ сдвига — 3).

Шифр простой замены

В данном шифре сначала согласные буквы нумеруются по порядку, затем гласные буквы, и в конце «Ъ» и «Ь» знаки (табл. 4).

Таблица 4

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

Исходные буквы	А	Б	В	Г	Д	Е	Ж	3	И	Й	К	Л	М	Н	О	П
Зашифрованные буквы	22	1	2	3	4	23	5	6	24	7	8	9	10	11	25	12
Исходные буквы	Р	С	Т	У	Ф	X	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
Зашифрованные буквы	13	14	15	26	16	17	18	19	20	21	31	27	32	28	29	30

Символы открытого текста запишем столбцом и зашифруем с помощью ключа (см. формулу 4):

буква = 9*n , (4)

где 9 — коэффициент шифрования (вместо 9 может быть любое целое число), а n — номер буквы открытого текста.

Зашифруем слово ШИФР (табл. 5):

Ш — 20 * 9 = 180

И — 24 * 9 = 216

Ф — 16 * 9 = 144

Р — 13 * 9 = 117

Пример шифрования:

исходная фраза: «ШИФР»

зашифрованная фраза: «180216144117».

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

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

В таблице в каждой строке 33 буквы, следующие строки сдвигаются на несколько позиций. Получается, что в такой таблице Виженера 33 различных шифров Цезаря.

В шифре Виженера (рис. 1) используется ключевое слово. Оно указывает величину сдвига. Шифр обладает значительно более высокой криптостойкостью, чем шифр Цезаря. Слово шифруется по принципу: буква ключа — строка в таблице, буква исходного слова — столбец. Зашифрованная буква находится на их пересечении.

Рис. 1. Шифр Виженера для русского алфавита

В табл. 5 представлен пример применения шифра Виженера. К исходному слову «Виженер» выбран ключ «Цезарь». Ключ короче исходного слова, поэтому его нужно повторять, пока количество букв не сравняется — «ЦезарьЦезарь…» — в примере достаточно добавить «Ц». Шифруем слово, согласно описанному выше алгоритму.

Таблица 5

Пример шифрования с помощью шифра Виженера

Исходное слово	П	Р	О	Е	К	Т
Ключ	П	Л	Ю	С	П	Л
Зашифрованное слово	Я	Ь	Н	Ч	Ъ	Ю

2. Шифры перестановки

Алгоритмы перестановки — процесс изменения символов исходного текста по заранее определенному алгоритму. Он является секретным ключом.

Рассмотрим шифрующие таблицы. Ключом в них используются:

а) размер таблицы;

б) слово или фраза, задающие перестановку;

c) особенности структуры таблицы.

Шифр «Перестановка по ключу»

Сообщение записывается в таблицу по столбцам (табл. 6) под ключевым словом. Далее столбцы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Применим в качестве ключа, например, слово «ВЕКТОР», текст сообщения: «ДЕТИ ЛЮБЯТ УЧИТЬ МАТЕМАТИКУ В ШКОЛЕ».

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

Таблица 6

Таблицы, заполненные ключевым словом и текстом сообщения

К

О

Р

Е

Н

Ь

Е

К

Н

О

Р

Ь

2

4

5

1

3

6

1

2

3

4

5

6

Д

Ю

Ч

А

Т

Ш

А

Д

Т

Ю

Ч

Ш

Е

Б

И

Т

И

К

Т

Е

И

Б

И

К

Т

Я

Т

Е

К

О

Е

Т

К

Я

Т

О

И

Т

Ь

М

У

Л

М

И

У

Т

Ь

Л

Л

У

М

А

В

Е

А

Л

В

У

М

Е

перестановка столбцов

При считывании содержимого правой таблицы по строкам и записи шифрованного текста группами по пять букв получим шифрованное сообщение: «АДТЮЧШ ТЕИБИК ЕТКЯТО МИУТЬЛ АЛВУМЕ».

Шифр «Двойной перестановки»

Сначала в таблицу построчно записывается текст сообщения, потом поочередно переставляются столбцы, а затем строки (табл. 7).

Ключом к шифру двойной перестановки служит последовательность номеров столбцов и строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы.

На начальном этапе вписывается исходная фраза в таблицу, затем переставляются столбцы, и на последнем этапе переставляются строки.

Таблица 7

Пример использования шифра «Д войной перестановки»

4

1

3

2

1

2

3

4

1

2

3

4

3

И

З

У

Ч

3

З

Ч

У

И

1

Ю

И

Ш

А

1

А

Ю

Ш

И

1

Ю

И

Ш

А

2

Р

И

О

Ф

4

Ф

Р

О

В

4

Р

И

О

Ф

3

З

Ч

У

И

2

А

Н

И

Е

2

Н

Е

И

А

4

Р

И

О

Ф

исходная таблица

перестановка столбцов

перестановка строк

Исходная фраза: «ИЗУЧАЮ ШИФРОВАНИЕ»

Зашифрованная фраза: «ЮИША РИОФ ЗЧУИ РИОФ»

Шифр «Магические квадраты»

В квадрат размером 4×4 (размеры могут быть другими) вписывались числа от 1 до 16 (табл. 8). «Магия» квадратов состояла в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному и тому же значению числу.

Таблица 8

Шифр «Двойной перестановки»

16	3	2	13	34
5	10	11	8	34
9	6	7	12	34
4	15	14	1	34
34	34	34	34

Примечание: «34» — это сумма цифр по столбцам или строкам.

Шифрование по магическому квадрату производилось следующим образом. Буквы фразы вписываются последовательно в квадрат, согласно записанным в них числах, а в пустые клетки ставятся произвольные буквы табл.9).

Таблица 9

Пример использования шифра Магического квадрата

16 Т	3 Ш	2 Е	13 О
5 Д	10 Т	11 П	8 А
9 Е	6 Е	7 Л	12 Р
4 А	15 К	14 Е	1 Л

Пример шифрования:

исходная фраза: «ЛЕША ДЕЛАЕТ ПРОЕКТ»

зашифрованная фраза: «ТШЕО ДТПА ЕЕЛР АКЕЛ»

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

Литература:

1. Жельников В. Криптография от папируса до компьютера. — М.: «АВF», 1996 -335с.
2. Виленкин Н. Я. Математика и шифры. — Квант, № 8, 1977
3. Всё о шифрах и кодах в мире математики и криптографии / Роман Душкин: ил. Е. Колосовской. — Москва: Издательство «АСТ», 2018. — 448 с.
4. Виленкин Н. Я., Депман И. Я. За страницами учебника математики — М.: Просвещение, 1986.