14 14.11.2020

Министерство образования и науки РФ

Госуниверситет – УНПК

Кафедра ЭВТИБ

Введение в специальность

Практическая работа № 4

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

Краткие теоретические сведения

I. Перестановка (транспозиция) символов сообщения между собой по некоторому алгоритму.

Постолбцовая транспозиция. Шифрование.

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

Б) Составляется таблица из k строк и m столбцов, где m – число символов в ключе; k – результат деления общего числа символов в сообщении на m, округлённый до ближайшего большего целого. Таблица построчно заполняется символами сообщения. Пробелы между словами и знаки препинания обычно исключаются для усложнения криптоанализа противником, но для адресата затруднений в понимании не вызывает. Если число символов в сообщении не кратно m, в оставшиеся пустые позиции последней строки заносятся произвольные символы.

В) Каждому столбцу присваивается ранг того из символов ключевого слова, порядковый номер следования которого в данном слове совпадает с номером соответствующего столбца.

Г) Криптограмма формируется как последовательность столбцов таблицы, располагаемых в порядке возрастания их рангов.

Расшифрование адресатом – путём восстановления шифровальной таблицы.

А) Число столбцов таблицы устанавливается равным количеству символов в ключе. Число строк вычисляется как результат деления общего количества символов криптограммы на число символов в ключе.

Б) Символы ключа ранжируются аналогично, как при шифровании.

В) Криптограмма делится на фрагменты по k символов в каждом, где k – число строк в восстанавливаемой таблице. Далее таблица восстанавливается по правилу: в качестве i- столбца таблицы выступает j- фрагмент шифрованного сообщения, где j – ранг i- символа ключа.

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

В указанных методах ключом могут быть:

‑ некоторое выбранное слово (лозунг, имя, дата);

‑ цитата из книги, имеющейся у каждого корреспондента; тогда ключ получает заголовок из двух чисел, передаваемых вместе с криптограммой (или по отдельному каналу связи) – номера страницы с начала или с конца книги и номера строки на ней сверху или снизу. На этой строке находится ключевая цитата;

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

Обобщённый алгоритм шифрования по принципу нескольких алфавитов. Формируется ключевая последовательность символов, представляющая собой повторенный n раз ключ, где n – результат деления количества символов в сообщении на количество символов в ключе, округлённый до ближайшего целого. Пробелы и знаки препинания в ключе и сообщении часто исключаются. Затем каждый символ сообщения заменяется другим, однозначно зависящим от того из символов ключевой последовательности, порядковый номер которого в ней совпадает с порядковым номером заменяемого символа в сообщении.

Шифрование по таблице Виженера (Виженер – фр. дипломат 19 в.). Основано на применении таблицы из m строк и m столбцов, где m – общее число символов в алфавите с ообщений (прил. Б-В). Первая строка таблицы составляется из символов используемого алфавита, располагаемых по возрастанию их порядковых номеров в нём, а каждая последующая формируется путём циклического сдвига предыдущей на 1 символ влево. Таблица м. б. сформирована для любого алфавита.

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

,

где i_j, k_j, с_j – порядковые номера по алфавиту j- символа соответственно сообщения, ключа и криптограммы;

m – общее число символов в используемом алфавите.

Адресат расшифровывает криптограмму путём замены каждого символа по правилу:

, (1)

где d_j – порядковый номер по алфавиту j- символа расшифровываемого сообщения.

Можно работать без таблицы – путём аналитических преобразований. Выбирается ключ – набор из k_j букв – слово или фраза; k_j – длина (период) ключа. Ключевое слово подписывается под буквами сообщения столько раз, сколько необходимо для перекрытия всего объёма сообщения. Общая последовательность, составленная из букв ключа – шифрующая гамма. Далее производится модульное сложение (mod N) чисел, обозначающих буквы алфавита. За модуль N принимается число букв алфавита. В куском язык N = 32 (без Ё). При сложении по mod 32, если получается сумма, превышающая N – 1, то из неё вычитается N.

Из-за возможности совпадения букв и определённого шага – периода ключа в криптограмме может содержаться информация о периоде ключа, что облегчает криптоанализ. При малом периоде ключа шифр не обладает высокой стойкостью. Для её повышения ключ выбирают как можно длиннее.

III. Шифрование методом суммирования реализуется заменой каждого символа сообщения другим, порядковый номер которого в алфавите определяется выражением:

,

где i_j, k_j, с_j – порядковые номера по алфавиту j- символа соответственно сообщения, ключа и криптограммы;

m – общее число символов в используемом алфавите.

Адресат расшифровывает криптограмму путём замены каждого символа по правилу:

,

где d_j – порядковый номер по алфавиту j- символа расшифровываемого сообщения.

Примеры решения задач

1) Шифрование методом постолбцовой транспозиции. Зашифровать сообщение ПИАНИСТКА НА СВЯЗЬ НЕ ВЫШЛА. Ключ – слово ЮСТАС. Пробелы между словами игнорируются.

Решение. Ранжируем символы ключа по их порядковым номерам в алфавите. В соответствии с порядковыми номерами в алфавите русского языка буквам ключа с первой по пятую присваиваем ранги 5, 2, 4, 1 и 3 соответственно (прил. А).

Составляем таблицу шифрования. Сообщение после исключения пробелов содержит 23 символа, а ключ – 5. Поэтому таблица должна содержать 5 столбцов и 5 строк. Построчно вписываем в неё сообщение. В оставшиеся свободными 2 последние позиции 5 строки пишем, например, буквы А и Б:

Номер столбца, соответствующая ему буква ключа и присвоенный ей ранг
1 (Ю; 5)	2 (С; 2)	3 (Т; 4)	4 (А; 1)	5 (С; 3)
П	И	А	Н	И
С	Т	К	А	Н
А	С	В	Я	З
Ь	Н	Е	В	Ы
Ш	Л	А	А	Б

Составляем криптограмму, выписывая из таблицы столбцы в порядке возрастания рангов соответствующих им букв ключа: 4, 2, 5, 3, 1:

Наяваитснлинзыбаквеапсаьш.

2) Шифрование по таблице Виженера. Зашифровать сообщение meet me tomorrow (встречаемся завтра) по таблице Виженера. Ключ computer. Пробелы исключить.

Решение. Составляем ключевую последовательность символов. Сообщение содержит (исключая пробелы) 14 букв, а ключ – 8, поэтому формируем последовательность путём двухкратного повторения ключа. Далее действуем по вышеизложенному правилу для этого метода с пояснением (прил. Б):

Текущий символ ключа	Текущий символ сообщения	Текущий символ криптограммы
C	M	O
O	E	S
M	E	Q
P	T	I
U	M	G
T	E	X
E	T	X
R	O	F
C	M	O
O	O	C
M	R	D
P	R	G
U	O	I
T	W	P

Получаем криптограмму: OSQIGXXFOCDGIP.

Каждой из одинаковых букв в сообщении (например, Е) соответствуют различные символы криптограммы, а каждой из имеющихся в криптограмме одинаковых букв (например, О) – различные символы исходного сообщения. Отсюда название принципа нескольких алфавитов. Благодаря этому свойству дешифрование криптограмм чрезвычайно затруднительно. При известном ключе восстановление сообщения – по выражению (1). Так же можно работать с русским и другими алфавитами.

3) Шифрование методом суммирования. Условия задачи – из примера 1.

Решение. Сообщение содержит 23 символа, а ключ – 5. Поэтому формируем ключевую последовательность путём пятикратного повторения ключа. Шифрование осуществляется, используя порядковые номера букв по русскому или латинскому алфавитам:

Текущий символ ключа и его номер по алфавиту	Текущий символ сообщения и его номер по алфавиту	Номер по алфавиту текущего символа криптограммы	Текущий символ криптограммы
Ю (32)	П (17)	32 + 17 – 33 = 16	О
С (19)	И (10)	19 + 10 = 29	Ы
Т (20)	А (1)	20 + 1 = 21	У
А (1)	Н (15)	1 + 15 = 16	О
С (19)	И (10)	19 + 10 = 29	Ы
Ю (32)	С (19)	32 + 19 – 33 = 18	Р
С (19)	Т (20)	19 + 20 – 33 = 6	Е
Т (20)	К (12)	20 + 12 = 32	Ю
А (1)	А (1)	1 + 1 = 2	Б
С (19)	Н (15)	19 + 15 – 33 = 1	А
Ю (32)	А (1)	32 + 1 = 33	Я
С (19)	С (19)	19 + 19 – 33 = 5	Д
Т (20)	В (3)	20 + 3 = 23	Х
А (1)	Я (33)	1 + 33 – 33 = 1	А
С (19)	З (9)	19 + 9 = 28	Ъ
Ю (32)	Ь (30)	32 + 30 – 33 = 29	Ы
С (19)	Н (15)	19 + 15 – 33 = 1	А
Т (20)	Е (6)	20 + 6 = 26	Ш
А (1)	В (3)	1 + 3 = 4	Г
С (19)	Ы (29)	19 + 29 – 33 = 15	Н
Ю (32)	Ш (26)	32 + 26 – 33 = 25	Ч
С (19)	Л (13)	19 + 13 = 32	Ю
Т (20)	А (1)	20 + 1 = 21	У

Получаем шифрованное сообщение:

ОЫУОЫРЕЮБАЯДХАЪЫАШГНЧЮУ.

Шифрование методом суммирования обладает свойствами, характерными для принципа нескольких алфавитов. Одинаковые символы исходного текста заменяются различными. Но возможны случаи, когда одинаковым символам сообщения соответствуют одинаковые символы криптограммы. Такие случаи нежелательны. Следует по возможности избегать повторов букв. Для сведéния к минимуму этого явления следует выбирать ключи с большим количеством знаков и меньшим числом их повторов.