Введение

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

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

Ниже приведены примеры обозначений, используемых при описании алгоритмов и заданий [10]:

C_i, P, G - открытые параметры, которые могут быть известны противнику обозначаются заглавными символами;

k, x, q - секретные параметры, известные только корреспондентам (или только одному корреспонденту) обозначаются строчными символами;

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

m, m’ – исходный и восстановленный, например, при расшифровании, параметры;

(mod N) - все операции выполняются по модулю (в остатках от деления) числа N.

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

Например, вместо:

(357 - 654) ∙ 46 (mod 701) = - 13662 mod 701 = 358

Производим последовательные вычисления:

(357 - 654) ∙ 46 (mod 701) = 404 ∙ 46 (mod 701) = 358

При решении задач рекомендуется использование встроенного калькулятора Windows, а также для реализации некоторых операций - редактора электронных таблиц MS Excel или Open Office Calc. Примеры реализации операций, таких как: вычисление мультипликативного обратного, модульное экспоненцирование, приведены в соответствующих разделах пособия. Все задания строятся на использовании относительно небольших чисел. В случае значительного увеличения значений исходных данных рекомендуется написание программ, реализующих отдельные действия на одном из языков программирования. Примеры исходных кодов таких программ на языках C# и Pascal приведены в приложении 2.

Часть 1. Арифметика остатков. Элементарные шифры. Шифр Цезаря.

Один из наиболее ранних и примитивных шифров простой замены. Изначально шифрование производилось при помощи записи двух алфавитов – открытого текста и шифртекста один под другим со смещением влево на величину сдвига k - ключа (см. рис.1). Считается, что Юлий Цезарь, которому приписывается авторство этого шифра, использовал ключ k = 3. При зашифровании символы заменяются сверху вниз, а при расшифровании, соответственно – снизу вверх.

A	B	C	D	E	. . .	W	X	Y	Z
D	E	F	G	H	. . .	Z	A	B	C

Рис.1. Шифр Цезаря

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

Рис.2. Дисковый шифратор

Для удобства перехода к математической модели вместо символов будем использовать их порядковые номера от 0 до N - 1. И зашифрование и расшифрование будем производить сверху-вниз. Для этого при зашифровании внутреннее кольцо будем поворачивать на k делений против часовой стрелки, а при расшифровании на k делений по часовой стрелке, или на N – k делений против часовой стрелки, что одно и то же.

Таким образом, количество возможных ключей шифра Цезаря – (N – 1), за исключением сдвига на величину 0  N. Математически выразим функции зашифрования и расшифрования для шифра Цезаря. Операцией наложения ключа является сложение по модулю N.

Функция зашифрования : ,

Функция расшифрования: ,

где:

m_i – i-ый символ открытого текста,

C_i – i-ый символ шифртекста, k – ключ зашифрования,

- ключ расшифрования.

Задача 1.1. Осуществить зашифрование и расшифрование символа m₁ на алфавите N при помощи шифра Цезаря на ключе k. Проверить правильность расшифрования.

Пример решения.

Дано: k = 7 m1 = 24 N = 26	Решение:
Найти: C1, m1’ Проверить: m1’ = m1

Недостаток операции сложения заключается в ее линейности (см. столбец 2 табл. 1), что позволяет восстановить ключ k уже по одному известному паросочетанию m_i  C_i для чего достаточно решить одно линейное сравнение:

Несколько лучшие характеристики перемешивания дает операция модульного умножения (см. столбец 3 табл. 1), но здесь первым недостатком является то, что элемент 0 всегда будет зашифрован как 0. Вторым недостатком считается то, что в качестве ключа по умножению можно использовать не все значения алфавита N, а только взаимно простые с N. Например, при попытке использовать k = 2 (см. столбец 5 табл. 1) не удается добиться однозначности расшифрования – одному шифробозначению соответствует две шифрвеличины. Например 6 может быть расшифровано как 3 или 7.

Таблица 1

N=8, k2=2
m	k = k1 = 3			k = 2
	m+k(mod N)	m×k(mod N)	m×k1+k2(mod N)		m×k(mod N)
0	3	0	2		0
1	4	3	5		2
2	5	6	0		4
3	6	1	3		6
4	7	4	6		0
5	0	7	1		2
6	1	2	4		4
7	2	5	7		6

Первый недостаток исправляется введением дополнительной операции сложения, а второй – ограничением пространства ключей:

Нахождение наибольшего общего делителя возможно при помощи основной теоремы арифметики [11]:

Например для : , то есть k₁ не должен делиться на 2 и 3, но ввиду высокой вычислительной сложности метода на практике применяют алгоритм Евклида.

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

Например:

Особый интерес представляют частные случаи функции Эйлера от простого числа и от произведения двух простых чисел (при известных p и q):

На основании вышеизложенного приведем модель аффинного шифра.