Некоммерческое акционерное общество
АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ
Кафедра телекоммуникационных систем
ЗАЩИТА
ИНФОРМАЦИИ В ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ
Методические указания к
выполнению курсовой работы
для студентов специальности
5В071900 - Радиотехника,
электроника и телекоммуникации
СОСТАВИТЕЛИ: А.С. Байкенов, Е.А. Шкрыгунова. Защита информации в телекоммуникационных системах. Методические указания к выполнению курсовой работы для студентов специальности 5В071900 – Радиотехника, электроника и
телекоммуникации – Алматы; АУЭС, 2012
– 23с.
Методические
указания содержат общие положения по выполнению курсовой работы. Приводится рекомендуемая литература.
Ил. 3 , табл.10 , библиогр.- 3 назв.
Рецензент: канд. техн. наук,
проф. К.Х. Туманбаева.
Печатается
по плану издания некоммерческого акционерного общества «Алматинский университет
энергетики и связи» на
© НАО “Алматинский университет энергетики и связи”,
Содержание
Введение |
4 |
Задание № 1 |
5 |
Задание 1.1 |
5 |
Методические указания к решению задания 1.1 |
5 |
Задание 1.2 |
9 |
Задание № 2 |
13 |
Задание 2.1 |
13 |
Методические указания к решению задания 2.1 |
13 |
Задание 2.2 |
16 |
Методические указания к решению задания 2.2 |
16 |
Задание
2.3 |
19 |
Методические указания к заданию 2.3 |
20 |
Список
литературы |
22 |
Введение
Целью
курсовой работы является ознакомление студентов с математической основой
построения систем защиты информации в телекоммуникационных системах - методами
криптографии. Курсовая работа направлена на формирование у студентов
систематизированного представления о
принципах, методах и средствах реализации защиты данных.
Курсовая
работа посвящена изучению систем шифрования с закрытым ключом. Задание №1
посвящено шифрованию с закрытым ключом. Рассматривается алгоритм RSA, а
также предлагаются расчеты по
электронной подписи с использованием
хеш-функции.
Задание №2 посвящено асимметричному шифрованию или шифрованию с открытым ключом. Рассматриваются алгоритмы Диффи–Хелмана, Шамира и Эль-Гамаля.
Исследование симметричных и ассиметричных методов шифрования
Целью
курсовой работы является ознакомление студентов с математической основой
построения систем защиты информации в телекоммуникационных системах - методами
криптографии.
Задание № 1
Задание 1.1.
Несимметричное шифрование – дешифрование
Зашифровать информацию по методу RSA для
последующей передачи.
Сгенерировать секретный ключ с предложенными двумя
вариантами и с использованием расширенного алгоритма Эвклида.
Вариант задания определяется
последними цифрами номера студенче-ского билета. По номеру i (предпоследняя
цифра) студент выбирает сообщение для зашифровывания, по j –
требуемые для реализации этого алгоритма числа р и q.
Таблица 1.1 - Исходные
данные:
I |
0 |
1 |
2 |
3 |
4 |
Сообщение |
Принтер |
Интеграл |
Минус |
Модуль |
Плюс |
J |
0 |
1 |
2 |
3 |
4 |
p q |
7.11 |
5.17 |
3.11 |
11.19 |
13.17 |
Продолжение таблицы 1.1
I |
5 |
6 |
7 |
8 |
9 |
Сообщение |
Число |
Дробь |
Корень |
Остаток |
Степень |
J |
5 |
6 |
7 |
8 |
9 |
p q |
7.17 |
5.11 |
7.13 |
11.17 |
5.13 |
Методические указания к
решению задания 1.1
Одним
из наиболее распространенных методов несимметричного шифрования - дешифрования
является метод шифрования с открытым ключом, в котором используется алгоритм RSA.
Несмотря на довольно большое число различных СОК
(система с открытым ключом), наиболее популярна – криптосистема RSA,
разработанная в 1977 году и получившая название в честь ее создателей: Рона
Ривеста, Ади Шамира и Леонарда Эйдельмана.
Они воспользовались тем фактом, что нахождение больших
простых чисел в вычислительном отношении осуществляется легко, но разложение на
множители произведения двух таких чисел практически невыполнимо. Доказано
(теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению.
Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для
раскрытия шифра, а с учетом производительности современных компьютеров оценить
и необходимое на это время.
Возможность, гарантированно оценить защищенность
алгоритма RSA стала одной из причин популярности этой СОК на фоне десятков
других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях,
особенно для работы с удаленными клиентами (обслуживание кредитных карточек).
Рассмотрим математические результаты, положенные в
основу этого алгоритма.
Теорема 1. (Малая теорема Ферма.)
Если р – простое число, то
xp-1 = 1(mod p) (1)
для любого х, простого относительно р, и
xp = x(mod p) (2)
для
любого х.
Доказательство. Достаточно доказать справедливость
уравнений (1) и (2) для xp.
Проведем доказательство методом индукции.
Очевидно, что уравнение (3) выполняется при х=0 и 1.
Далее
xp = (x –1 + 1)p = C(p,j)(x –1)j = (x –1)p + 1(mod 2),
так как C(р,j)=0(mod р) при 0<j<р.
С учетом этого неравенства и предложений метода
доказательства по индукции, теорема доказана.
Определение. Функцией Эйлера φ(n) называется
число положительных целых, меньших n и простых относительно n.
Таблица 1.2 - Исходные
данные:
N |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
φ(n) |
1 |
2 |
2 |
3 |
2 |
6 |
4 |
6 |
4 |
10 |
4 |
Теорема 2. Если n = рq, (р и q – отличные друг от
друга простые числа), то
φ(n)=(р-1)(q-1).
Теорема 3. Если n = рq, (р и q - отличные друг от друга
простые числа) и х – простое
относительно р и q, то
xφ(n) = 1(mod n).
Следствие. Если n = рq, (р и q - отличные друг от
друга простые числа) и е простое относительно (n), то отображение
Eв,n : xxв(mod n)
является взаимно однозначным на Zn.
Очевиден и тот факт, что если е – простое относительно
f(n), то существует целое d, такое, что
ed
≡ 1 (mod φ(n)). (3)
На этих математических фактах и основан популярный
алгоритм RSA.
Пусть n = рq, где р и q – различные простые числа.
Если e и d удовлетворяют уравнению, то отображения Еe,n и Еd,n являются
инверсиями на Zn. Как Еe,n, так и Еd,n легко рассчитываются, когда известны e,
d, р, q.
Если известны e и n, но р и q неизвестны, то Еe,n
представляет собой одностороннюю функцию; нахождение Еd,n по заданному n
равносильно разложению n. Если р и q – достаточно большие простые, то
разложение n практически неосуществимо. Это и заложено в основу системы
шифрования RSA.
Шифросистема RSA.
Система RSA в настоящее
время является наиболее распространенной системой шифрования с открытым ключом.
Пусть n = pq – целое число, представляемое в виде произведения
двух больших простых чисел p, q. Числа e и d, определяющие алгоритмы шифрования и расшифрования
соответственно, должны отвечать условию
ed ≡ (mod
φ(n)), (1)
где φ(n) = (p-1)(q-1) – значение
функции Эйлера от числа n.
Пусть k = (n,p,q,e,d) – выбранный ключ, состоящий из открытого ключа k1 = (n,e) и секретного ключа k2 = (n,p,q,d).
Пусть M – блок
открытого текста и C – соответствующий блок
шифрованного текста. Тогда правила шифрования и расшифрования определяются
формулами:
С = Ek (M) =Me
(mod n), Dk(C) = Cd
(mod n). (2)
Заметим, что в соответствии с (2) Dk(C) = M.
При нахождении значений e и d,
удовлетворяющих условию (1), значение e обычно
задают таким образом, чтобы оно было взаимнопростым с φ(n), а значение d определяют из уравнения
φ(n)x + ed = 1. (3)
В общем случае уравнение (3) имеет вид ax + by = c (здесь a = φ(n), b = e, y = d) и называется
Диафантовым уравнением.
Решение этого уравнения
y = (–1)μ · aμ-1 · x = (–1)μ+1 · b μ-1 (4)
можно получить с помощью разложения отношения a/b в цепную
дробь:
,
где μ – порядок цепной дроби, т.е. индекс
коэффициента дроби, у которого остаток равен нулю,
(5)
а для всех членов, начиная с третьего справедливо
(6)
Таким образом, для решения уравнения (3) необходимо
представить отношение a/b в виде цепной дроби, определить при этом значения r0, r1…rμ и
μ. Потом в соответствии с (4) – (6) определяются значения ai, bi, а
также x и y.
Пример.
Зашифруем аббревиатуру RSA, используя p = 17, q = 31. Для этого вычислим n = pq = 527 и
μ(n) = (p-1)(q-1) = 480. Выберем далее в качестве e число, взаимно простое с μ(n), например, e = 7. С
помощью цепных дробей найдем целые числа x и y,
удовлетворяющие соотношению μ(n)x + ey = 1. Запишем
480x + 7y = 1
Следовательно,
μ = 3, a0 = 68, b0 = 1, a1 = 69, a2 = 1·69 + 68 = 137, b2 = 1·1 +
1 = 2.
Таким образом, x = –2, y = –137.
Поскольку
–137 (mod 480) = 343,
то d = 343.
Проверка
7 · 343 = 2401 = 1(mod 480).
Теперь представим данное сообщение в виде
последовательности чисел, содержащихся в интервале 0…526. Для этого буквы R, S и A закодируем пятимерными двоичными векторами,
воспользовавшись двоичной записью их порядковых номеров в алфавите:
R = 18 = (10010), S
= 19 (10011), A = 1 (00001).
Тогда RSA =
(100101001100001). Укладываясь в заданный
интервал 0…526, получаем следующее представление:
RSA = (100101001), (100001) = (M1 =
Далее последовательно шифруем M1 и M2:
C1 = Ek (M1) = M1в = 2977
(mod 527) = 474.
При этом мы воспользовались тем, что
т.е. 2977 =
((2972)3297)(mod 527) = ((2003(mod 527)297)mod
527),
C2 = Ek(M2) = M2в = 337(mod 527) = 407.
В итоге получаем шифротекст: С1 = 474, С2
= 407.
При расшифровании нужно выполнить следующую
последовательность действий. Во-первых, вычислить
Dk (C1)
= C1d = 337 (mod 527) = 474343 (mod
527).
Отметим, что при возведении в степень, удобно
воспользоваться тем, что 343 = 256 + 64 + 16 + 4 + 2 + 1. На основании этого
представления получаем:
4742(mod
527) = 174, 4744(mod
527) = 237,
4748(mod
527) = 307, 47416(mod
527) = 443,
47432(mod
527) = 205, 47464(mod 527)
= 392,
474128(mod
527) = 307, 474256(mod 527)
= 443,
в силу чего
474343(mod
527) = (443×392×443×237×174×474)(mod 527) =
297,
Аналогично
407343(mod 527) = 33.
Возвращаясь к буквенной записи, получаем после
расшифрования RSA.
Произвести генерацию закрытого ключа используя расширенный
алгоритм Эвклида, подробно описанный в алгоритме Шамира п.2.2.
Задание 1.2. Хеширование и
цифровая подпись документов
Используя данные задания
1.1, получить хеш – код m для сообщения М при помощи
хеш – функции Н, взятой из рекомендаций МККТТ Х.509. Вектор инициализации Н0
выбрать равным нулю.
Вычислить цифровую подпись
методом RSA под электронным документом М, используя рассчитанный
хеш – код m и секретный ключ d.
Представить схему цифровой
подписи с подробным описанием ее функционирования.
Хеш – функцию МККТТ Х.509
запишем следующим образом:
Hi=[(Hi-1 Å Mi)2] (mod n), где i=l,n, H0 – вектор инициализации, Мi
=М1,М2,М3…,Мn - длина блока.
Все блоки делят пополам и к
каждой половине прибавляют равноценное количество единиц. С преобразованными
таким образом блоками производят интеграционные действия.
Пример.
Необходимо получить хеш –
код сообщения ПРЕДЕЛ при помощи хеш функции Х.509 с
параметрами p=3, q=11.
Порядок вычисления хеш –
кода:
а) получить значение модуля:
n=pq= 3×11=33;
б)представить сообщение в
виде номеров букв русского алфавита в десятичном и двоичном видах:
П Р
Е Д Е Л
16 17 6 5 6 12
00010000,
00010001, 00000110, 00000101, 00000110, 00001100:
в) Разбить байт пополам,
добавив в начало полубайта единицы, и получить хешируемые блоки Мi:
Таблица 1.3 - Исходные
данные:
M1 |
M2 |
M3 |
M4 |
M5 |
M6 |
11110001 |
11110000 |
11110001 |
11110001 |
11110000 |
11110110 |
M7 |
M8 |
M9 |
M10 |
M11 |
M12 |
11110000 |
11110101 |
11110000 |
11110110 |
11110000 |
11111100 |
г) Выполнить интеративные
шаги:
Первая интерация
М1 |
11110001 |
Å |
|
Н0=0 |
00000000 |
Н0 Å М1 |
11110001=24110 |
[(H0Å M1)2]
(mod 33) |
2412 mod
33 = 10 |
Н1 |
1010=00001010 |
Вторая интерация
М2 |
11110000 |
Å |
|
Н1 |
00001010 |
Н1 Å М2 |
11111010=25010 |
[(H1Å M2)2]
(mod 33) |
2502 mod 33 = 19 |
Н1 |
00010011 |
Третья интерация
М3 |
11110001 |
Å |
|
Н2 |
00010011 |
Н2 Å М3 |
11100010=22610 |
[(H2Å M3)2]
(mod 33) |
2262 mod 33 = 28 |
Н3 |
00011100 |
Четвертая интерация
М4 |
11110001 |
Å |
|
Н3 |
00011100 |
Н3 Å М4 |
11101101=23710 |
[(H3Å M4)2]
(mod 33) |
2372 mod 33 = 6 |
Н4 |
00000110 |
Пятая интерация
М5 |
11110000 |
Å |
|
Н4 |
00000110 |
Н4 Å М5 |
11110110=24610 |
[(H4Å M5)2]
(mod 33) |
2462 mod 33 = 15 |
Н5 |
00001111 |
Шестая интерация
М6 |
11110110 |
Å |
|
Н5 |
00001111 |
Н5 Å М6 |
11111001=24910 |
[(H5Å M6)2]
(mod 33) |
2492 mod 33 =18 |
Н6 |
00010010 |
Седьмая интерация
М7 |
11110000 |
Å |
|
Н6 |
00010010 |
Н6 Å М7 |
11100010 = 22610 |
[(H6Å M7)2]
(mod 33) |
2262 mod 33 = 28 |
Н7 |
00011100 |
Восьмая интерация
М8 |
11110101 |
Å |
|
Н7 |
00011100 |
Н7 Å М8 |
11101001= 233 |
[(H7Å M8)2]
(mod 33) |
2332 mod 33 = 2 |
Н8 |
00000010 |
Девятая интерация
М9 |
11110000 |
Å |
|
Н8 |
00000010 |
Н8 Å М9 |
11110010 = 24210 |
[(H8Å M9)2] (mod
33) |
2422 mod 33 = 11 |
Н9 |
00001011 |
Десятая интерация
М10 |
11110110 |
Å |
|
Н9 |
00001011 |
Н9 Å М10 |
11111101 = 253 |
[(H9Å M10)2]
(mod 33) |
2532 mod 33 = 22 |
Н10 |
00010110 |
Одиннадцатая интерация
М11 |
11110000 |
Å |
|
Н10 |
00010110 |
Н10 Å М11 |
11100110 =23010 |
[(H10ÅM11)2]
(mod 33) |
2302 mod 33 = 32 |
Н11 |
00100000 |
Двенадцатая интерация
М12 |
11111100 |
Å |
|
Н11 |
00100000 |
Н11 Å М12 |
11011100 = 22010 |
[(H11ÅM12)2]
(mod 33) |
2202 mod 33 = 22 |
Н12 |
00010110 |
Таким образом, исходное
сообщение ПРЕДЕЛ имеет хеш – код m=22.
Для вычисления цифровой
подписи используем следующую формулу:
S=md (mod n) = 223 mod 33 = 22.
Пара (M, S)
передается получателю как электронный документ М, подписанный цифровой подписью
S, причем подпись S сформирована обладателем
секретного ключа d.
Получив пару (M, S), получатель
вычисляет хеш – код сообщения М двумя способами:
1) Восстанавливает хеш – код
m’, применяя криптографическое преобразование подписи S с
использованием открытого ключа e:
m’=Se
(mod n) =227 mod 33 = 22.
2) Находит результат
хеширования принятого сообщения с помощью той же хеш – функции: m=H(M) =22.
При равенстве вычисленных
значений m’ и m получатель признает пару (M, S)
подлинной.
Контрольные вопросы
1. Изложите принципиальную
схему организации секретной связи с использованием системы шифрования с
открытым ключом.
2. Изложите принципиальную
схему организации обмена документами, заверенными цифровой подписью.
3. Перечислите основные
требования, предъявляемые к хеш-функции, пригодной для использования при
вычислении цифровой подписи документа.
4. Каким
образом с помощью криптосистемы RSA можно организовать передачу
шифрованных сообщений, подлинность которых подтверждена цифровой подписью?
Приведите примеры.
Задание
№2
Задание 2.1. Система
с открытым ключом Диффи-Хелмана
Сгенерировать секретные
ключи для пяти абонентов по методу Диффи-Хеллмана
(DH). Для этого взять значение секретного ключа x из таблицы 1.
Соответствующие значения открытого ключа вычислить и результаты
внести в таблицу.
Вариант задания определяется по номеру i (предпоследняя
цифра) и j (последняя цифра зачетной книжки) – требуемая для
реализации этого алгоритма число x .
Число j –
начальный номер для второго абонента при выборе числа x. Для выбора x для
связи с пятью абонентами необходимо по циклической процедуре выбрать x по
последней цифре зачетки. Например, цифры в зачетной книжке (15). Выбираем для
первого абонента x=11, т.к. i =1. Для
второго по второй цифре
x =29, т.к. j= 5. Для третьего по формуле (j +1)=i выбираем
x= 31, т.к. j =6. Для четвертого выбираем x = 37, j =7.
Для пятого выбираем x = 39, т.к. j=8. Если, например, последняя цифра (27) больше пяти - пусть j =7, то выбираем x = 31,37, 39,41, 7.
Рекомендуемые значения p =
Таблица 2.1 - Исходные данные:
I |
0 |
1 |
2 |
3 |
4 |
X |
7 |
11 |
13 |
17 |
19 |
I |
5 |
6 |
7 |
8 |
9 |
x
|
29 |
31 |
37 |
39 |
41 |
Методические указания к
решению задания 2.1
Первая система с открытым ключом — система Диффи-Хеллмана.
Эта криптосистема была открыта в середине 70-х годов
американскими учеными Диффи (Whitfield Diffie) и Хеллманом (Martin Hell-man) и привела к настоящей революции в криптографии и ее
практических применениях. Это первая система, которая позволяла защищать
информацию без использования секретных ключей, передаваемых по защищенным
каналам. Для того чтобы продемонстрировать одну из схем применения таких
систем, рассмотрим сеть связи с N пользователями,
где N — большое число. Пусть мы
хотим организовать секретную связь для каждой пары из них. Если мы будем
использовать обычную систему распределения секретных ключей, то каждая пара
абонентов должна быть снабжена своим секретным ключом, т.е. всего потребуется ключей.
Если абонентов 100, то требуется 5000 ключей, если же
абонентов 104 , то ключей должно быть 5∙107. Мы
видим, что при большом числе абонентов система снабжения их секретными ключами
становится очень громоздкой и дорогостоящей.
Диффи и
Хеллман решили эту проблему за счет открытого распространения и вычисления
ключей. Перейдем к описанию предложенной ими системы.
Пусть строится система связи для абонентов А,В,С,... .
У каждого абонента есть своя секретная и открытая
информация. Для организации этой системы
выбирается большое простое число р и
некоторое число g, 1 < g < р — 1 такое, что все числа из множества {1, 2, ∙ ∙
∙ , р — 1} могут быть представлены как различные степени g mod p (известны
различные подходы для нахождения
таких чисел g, один из них будет представлен ниже).
Числа р и g известны всем абонентам.
Абоненты выбирают большие числа Xa,Xb,Xc, которые хранят в секрете (обычно такой выбор рекомендуется
проводить случайно, используя датчики случайных чисел). Каждый абонент вычисляет
соответствующее число Y, которое открыто передается другим
абонентам,
YА = gXa mod р ,
YB = gXb mod р.. (1)
Yс = gXc mod р.
В
результате получаем следующую таблицу.
Таблица 2.2
- Ключи пользователей в системе Диффи-Хеллмана
Абонент |
Секретное
число |
Открытый
ключ |
Закрытый
ключ |
A B C |
XA XB XC |
YA YB YC |
ZAB, ZAC ZBA, ZBC ZCA, ZCB |
Допустим, абонент А
решил организовать сеанс связи с В,
при этом обоим абонентам доступна открытая информация из таблицы 2. Абонент А сообщает В по открытому каналу, что он хочет передать ему сообщение.
Затем абонент А вычисляет
величину
ZAB = (YB)ХА modp. (2)
Никто другой, кроме А,
этого сделать не может, так как число ХА секретно.
В свою очередь, абонент В вычисляет число
ZBA = (YA)XBmodp. (3)
На рисунке 1 представлена схема обмена ключами в системе
Диффи-Хеллмана.
Остановимся теперь на упомянутой выше задаче выбора числа р. При произвольно заданном g она может оказаться трудной задачей, связанной с разложением на
простые множители числа g - 1. Дело в том, что для обеспечения высокой
стойкости рассмотренной системы число g - 1 должно обязательно содержать большой
простой множитель. Поэтому часто рекомендуют использовать следующий подход.
Число р выбирается таким, чтобы выполнялось равенство
р=2q+1 (где q- также простое число)
и были справедливы неравенства
1 < g < р - 1 и gq mod р 1.
Для того чтобы система была устойчива к криптоанализу,
необходимо выбирать число р очень большим.
Рисунок 1 - схема обмена ключами в системе
Диффи-Хеллмана
Пример.
Пусть g = 43. Выберем параметр
p. Попробуем взять q=17 401.
Соответственно р=2*17 401+1=34 803. Проверим:
4317401 mod 34 803 = 17 746.
Необходимые условия выполняются, значит, такое р подходит. Итак, мы выбрали параметры р =
Контрольные вопросы
1. Какими преимуществами
перед другими алгоритмами с закрытым ключом обладает система Диффи-Хеллмана?
2.
Дайте краткую характеристику системы Диффи-Хеллмана.
3.
Объясните, почему число р, необходимое при вычислении секретных ключей, следует
выбирать большим?
Задание 2.2. Шифрование
по алгоритму Шамира
Зашифровать
сообщение по алгоритму Шамира для трех абонентов, взяв значение сообщения m и значение p из таблицы 2.3. По номеру i
(предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j –
требуемые для реализации этого алгоритма число р. Выбор данных для других абонентов
произвести циклически согласно процедуре (I + 1) и (G +
1). Например, последние цифры номера зачетной книжки – (26). Выбираем для трех
абонентов (сообщение, p)
- (16,49), (18,51), (20,53).
Таблица 2.3 – Исходные
данные
I |
0 |
1 |
2 |
3 |
4 |
Сообщение |
12 |
14 |
16 |
18 |
20 |
G |
0 |
1 |
2 |
3 |
4 |
p
|
29 |
31 |
37 |
41 |
43 |
I |
5 |
6 |
7 |
8 |
9 |
Сообщение |
22 |
24 |
26 |
28 |
30 |
G |
5 |
6 |
7 |
8 |
9 |
p |
47 |
49 |
51 |
53 |
57 |
Методические указания к
заданию 2.2
Этот шифр, предложенный
Шамиром (Adi Shamir),
был первым, позволяющим организовать обмен секретными сообщениями по открытой
линии связи для лиц, которые не имеют никаких защищенных каналов и секретных
ключей и, возможно, никогда не видели друг друга. (Напомним, что система Диффи-Хеллмана позволяет сформировать
только секретное слово, а передача сообщения потребует использования
некоторого шифра, где это слово будет использоваться как ключ.)
Перейдем к описанию системы. Пусть есть
два абонента А и В, соединенные линией связи. А хочет передать сообщение m абоненту
B так, чтобы никто не
узнал его содержание. А выбирает
случайное большое простое число р и
открыто передает его В. Затем А выбирает два числа сА
и dA , такие, что
сАdA mod (р - 1) = 1. (2.1)
Эти числа А держит в секрете и передавать не будет. В тоже выбирает два секретных числа св и dв, такие, что
свdв mod (p - 1) = 1. (2.2)
После этого А передает
свое сообщение m,
используя трехступенчатый протокол. Если 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, вычисляет число
х2 = х1CB mod p. (2.4)
и передает х2 к А.
Шаг 3. А вычисляет число
х3 = х2dA mod p.
(2.5)
и передает его В.
Шаг 4. В, получив х3, вычисляет число
Х4 = x3dB mod p. (2.6)
Схема обмена ключами по алгоритму Шамира представлена на рисунке
2.
Рисунок 2 - схема обмена ключами в системе
Шамира
Утверждение (свойства
протокола Шамира):
1) х4 = m, т.е. в результате реализации протокола от А к В
действительно передается исходное сообщение;
2) злоумышленник не может узнать, какое сообщение было передано.
Доказательство. Вначале заметим, что любое
целое число е 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 с помощью обобщенного алгоритма Евклида.
Пример.
Пусть А хочет передать В сообщение m = 10. А выбирает
р = 23, сА = 7 (gcd(7,22) = 1) и вычисляет dA = 19. Аналогично, В выбирает
параметры cB = 5 (взаимно простое с 22) и dB = 9.
Переходим к протоколу Шамира.
Шаг 1. x1 = 107
mod 23 = 14.
Шаг 2. х2
= 145 mod 23 = 15.
ШагЗ. x3= 1519 mod 23 = 19.
Шаг 4. х4
= 199 mod 23 = 10.
Таким образом, В получил
передаваемое сообщение m = 10.
Контрольные
вопросы
1.
Дайте краткую характеристику системы шифрования по алгоритму Шамира.
2.
Сколько пересылок между двумя абонентами необходимо совершить для передачи
одного сообщения в данном алгоритме?
3.
Какими преимуществами перед другими алгоритмами шифрования обладает система
Шамира?
Задание 2.3. Шифрование по алгоритму Эль-Гамаля
По таблице 2.4 выбрать сообщение
m и секретный ключ x и провести шифрование по методу Эль-Гамаля
для пяти абонентов. Вариант задания определяется последними цифрами номера
студенческого билета. По номеру i (предпоследняя цифра)
студент выбирает сообщение для зашифровывания, по j (последняя цифра) –
требуемые для реализации этого алгоритма
секретный ключ x. Исходные данные для других
четырех секретных ключей x выбираются циклически по
процедуре (i+1) и (j+1). Например, последние
цифры 24. Выбираем для пяти абонентов- (сообщение, x) - (9,37), (11,43),
(13,47), (3,51), (15,29). Результаты заносятся в таблицу по схеме «абонент –
секретный ключ – открытый ключ». Аналогично таблице 2.5. Рекомендуемые значения
для p =
Таблица 2.4 - Исходные
данные
I |
0 |
1 |
2 |
3 |
4 |
Сообщение |
5 |
7 |
9 |
11 |
13 |
G |
0 |
1 |
2 |
3 |
4 |
X |
29 |
11 |
13 |
7 |
19 |
I |
5 |
6 |
7 |
8 |
9 |
Сообщение |
3 |
15 |
11 |
15 |
13 |
G |
5 |
6 |
7 |
8 |
9 |
X |
31 |
37 |
43 |
47 |
51 |
Методические указания к заданию 2.3
Пусть имеются абоненты А, В, С, ..., которые хотят передавать друг другу зашифрованные
сообщения, не имея никаких защищенных каналов связи. Шифр, предложенный
Эль-Гамалем (Tahcr ElGamal), решает эту задачу, используя, в отличие от шифра Шамира, только
одну пересылку сообщения. Фактически здесь используется схема Диффи-Хеллмана,
чтобы сформировать общий секретный ключ для двух абонентов, передающих друг
другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ.
Для каждого следующего сообщения секретный ключ вычисляется заново. Перейдем к
точному описанию метода.
Для всей группы абонентов выбираются
некоторое большое простое число р и
число g, такие, что
различные степени g суть различные числа по модулю р. Числа р и g передаются абонентам в открытом виде (они
могут использоваться всеми абонентами сети).
Затем каждый абонент группы выбирает свое секретное число ci, 1 < сi < р - 1 и
вычисляет соответствующее ему открытое число di,
di=gcimodp. (3.1)
Результат
представлен в таблице 2.5.
Необходимо выбрать числа p и g
так, чтобы они отвечали следующим требованиям:
gq mod p 1,
где p=2q+1.
Таблица 2.5- Ключи пользователей в системе
Эль-Гамаля
Абонент |
Секретный ключ |
Открытый ключ |
А |
сА |
dA |
В |
сВ |
dB |
С |
сD |
dC |
Покажем теперь, как А
передает сообщение абоненту В. Будем
предполагать, как и при описании шифра Шамира, что сообщение представлено в
виде числа m < р.
Схема обмена ключами по алгоритму Эль-Гамаля представлена на
рисунке 3.
Рисунок 3 - схема обмена ключами в системе Эль-Гамаля
Шаг 1. А
формирует случайное число к, 1
к р-2, вычисляет
числа
r = gk
mod p, (3.2) e = m dBk mod
p (3.3)
и передает пару чисел (r, е) абоненту В.
Шаг 2. В, получив (r,е), вычисляет
m' = е rp-1-cBmod р. (3.4)
Ясно, что по аналогичной схеме могут передавать
сообщения все абоненты в сети. Заметим, что любой абонент, знающий открытый
ключ абонента В, может посылать
ему сообщения, зашифрованные с помощью открытого
ключа dB. Но только абонент В, и никто другой, может расшифровать эти
сообщения, используя известный только ему секретный ключ сВ. Отметим также, что
объем шифра в два раза превышает объем сообщения, но требуется только одна
передача данных (при условии, что таблица с открытыми ключами заранее известна
всем абонентам).
Контрольные вопросы
1.
Дайте краткую характеристику системы шифрования по алгоритму Эль-Гамаля.
2.
Сколько секретных ключей генерируется для пересылки, например, трех сообщений
между абонентами А и В?
3. Какими основными преимуществами обладает эта система перед другими?
1.Романец Ю. В. Защита информации в компьютерных системах и сетях. /Под ред. В.Ф. Шаньгина. – М.: Радио и связь 1999
2.Петраков А.В. Основы практической
защиты информации. 2-е издание Учебн. Пособие. – М.: Радио и связь, 200 с.
3. Рябко Б. Я., Фионов А.Н.
Криптографические методы защиты информации. –М.: Горячая линия- Телеком, 2005.
Сводный
план