Схемы, методики создания и проверки подлинности цифровой подписи

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

1. Цель работы

Ознакомиться со схемами цифровой подписи и получить навыки создания и проверки подлинности ЦП.

2. Теоретические сведения

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

– гарантирование истинности письма путем сличения подписи с имеющимся образцом;

– гарантирование авторства документа (с юридической точки зрения).

Выполнение данных требований основывается на следующих свойствах подписи:

– подпись аутентична, т.е. с ее помощью получателю документа можно доказать, что она принадлежит подписывающему;

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

– подпись непереносима, т.е. является частью документа и поэтому перенести ее на другой документ невозможно;

– документ с подписью является неизменяемым, т.е. после подписания его невозможно изменить, оставив данный факт незамеченным;

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

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

С переходом к безбумажным способам передачи и хранения данных, а также с развитием систем электронного перевода денежных средств, в основе которых - электронный аналог бумажного платежного поручения, проблема виртуального подтверждения аутентичности документа приобрела особую остроту. Развитие любых подобных систем теперь немыслимо без существования электронных подписей под электронными документами.

Схема 1

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

Рисунок 1 - Основные методы построения схем ЭЦП. Схема 1

Участник A зашифровывает сообщение своим секретном ключе KA, знание которого разделено с арбитром (С на рисунке 1), затем шифрованное сообщение передается арбитру с указанием адресата данного сообщения (информация, идентифицирующая адресата, передается также в зашифрованном виде).

Арбитр расшифровывает полученное сообщение ключом КА, производит необходимые проверки и затем зашифровывает его секретным ключом участника B (KB). Далее зашифрованное сообщение посылается участнику B вместе с информацией, что оно пришло от участника A.

Участник B расшифровывает данное сообщение и убеждается в том, что отправителем является участник A.

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

Схема 2.

Фактом подписания документа в данной схеме является шифрование документа секретным ключом его отправителя. Здесь используются асимметричные алгоритмы шифрования.

Рисунок 2 - Основные методы построения схем ЭЦП. Схема 2

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

Схема 3.

Наиболее распространенная схема ЭЦП использует шифрование окончательного результата обработки ЭД хэш-функцией при помощи асимметричного алгоритма. Структурная схема такого варианта построения ЭЦП представлена на рисунке 3.

Процесс генерации ЭЦП происходит следующим образом.

Участник A вычисляет хэш-код от ЭД. Полученный хэш-код проходит процедуру преобразования с использованием своего секретного ключа. После чего полученное значение (которое и является ЭЦП) вместе с ЭД отправляется участнику B.

Участник B должен получить ЭД с ЭЦП и сертифицированный открытый ключ участника A, а затем произвести расшифрование на нем ЭЦП, сам ЭД подвергается операции хэширования, после чего результаты сравниваются, и если они совпадают, то ЭЦП признается истинной, в противном случае ложной.

Рисунок 3 - Основные методы построения схем ЭЦП. Схема 3

Процесс генерации ЭЦП

В настоящее время применяются несколько алгоритмов цифровой подписи:

– RSA (наиболее популярен);

– Digital Signature Algorithm, DSA (алгоритм цифровой подписи американского правительства);

– алгоритм Эль-Гамаля (иногда можно встретить);

– алгоритм, который применяют в стандарте ГОСТ Р34.10-94 (в основе лежит DSA и является вариацией подписи Эль-Гамаля);

– алгоритмы подписей на основе криптография эллиптических кривых (алгоритм ECDSA, на этом алгоритме базируется украинский ДСТУ 4145-2002, российский стандарт ГОСТ Р34.10-200).

Электронная подпись RSA.

Для осуществления подписи сообщения M = m1m2…mn необходимо вычислить хеш-функцию h = H(M), которая ставит в соответствие сообщению M число h. На следующем шаге достаточно снабдить подписью только число h, и эта подпись будет относиться ко всему сообщению M.

Далее по алгоритму RSA вычисляются ключи (e, n) и (d, n).

Затем вычисляется s = hd mod n (d - секретная степень).

Число s - это и есть цифровая подпись. Она просто добавляется к сообщению и получается подписанное сообщение {M, s}.

Теперь каждый, кто знает параметры подписавшего сообщение (т.е. числа e и n), может проверить подлинность подписи.

Для этого необходимо проверить выполнение равенства H(M) = se mod n.

Электронная подпись на основе алгоритма Эль-Гамаля.

Для генерации пары ключей сначала выбирается большое простое число p и два числа g и x (g < p, x < p). Причем g - первичный корень по модулю p, а x случайное число (1< x < р -1).

Затем вычисляется Kx = gx mod p.

Открытым ключом являются Kx, g и p. Закрытым ключом является x.

Чтобы подписать сообщение М, сначала вычисляется хэш (дайджест) сообщения: h = Н(M).

Затем выбирается случайное число k, взаимно простое с p - 1 (k - секретно).

Вычисляется r = gk mod p.

Из соотношения h = (xr+ks) mod (p-1) находится s. Выполнив преобразования, получим s = k -1(h-xr) mod (p-1), k -1•k ? 1 (mod (p-1)).

В результате подписью является пара чисел (r, s). Она добавляется к сообщению и получается подписанное сообщение {M, r, s}.

Для проверки подписи:

Проверяется выполнимость условий: 0 < r = < p-1 и 0 < s = < p-1. Если хотя бы одно из них не выполняется, то подпись считается неверной.

Вычисляется хэш сообщения: h = Н(M).

Необходимо убедиться, что

Kxr•rs mod p = gh mod p.

3. Ход работы

Расчет хэш-функции

Данные:

Табл. 1

№	Открытый текст	p	q
H0=13
3	ГАМУВАННЯ	11	73

Рисунок 4

подпись цифровой шифрование алгоритм

п = pq =803

М1 + H0 =(13+5) 2 (mod 803 ) = 609

М2 + H1 =(2+609) 2 (mod 803 ) =729

М3 + H2 =(17+729) 2 (mod 803 ) = 566

М4 + H3 =(24+566) 2 (mod 803 ) = 201

М5 + H4 =(4+201) 2 (mod 803 ) = 269

М6 + H5 =(269+5) 2 (mod 803 ) = 397

М7 + H6 =(18+397) 2 (mod 803 ) = 383

М8 + H7 =(18+383) 2 (mod 803 ) = 201

М9 + H8 =(33+201) 2 (mod 803 ) = 625

1. Для указанных открытых ключей пользователя RSA проверил подлинность подписанных сообщений по формуле H(M) = se mod n, хэш которых указан вместо M:

n=55, e=3: {7,28}, {22,15}, {16,36}.

7 = 283 mod 55 22 ? 153 mod 55 = 20 16 = 363 mod 55

n=65, e=5: {6,42}, {10,30}, {6,41}.

6 ? 425 mod 65 = 22 10 = 305 mod 65 6 = 415 mod 65

n=77, e=7: {13,41}, {11,28}, {5,26}.

13 = 417 mod 77 11 ? 287 mod 77 = 63 5 = 267 mod 77

n=91, e=5: {15,71}, {11,46}, {16,74}.

15 = 715 mod 91 11 ? 465 mod 91 = 37 16 = 745 mod 91

n=33, e=3: {10,14}, {24,18}, {17,8}.

10 ? 143 mod 33 = 5 24 = 183 mod 33 17 = 83 mod 33

Задание 2.

Для указанных открытых ключей пользователя создал цифровую подпись RSA для сообщения M, хэш которого равен 201:

q=11, p=5, e=3.

По формуле s = hd mod n буду создавать подпись RSA. Для этого сначала нахожу n = p*q = 55. Для того чтобы найти d воспользуюсь расширенным алгоритмом Евклида d*e ? 1 mod n.

d ? 1* en-2 mod n ? en-2 mod n

d = 38

s = hd mod n = 20138 mod 55=16

q=5, p=13, e=5.

n = p*q = 65

d ? en-2 mod n

d = 60

s = hd mod n = 20160 mod 65=1

q=11, p=7, e=7.

n = p*q = 77

d ? en-2 mod n

d = 21

s = hd mod n = 20121 mod 77=69

q=7, p=13, e=5.

n = p*q = 91

d ? en-2 mod n

d = 31

s = hd mod n = 20131 mod 91=33

q=11, p=3, e=3.

n = p*q = 33

d ? en-2 mod n

d = 3

s = hd mod n = 2013 mod 33=27

Задание 3. Абоненты некоторой сети применяют подпись Эль-Гамаля с общими параметрами p = 23, g = 5. Для указанных секретных параметров абонентов нашёл открытый ключ y и построил подпись для сообщения M, хэш которого равен 201: 1. x=11, k=3.

Вычисляю:

Kx = gx mod p= 511 mod 23 = 22.

Хэш сообщения:

h = Н(M) = 201.

Вычисляю:

r = gk mod p = 53 mod 23 = 10.

С помощью расширенного алгоритма Евклида нахожу k -1 из выражения:

k -1•k ? 1 (mod (p-1)). kp-2mod p=k-1

k -1 = 8

Из соотношения:

h = (xr+ks) mod (p-1) нахожу s.

s = k -1(h-xr) mod (p-1) = 8(201-11*10) mod (p-1) = 2

В результате подписью является пара чисел (r, s) = (10,2).

2. x=10, k=15.

Вычисляю:

Kx = gx mod p= 510 mod 23 = 9.

Хэш сообщения::

h = Н(M) = 201.

Вычисляю:

r = gk mod p = 515 mod 23 = 19.

k -1 = 20

s = k -1(h-xr) mod (p-1) = 20(201-10*19) mod (p-1) = 0

Подписью является пара чисел (r, s) = (19,0).

3. x=3, k=13.

Вычисляю:

Kx = gx mod p= 53 mod 23 = 10.

Хэш сообщения:

h = Н(M) = 201.

Вычисляю:

r = gk mod p = 513 mod 23 = 21.

k -1 = 16. s = k -1(h-xr) mod (p-1) = 16(201-3*21) mod (p-1) = 8

Подписью является пара чисел (r, s) = (21,8).

4. x=18, k=7.

Вычисляю:

Kx = gx mod p= 518 mod 23 = 6.

Хэш сообщения::

h = Н(M) = 201.

Вычисляю:

r = gk mod p = 57 mod 23 = 17.

k -1 = 10

s = k -1(h-xr) mod (p-1) = 10(201-18*17) mod (p-1) = -16+22=6

Подписью является пара чисел (r, s) = (17,6).

5. x=9, k=19.

Вычисляю:

Kx = gx mod p= 59 mod 23 = 11.

Хэш сообщения:

h = Н(M) = 201.

Вычисляю:

r = gk mod p = 519 mod 23 = 7.

k -1 = 17

s = k -1(h-xr) mod (p-1) = 17(201-9*7) mod (p-1) = 14

Подписью является пара чисел (r, s) = (7,14).

Вывод: в ходе выполнения работы ознакомился со схемами цифровой подписи и получил навыки создания (на основе алгоритмов RSA и Эль-Гамаля) и проверки подлинности ЦП.

Размещено на Allbest.ru

...