22

РЕСПУБЛИКА КАЗАХСТАН

АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра Автоматической электросвязи

Дисциплина: Защита информации в телекоммуникационных системах

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА №2

Тема: «Алгоритмы шифрования c открытым ключом»

                                                                                                                                                     Принял:

ст. преп-ль

Е. А. Шкрыгунова

«__» ________ 2009

Выполнил:

Ш. Р. Шагеев

Группа БРЭ-06-08

Специальность РЭиТ

№ зач. кн. 063097

Алматы 2009

СОДЕРЖАНИЕ

ВВЕДЕНИЕ              3

1 СИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ ДИФФИ-ХЕЛМАНА              4

1.1 Задание 1. Исходные данные              4

1.2 Выполнение задания 1              5

2 ШИФРОВАНИЕ ПО АЛГОРИТМУ ШАМИРА              8

2.1 Задание 2. Исходные данные              8

2.2 Выполнение задания 2              9

3 ШИФРОВАНИЕ ПО АЛГОРИТМУ ЭЛЬ-ГАМАЛЯ              16

3.1 Задание 3. Исходные данные              16

3.2 Выполнение задания 3              17

ЗАКЛЮЧЕНИЕ              21

СПИСОК ЛИТЕРАТУРЫ              22

ВВЕДЕНИЕ

С развитием информационных технологий в современном мире понятие «защита информации» приобретает все более важное значение. Особую роль в этом отношении играет защита данных с помощью шифрования. Уже с древних времен люди, особенно во время военных действий, использовали примитивные методы шифрования (к примеру, шифр Цезаря), так как понималось, что зашифрованные данные доступны лишь тому, кто знает ключ к расшифровке, поэтому бессмысленно похищение зашифрованных данных для несанкционированных пользователей.

Алгоритмы шифрования можно разделить на симметричные (одноключевые, с одним секретным ключом для шифрования и расшифрования) и асимметричные (с открытым ключом для шифрования и с секретным для дешифрования).

Первая система с открытым ключом — система Диффи-Хеллмана. Эта криптосистема была открыта в середине 70-х годов американ­скими учеными Диффи (Whitfield Diffie) и Хеллманом (Martin Hell-man) и привела к настоящей революции в криптографии и ее практи­ческих применениях. Это первая система, которая позволяла защи­щать информацию без использования секретных ключей, передавае­мых по защищенным каналам.

Шифр, предложенный Шамиром (Adi Shamir), был первым, позволяющим организовать обмен секретными сообщениями по от­крытой линии связи для лиц, которые не имеют никаких защищен­ных каналов и секретных ключей и, возможно, никогда не видели друг друга (используются несколько пересылок сообщений). Шифр, предло­женный Эль-Гамалем (Tahcr ElGamal), решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку со­общения.

1 СИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ ДИФФИ-ХЕЛМАНА

1.1 Задание 1. Исходные данные

Сгенерировать секретные ключи для пяти абонентов по методу  Диффи-Хеллмана (DH). Для этого взять значение g из таблицы 1.1, а значение p подобрать согласно методическим указаниям. Результаты внести в таблицу. Вариант задания определяется по номеру i (последняя цифра зачетной книжки) – требуемая для реализации этого алгоритма число g .

Таблица 1.1 –  Исходные данные:

ИСХОДНЫЕ ДАННЫЕ:

g=101.

1.2 Выполнение задания 1

Рассмотрим сеть связи с N пользователями, где N — большое число. Пусть мы хотим органи­зовать секретную связь для каждой пары из них. Если мы будем использовать обычную систему распределения секретных ключей, то каждая пара абонентов должна быть снабжена своим секретным ключом, т.е. всего потребуется ключей.

Если абонентов 100, то требуется 5000 ключей, если же абонен­тов 104, то ключей должно быть 5∙107. Мы видим, что при большом числе абонентов система снабжения их секретными ключами стано­вится очень громоздкой и дорогостоящей.

Диффи и Хеллман решили эту проблему за счет открытого рас­пространения и вычисления ключей.

Строится система связи для абонентов А, В, С, D, E .У каж­дого абонента есть своя секретная и открытая информация. Для  организации этой системы выбирается большое простое число р и некоторое число g,                 1 < g < р — 1, такое, что все числа из множе­ства {1, 2, ∙ ∙ ∙ ,р — 1} могут быть представлены как различные сте­пени g mod p. Числа р и g известны всем абонентам. Выберем р таким, чтобы выполнялось равенство:

р=2q+1,

где q - также простое число. Проследим выполнение неравенства:

1 < g < р — 1    и    gq mod р 1.

Возьмём q=15401. При этом р=2*15401+1=30803.   Проверим соотношение:

10115401 mod 30803 = 30802,

примем данное значение р. Итак, имеем:

р=30803, g=101.

Абоненты выбирают большие числа XA, XB, XC, XD, XE (см. табл. 1.2), которые хра­нят в секрете (обычно такой выбор рекомендуется проводить случай­но, используя датчики случайных чисел). Каждый абонент вычис­ляет соответствующее число Y, которое открыто, передается другим абонентам [3, формула (2.9)].

YA = gXa mod р

YB = gXb mod р

YC = gXc mod р

YD = gXd mod р

YE = gXe mod р

Вычисляем:

Таблица 1.2 - Ключи пользователей в системе Диффи-Хеллмана

Пусть А и В реши­ли сформировать общий секретный ключ. Абонент А сообщает В по открытому каналу, что он хочет передать ему сообщение. Затем абонент А вычисляет величину [3]:

ZAB = (YB)XA mod p                                       (1.2)

ZAB = 439841 mod 30803 = 13497,

(никто другой кроме А этого сделать не может, так как число Х секретно). В свою очередь, абонент В вычисляет число [3]:

ZBA = (YA)XB mod p                                   (1.3)

ZBA = 729737 mod 30803 = 13497.

Теперь они имеют общий ключ 13497, который не передавался по кана­лу связи.

Точно так же вычисляем для остальных участников:

Таблица 1.3 – Результаты выполнения задания

2 ШИФРОВАНИЕ ПО АЛГОРИТМУ ШАМИРА

2.1 Задание 2. Исходные данные

Зашифровать сообщение по алгоритму Шамира для трех абонентов,  взяв значение сообщения m и значение p из таблицы 2.1. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j – требуемое для реализации этого алгоритма число р. Выбор сообщений для других абонентов произвести циклически согласно процедуре (i + 1). Например, последние цифры номера зачетной книжки – (63). Выбираем для трех абонентов (сообщение, p) -  (24,41), (26,41), (28,41).

Таблица 2.1 – Исходные данные

ИСХОДНЫЕ ДАННЫЕ:

Сообщение 1 – 30;

Сообщение 2 – 12;

Сообщение 3 – 14;

P=61.

2.2 Выполнение задания 2

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

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

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

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

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

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

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

                                                        ax + by = gcd(a, b)                            (2.3)  [3]

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

ВХОД:              Положительные целые числа a, b, .

ВЫХОД:    gcd(a,b), x, y, удовлетворяющие (2.3).

1.                       U←(a,1,0), V←(b,0,1)

2.                       WHILE DO

3.                       q←u1 div v1

4.                       T←(u1 mod  v2, u2-qu2, u3-qv3);

5.                       U←V, V←T.

6.                       RETURN U=(gcd(a,b),x,y).

Результат содержится в строке U.

Операция div в алгоритме – это целочисленное деление

a div b=[a/b]

Важное применение обобщенного алгоритма Евклида: во многих задачах криптографии для заданных чисел с, m требуется находить такое число d<m, что

                                                                      cd mod m = 1.                                                        (2.4)

Отметим, что такое d существует тогда и только тогда, когда числа c и m взаимно простые. Число d, удовлетворяющие (2), называется инверсией  c по модулю m и часто обозначается c-1 mod m = 1.

Покажем, как можно вычислить инверсию с помощью обобщенного алгоритма Евклида. Равенство (2.4) означает, что для некоторого целого k

                                                                      cd – km = 1                                          (2.5)

Учитывая, что c и m взаимно просты, перепишем (2.5) в виде

                                                        m(-k)+cd=gcd(m,c),                            (2.6)

что полностью соответствует (2.3), здесь только по-другому обозначены переменные. Поэтому, чтобы вычислить с-1 mod m, т. е. найти число d, нужно просто использовать обобщенный алгоритм Евклида для решения уравнения (2.6) если число d получается отрицательным, то нужно прибавить к нему m, так как по определению число а mod m берется из множества {0,1,…,m-1} [3].

Произведем расчет сА dA ; сВ dВ ; сС dС.

Имеем:

ma=30                                          mb=12                            mc=14

P=61                                          P=61                                          P=61                                                                  

P-1=60

Случайные числа  cA=7,    cB=19,   cC=47

Подставим в уравнение (2.5):

cАdА – k(p-1) = 7dА – 60k =1

Обратимся к алгоритму Евклида:

60              0

7              1

4              -8              q=8

3              9              q=1

1              -17              q=1

0              60              q=3

dА=-17    прибавим m:    dА=43

Произведем проверку, правильно ли мы вычислили dА. Для того проверим верность следующего уравнения:

cA*dA mod (p-1) = 1                            7*43 mod (61-1)=301 mod 60=1

То же самое делает другой абонент, которому адресовано сообщение:

Второй абонент:

cВdВ – k(p-1) = 19dА – 60k =1

Обратимся к алгоритму Евклида:

60              0

19              1

3              -3              q=3

1              19              q=6

0              -60              q=3

dB=19.

Произведем проверку, правильно ли мы вычислили dB. Для того проверим верность следующего уравнения:

cB*dB mod (p-1) = 1                            19*19 mod (61-1)=361 mod 50=1

Третий абонент:

cCdC – k(p-1) = 47dC – 60k =1

Обратимся к алгоритму Евклида:

60              0

47              1

13              -1              q=1

8              4              q=3

5              -5              q=1

3              9              q=1

2              -14              q=1

1              23              q=1

0              -60              q=2

dC=23.

Произведем проверку, правильно ли мы вычислили dА. Для того проверим верность следующего уравнения:

cC*dC mod (p-1) = 1                            47*23 mod (61-1)=1081 mod 60=1

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

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

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

х1 =mСа mod p                         (2.3)

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

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

x2 = х2Cb mod p                         (2.4)

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

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

x3 = х2da mod p                          (2.5)

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

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

x4 = x3dB mod p                         (2.6)

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

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

2)   злоумышленник не может, узнать, какое сообщение было пе­редано [3].

A передает сообщение ma=30 абоненту В, выбрав p=61 (открыто передается). А вычисляет cA=7, dА=43 (закрыт, не передается) и В вычисляет cB=19,  dB=19 (тоже не передается).

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

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

х1 = mСа mod p

х1 = 307 mod 61 = 10

и пересылает х1 к В.

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

x2 = х1Cb mod p

х2 = 1019 mod 61 = 44

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

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

x3 = х2da mod p

х3 = 4443 mod 61 = 35

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

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

x4 = x3db mod p.

х4 = 3519 mod 61 = 30

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

B передает сообщение mb=12 абоненту C, выбрав p=61 (открыто передается). А вычисляет cB=19, dB=19 (закрыт, не передается) и C вычисляет cC=47,  dC=23 (тоже не передается).

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

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

х1 = mСb mod p

х1 = 1219 mod 61 = 57

и пересылает х1 к C.

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

x2 = х1Cc mod p

х2 = 4247 mod 61 = 16

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

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

x3 = х2db mod p

х3 = 1619 mod 61 = 22

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

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

x4 = x3dc mod p.

х4 = 2223 mod 61 = 12

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

C передает сообщение mc=14 абоненту A, выбрав p=61 (открыто передается). C вычисляет cC=47, dC=23 (закрыт, не передается) и A вычисляет cA=7,  dA=43 (тоже не передается).

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

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

х1 = mСc mod p

х1 = 1447 mod 61 = 48

и пересылает х1 к A.

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

x2 = х1Ca mod p

х2 = 487 mod 61 = 48

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

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

x3 = х2dc mod p

х3 = 4823 mod 61 = 14

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

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

x4 = x3da mod p.

х4 = 1419 mod 61 = 14

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

3 ШИФРОВАНИЕ ПО АЛГОРИТМУ ЭЛЬ-ГАМАЛЯ

3.1 Задание 3. Исходные данные

По таблице 3.1 выбрать числа p и  g и провести шифрование по методу Эль-Гамаля для пяти абонентов. Вариант задания определяется последними цифрами номера студенческого билета. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j – требуемые для реализации этого алгоритма числа р и q. Исходные сообщения для других четырех абонентов выбираются циклически по процедуре (i + 1)

Таблица 3.1 – Исходные данные

ИСХОДНЫЕ ДАННЫЕ:

Сообщение 1 – 13;

Сообщение 2 – 5;

Сообщение 3 – 7;

Сообщение 4 – 9;

Сообщение 5 – 11;

p=17;

g=7.

3.2 Выполнение задания 3

Пусть имеются абоненты А, В, С, D, E, которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищен­ных каналов связи. Шифр Эль-Гамаля решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку со­общения. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего со­общения секретный ключ вычисляется заново.

Для всей группы абонентов выбираются некоторое большое про­стое число р и число g, такие, что различные степени g суть раз­личные числа по модулю р. Числа р и g передаются абонентам в открытом виде (они могут использоваться всеми або­нентами сети).

Нам необходимо выбрать числа p и g так, чтобы они отвечали следующим требованиям[3]:

gq mod p 1,

где p=2q+1.

Возьмем p=17 и g=7.

P=2q+1=2*8+1=17                            q=8

Проверим соотношение:

78 mod 17 = 16 – выполняется.

Затем каждый абонент группы выбирает свое секретное число ci, 1 < Ci < р – 1 (см. таблицу 3.1), и вычисляет соответствующее ему открытое число di:

di=gci mod p                                  (3.1)

Таблица 3.1 – Ключи пользователей в системе Эль-Гамаля

Покажем теперь, как А передает сообщение m абоненту В. Бу­дем предполагать, как и при описании шифра Шамира, что сообще­ние представлено в виде числа m < р.

Шаг 1. А формирует случайное число к, 1 к р-2, вычисляет числа

r=gk mod p,                                                     (3.2)

e=mdBk mod p,                                       (3.3)

и передает пару чисел (r, е) абоненту В.

Шаг 2. В, получив (r,е), вычисляет

m'=еrp-1-cB mod р                         (3.4)

Утверждение  (свойства шифра Эль-Гамаля):

1)   Абонент В получил сообщение, т.е. m'=m;

2)  противник, зная р, g, dB, r и е, не может вычислить m.

Передадим сообщение m = 13 от А к В. Возьмем р = 17, g = 7. Пусть абонент В выбрал для себя секретное число сВ = 11 и вычислил по (3.1) dB =  = 14.

Абонент А выбирает случайно число k, например k = 8, и вы­числяет по (3.2), (3.3):

r = 78 mod 17 = 16,

е = 13148 mod 17 = 4.

Теперь A посылает к В зашифрованное сообщение в виде пары чи­сел (16,4). B вычисляет по (3.4):

m' = 41617-1-11 mod 17 = 13.

Мы видим, что В смог расшифровать переданное сообщение. 

Ясно, что по аналогичной схеме могут передавать сообщения все абоненты в сети. Заметим, что любой абонент, знающий открытый ключ абонента В, может посылать ему сообщения, зашифрованные с помощью открытого ключа dB. Но только абонент В, и никто другой, может расшифровать эти сообщения, используя известный только ему секретный ключ сВ. Отметим также, что объем шифра в два раза превышает объем сообщения, но требуется только одна передача данных (при условии, что таблица с открытыми ключами заранее известна всем абонентам).

Передадим сообщение m=5 от B к C. (р = 17, g = 7. Пусть абонент С выбрал для себя секретное число сС = 5 и вычислил по (3.1) dС = 11.

Абонент B выбирает случайно число k, например k = 6, и вы­числяет по (3.2), (3.3):

r = 76 mod 17 =9,

е = 5116 mod 17 = 6.

Теперь B посылает к C зашифрованное сообщение в виде пары чи­сел (9,6). С вычисляет по (3.4):

m' = 6917-1-5 mod 17 = 5

Мы видим, что C смог расшифровать переданное сообщение.        

Передадим сообщение m=7 от C к D. (р = 17, g = 7). Пусть абонент D выбрал для себя секретное число сD = 7 и вычислил по (3.1)  dD=12.

Абонент C выбирает случайно число k, например k = 12, и вы­числяет по (3.2), (3.3):

r = 712 mod 17 =13,

е = 71212 mod 17 = 11.

Теперь C посылает к D зашифрованное сообщение в виде пары чи­сел (13,11). D вычисляет по (3.4):

m' = 111317-1-7 mod 17 = 7.

Мы видим, что D смог расшифровать переданное сообщение.        

Передадим сообщение m=9 от D к Е. (р = 17, g = 7). Пусть абонент E выбрал для себя секретное число сЕ = 13 и вычислил по (3.1) dЕ =6.

Абонент D выбирает случайно число k, например k = 11, и вы­числяет по (3.2), (3.3):

r = 711 mod 17 =14,

е = 9611 mod 17 = 11.

Теперь D посылает к E зашифрованное сообщение в виде пары чи­сел (14,11). B вычисляет по (3.4):

m' = 111417-1-13 mod 17 = 9.

Мы видим, что E смог расшифровать переданное сообщение.

Передадим сообщение m=11 от E к A. (р=17, g = 7). сА = 3,  dА =3.

Абонент E выбирает случайно число k, например k = 4, и вы­числяет по (3.2), (3.3):

г = 74 mod 17 =4,     е = 1134 mod 17 = 7 .

Теперь E посылает к A зашифрованное сообщение в виде пары чи­сел (4,7). А вычисляет по (3.4)

m' = 7417-1-3 mod 17 = 11.

Мы видим, что A смог расшифровать переданное сообщение.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ЛИТЕРАТУРЫ

1.        Романец Ю. В. Защита информации в компьютерных системах и сетях. /Под ред. В.Ф. Шаньгина. – М: Радио и связь, 1999.

2.        Петраков А.В. Основы практической защиты информации. 2-е издание Учебн. Пособие. – М: Радио и связь, 2001.

3.        Рябко Б. Я., Фионов А. Н. Криптографические методы защиты информации: Учебное пособие для вузов. – М.: Горячая линия – Телеком, 2005.

4.        Байкенов А. С., Шкрыгунова Е. А. Защита информации в телекоммуникационных системах. Конспект лекций. – Алматы: АИЭС, 2007.