Алгоритм DSA

Введение 3

 

История создания 8

 

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

 

Алгоритм DSA 11

 

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

 

Проверка ЭЦП 13

 

Выводы 14

 

Введение

 

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

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

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

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

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

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

 

В случае с ЭЦП процесс обмена сообщением выглядит следующим образом:

 

- отправитель получает у удостоверяющего  центра секретный ключ;

 

- используя этот ключ, формирует  электронную цифровую подпись  и отправляет письмо;

 

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

 

Электронная цифровая подпись, как  средство защиты электронных документов

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

Основные термины, применяемые  при работе с ЭЦП:

 

Закрытый ключ – это некоторая  информация длиной 256 бит, хранится в  недоступном другим лицам месте  на дискете, смарт-карте, touch memory. Работает закрытый ключ только в паре с открытым ключом.

 

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

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

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

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

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

 

·  имя файла открытого ключа подписи.

 

·  информация о лице, сформировавшем подпись.

 

·  дата формирования подписи.

 

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

Использование ЭЦП позводяет:

·  минимизировать риск финансовых потерь за счет повышения конфиденциальности информационного обмена документами придание документам юридической значимости;

 

·  значительно сократить время движения документов в процессе оформления отчетов и обмена документацией;

 

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

 

·  усовершенствовать и удешевить процедуру подготовки, доставки, учета и хранения документов; гарантировать достоверность документации;

 

·  соглашение с основными зарубежными системами удостоверения о кросс-сертификации. Обеспечение возможности использования украинского ЭЦП, для международного документооборота;

 

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

 

·  построить корпоративную систему обмена документами.

История создания

 

Электронная подпись – это данные в электронном формате, которые  прилагаются к другим электронным  данным или логически ассоциируются  с ними и служат в качестве метода установления аутентичности.

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

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

В 1973 г. 239 банков стран Европы и Северной Америки учредили Сообщество всемирных межбанковских финансовых телекоммуникаций с целью создания международной сети для передачи данных между финансовыми организациями. Сегодня S.W.I.F.T. является ведущей международной организацией в сфере финансовых телекоммуникаций, обеспечивающих оперативную, безопасную и надежную передачу финансовых сообщений по всему миру. Пользователями этой системы являются крупнейшие финансовые институты из 177 стран мира.

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

С 1996 г. начались работы по созданию Типового закона об электронной подписи в специально созданной рабочей группе в рамках Комиссии ООН по праву международной торговли (UNCITRAL). В феврале 2000 г. был представлен проект Типового закона, вызвавший, впрочем, неоднозначную реакцию в деловых кругах. Документ представляет собой, скорее, набор основных принципов регулирования электронной подписи и должен рассматриваться как минимальный стандарт для регулирования сделок и сообщений, передаваемых электронным путем. Новейшее законодательство об электронной подписи, принятое в Европейском Союзе, США, Японии и некоторых других странах, идет значительно дальше по сравнению с проектом Типового закона UNCITRAL.

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

Этот институт призван устранить  существенные барьеры на пути широкого использования электронных средств  коммуникации и электронной торговли.

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

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

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

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

 

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

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

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

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

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

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

Алгоритм 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 и  а являются открытыми и могут  быть общими для всех пользователей  сети. Число х является секретным  ключом. Число у является открытым ключом.