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

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

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

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

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

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

y = a^х mod p.

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

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

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

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

2. Пользователь А вычисляет значения

r = (a^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²⁵⁶ и s mod 2²⁵⁶.

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

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

вычисляя

v = H(m)^q–2 mod q,

z₁ = (s∙v) mod q,

z₂ = ((q – r)∙v) mod q,

u = ( mod p) mod q.

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

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

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

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

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

40.10. Цифровые подписи с дополнительными
функциональными свойствами

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

К схемам цифровой подписи с дополнительными функциональными свойствами относятся:

- схемы слепой (blind) подписи,

- схемы неоспоримой (undeniable) подписи.

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

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

Приведем пример применения слепой подписи. Схема слепой подписи может найти применение в тех случаях, когда отправитель А (клиент банка) не хочет, чтобы подписывающая сторона В (банк) имела возможность в дальнейшем связать сообщение m и подпись s_B(m) c определенным шагом выполненного ранее протокола.

В частности, это может быть важно при организации анонимных безналичных расчетов, когда сообщение m могло бы представлять денежную сумму, которую А хочет потратить. Когда сообщение m c подписью s_B(m) предъявляется банку В для оплаты, банк В не сможет проследить, кто именно из клиентов предъявляет подписанный документ. Это позволяет пользователю А остаться анонимным. Принципы организации системы анонимных безналичных расчетов с использованием так называемой «электронной наличности» («цифровых денег») на базе протоколов слепой подписи рассмотрены в работах:

1. Joux A., Lercier R. Improvements on the general number field sieve for discrete logarithms in prime fields (a comparison with the Gaussian integer method) // Elliptic curve cryptography workshop. – 1999. – http: // exp-math.uni-essen.de.

2. Preneel B. Cryptographic hash functions // European Trans. on Telecomm. – 1994. – 5. – c. 431-448.

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

1. Механизм обычной цифровой подписи для подписывающей стороны В. Пусть s_B(Х) обозначает подпись стороны В на документе Х.

2. Функции f(×) и g(×) (известные только отправителю) такие, что

g(s_B (f(m))) = s_m(m),

при этом f(×) – маскирующая (blinding) функция,

g(×) – демаскирующая (unblinding) функция,

f(m) – замаскированное (blinded) сообщение m.

При выборе s_B, f и g существует ряд ограничений.

Выберем в качестве алгоритма подписи s_B для стороны В схему цифровой подписи RSA с открытым ключом (N, E) и секретным ключом D, причем

N = PQ – произведение двух больших случайных простых чисел. Пусть k – некоторое фиксированное целое число, взаимно простое с N, т.е. НОД (N, k) = 1.

Маскирующая функция f: Z_n ® Z_n определяется как f(m)=mk^E modN, а демаскирующая функция g: Z_n ® Z_n определяется как g(m) = k^-1m modN. При таком выборе f, g и s получаем

g(s_B (f(m))) = g(s_B(mk^E mod N)) = g(m^D k mod N) = m^D mod N = s_B (m),

что соответствует требованию 2.

Согласно протоколу слепой подписи, который предложил Д.Чом, отправитель А сначала получает подпись стороны В на замаскированном сообщении m^*. Используя эту подпись, сторона А вычисляет подпись В на заранее выбранном сообщении m, где 0 £ m £ N-1. При этом стороне В ничего неизвестно ни о значении m, ни о подписи, связанной с m.

Пусть сторона В имеет для подписи по схеме RSA открытый ключ (N, E) и секретный ключ D. Пусть k – случайное секретное целое число, выбранное стороной А и удовлетворяющее условиям 0 £ k £ N-1 и НОД (N, k).

Протокол слепой подписи Д.Чома включает следующие шаги:

(1) Отправитель А вычисляет замаскированное сообщение m^* = mk^E modN и посылает его стороне В.

(2) Подписывающая сторона В вычисляет подпись s^* = (m^*)^D modN и отправляет эту подпись стороне А.

Сторона А вычисляет подпись s = k^-1 s^*modN, которая является подписью В на сообщение m.

Нетрудно видеть, что

(m^*)^D º (mk^E)^D º m^Dk (mod N),

поэтому

k^-1 s^* º m^D k k^-1 º m^D (mod N).

Д.Чом разработал несколько алгоритмов слепой подписи для создания системы анонимных безналичных электронных расчетов eCash.

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

Рассмотрим два возможных сценария применения неоспоримой подписи.

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

Сценарий 2. Предположим, что известная корпорация А разработала пакет программного обеспечения. Чтобы гарантировать подлинность пакета и отсутствие в нем вирусов, сторона А подписывает этот пакет неоспоримой подписью и продает его стороне В. Сторона В решает сделать копии этого пакета программного обеспечения и перепродать его третьей стороне С. При использовании стороной А неоспоримой подписи сторона С не сможет убедиться в подлинности этого пакета программного обеспечения и отсутствии в нем вирусов без участия стороны А.

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

40.11. Алгоритм неоспоримой
цифровой подписи Д.Чома

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

Каждая сторона А должна выполнить следующее:

1. Выбрать случайное простое число p = 2q + 1, где q – также простое число.

2. Выбрать генераторное число a для подгруппы порядка q в циклической группе Z_p^*:

2.1. Выбрать случайный элемент b Î Z_p^* и вычислить a = b^(p-1)/q mod p.

2.2. Если a = 1, тогда возвратиться к шагу 2.1.

3. Выбрать случайное целое x Î{1, 2,..., q-1} и вычислить у = a^x mod p.

4. Для стороны А открытый ключ равен (p, a, y), секретный ключ равен x.

Согласно алгоритму неоспоримой подписи Д.Чома, сторона А подписывает сообщение m, принадлежащее подгруппе порядка q в Z_p^*. Любая сторона В может проверить эту подпись при участии А.

В работе алгоритма неоспоримой подписи можно выделить два этапа:

1. Генерация подписи,

2. Верификация подписи.

На этапе генерации подписи сторона А вычисляет

s = m^x mod p,

где s – подпись стороны А на сообщении m.

Сообщение m с подписью s отсылается стороне В.

Этап верификации подписи выполняется стороной В с участием стороны А и включает следующие шаги:

(1) В получает подлинный открытый ключ (p, a, y) стороны А.

(2) В выбирает два случайных секретных целых числа a, b Î {1, 2,..., q-1}.

(3) B вычисляет z = s^a y^b mod p и отправляет значение z стороне А.

(4) А вычисляет w = (z)^1/x mod p, где хх^-1 º 1 (mod q), и отправляет значение w стороне В.

(5) В вычисляет w’ = m^a a^b mod p и признает подпись s подлинной, если и только если w = w’.

Убедимся, что проверка подписи s работает:

w º (z)^1/x º (s^a y^b)^1/x º (m^xaa^xb)^1/x º m^aa^b º w’mod p.

Можно показать, что с высокой степенью вероятности злоумышленник не сможет заставить В принять фальшивую подпись. Предположим, что s представляет собой подделку подписи стороны А на сообщении m, т.е. s ¹ m^x mod p. Тогда вероятность принятия стороной этой подписи в данном алгоритме составляет только 1/q, причем эта вероятность не зависит от вычислительных ресурсов злоумышленника.

Подписавшая сторона А при некоторых обстоятельствах могла бы попытаться отказаться от своей подлинной подписи одним из трех способов:

(а) отказаться от участия в протоколе верификации;

(б) некорректно выполнить протокол верификации;

(в) объявить подпись фальшивой, даже если протокол верификации оказался успешным.

Отречение от подписи способом (а) рассматривалось бы как очевидная попытка неправомерного отказа.

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

Протокол дезавуирования для схемы неоспоримой подписи Д.Чома включает следующие шаги:

(1) В принимает от стороны А сообщение m с подписью s и получает подлинный открытый ключ (p, a, y) стороны А.

(2) В выбирает случайные секретные целые числа a, bÎ{1,2,...,q-1}, вычисляет z = s^a y^b mod p и отправляет значение z стороне А.

(3) А вычисляет w = (z)^1/x mod p, где xx^-1 º 1(modq), и отправляет значение w стороне В.

(4) Если w = m^a a^b modp, тогда В признает подпись s подлинной и протокол прекращается.

(5) В выбирает случайные секретные целые числа a’, b’ Î {1, 2,..., q-1}, вычисляет z’= s^a’y^b’mod p и отправляет значение z’ стороне А.

(6) А вычисляет w’= (z’)^1/x modp и отправляет значение w’ стороне В.

(7) Если w’ = m^a’a^b’ modp, тогда В принимает подпись s и протокол останавливается.

(8) В вычисляет c = (wa^-b)^a’ mod p, c’= (w’a^-b’)^a mod p. Если с = c’, тогда В заключает, что подпись s фальшивая; в противном случае, В делает вывод, что подпись s подлинная, а сторона А пытается дезавуировать подпись s.

Нетрудно убедиться в том, что этот протокол достигает поставленной цели. Пусть m – сообщение и предположим, что s – подпись стороны А под сообщением m.

Если подпись s фальшивая, т.е. s ¹ m^x modp и если стороны А и В следуют протоколу должным образом, тогда w = w’ (и поэтому справедливо заключение В, что подпись s фальшивая).

Пусть s на самом деле является подписью стороны А под сообщением m, т.е. s = m^x mod p. Предположим, что В точно следует протоколу, а А не следует. Тогда вероятность того, что w=w’ (и А преуспевает в дезавуировании подписи), составляет только 1/q.

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

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

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

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

Зафиксируем конечное поле , где p – простое число. Пусть g – первообразный вычет по mod p. Вычет , где , есть секретный ключ А. Пусть сообщение (хэш-значение сообщения). Отправитель сообщения А вычисляет подпись под сообщением m. Таки образом (m,c) есть подписанный документ.

Протокол проверки подписи:

1) Получатель Б выбирает случайный вычет , вычисляет и передает вычет z отправителю А,

2) А вычисляет и и передает d получателю Б,

3) Б проверяет сравнение . Если оно выполнено, то Б принимает подпись, в противном случае подпись отвергается.

Легко проверить, что если подпись верна, то выполняется сравнение . Пусть теперь Б хочет продать копию документа m другому персонажу К. Б должен убедить К, что именно А подписал m. Для этого Б показывает запись протокола проверки подписи. Однако, К мог бы составить такую запись сам, не общаясь с А. Действительно, надо сгенерировать случайное и и вычислить . Таким образом, Б не в состоянии доказать, что именно А подписал сообщение m.

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

Глава 41.