Некоммерческое акционерное общество
АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ
Кафедра Автоматическая Электросвязь
ЗАЩИТА ИНФОРМАЦИИ В ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ
Методические указания к выполнению расчетно- графических работ
для студентов очной формы обучения специальности 050719 -
– Радиотехника, электроника и телекоммуникации
Алматы 2008
СОСТАВИТЕЛИ: А.С. Байкенов, Шкрыгунова Е.А. Защита информации в телекоммуникационных системах. Методические указания к выполнению расчетно-графических работ для студентов очной формы обучения специальности 050719 – Радиотехника, электроника и телекоммуникации – Алматы; АИЭС, 2008 – 22 с.
Методические указания содержат общие положения по выполнению расчетно-графических работ. Приводится рекомендуемая литература.
Содержание
1 Введение…………………………………………………………………...4
Расчетно-графическое задание № 1……………………………………….4
Задание 1.1…………………………………………………………………..4
Методические указания к решению задания 1.1………………………….5
Задание 1.2…………………………………………………………………..7
Расчетно-графическое задание № 2……………………………………..12
Задание 2.1…………………………………………………………………12
Методические указания к решению задания 2.1……………………… 12
Задание 2.2…………………………………………………………………15
Методические указания к заданию №2.2……………………………… 15
Задание 2.3…………………………………………………………………18
Методические указания к заданию 2.3………………………………… 19
Список литературы ……………………………………………………….21
Введение
Целью расчетно-графических работ является ознакомление студентов с математической основой построения систем защиты информации в телекоммуникационных системах - методами криптографии. Расчетно-графические работы направлены на формирование у студентов систематизированного представления о принципах, методах и средствах реализации защиты данных.
Расчетно-графические работы посвящены изучению систем шифрования с закрытым и открытым ключом. Расчетно-графическая работа №1 посвящена шифрованию с закрытым ключом. Рассматриваются алгоритмы RSA, а также предлагаются расчеты по электронной подписи с использованием хеш-функции
Расчетно-графическая работа №2 посвящена асимметричному шифрованию или шифрованию с открытым ключом. Рассматриваются алгоритмы Дифи –Хелмана, Шамира, Эль-Гамаля.
1 Расчетно-графическое задание № 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 |
0 |
1 |
2 |
3 |
4 |
p q |
7.17 |
5.11 |
7.13 |
11.17 |
5.13 |
Методические указания к решению задания 1.1
Одним из наиболее распространенных методов несимметричного шифрования- дешифрования является метод шифрования с открытым ключом, в котором используется алгоритм RSA.
Алгоритм основан на использовании операции возведения в степень модульной арифметики. Его можно представить в виде следующей последовательности шагов:
Шаг 1. Выбирается два больших простых числа числа р и q. Простыми называются числа, которые делятся на самих себя и на 1. На практике для обеспечения криптостойкости системы величина этих чисел должна быть длиной не менее двухсот десятичных разрядов.
Шаг 2. Вычисляется открытая компонента ключа n
n = р q.
Шаг 3. Находится функция Эйлера по формуле
f(р q.)=(р-1)(q-1)
Функция Эйлера показывает количество целых положительных чисел от1 до n, которые не имеют ни одного общего делителя, кроме 1.
Шаг 4. Выбирается число е, которое должно взаимно простым со значением функции Эйлера и меньшим, чем f(р q.)
Шаг 5. Определяется число d, удовлетворяющее соотношению
е * d(mod f(р q.))=1
Числа е и n принимаются в качестве открытого ключа. В качестве секретного ключа используются числа d и n.
Шаг 6. Исходная информация независимо от её физической природы представляется в числовом двоичном виде. Последовательность бит разделяется на блоки длиной L бит, где L – наименьшее целое число, удовлетворяющее условию L ³ log2(n.+1); Каждый блок рассматривается как целое положительное число X(i), принадлежащее интервалу (0, n-1). Таким образом, исходная информация представляется последовательностью чисел X(i), (i = 1.I).Значение I определяется длиной шифруемой последовательности.
Шаг 7. Зашифрованная информация получается в виде последовательности чисел Y(i)= (Y(i)) e (mod n).
Шаг 8. Для расшифрования информации используется следующая зависимость Х(i)= (Y(i)) e (mod n).
Рассмотрим числовой пример применения метода RSA для криптографического закрытия информации, в котором для простоты вычислений использованы минимально возможные числа. Пусть требуется зашифровать сообщение на русском языке ПРЕДЕЛ.
Сообщение: ПРЕДЕЛ
Простые числа p и q - 3,11
Зашифруем и расшифруем сообщение "ПРЕДЕЛ" по алгоритму RSA:
1) Выберем p=3 and q=11.
2)Вычислим открытую компоненту ключа: n = 3*11=33.
3) Определим функцию Эйлера: (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
4) Выберем число е по следующей формуле: (e*3) mod 20=1. е будет равно 7: (e=7).
Числа е и n принимаются в качестве открытого ключа, d и n используются в качестве секретного ключа.
Таблица 1.2 – Позиции букв в алфавите
Буквы алфавита |
А |
Б |
В |
Г |
Д |
Е |
Ж |
З |
И |
Й |
К |
Л |
М |
Н |
О |
П |
Р |
Номер буквы |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
Буквы алфавита |
С |
Т |
У |
Ф |
Х |
С |
Ч |
Ш |
Щ |
Ъ |
Ы |
Ь |
Э |
Ю |
Я |
|
|
Номер буквы |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
|
|
5) Представим шифруемое сообщение как последовательность чисел в диапазоне от 0 до 32: 16, 17, 6, 5, 6, 12,
Для представления чисел в двоичном виде требуется 6 двоичных разрядов, так как в русском алфавите используются 33 буквы, поэтому исходный текст имеет вид: 010000, 010001, 000110, 000101, 000110, 001100.
Длина блока L определяется как минимальное число из целых чисел, удовлетворяющих условию L ³ log2(33+1); L=6
Теперь зашифруем сообщение, используя открытый ключ {7,33}
Y1 = (167) mod 33 = ;
Y2 = (177) mod 33 = ;
Y3 = (67) mod 33 = ;
Y4 = (57) mod 33 = ;
Y5 = (67) mod 33 = ;
Y6 = (12^7) mod 33 = ;
Расшифруем полученные данные, используя закрытый ключ {3,33}.
Y1 = (253) mod 33 = ;
Y2 = (83) mod 33 = ;
Y3 = (303) mod 33 = ;
Y4 = (143) mod 33 = ;
Y5 = (307) mod 33 = ;
Y6 = (123) mod 33 = ;
Данные расшифрованы, сопоставим последовательность <16, 17, 6, 5, 6, 12> с последовательностью букв нашего алфавита. Получили слово ПРЕДЕЛ.
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:
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 Система с открытым ключом Диффи-Хелмана
Сгенерировать секретные ключи для пяти абонентов A, B, C, D и по методу Диффи-Хеллмана (DH). Для этого взять значение g из таблицы 1.1 (i - предпоследняя цифра номера зачетной книжки), а значение р подобрать согласно методическим указаниям.
Число j (последняя цифра номера зачетной книжки) – номер для первого абонента (абонента А) при выборе числа ХА. Значения XB, XC, XD, XE для остальных четырех абонентов необходимо выбрать по циклической процедуре, прибавляя каждый раз по единице.
Например, цифры в зачетной книжке (15). Выбираем число g = 3, т.к. i= 1. Значение ХА равно 29 (т. к. j =5). Для второго абонента значение ХВ будет равно 31 (j =5+1=6), Для третьего ХС = 37, т. к. j =7. Для пятого выбираем ХЕ = 41, т.к. j=9. Если, например, последняя цифра номера зачетной книжки 7 (больше пяти), то выбираем ХА=37, ХВ=39, ХС=41, ХD=7, ХE= 11.
Таблица 1.1 Исходные данные для числа g:
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
g |
1 |
3 |
5 |
11 |
23 |
29 |
41 |
101 |
113 |
179 |
Таблица 1.2 Исходные данные для чисел XA, XB, XC, XD, XE:
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
X |
7 |
11 |
13 |
17 |
19 |
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 р.
В результате получаем следующую таблицу.
Таблица 1.3 Ключи пользователей в системе Диффи-Хеллмана
Абонент |
Секретное число |
Открытый ключ |
Закрытый ключ |
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 - схема обмена ключами в системе Диффи-Хеллмана
Пример 2.1. Пусть g = 43. Выберем параметр p. Попробуем взять q=17 401.
Соответственно р=2*17 401+1=34 803. Проверим: 4317401 mod 34 803 = 17 746. Необходимые условия выполняются, значит, такое р подходит. Итак, мы выбрали параметры р = 34 803, g = 43. Теперь каждый абонент выбирает секретное число и вычисляет соответствующее ему открытое число. Пусть выбраны ХA = 7, ХB = 13. Вычисляем YA = 437 mod 34 803 = 11 689, YB = 4313 mod 34 803 = 14 479. Пусть А и В решили сформировать общий секретный ключ. Для этого А вычисляет ZAB = 144797 mod 34 803=6 415, а В вычисляет ZBA = 11 68913 mod 34 803 = 6 415. Теперь они имеют общий ключ 6 415, который не передавался по каналу связи.
Контрольные вопросы
1. Какими преимуществами перед другими алгоритмами с закрытым ключом обладает система Диффи-Хеллмана?
2. Дайте краткую характеристику системы Диффи-Хеллмана.
3. Объясните, почему число р, необходимое при вычислении секретных ключей, следует выбирать большим?
2.2 Шифрование по алгоритму Шамира
Зашифровать сообщение по алгоритму Шамира для трех абонентов, взяв значение сообщения m и значение p из таблиц 2.1 и 2.2 соответственно. По номеру j (последняя цифра номера зачетной книжки) выбирается требуемое для реализации этого алгоритма число р. По i (предпоследняя цифра номера зачетной книжки) студент выбирает сообщение для зашифровывания, передаваемое первым абонентом. Выбор сообщений для других абонентов производится циклически, согласно процедуре (i + 1). Например, последние цифры номера зачетной книжки – (63). Выбираем для трех абонентов p = 41, mA=24, mB=24, mC=24.
Таблица 2.1 – исходные данные для выбора сообщений (m)
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Сообщение (m) |
12 |
14 |
16 |
18 |
20 |
22 |
24 |
26 |
28 |
30 |
Таблица 2.2 – исходные данные для выбора числа р
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
р |
29 |
31 |
37 |
41 |
43 |
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 с помощью обобщенного алгоритма Евклида.
Пример 2.1. Пусть А хочет передать В сообщение 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 Шифрование по алгоритму Эль-Гамаля
По таблице 3.2 выбрать числа p и g и провести шифрование по методу Эль-Гамаля для пяти абонентов. Вариант задания определяется последними цифрами номера студенческого билета. По номеру j (последняя цифра номера зачетной книжки) студент выбирает требуемые для реализации этого алгоритма числа р и g. По номеру i (предпоследняя цифра номера зачетной книжки) - сообщение первого абонента. Сообщения для других четырех абонентов выбираются циклически по процедуре (i + 1). Например, последние цифры 27. Выбираем для пяти абонентов: p=17, g=7, m=9, m=11, m=13, m=3, m=15.
Таблица 3.1 Исходные данные для выбора сообщений
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Сообщение (m) |
5 |
7 |
9 |
11 |
13 |
3 |
15 |
11 |
15 |
13 |
Таблица 3.2 Исходные данные для выбора чисел p и g
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
p, g |
29,11 |
17,11 |
21,11 |
13,11 |
23,17 |
23,7 |
29,7 |
17,7 |
19,7 |
19,11 |
Методические указания к заданию 2.3
Пусть имеются абоненты А, В, С, ..., которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищенных каналов связи. Шифр, предложенный Эль-Гамалем (Tahcr ElGamal), решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку сообщения. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего сообщения секретный ключ вычисляется заново. Перейдем к точному описанию метода.
Для всей группы абонентов выбираются некоторое большое простое число р и число g, такие, что различные степени g суть различные числа по модулю р. Числа р и g передаются абонентам в открытом виде (они могут использоваться всеми абонентами сети).
Затем каждый абонент группы выбирает свое секретное число ci, 1 < сi < р - 1 и вычисляет соответствующее ему открытое число di,
di=gcimodp. (3.1)
Результат представлен в таблице 3.3.
Таблица 3.3- Ключи пользователей в системе Эль-Гамаля
Абонент |
Секретный ключ |
Открытый ключ |
А |
сА |
dA |
В |
сВ |
dB |
С |
сD |
dC |
Покажем теперь, как А передает сообщение абоненту В. Будем предполагать, как и при описании шифра Шамира, что сообщение представлено в виде числа m < р.
Шаг 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)
Схема обмена ключами по алгоритму Эль-Гамаля представлена на рисунке 3.
Рисунок 3 - схема обмена ключами в системе Эль-Гамаля
Контрольные вопросы
1. Дайте краткую характеристику системы шифрования по алгоритму Эль-Гамаля.
2. Сколько секретных ключей генерируется для пересылки, например, трех сообщений между абонентами А и В?
3. Какими основными преимуществами обладает эта система перед другими?
Список литературы
1.Романец Ю. В. Защита информации в компьютерных системах и сетях. /Под ред. В.Ф. Шаньгина. – М: Радио и связь 1999
2.Петраков А.В. Основы практической защиты информации. 2-е издание Учебн. Пособие. – М: Радио и связь 200
3. Рябко Б. Я., Фионов А.Н. Криптографические методы защиты информации. –М: Горячая линия- Телеком, 2005.