Шифрование по алгоритму Шамира

Защита информации

уровень высшего образования - бакалавриат

                   _{(образовательно-квалификационный уровень)}

Расчетно-графическая работа по теме: Шифрование по алгоритму Шамира

 

	Выполнил: студентка IV курса
	группы: СА-бо-161
	направление подготовки (специальность):
	27.03.03 – системный анализ и управление
	(шифр и название направления подготовки, специальности)
	Колесников Анатолий Сергеевич
	(Фамилия Имя Отчество)
	Руководитель	Родзевич Н.А.
		(Фамилия, Имя, Отчество)
	Оценка:

 

 

Симферополь 2020 г.

Содержание

Шифрование по алгоритму Шамира. 3

Примеры.. 6

 

 

Шифрование по алгоритму Шамира

Зашифровать сообщение по алгоритму Шамира для двух абонентов, взяв значение сообщения m и значение p из таблицы 2. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j - требуемые для реализации этого алгоритма число р. Выбор данных для других абонентов произвести циклически согласно процедуре (i + 1) и (g + 1).

Последние цифры номера зачетной книжки - (00). Выбираем для двух абонентов (сообщение, p) - (12,29), (14,31).

Таблица 2. Исходные данные для выбора сообщений (m)

I	0	1
Сообщение	14	18
J	0	2
p	31	41

Перейдем к описанию системы. Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение m абоненту Б так, чтобы никто не узнал его содержание. А выбирает случайное большое простое число р и открыто передает его В. Затем А выбирает два числа сА и dA, такие, что

сАdA mod (р - 1) = 1. (2.1)

Эти числа А держит в секрете и передавать не будет. В тоже выбирает два числа св dв, такие, что

св<dв mod (p - 1) = 1, (2.2)

и держит их в секрете.

После этого А передает свое сообщение m, используя трехступенчатый протокол. Если m < р (m рассматривается как число), то сообщение т передается сразу, если же т р, то сообщение представляется в виде m1, m2,., mt, где все mi < р, и затем передаются последовательно m1, m2,., mt. При этом для кодирования каждого mi лучше выбирать случайно новые пары (cA,dA) и (cB,dB) - в противном случае надежность системы понижается. В настоящее время такой шифр, как правило, используется для передачи чисел, например, секретных ключей, значения которых меньше р. Таким образом, мы будем рассматривать только случай m < р.

Описание протокола.

Шаг 1. А вычисляет число:

Х1 =mСА modp (2.3),

где m - исходное сообщение, и пересылает х1 к В.

Шаг 2. В, получив х1, вычисляет число:

X2 = х1CB mod p (2.4),

и передает х2 к А.

Шаг 3. А вычисляет число:

X3 = х2dA mod p (2.5),

и передает его В.

Шаг 4. В, получив х3, вычисляет число

X4 = x3dB mod p (2.6).

Утверждение (свойства протокола Шамира).

 х4 = m, т.е. в результате реализации протокола от А к В действительно передается исходное сообщение; злоумышленник не может, узнать, какое сообщение было передано.

Доказательство. Вначале заметим, что любое целое число е 0 может быть представлено в виде

е = k(р-1)+r, где r = е mod (p-1)

Поэтому на основании теоремы Ферма:

(2.7).

Справедливость первого пункта утверждения вытекает из следующей цепочки равенств:

(Предпоследнее равенство следует из (2.7), а последнее выполняется в силу (2.1) и (2.2)).

Доказательство второго пункта утверждения основано на предположении, что для злоумышленника, пытающегося определить m, не существует стратегии более эффективной, чем следующая. Вначале он вычисляет CB из (2.4), затем находит dB и, наконец, вычисляет Х4 = m по (2.6). Но для осуществления этой стратегии злоумышленник должен решить задачу дискретного логарифмирования (2.4), что практически невозможно при больших р.

Опишем метод нахождения пар cA,dA и сB,dB, удовлетворяющих (2.1) и (2.2). Достаточно описать только действия для абонента А. так как действия для В совершенно аналогичны. Число сA выбираем случайно так, чтобы оно было взаимно простым с р-1 (поиск целесообразно вести среди нечетных чисел, так как р - 1 четно), Затем вычисляем dA с помощью обобщенного алгоритма Евклида.

Теорема Пусть a и b - два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа x и y, такие, что ax + by = gcd(a, b). (1)

Обобщенный алгоритм Евклида служит для отыскания gcd(a,b) и x,y, удовлетворяющих (1). Введем три строки U=(u1, u2, u3), V=(v1, v2, v3) и Т=(t1, t2, t3). Тогда алгоритм записывается следующим образом.

Примеры:

1. Пусть А хочет передать В сообщение m = 14. А выбирает р = 31,

сАdA mod (р - 1) = 1.

сА = 11, dA = 41.

Аналогично, В выбирает параметры

свdв mod (p - 1) = 1

B = 31 и dB = 21.

Переходим к протоколу Шамира.

Шаг 1. x1 = 1411mod 51 =44.

Шаг 2. х2 = 4431 mod 51 = 29.

Шаг З. x3= 2941 mod 51 = 5.

Шаг 4. х4 = 521 mod 51 = 14.

Таким образом, В получил передаваемое сообщение m = 14.

2. Пусть R хочет передать A сообщение m = 18. C выбирает р = 57,

СRdR mod (р - 1) = 1.

СR = 5, dR = 45.

Аналогично. В выбирает параметры

СAdA mod (p - 1) = 1

A = 101 и dA = 173. Переходим к протоколу Шамира.

Шаг 1. x1 = 185mod 57 =18.

Шаг 2. х2 = 18101 mod 57 = 18.

Шаг З. x3= 1845 mod 57 = 18.

Шаг 4. х4 = 18173 mod 57 =18.

Таким образом, A получил передаваемое сообщение m = 18.

 

Примеры

1. Пусть А хочет передать В сообщение m = 10. А выбирает р = 23, с_А = 7 (gcd(7,22) = 1) и вычисляет d_A = 19. Аналогично, В выбирает параметры c_B = 5 (взаимно простое с 22) и d_B = 9.

 

2. Пусть B хочет передать C сообщение m = 16. B выбирает р = 53, СBdB mod (р - 1) = 1. СB = 5, dB = 21. Аналогично. C выбирает параметры Сcdc mod (p - 1) = 1 c = 11 и dc = 19.