Методическое пособие по теме "Шифрование"

КОМИТЕТ ПО КУЛЬТУРЕ САНКТ-ПЕТЕРБУРГА

САНКТ-ПЕТЕРБУРГСКОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«САНКТ-ПЕТЕРБУРГСКИЙ ТЕХНИКУМ БИБЛИОТЕЧНЫХ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ»

Методическое пособие по теме

«Методы шифрование»

Преподаватель Фомина Е.А.

Санкт-Петербург

2023

Пояснительная записка

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

Шифрование

Цель шифрования – это сокрытие, защита информации.

Шифрование – преобразование информации из одной знаковой системы в другую в целях сокрытия ее смысла от посторонних лиц.

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

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

Криптография — это наука о том, как обеспечить секретность сообщения.

Криптоанализ — это наука о том, как вскрыть зашифрованное сообщение, не зная ключа.

Дешифровка — это процeсс получения открытого текста средствами криптоанализа.

Расшифрование — это процесс получения открытого текста с использованием ключа и алгоритма расшифрования, предусмотренного для данного шифра.

Смысл шифрования — сделать исходное сообщение нечитаемым для любого, кто не владеет ключом. Ключ —это параметр алгоритма, в котором сосредоточен секрет алгоритма.

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

Примеры.

1) Каждую гласную букву русского алфавита заменяем на 1, а каждую согласную букву на 0. Слово МИР будет зашифровано последовательностью 010. Алгоритм не будет обратимым, т.к. последовательности 010 могут соответствовать и другие слова: КИТ, РИС, РАК и т.д.

2) Каждую гласную букву слова сдвигаем на одну позицию вперед по алфавиту, а каждую согласную на одну позицию назад. Слово МИР будет зашифровано последовательностью ЛЙП. Алгоритм не будет обратимым. Подумайте почему?

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

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

Шифр сдвига (подстановки)

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

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

Задача. Зашифруем слово МИР ключом, который равен 3, сдвигая буквы вперед по алфавиту.

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

М – П И – Л Р – У. Ответ: ПЛУ

Расшифрование

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

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

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

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

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

Задача. Зашифровать слово ВАГОН ключом ВАЗА.

В А З А - ключевое слово

3 1 9 1 - номера букв в алфавите

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

В А Г О Н

3 1 9 1 3

Остается произвести сдвиг по алфавиту на указанную позицию.

В Г Д Е - 3

А Б- 1

Г Д Е Ё Ж З И Й К Л- 9

О П- 1

Н О П Р - 3

ВАГОН - ЕБЛПР

Шифр замены

Рис.1

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

Пример шифра на рис.1. При таком способе шифрования слово ИНФОРМАТИКА шифруется последовательностью ЩЫДВПФЙОЩХЙ

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

Расшифрование

При расшифровании заменяем каждый символ шифротекста соответствующим символом из известной нам таблицы подстановки:

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

Криптоанализ этого шифра также выполняется методом частотного анализа текста.

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

Рис. 2

Соответственно, нам нужно найти самую часто встречаемую букву в нашем шифре и сопоставить ей букву.

В книге Артура Конан Дойля  «Пляшущие человечки» используется шифр замены рис.3

Рис. 3

Задание. Расшифровать слово

Перестановочный шифр

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

Пример:

ВАГОН – НОГАВ - слово записывается задом наперед

ВАГОН - АВОГН – меняются местами каждые две буквы

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

Криптоанализ этого шифра выполняется методом перебора.

Шифр, содержащий шум

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

Шифр решетки Кардано задается с помощью координат отверстий.

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

Рис. 4

Задание. Подумать, в чем заключается шум, и расшифровать

А) ЛБКО, УМЫЗАК, АШНРРИ, РКДЕТИ.
В) ИАНТФТОАРТМТААТТИАКТАА, ПТРТИАНТТТЕАРТ.
С) АКРОЛДИИТРБО ФВНАЗНГИЦЕШ, ЩИКНГФЗОЕРУМЦ АЫЦГИХИ

Г рафические алгоритмы

Шифрование при помощи карты – графический алгоритм

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

П ринцип шифрования: пусть необходимо закодировать букву «Р», которая находится на пересечении цифр 3 и 6. Это значит, что символ-дерево для данной буквы будет иметь 3 «ветви» с левой стороны и 6 «ветвей» с правой стороны. Все остальные буквы можно изобразить подобным образом.

Пример.

33 – Н 16 - Е 43 - У 51 – Ч 24 - И

43 – У 51- Ч 21 – Ё 33 - Н 34 - О 14 - Г 34 - О

Ответ: Не учи учёного

К графическим алгоритмам можно отнести всем известные ребусы.

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

Алгоритм шифра Зорге

1 шаг – построение таблицы кодов.

1.1 Таблица букв с исходным словом

Выбирается первый элемент ключа в виде слова s, у которого все буквы различны: S=ВАГОН. Далее в последующих строках записывают буквы по алфавиту, исключая те, что записаны в первой строке. Если образовались пустые клетки, то их заполняют символами ( . / ! ? : ;)

1.2 В таблице выделяю буквы, которые по частоте чаще всего встречаются при написании (это буквы ОЕАНТСР). Таблицу читают по столбцам, сверху вниз. Номер буквы – это ее номер встречи по порядку.

Пример: Первой встретили букву А, второй - букву Е, третьей – букву Р и т.д.

1.3 Кодовая таблица

Сначала в строку по столбцам записывают наиболее часто встречаемые буквы в порядке нумерации, а затем записывают и все остальные буквы, также по столбцам в строки. Нумерация для второй строки начинается с 7, столбцы нумеруются от 0 до 9.

2 шаг - для каждой буквы сообщения записать код по таблице, первая цифра – номер строки, вторая – номер столбца

Замечание: буквы в первой строке получают короткий код от 0 до 6, остальные буквы получают двухзначный код. Разделителем между словами выступает /.

3 шаг - перегруппировка шифротекста на блоки одинаковой длины по пять символов k=5 (количество символов k выступает в качестве элемента ключа). Последние цифры шифротекста после группировки отбрасываются

4 шаг - наложить на полученный шифротекст гамму g (последовательность чисел, которая выбирается для сложения с исходным шифротекстом). Гамма – элемент ключа шифра.

5 шаг – передача полученного шифротекста.

Замечание: ключ шифра Зорге – слово S, число k и гамма g, в записи которой используется разделитель.

S=ВАГОН k=5 g=28.19.2020

Алгоритм шифрования с помощью квадрата Полибия

1 шаг - построить таблицу для шифрования букв алфавита (количество строк и столбцом выбирается исходя из количества букв в алфавите)

2 шаг - для каждой буквы слова записать координаты, определив столбец и строку, в которых располагается буква.

Пример. КРОТ

3 шаг - выписывают числа из таблицы по строкам в одну строчку.

Пример. 6 6 4 2 2 3 3 4

4 шаг - полученную последовательность цифр сдвинуть циклично влево на нечетное количество шагов к

П ример. Пусть к=3

5 шаг - полученную последовательность разбивают на группы по две цифры. Каждая пара чисел обозначает координаты буквы.

Пример. 2 2 3 3 4 6 6 4 - 22 33 46 64

6 шаг -по полученным координатам найти буквы для шифрования из таблицы.

Пример. 22 33 46 64

7 шаг - записывают слово из получившихся букв

Задания практической работы

Задание 1. Зашифровать свою фамилию и имя шифром Зорге. В качестве ключей использовать:

S - слово, состоящее из шести различных букв

k=4 – длина блока

g =2.3.5.7.11.13... ряд простых чисел, начиная с 2. Длину гаммы взять согласно количеству полученных блоков.

Пример: Елисеев / Вадим S= ГРАФИК k=4 g=2.3.5.7.11.13

Задание 2. С помощью квадрата Полибия зашифровать свою фамилию, используя ключ k, который определяется по правилу:

пусть g - количество гласных букв в вашем имени;

k = g, если g - нечетное число;

k = g+1, если g четное число

Пример: Елисеев Вадим

Шифровать фамилию ЕЛИСЕЕВ

k=2+1=3 – в слове ВАДИМ две гласные буквы

Задание 3. Пусть для написания слов используют старославянский алфавит. Расшифровать слова, зашифрованные по указанным алгоритмам. Работа по вариантам.

Список литературы

Кудинов Ю. И. Основы современной информатики : учебное пособие для СПО / Ю. И. Кудинов, Ф. Ф. Пащенко. — Санкт-Петербург : Лань, 2021.

Барычев, С. Основы современной криптографии / С. Барычев, Р. Серов. – М.: 2001.

Адаменко М. Основы классической криптологии. Секреты шифров и кодов - ДМК-Пресс,2012

Поляков К. Ю., Еремин Е. А. ИНФОРМАТИКА: Учебник — М. : Просвещение, 2021