Алгоритм DSA

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

Генерация ключей

 

Существует несколько методов  посторения ЭЦП, а именно:

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

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

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

Кроме перечисленных, существуют и  другие методы построения схем ЭЦП

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

Алгоритм DSA

 

В 1991 г. в США был опубликован проект федерального стандарта цифровой подписи - DSS (Digital Signature Standard, [DSS91], описывающий систему цифровой подписи DSA (Digital Signature Algorithm). Одним из основных критериев при создании проекта была его патентная чистота.

Предлагаемый алгоритм DSA, имеет, как  и RSA, теоретико-числовой характер, и  основан на криптографической системе  Эль-Гамаля в варианте Шнорра . Его надежность основана на практической неразрешимости определенного частного случая задачи вычисления дискретного логарифма. Современные методы решения этой задачи имеют приблизительно ту же эффективность, что и методы решения задачи факторизации; в связи с этим предлагается использовать ключи длиной от 512 до 1024 бит с теми же характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит.

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

Функции DSA ограничены только цифровой подписью, система принципиально  не предназначена для шифрования данных. По быстродействию система DSA сравнима с RSA при формировании подписи, но существенно (в 10-40 раз) уступает ей при проверке подписи.

Вместе с проектом DSS опубликован  проект стандарта SHS (Secure Hash Standard), описывающий  однонаправленную хэш-функцию SHA (Secure Hash Algorithm), рекомендованную для использования  вместе с DSA. Хэш-функция SHA является модификацией алгоритма MD4, хорошо известного в криптографической литературе.

Генерация ЭЦП

 

При генерации  ЭЦП используются параметры трех групп:

общие параметры

секретный ключ

открытый ключ

Общие параметры необходимы для  функционирования системы в целом. Секретный ключ используется для  формирования ЭЦП, а открытый – для  проверки ЭЦП. Общими параметрами системы  являются простые целые числа p,q,g, удовлетворяющие следующим условиям:

p: 2^511<p<2^512

q: простой делитель числа (p-1), который удовлетворяет условию 

2^159<q<2^160

g: так называемый генератор,удовлетворяющий равенству g=h^((p-1)/q)mod p >1.

Парараметры p,q,g публикуются для  всех участников обмена  ЭД  с  ЭЦП.

Секретный ключ x случайно выбирается из диапазона [1,q] и держится в секрете.

Открытый ключ вычисляется:  y=g^x mod p.

Также при описании данной схемы  будут использоваться следующие  обозначения и дополнительные параметры: m – входное сообщение пользователя для схемы с ЭЦП;  k -  случайное  число, удовлетворяющее условию  0<k<q, хранящееся в секрете и  меняющееся от одной подписи к  другой; H – хэш-функция, h – хэш-код  сообщения.

Процесс генерации ЭЦП состоит  из нескольких этапов:

1.Вычисляется хэш-код сообщения  m h=H(m)

2.Из диапазона [1,q] случайным  образом  выбирается значение k и вычисляется r= (g^k mod p) mod q

3. Вычисляется S= (k^-1(h+xr)) mod q, где  k^-1 удовлетворяет условию

(k^-1*k) mod q =1

Значения r,s являются ЭЦП сообщения m  и передаются вместе с ним  по каналам связи.

Проверка ЭЦП

 

Пусть принято сообщение m1 и его  подпись s1,r1.

Проверка ЭЦП происходит следующим  образом:

проверяется выполнений условий 0<r1<q, 0<s1<q, и если хотя бы одно из них  нарушено, подпись отвергается.

Вычисляются значения:

w= s1^-1 mod q

u1 = (H(m1)w) mod q

u2 = ((r1/w) mod q

v = (( g^u1y^u2) mod p ) mod q

проверяется равенство v = r1

Если последнее равенство выполняется, то подпись принимается. В данном стандарте специфицируется также  процедура генерации основных параметров системы и проводится доказательство того, что если v=r1, то m1=m, r1=r, s1=s.

 

Выводы

 

Электронная цифровая подпись - эффективное  решение для всех, кто хочет  идти в ногу с новыми требованием  времени. Если у Вас нет времени ждать прихода фельдъегерской или курьерской почты за многие сотни километров, чтобы проверить подтвердить заключение сделки или подлинность полученной информации. Преимущества ЭЦП очевидны - документы, подписанные электронной цифровой подписью, могут быть переданы к месту назначения в течение нескольких секунд. Все участники электронного обмена документами получают равные возможности независимо от их удаленности друг от друга. Границы благодаря новым технологиям стираются в 21 веке.

Подделать ЭЦП невозможно – для этого требуется огромного количества вычислений, которые не могут быть реализованы при современном уровне вычислительной техники и математики за приемлемое время, то есть пока информация, содержащаяся в подписанном документе, сохраняет актуальность.

Дополнительная защита от подделки обеспечивается сертификацией Удостоверяющим центром открытого ключа подписи. Кроме того по желанию клиента  Удостоверяющий центр может застраховать ЭЦП клиента.

С использованием ЭЦП меняется мышление схема работы "разработка проекта  в электронном виде - создание бумажной копии для подписи - пересылка  бумажной копии с подписью - рассмотрение бумажной копии - перенос ее в электронном  виде на компьютер" уходит в прошлое.

 

 

 

Источники данных

 

1. Петров А.А

  Компьютерная безопасность. Криптографические   методы защиты. ДМК

   Москва, 2000 г.

2.  "Методы и средства защиты  информации" (курс лекций)

  Авторские права: Беляев  А.В.

(http://www.citforum.ru/internet/infsecure/index.shtml)

3. Криптография  (http://www.citforum.ru/internet/securities/crypto.shtml)

4. http://www.e-sign.ru

5. Александр Володин  «Кто  заверит ЭЦП»

   - журнал «Банковские системы» - ноябрь 2000

    (http://www.bizcom.ru/system/2000-11/04.html)

6. Теоретические основы - Безопасность информационных систем

    Криптографические системы

( http://argosoft.webservis.ru/Base/Crypt.html#Механизмы  шифрования )

7.  Криптографические алгоритмы  с открытым ключом

(http://argosoft.webservis.ru/Base/RSAintro.html#Криптографические  алгоритмы с открытым ключом)

8. Совpеменные кpиптогpафические методы защиты инфоpмации –

 Системы с откpытым ключом  ( http://ppt.newmail.ru/crypto04.htm#Heading20 )

9. Криптография с открытым ключом: от теории к стандарту 

    А.Н.Терехов, А.В.Тискин  "Программирование РАН", N 5 (сентябрь-октябрь), 1994, стр. 17--22

   (http://www1.tepkom.ru/users/ant/Articles/Pkcstand.html)

10. Баричев С.Г., Гончаров В.В., Серов  Р.Е. Основы современной криптографии  –  Москва,  Горячая линия  – Телеком, 2001

11. В. Столлингс. Криптография  и защита сетей: теория и  практика. М: Вильямс. 2001. Пер. с  англ.

 

Алгоритм цифровой подписи DSA

 

 Алгоритм цифровой подписи  DSA (Digital Signature Algorithm) предложен в 1991 г. в НИСТ США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритмов цифровой подписи Эль Гамаля и К. Шнорра.

 Отправитель и получатель  электронного документа используют  при вычислении большие целые  числа: G и Р - простые числа, L бит каждое (); q-простое число длиной 160 бит (делитель числа (Р-1)). Числа G, P, q являются открытыми и могут быть общими для всех пользователей сети. Отправитель выбирает случайное целое число X,1

 Затем отправитель вычисляет  значение.

 Число Y является открытым  ключом для проверки подписи  отправителя. Число Y передается  всем получателям документов. Этот  алгоритм также предусматривает  использование односторонней функции  хэширования h(-). В стандарте DSS определен 3 алгоритм безопасного хэширования SHA (Secure Hash Algorithm).

 Для того чтобы подписать  документ М, отправитель хэширует  его в целое хэш-значение m:

 затем генерирует случайное целое число K, 1

 Затем отправитель вычисляет  с помощью секретного ключа  X целое число s:

 Пара чисел r и s образует  цифровую подпись S = (r, s) под документом  М.

 Таким образом, подписанное сообщение представляет собой тройку чисел [М, r, s].

 Получатель подписанного сообщения  [М, r, s] проверяет выполнение условий  и отвергает подпись, если хотя  бы одно из этих условий  не выполнено.

 Затем получатель вычисляет  значение хэш-значение m = h(m) и числа ,

 Далее получатель с помощью  открытого ключа Y вычисляет значение  и проверяет выполнение условия  v = r.

 Если условие v = г выполняется,  тогда подпись S = (r, s) под документом  М признается получателем подлинной.

 По сравнению с алгоритмом  цифровой подписи Эль Гамаля  алгоритм DSA имеет следующие основные  преимущества;

 При любом допустимом уровне  стойкости, т.е. при любой паре  чисел G и Р (от 512 до 1024 бит), числа q, X, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.

 Большинство операций с числами К, r, s, X при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.

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

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

 Реальное исполнение алгоритма  DSA может быть ускорено с помощью  выполнения предварительных вычислений. Заметим, что значение r не зависит  от сообщения М и его хэш-значения m. Можно заранее создать строку  случайных значений К и затем для каждого из этих значений вычислить значения г. Можно также заранее вычислить обратные значения К-1 для каждого из значений К. Затем, при поступлении сообщения М, можно вычислить значение s для данных значений r и К1. Эти предварительные вычисления значительно ускоряют работу алгоритма DSA.

Отечественный стандарт цифровой подписи. Отечественный стандарт цифровой подписи  обозначается как ГОСТР 34.10-94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. В нем используются следующие  параметры:

 р- большое простое число длиной от 509 до 512 бит либо от 1020 до 1024 бит;

q-простой сомножитель числа  (р-1), имеющий длину 254...256 бит.

 а- любое число, меньшее (р-1), причем такое, что mod p = 1;

 х- некоторое число, меньшее q; .

 Кроме того, этот алгоритм  использует однонаправленную хэш-функцию  Н(х). Стандарт ГОСТР34,11-94 определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147-89.

 Первые три параметра p,q и  а являются открытыми и могут  быть общими для всех пользователей  сети. Число х является секретным  ключом. Число у является открытым ключом.