Меню Закрыть

Алгоритм шифрования электронной подписи

Содержание

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

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

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

Ключевая пара – открытый и закрытый ключи, которые используются для шифрования данных.

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

· симметричные криптосистемы (одноключевые);

· асимметричные криптосистемы (двухключевые).

Ключи, используемые в одноключевых и двухключевых криптосистемах, называются, соответственно, симметричными и асимметричными.

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

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

Закрытый и открытый ключи определенным образом связаны между собой и

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

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

Основное применение ассиметричных криптосистем – создание/проверка электронной цифровой подписи и асимметричное шифрование.

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

Шифрование информации гарантирует вам:

· недоступность информации для сторонних лиц;

· подлинность информации (информации поступит в неискаженном виде);

· целостность информации (данные, которые вы хотите передать останутся целыми в процессе передачи).

В общем случае шифрование состоит из следующих этапов (рис. 5.9):

Рис. 5.9 Шифрование данных

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

2) после этого вы отправляете зашифрованные данные партнеру;

3) ваш партнер получает зашифрованные данные. С помощью своего закрытого ключа и вашего открытого он расшифровывает данные. В результате ваш партнер получает тот самый открытый текст (конфиденциальные данные) который вы зашифровали.

Одним из самых распространенных алгоритмов шифрования является алгоритм RSA, длина ключа которого обычно 1024 бита. Принцип работы этого алгоритма достаточно простой. Каждый участник криптосистемы генерирует два случайно больших простых числа p и q, выбирает число e, меньшее pq и не имеющее общего делителя с (p-1)(q-1), и число d, такое, что (ed-1) делится на (p-1)(q-1). Затем он вычисляет n = pq, а p и q уничтожает. Пара (n,e) называется открытым ключом, а пара (n,d) – закрытым ключом.

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

Стойкость RSA есть функция сложности разложения произведения pq на простые множители p и q (эту задачу придется решать тому, кто вознамерится «вычислить» закрытый ключ из открытого). При достаточной длине этих простых чисел (несколько тысяч двоичных разрядов) такое разложение вычислительно невозможно. Для обеспечения конфиденциальности участник А «шифрует» сообщение m участнику Б с помощью открытого ключа Б:

а участник Б «расшифровывает» его с помощью своего закрытого ключа:

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

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

При соблюдении правовых условий использования ЭЦП в электронном документе она признается равнозначной собственноручной подписи в документе на бумажном носителе. Правовыми основами использования ЭЦП в системах электронного документооборота являются главы Гражданского кодекса Российской Федерации, федеральные законы (ФЗ) РФ «Об информации, информатизации и защите информации» № 24-ФЗ от 20 февраля 1995 г. и «Об электронной цифровой подписи» №

1-ФЗ от 10 января 2002 г.

При использовании электронно-цифровой подписи в условиях электронного документооборота применяется технология «криптография с открытым ключом». Для наложения цифровой подписи (рис. 5.10) участник А «шифрует» сообщение m участнику Б с помощью своего закрытого ключа:

и отправляет подпись s вместе с сообщением m. Участник Б может верифицировать подпись участника А с помощью открытого ключа А, вычислив:

Если m = mп, то сообщение m признается подписанным пользователем, который предоставил ранее открытый ключ (n,e).

Рис. 5.10 Работа с электронно-цифровой подписью

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

Перед непосредственным созданием ЭЦП (см. рис. 5.10) на документе происходит процесс хэширования с помощью специальной хэш-функции. Представленная на рис. 5.10 процедура соответствует, например, стандарту ГОСТ Р 34.10-94.

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

механизма, который позволяет вычислить для сообщения m произвольный длины так называемый хэш-код h(m) фиксированного размера r (обычно r = 128 бит). Этот код является подобием «слепка» сообщения m. Важно знать, что в системах электронно-цифровой подписи вместо подписывания сообщения (например, документов большого объема) используется подписывание соответствующих им хэш-функций, то есть ЭЦП накладывается не на сам документ, а на его хэш-код, и потом полученный результат записывается в конец файла документа. Тот факт, что сообщение m считается подписанным, если подписана его хэш-функция, определяет следующие основные требования к хэш-функциям:

· вычислительно неосуществимо нахождение сообщения m, хэш-функция которого была бы равна заданному значению h;

Читайте также:  Nvidia занижает производительность старых видеокарт

· вычислительно неосуществимо нахождение двух сообщений m1 и m2 m1 с равными значениями хэш-функций, то есть удовлетворяющих условию h(m1) = h(m2).

Если эти требования не выполняются, то потенциальный злоумышленник может подделать сообщение для подписанной хэш-функции. Во втором случае это осуществляется путем совместной подготовки истинного и поддельного документа. Отметим, что трудоемкость такой атаки в среднем составляет около 2 r/2 вычислений хэш-функции и не зависит от качества преобразований, используемых для задания хэш-функции. Это обстоятельство определяет длину хэш-кода r = 128 бит.

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

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

Сертификат предназначен для:

· подтверждения подлинности ЭЦП и идентификации ее автора;

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

· аутентификации владельца при установлении защищенных соединений по TLS/SSL протоколам.

Сертификат представляет собой информационный блок данных, формат которого включает следующую информацию (в соответствии с положениями международной Рекомендации ITU-T Х.509):

· номер версии сертификата;

· серийный номер сертификата;

· идентификатор алгоритма, используемого для подписи удостоверяющего центра;

· сведения об издателе сертификата (УЦ);

· период действия сертификата: начало и конец периода;

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

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

· дополнительные атрибуты, определяемые требованиями использования сертификата в системе;

· ЭЦП Удостоверяющего Центра.

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Общее

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

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

В нашем современном криминальном обществе, ни одно из перечисленных свойств на все 100% не реализуются. Можно и подделать подпись, и убрать но это реализуется не просто и быть пойманным есть риск. Существуют также дополнительные вопросы, при отправки документа по почте. Любой документ можно скопировать вместе с подписью. Также можно внести из мнения после подписания документа. Для ликвидации таких угроз используют электронно цифровую подпись. Подделать подпись очень сложно, так как она создается на основе большого объема математических операций. Цифровая подпись может хранится вместе с документом, или быть отдельно от него.

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

  • большая степень защиты от подделок
  • идентификация принадлежности подписи на основе характеристик
  • сильная связь с подписываемым документом

Возможные угрозы которые наносят ущерб развитию электронного документооборота показаны на рис.1. Эти угрозы:

  • отказ от факта получения документа или авторства
  • изменение документа
  • замена документа
  • замена имени
  • повторная рассылка документов

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

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

Алгоритмы электронной цифровой подписи

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

  • задача факторизации(разложение) больших целых чисел
  • задача дискретного логарифмирования

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

Первая и самая встречаемая система ЭЦП на основе RSA. Сначала нужно вычислить пару ключей. Отправитель (автор) электронных документов вычисляет два больших простых числа P и Q, затем находит произведение и значение функции:

N = P * Q; φ (N) = (Р-1)(Q-1).

Затем отправитель вычисляет число Е из условий:

Е £ φ (N), НОД (Е, φ (N)) = 1

D 18 , нужно использовать целый числа не менее 2 215 что требует больших вычислительных затрат, а это на 20.. 30% больше чем другие алгоритмы цифровой подписи при той же криптостойкости.

Алгоритм цифровой подписи Эль Гамаля (EGSA)

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

Что бы генерировать пару ключей, нужно выбрать простое целое число P и G, причем G 308 =

1 512 ) которые не секретные. Отправитель выбирает случайное целое число X, 1 X mod P;

Число Y является открытым ключом, который используется для проверки подписи отправителя. Число Х является секретным ключом отправителя для подписи документов. Что бы подписать сообщение М, сначала нужно что бы отправитель захэшировал его с помощью хэш-функции h в целое число m: m = h(M), 1 K mod P; используя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b: m = X * a + K * b (mod (P — 1)); Пара чисел (a, b) образуют цифровую подпись S: S = (a, b);

Тройка чисел (M, a, b) транспортируется получателю, в то время как пара чисел (X, K) держится в секрете. Получатель получив сообщение (M, a, b) должен вычислить число m: m = h(M). затем получатель вычисляет: A = Y a a b mod (P), и признает сообщение M подлинным, если — A = G m mod (P). Можно строго математически доказать, что последнее равенство будет равно тогда, когда подпись S под документом M получена с помощью именно секретного ключа X, из которого был получен открытый ключ Y. Нужно отметить, что процедура каждой подписи требует нового значения К, и выбирается случайным образом.

Читайте также:  Как обвести перо в фотошопе

Схема Эль Гамаля является типичным примером, который разрешает пересылку сообщений М в открытой форме вместе с аутентификатором (a, b). Такая схема имеет преимущества перед схемой ЭЦП RSA:

  • Для одинакового уровня стойкости, алгоритм Эль Гамаля использует целые числа короче на 25%, что уменьшает сложность вычислений почти в 2 раза.
  • Выбор модуль Р прост, нужно убедится что число простое, и что у числа (Р — 1_ есть большой простой множитель.
  • Схема создания подписи по алгоритму Эль Гамаля не разрешает вычислять ЭЦП под новыми сообщениями без знания секретного ключа.

К недостаткам можно отнести то, что подпись получается в 1,5 раза больше чем RSA.

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

DSA — Digital Signature Algorithm — это развитие алгоритмов цифровой подписи Эль Гамаля и К.Шнорра. Получатель и отправитель электронного документа реализуют при вычислении большие целые числа G и P — простые числа, L бит каждое (512 £ L £ 1024), q — простое число длинной 160 бит (делитель числа (P — 1)). Числа P, G, q есть открытыми и могут быть общими для пользователей. Отправитель берет случайное целое число X, 1 X mod P. Число Y — открытый ключ. Что бы подписать документ М, отправитель хэширует его в целое хэш-значение m: m = h(M), 1 K mod P) mod q. Также нужно вычислить: s = ((m + r * X)/ K) mod q; Пара чисел S = (r, s) образуют цифровую подпись. Получатель проверяет выполнение условий: 0 u1 * Y u2 ) mod P) mod q; Если условие v = r выполняется, тогда подпись S под документом подлинная.

Можно математически доказать, что последнее равенство будет выполнятся тогда, когда подпись S под документом получена с помощью секретного ключа X, из которого был получен открытый ключ Y. Алгоритм DSA имеет преимущества над ЭЦП Эль Гамаля:

  • При одинаковом уровне стойкости, длина подписи явно меньше у DSA
  • Также меньше время вычисления подписи

Недостатками алгоритма является то, что при проверке подписи нужно реализовывать сложные операции деления по модулю q. Следует отметить, что реальное исполнение алгоритма DSА может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения М и его хэш-значения m.

Технология применения системы ЭЦП предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа. Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и автора подписи. Открытый ключ не позволяет вычислить секретный ключ.

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

задача факторизации (разложения на множители) больших целых чисел;

задача дискретного логарифмирования.

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

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.

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

и значение функции

Далее отправитель вычисляет число E из условий:

E £ j (N), НОД (E, j (N)) =1

и число D из условий:

Пара (M,S) передается партнеру-получателю как электрон-ный документ M, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.

Рис.6.4. Обобщенная схема цифровой подписи RSA

ское преобразование подписи S с использованием открытого ключа E:

Кроме того, он находит результат хэширования принятого сообщения M с помощью такой же хэш-функции h(·):

Если соблюдается равенство вычисленных значений, т.е.

то получатель признает пару (M,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу M, а определить секретное число D по открытому числу E не легче, чем разложить модуль N на множители.

Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу E. Поэтому открытый ключ E иногда называют "идентификатором" подпи-савшего.

Недостатки алгоритма цифровой подписи RSA.

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

2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 10 18 , необходимо использовать при вычислениях N, D и E целые числа не менее 2 512 (или около 10 154 ) каждое, что требует больших вычислительных затрат, превышающих на 20…30% вычислительные затраты других алгоритмов циф-ровой подписи при сохранении того же уровня криптостойкости.

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

Пример. Допустим, что злоумышленник может сконструировать три сообщения M1, M2 и M3, у которых хэш-значения

Допустим также, что для двух сообщений M1 и M2 получены законные подписи

Тогда злоумышленник может легко вычислить подпись S3 для документа M3, даже не зная секретного ключа D:

Более надежный и удобный для реализации на персональных компьютерах алгоритм цифровой подписи был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем. В 1991 г. НИСТ США обосновал перед комиссией Конгресса США выбор алгоритма цифровой подписи Эль Гамаля в качестве основы для национального стандарта.

Алгоритм цифровой подписи Эль Гамаля (EGSA)

Название EGSA происходит от слов El Gamal Signature Algorithm (алгоритм цифровой подписи Эль Гамаля). Идея EGSA основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа,– задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSA, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

Рассмотрим подробнее алгоритм цифровой подписи Эль Гамаля. Для того чтобы генерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое целое число P и большое целое число G, причем G 308 или

2 512 ), которые не являются секретными.

Отправитель выбирает случайное целое число X, 1 X mod P.

Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов.

Число X является секретным ключом отправителя для подписывания документов и должно храниться в секрете.

Читайте также:  Установка windows 10 на новый ssd диск

Для того чтобы подписать сообщение M, сначала отправитель хэширует его с помощью хэш-функции h(·) в целое число m:

m = h(M), 1 K mod P

и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа X целое число b из уравнения

m = X* a + K * b (mod (P –1)).

Пара чисел (a,b) образует цифровую подпись S:

проставляемую под документом M.

Тройка чисел (M,a,b) передается получателю, в то время как пара чисел (X,K) держится в секрете.

После приема подписанного сообщения (M,a,b) получатель должен проверить, соответствует ли подпись S = (a,b) сообщению M. Для этого получатель сначала вычисляет по принятому сообщению M число

т.е. хэширует принятое сообщение M.

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

A = Y a a b (mod P)

и признает сообщение M подлинным, если, и только если

Иначе говоря, получатель проверяет справедливость соотношения

Y a a b (mod P) = G m (mod P).

Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(a,b) под документом M получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправителем сообщения M был обладатель именно данного секретного ключа X, не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ M.

Следует отметить, что выполнение каждой подписи по методу Эль Гамаля требует нового значения K, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение K, повторно используемое отправителем, то он сможет раскрыть секретный ключ X отправителя.

Пример. Выберем: числа P =11, G = 2 и секретный ключ X = 8. Вычисляем значение открытого ключа:

Y = G X mod P = Y = 2 8 mod 11 = 3.

Предположим, что исходное сообщение M характеризуется хэш-значени-

Для того чтобы вычислить цифровую подпись для сообщения M, имеющего хэш-значение m = 5, сначала выберем случайное целое число K = 9. Убедимся, что числа K и (P – 1) являются взаимно простыми. Действительно,

Далее вычисляем элементы a и b подписи:

a = G K mod P = 2 9 mod 11 = 6,

элемент b определяем, используя расширенный алгоритм Евклида:

m = X * a + K * b (mod (P – 1)).

При m = 5, a = 6, X = 8, K = 9, P = 11 получаем

5 = (6 * 8 + 9 * b)(mod 10)

9 * b º – 43 (mod 10).

Решение: b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3.

Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 3, получатель вычисляет хэш-значение для сообщения M : m = 5, а затем вычисляет два числа:

1) Y a a b (mod P) = 3 6 * 6 3 (mod 11) =10 (mod 11);

2) G m (mod P) = 2 5 (mod 11) =10 (mod 11).

Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.

Следует отметить, что схема Эль Гамаля является характерным примером подхода, который допускает пересылку сообщения M в открытой форме вместе с присоединенным аутентификатором (a,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.

Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSA:

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

2. При выборе модуля P достаточно проверить, что это число является простым и что у числа (P –1) имеется большой простой множитель (т.е. всего два достаточно просто проверяемых условия).

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

Однако алгоритм цифровой подписи Эль Гамаля имеет и некоторые недостатки по сравнению со схемой подписи RSA. В частности, длина цифровой подписи получается в 1,5 раза больше, что, в свою очередь, увеличивает время ее вычисления.

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

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

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

Отправитель выбирает случайное целое число X, 1 X mod P.

Число Y является открытым ключом для проверки подписи отправителя. Число Y передается всем получателям документов.

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

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

m = h(M), 1 K mod P) mod q.

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

s = mod q.

Пара чисел r и s образует цифровую подпись

под документом M.

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

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

0 –1 для каждого из значений K. Затем, при поступлении сообщения M, можно вычислить значение s для данных значений r и K –1 . Эти предварительные вычисления значительно ускоряют работу алгоритма DSA.

Отечественный стандарт цифровой подписи

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

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

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

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

x – некоторое число, меньшее q;

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

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

Чтобы подписать некоторое сообщение m, а затем проверить подпись, выполняются следующие шаги.

1. Пользователь A генерирует случайное число k, при-чем k k mod p) mod q,

s = (x * r + k (H(m))) mod q.

Если H(m) mod q=0, то значение H(m) mod q принимают равным единице. Если r=0, то выбирают другое значение k и начина-ют снова.

Цифровая подпись представляет собой два числа:

r mod 2 256 и s mod 2 256 .

Пользователь А отправляет эти числа пользователю В.

3. Пользователь В проверяет полученную подпись,

u = (mod p) mod q.

Если u = r, то подпись считается верной.

Различие между этим алгоритмом и алгоритмом DSA заключается в том, что в DSA

s = (k –1 (x * r + (H(m)))) mod q,

что приводит к другому уравнению верификации.

Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в значениях параметра q является отражением стремления разработчиков отечественного стандарта к получению более безопасной подписи.

Этот стандарт вступил в действие с начала 1995 г.

Рекомендуем к прочтению

Добавить комментарий

Ваш адрес email не будет опубликован.