РЕАЛИЗАЦИЯ ПРОТОКОЛА КОЛЛЕКТИВНОЙ ПОДПИСИ НА ОСНОВЕ СТАНДАРТОВ ЭЦП
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
УДК 681.3
М. Ю. АНАНЬЕВ, Л. В. ГОРТИНСКАЯ, А. А. КОСТИН, Н. А. МОЛДОВЯН
РЕАЛИЗАЦИЯ ПРОТОКОЛА КОЛЛЕКТИВНОЙ ПОДПИСИ НА ОСНОВЕ СТАНДАРТОВ ЭЦП
Рассматривается обобщенный протокол формирования коллективной электронной цифровой подписи, основанный на выполнении процедур „свертки“ индивидуальных параметров, вырабатываемых отдельными пользователями в зависимости от подписываемого документа и своих секретных ключей. Протокол обеспечивает одновременность формирования подписи и использует стандартную инфраструктуру открытых ключей. Сформулированы основные требования и рассмотрен вопрос создания протоколов коллективной электронной цифровой подписи на основе российских стандартов ЭЦП 1994 и 2001 гг.
Ключевые слова: цифровая подпись, коллективная подпись, криптографические протоколы.
Введение. В технологиях электронного документооборота широко используются алгоритмы электронной цифровой подписи (ЭЦП), на основе которых в сочетании с нормативноправовыми механизмами обеспечивается придание юридической силы электронной документации [1, 2]. При разработке разнообразных коллективных проектов важной проблемой является создание протоколов, обеспечивающих реализацию коллективной (или кратной) ЭЦП [3].
Изложенные в работе [3] подходы к решению этой задачи на основе генерации совокупности ЭЦП, принадлежащей отдельным пользователям, имеют следующие недостатки:
— необходимость использования дополнительных процедур проверки целостности коллективной ЭЦП (КЭЦП), которые позволяют проверить ее полноту, т.е. обнаружить попытки формирования КЭЦП, принадлежащей измененному числу пользователей;
— увеличение размера КЭЦП пропорционально числу подписавших документ участников (размер ЭЦП особенно важен при необходимости ее записи в виде штрих-кода на бумажных носителях).
Для устранения указанных недостатков был предложен [4] новый способ формирования и проверки подлинности КЭЦП, использующий понятие общего (коллективного) открытого ключа, формируемого на основе данных, имеющихся в стандартных справочниках открытых ключей.
В настоящей статье рассматриваются вопросы применения предложенной в работе [4] обобщенной схемы формирования КЭЦП с использованием коллективного открытого ключа и вопросы ее реализации на основе процедур генерации и проверки ЭЦП, регламентируемых стандартами ЭЦП — ГОСТ Р 34.10–94 и ГОСТ Р 34.10–2007 [5, 6].
Концепция коллективной подписи. Поставлена задача построить протокол формирования и проверки подписи следующим образом: ЭЦП обычного размера должна подтверждать то, что некоторый электронный документ подписан каждым пользователем из некото-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
Реализация протокола коллективной подписи на основе стандартов ЭЦП
27
рого заданного множества пользователей. При этом приняты следующие дополнительные
требования к разрабатываемому протоколу КЭЦП:
— целостность — из КЭЦП нельзя вычислить правильную подпись, соответствующую
другому подмножеству пользователей;
— независимость от пользователей — КЭЦП может сформировать любая группа поль-
зователей, независимо от их числа и состава;
— одновременность генерации КЭЦП — все значения, возникающие на промежуточ-
ных этапах процедуры генерации КЭЦП, не должны быть правильными подписями к каким-
либо сообщениям;
— неразрывность — по данной коллективной подписи вычислительно невозможно
сформировать другую коллективную подпись
В качестве базовой идеи протокола коллективной подписи была принята концепция ис-
пользования коллективного открытого ключа, являющегося функцией открытых ключей
пользователей. Коллективный открытый ключ некоторой произвольно задаваемой совокуп-
ности m пользователей, каждый из которых является владельцем соответствующего открытого
ключа из множества y1, y2, …, ym, представляет собой некоторое значение y = f(y1, y2, …, ym). Общая схема формирования КЭЦП была реализована в виде удовлетворяющих пере-
численным требованиям конкретных алгоритмов и протоколов с использованием следующих
трудных вычислительных задач:
— извлечение корней большой простой степени по большому простому модулю;
— дискретное логарифмирование в мультипликативной группе большого простого порядка;
— дискретное логарифмирование в группе точек эллиптической кривой специального вида.
Особый интерес представляют алгоритмы, основанные на последней из перечисленных
трудных задач, поскольку в этом случае обеспечивается наибольшая производительность
процедур генерации и проверки подписи. Достоинство предложенной концепции КЭЦП за-
ключается в использовании стандартной инфраструктуры открытых ключей.
Обратимся, далее, к реализации протоколов КЭЦП, основанной на проверочных урав-
нениях, предлагаемых стандартами ЭЦП.
Реализация протоколов на основе стандартов ЭЦП.
I. Стандарт ЭЦП — ГОСТ Р 34.10−94 [5] — регламентирует использование простого
числа p, такого что 510 ≤ |p| ≤ 512 бит либо 1022 ≤ |p| ≤ 1024 бит, где |p| — разрядность p в двоичном представлении, при этом число p – 1 содержит большой простой делитель: 2255 ≤ q ≤ 2256 либо 2511 ≤ q ≤ 2512 соответственно. Специфицируемые алгоритмы генерации и проверки ЭЦП используют число α ≠ 1, такое что α q mod p = 1, где α — генератор подгруппы достаточно большого простого порядка q. Вычисление ЭЦП осуществляется следующим об-
разом.
1. Генерируется случайное число k, 1 < k < q. 2. Вычисляется значение R = (α k mod p) mod q, являющееся первой частью подписи. 3. По ГОСТ Р 34.11–94 вычисляется хэш-функция H от подписываемого сообщения.
4. Вычисляется вторая часть подписи: S = kH + zR mod q , где z — секретный ключ. Если
S = 0, процедура генерации подписи повторяется.
Процедура проверки подлинности ЭЦП содержит следующие шаги.
1. Поверяется выполнение условий r < q и s < q, если они не выполняются, то подпись
недействительна.
2. Вычисляется значение
R′ = (αS / H yR / H mod p) mod q ,
(1)
где у — открытый ключ пользователя, сформировавшего проверяемую подпись.
3. Сравниваются значения R и R′. Если R = R′, то подпись признается действительной.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
28 М. Ю. Ананьев, Л. В. Гортинская, А. А. Костин, Н. А. Молдовян
Протокол КЭЦП реализуется следующим образом. Каждый i-й пользователь формирует открытый ключ вида yi = αzi mod p, где zi — личный (секретный) ключ, i = 1, 2, …, m. Коллективным открытым ключом является произведение
y = y1y2y3…ym mod p. Коллективная подпись формируется следующим путем. Каждый пользователь выбирает разовый случайный секретный ключ — число ki, затем вычисляет Ri = (αki mod p) mod q и предоставляет это значение для коллективного использования. Далее вычисляется произведение
R = R1R2R3…Rm mod q. Затем каждый пользователь по определенному им значению Ri и величине H вычисляет свою часть подписи
Si = ki H + zi R mod q .
Коллективной подписью является пара чисел (R, S), где S вычисляется по формуле S = S1 + S2 + S3 +…+ Sm mod q.
Проверка коллективной подписи осуществляется по формуле (1). Если R = R′, то КЭЦП совокупности т пользователей является подлинной, так как она могла быть сформирована только при участии каждого пользователя из этой группы, поскольку для ее формирования требуется использование секретного ключа каждого из них. Отметим, что аутентификация значений Ri осуществляется автоматически при проверке подлинности коллективной ЭЦП. Если нарушитель попытается подменить какое-либо из этих значений или заменить на ранее использованные значения, то факт вмешательства в протокол будет сразу же выявлен при
проверке подлинности ЭЦП, т. е. будет получено R′ ≠ R. Очевидно, что размер КЭЦП не зависит от m.
Покажем корректность предложенного алгоритма КЭЦП. Подставив подпись (R, S), где
mm
∑ ∏S = Si mod q и R = Ri mod q , в проверочное уравнение R = (αS / H yR / H mod p) mod q , i=1 i=1
убеждаемся, что оно выполняется:
∏ ∏ ∏R
=
⎢⎢⎡αi∑m=1Si / H ⎣
⎛ ⎝⎜⎜
m i=1
yi
⎞R/ H ⎟⎟⎠
mod
⎤ p⎥⎥ mod q
⎦
=
⎛ ⎜⎝⎜
m i=1
α Si
/H
m i=1
yi R / H
mod
p
⎞ ⎟⎟⎠
mod
q
=
⎡m
∏( ) ∏( )= ⎢
αSi / H α ziR / H
mod
p
⎤ ⎥
mod
q
=
⎡ ⎢
m
α(ki −ziR) / H α ziR / H
mod p
⎤ ⎥
mod
q
=
⎣⎢ i=1 ⎥⎦ ⎣⎢ i=1
⎥⎦
∏ ∏( ) ∏=
⎛ ⎜⎝⎜
m i=1
αki
mod
p
⎞ ⎠⎟⎟
mod
q
=
⎡ ⎢ ⎣⎢
m i=1
αki mod p
mod
q
⎤ ⎥
⎦⎥
mod
q
=
⎛ ⎝⎜⎜
m i=1
Ri
⎞ ⎠⎟⎟
mod
q.
II. Стандарт ЭЦП — ГОСТ Р 34.10−2001 [6] — регламентирует использование: простого числа p — модуля эллиптической кривой (ЭК), которая задается в декартовой системе
координат уравнением у2 = x3 + ax + b mod p с коэффициентами a и b: a,b ∈ GFp ( GFp —
поле Галуа порядка р); простого числа q — порядка циклической подгруппы точек ЭК; точки G
с координатами (xG , yG ) , такой что точка G не совпадает с началом координат, а произведе-
ние qG — совпадает. Секретным ключом является достаточно большое целое число d, а открытым ключом — точка Q = dG . Формирование подписи (R, S) осуществляется в соответст-
вии со следующим алгоритмом.
1. Генерируется случайное целое число k, 0 < k < q.
2. Вычисляются координаты точки ЭК C = kP и определяется значение R = xC mod q, где xC — координата точки С.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
Реализация протокола коллективной подписи на основе стандартов ЭЦП
3. Вычисляется значение S = ( Rd + ke) mod q , где e=H mod q.
Подписью является пара чисел (R, S). Проверка подписи заключается в вычислении координат точки ЭК:
(( ) ) ( )C = Se−1 mod q G + (q − R)e−1 mod q Q ,
29 (2)
а также в определении значения R′ = xC mod q и проверке выполнения равенства R′ = R. Протокол КЭЦП реализуется следующим образом. Каждый i-й пользователь формирует
открытый ключ вида Q = diG , где di — личный (секретный) ключ, i = 1, 2, …, m. Коллективным открытым ключом является сумма
Q = Q1 + Q2 + Q3 +… + Qm.
Коллективная подпись формируется следующим путем. Каждый пользователь выбирает разовый случайный секретный ключ — число ki, затем вычисляет координаты точки Ci = kiG и предоставляет их для коллективного использования. Далее определяется сумма всех точек Ci:
C = C1 + C2 + C3 +…+ C m,
по которой вычисляется значение R. Затем каждый i-й пользователь по своему секретному ключу di, значению ki и величине e вычисляет свою часть подписи
Si = ( Rdi + kie) mod q .
Коллективной подписью является пара чисел (R, S), где S вычисляется по формуле
S = S1 + S2 + S3 +…+ Sm mod q.
Проверка коллективной подписи осуществляется по проверочной формуле. Если R′ = xC′ mod q = R, где координаты точки C′ вычисляются по соотношению (2), то КЭЦП совокупности m пользователей является подлинной, так как она могла быть сформирована только при участии каждого пользователя из этой группы, поскольку для ее формирования требуется использование секретного ключа каждого из них.
Генерация индивидуальных
значений R1, …, Rm
Секретные ключи x1
x2
Вычисление коллективного рандомизирующего элемента ЭЦП R = f(R1, …, Rm)
Формирование части S1
Формирование части S2
Электронный документ
(представлен обычно значением хэш-функции Н) Интеграция
частей S1, …, Sm в единую КЭЦП
xm
Формирование части Sm
КЭЦП: (R, S)
Рис. 1
Общая схема формирования коллективной подписи представлена на рис. 1, а процедура проверки подлинности КЭЦП — на рис. 2.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
30 М. Ю. Ананьев, Л. В. Гортинская, А. А. Костин, Н. А. Молдовян
Справочник открытых ключей
у1 у2
уm
Формирование коллективного открытого ключа у
Значение КЭЦП: (R, S)
Проверка подлинности
КЭЦП
Электронный документ
Да/Нет Рис. 2
Заключение. Применение понятия коллективного открытого ключа позволяет построить протоколы КЭЦП, перспективные для практического применения в технологиях электронного документооборота благодаря обеспечению одновременности формирования подписи и ее целостности. Достоинством таких протоколов является возможность их практической реализации на основе стандартной инфраструктуры открытых ключей и стандартов ЭЦП. Использование КЭЦП является удачным решением известной проблемы одновременного подписания контракта [7]. Представляет интерес использование КЭЦП для построения протоколов „множественной подписи“ [7], что составляет самостоятельную задачу дальнейшего развития протоколов на основе понятия коллективного открытого ключа.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант № 08-07-90100-Мол_а.
СПИСОК ЛИТЕРАТУРЫ
1. Венбо Мао. Современная криптография. Теория и практика. М. — СПб. — Киев: Изд. дом „Вильямс“, 2005. 763 с.
2. Молдовян Н. А. Введение в криптосистемы с открытым ключом. СПб.: БХВ-Петербург, 2005. 286 с.
3. Min-Shiang Hawng, Cheng-Chi Lee. Research issues and challenges for multiple digital signature // Intern. J. of Network Security. 2005. Vol. 1, N 1. P. 1—7.
4. Способ генерации и проверки подлинности электронной цифровой подписи, заверяющей электронный документ / А. А. Молдовян, Н. А. Молдовян. Пат. заявка № 2007130982, РФ. Заявл. 13.08.2007.
5. ГОСТ Р 34.10–94. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. М.: Госстандарт Российской Федерации, 1994.
6. ГОСТ Р 34.10–2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. М.: Госстандарт России, 2001.
7. Schneier B. Applied Cryptography: Protocol, Algorithms, and Source Code. N. Y.: John Wiley & Sons, 1996. 758 p.
Сведения об авторах
Михаил Юрьевич Ананьев
— аспирант; Санкт-Петербургский государственный университет водных
коммуникаций; E-mail: nmold@cobra.ru
Лидия Вячеславовна Гортинская — канд. физ.-мат. наук; Научный филиал ФГУП НИИ „Вектор“ — Спе-
циализированный центр программных систем „Спектр“, Санкт-
Петербург; E-mail: lydia@cobra.ru
Андрей Алексеевич Костин
— канд. техн. наук; Научный филиал ФГУП НИИ „Вектор“ — Специа-
лизированный центр программных систем „Спектр“, Санкт-
Петербург; E-mail: anya@hotbox.ru
Николай Андреевич Молдовян
— д-р техн. наук; Научный филиал ФГУП НИИ „Вектор“ — Специали-
зированный центр программных систем „Спектр“, Санкт-Петербург;
E-mail: nmold@cobra.ru
Рекомендована НИИ „Вектор“
Поступила в редакцию 04.10.07 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
УДК 681.3
М. Ю. АНАНЬЕВ, Л. В. ГОРТИНСКАЯ, А. А. КОСТИН, Н. А. МОЛДОВЯН
РЕАЛИЗАЦИЯ ПРОТОКОЛА КОЛЛЕКТИВНОЙ ПОДПИСИ НА ОСНОВЕ СТАНДАРТОВ ЭЦП
Рассматривается обобщенный протокол формирования коллективной электронной цифровой подписи, основанный на выполнении процедур „свертки“ индивидуальных параметров, вырабатываемых отдельными пользователями в зависимости от подписываемого документа и своих секретных ключей. Протокол обеспечивает одновременность формирования подписи и использует стандартную инфраструктуру открытых ключей. Сформулированы основные требования и рассмотрен вопрос создания протоколов коллективной электронной цифровой подписи на основе российских стандартов ЭЦП 1994 и 2001 гг.
Ключевые слова: цифровая подпись, коллективная подпись, криптографические протоколы.
Введение. В технологиях электронного документооборота широко используются алгоритмы электронной цифровой подписи (ЭЦП), на основе которых в сочетании с нормативноправовыми механизмами обеспечивается придание юридической силы электронной документации [1, 2]. При разработке разнообразных коллективных проектов важной проблемой является создание протоколов, обеспечивающих реализацию коллективной (или кратной) ЭЦП [3].
Изложенные в работе [3] подходы к решению этой задачи на основе генерации совокупности ЭЦП, принадлежащей отдельным пользователям, имеют следующие недостатки:
— необходимость использования дополнительных процедур проверки целостности коллективной ЭЦП (КЭЦП), которые позволяют проверить ее полноту, т.е. обнаружить попытки формирования КЭЦП, принадлежащей измененному числу пользователей;
— увеличение размера КЭЦП пропорционально числу подписавших документ участников (размер ЭЦП особенно важен при необходимости ее записи в виде штрих-кода на бумажных носителях).
Для устранения указанных недостатков был предложен [4] новый способ формирования и проверки подлинности КЭЦП, использующий понятие общего (коллективного) открытого ключа, формируемого на основе данных, имеющихся в стандартных справочниках открытых ключей.
В настоящей статье рассматриваются вопросы применения предложенной в работе [4] обобщенной схемы формирования КЭЦП с использованием коллективного открытого ключа и вопросы ее реализации на основе процедур генерации и проверки ЭЦП, регламентируемых стандартами ЭЦП — ГОСТ Р 34.10–94 и ГОСТ Р 34.10–2007 [5, 6].
Концепция коллективной подписи. Поставлена задача построить протокол формирования и проверки подписи следующим образом: ЭЦП обычного размера должна подтверждать то, что некоторый электронный документ подписан каждым пользователем из некото-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
Реализация протокола коллективной подписи на основе стандартов ЭЦП
27
рого заданного множества пользователей. При этом приняты следующие дополнительные
требования к разрабатываемому протоколу КЭЦП:
— целостность — из КЭЦП нельзя вычислить правильную подпись, соответствующую
другому подмножеству пользователей;
— независимость от пользователей — КЭЦП может сформировать любая группа поль-
зователей, независимо от их числа и состава;
— одновременность генерации КЭЦП — все значения, возникающие на промежуточ-
ных этапах процедуры генерации КЭЦП, не должны быть правильными подписями к каким-
либо сообщениям;
— неразрывность — по данной коллективной подписи вычислительно невозможно
сформировать другую коллективную подпись
В качестве базовой идеи протокола коллективной подписи была принята концепция ис-
пользования коллективного открытого ключа, являющегося функцией открытых ключей
пользователей. Коллективный открытый ключ некоторой произвольно задаваемой совокуп-
ности m пользователей, каждый из которых является владельцем соответствующего открытого
ключа из множества y1, y2, …, ym, представляет собой некоторое значение y = f(y1, y2, …, ym). Общая схема формирования КЭЦП была реализована в виде удовлетворяющих пере-
численным требованиям конкретных алгоритмов и протоколов с использованием следующих
трудных вычислительных задач:
— извлечение корней большой простой степени по большому простому модулю;
— дискретное логарифмирование в мультипликативной группе большого простого порядка;
— дискретное логарифмирование в группе точек эллиптической кривой специального вида.
Особый интерес представляют алгоритмы, основанные на последней из перечисленных
трудных задач, поскольку в этом случае обеспечивается наибольшая производительность
процедур генерации и проверки подписи. Достоинство предложенной концепции КЭЦП за-
ключается в использовании стандартной инфраструктуры открытых ключей.
Обратимся, далее, к реализации протоколов КЭЦП, основанной на проверочных урав-
нениях, предлагаемых стандартами ЭЦП.
Реализация протоколов на основе стандартов ЭЦП.
I. Стандарт ЭЦП — ГОСТ Р 34.10−94 [5] — регламентирует использование простого
числа p, такого что 510 ≤ |p| ≤ 512 бит либо 1022 ≤ |p| ≤ 1024 бит, где |p| — разрядность p в двоичном представлении, при этом число p – 1 содержит большой простой делитель: 2255 ≤ q ≤ 2256 либо 2511 ≤ q ≤ 2512 соответственно. Специфицируемые алгоритмы генерации и проверки ЭЦП используют число α ≠ 1, такое что α q mod p = 1, где α — генератор подгруппы достаточно большого простого порядка q. Вычисление ЭЦП осуществляется следующим об-
разом.
1. Генерируется случайное число k, 1 < k < q. 2. Вычисляется значение R = (α k mod p) mod q, являющееся первой частью подписи. 3. По ГОСТ Р 34.11–94 вычисляется хэш-функция H от подписываемого сообщения.
4. Вычисляется вторая часть подписи: S = kH + zR mod q , где z — секретный ключ. Если
S = 0, процедура генерации подписи повторяется.
Процедура проверки подлинности ЭЦП содержит следующие шаги.
1. Поверяется выполнение условий r < q и s < q, если они не выполняются, то подпись
недействительна.
2. Вычисляется значение
R′ = (αS / H yR / H mod p) mod q ,
(1)
где у — открытый ключ пользователя, сформировавшего проверяемую подпись.
3. Сравниваются значения R и R′. Если R = R′, то подпись признается действительной.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
28 М. Ю. Ананьев, Л. В. Гортинская, А. А. Костин, Н. А. Молдовян
Протокол КЭЦП реализуется следующим образом. Каждый i-й пользователь формирует открытый ключ вида yi = αzi mod p, где zi — личный (секретный) ключ, i = 1, 2, …, m. Коллективным открытым ключом является произведение
y = y1y2y3…ym mod p. Коллективная подпись формируется следующим путем. Каждый пользователь выбирает разовый случайный секретный ключ — число ki, затем вычисляет Ri = (αki mod p) mod q и предоставляет это значение для коллективного использования. Далее вычисляется произведение
R = R1R2R3…Rm mod q. Затем каждый пользователь по определенному им значению Ri и величине H вычисляет свою часть подписи
Si = ki H + zi R mod q .
Коллективной подписью является пара чисел (R, S), где S вычисляется по формуле S = S1 + S2 + S3 +…+ Sm mod q.
Проверка коллективной подписи осуществляется по формуле (1). Если R = R′, то КЭЦП совокупности т пользователей является подлинной, так как она могла быть сформирована только при участии каждого пользователя из этой группы, поскольку для ее формирования требуется использование секретного ключа каждого из них. Отметим, что аутентификация значений Ri осуществляется автоматически при проверке подлинности коллективной ЭЦП. Если нарушитель попытается подменить какое-либо из этих значений или заменить на ранее использованные значения, то факт вмешательства в протокол будет сразу же выявлен при
проверке подлинности ЭЦП, т. е. будет получено R′ ≠ R. Очевидно, что размер КЭЦП не зависит от m.
Покажем корректность предложенного алгоритма КЭЦП. Подставив подпись (R, S), где
mm
∑ ∏S = Si mod q и R = Ri mod q , в проверочное уравнение R = (αS / H yR / H mod p) mod q , i=1 i=1
убеждаемся, что оно выполняется:
∏ ∏ ∏R
=
⎢⎢⎡αi∑m=1Si / H ⎣
⎛ ⎝⎜⎜
m i=1
yi
⎞R/ H ⎟⎟⎠
mod
⎤ p⎥⎥ mod q
⎦
=
⎛ ⎜⎝⎜
m i=1
α Si
/H
m i=1
yi R / H
mod
p
⎞ ⎟⎟⎠
mod
q
=
⎡m
∏( ) ∏( )= ⎢
αSi / H α ziR / H
mod
p
⎤ ⎥
mod
q
=
⎡ ⎢
m
α(ki −ziR) / H α ziR / H
mod p
⎤ ⎥
mod
q
=
⎣⎢ i=1 ⎥⎦ ⎣⎢ i=1
⎥⎦
∏ ∏( ) ∏=
⎛ ⎜⎝⎜
m i=1
αki
mod
p
⎞ ⎠⎟⎟
mod
q
=
⎡ ⎢ ⎣⎢
m i=1
αki mod p
mod
q
⎤ ⎥
⎦⎥
mod
q
=
⎛ ⎝⎜⎜
m i=1
Ri
⎞ ⎠⎟⎟
mod
q.
II. Стандарт ЭЦП — ГОСТ Р 34.10−2001 [6] — регламентирует использование: простого числа p — модуля эллиптической кривой (ЭК), которая задается в декартовой системе
координат уравнением у2 = x3 + ax + b mod p с коэффициентами a и b: a,b ∈ GFp ( GFp —
поле Галуа порядка р); простого числа q — порядка циклической подгруппы точек ЭК; точки G
с координатами (xG , yG ) , такой что точка G не совпадает с началом координат, а произведе-
ние qG — совпадает. Секретным ключом является достаточно большое целое число d, а открытым ключом — точка Q = dG . Формирование подписи (R, S) осуществляется в соответст-
вии со следующим алгоритмом.
1. Генерируется случайное целое число k, 0 < k < q.
2. Вычисляются координаты точки ЭК C = kP и определяется значение R = xC mod q, где xC — координата точки С.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
Реализация протокола коллективной подписи на основе стандартов ЭЦП
3. Вычисляется значение S = ( Rd + ke) mod q , где e=H mod q.
Подписью является пара чисел (R, S). Проверка подписи заключается в вычислении координат точки ЭК:
(( ) ) ( )C = Se−1 mod q G + (q − R)e−1 mod q Q ,
29 (2)
а также в определении значения R′ = xC mod q и проверке выполнения равенства R′ = R. Протокол КЭЦП реализуется следующим образом. Каждый i-й пользователь формирует
открытый ключ вида Q = diG , где di — личный (секретный) ключ, i = 1, 2, …, m. Коллективным открытым ключом является сумма
Q = Q1 + Q2 + Q3 +… + Qm.
Коллективная подпись формируется следующим путем. Каждый пользователь выбирает разовый случайный секретный ключ — число ki, затем вычисляет координаты точки Ci = kiG и предоставляет их для коллективного использования. Далее определяется сумма всех точек Ci:
C = C1 + C2 + C3 +…+ C m,
по которой вычисляется значение R. Затем каждый i-й пользователь по своему секретному ключу di, значению ki и величине e вычисляет свою часть подписи
Si = ( Rdi + kie) mod q .
Коллективной подписью является пара чисел (R, S), где S вычисляется по формуле
S = S1 + S2 + S3 +…+ Sm mod q.
Проверка коллективной подписи осуществляется по проверочной формуле. Если R′ = xC′ mod q = R, где координаты точки C′ вычисляются по соотношению (2), то КЭЦП совокупности m пользователей является подлинной, так как она могла быть сформирована только при участии каждого пользователя из этой группы, поскольку для ее формирования требуется использование секретного ключа каждого из них.
Генерация индивидуальных
значений R1, …, Rm
Секретные ключи x1
x2
Вычисление коллективного рандомизирующего элемента ЭЦП R = f(R1, …, Rm)
Формирование части S1
Формирование части S2
Электронный документ
(представлен обычно значением хэш-функции Н) Интеграция
частей S1, …, Sm в единую КЭЦП
xm
Формирование части Sm
КЭЦП: (R, S)
Рис. 1
Общая схема формирования коллективной подписи представлена на рис. 1, а процедура проверки подлинности КЭЦП — на рис. 2.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1
30 М. Ю. Ананьев, Л. В. Гортинская, А. А. Костин, Н. А. Молдовян
Справочник открытых ключей
у1 у2
уm
Формирование коллективного открытого ключа у
Значение КЭЦП: (R, S)
Проверка подлинности
КЭЦП
Электронный документ
Да/Нет Рис. 2
Заключение. Применение понятия коллективного открытого ключа позволяет построить протоколы КЭЦП, перспективные для практического применения в технологиях электронного документооборота благодаря обеспечению одновременности формирования подписи и ее целостности. Достоинством таких протоколов является возможность их практической реализации на основе стандартной инфраструктуры открытых ключей и стандартов ЭЦП. Использование КЭЦП является удачным решением известной проблемы одновременного подписания контракта [7]. Представляет интерес использование КЭЦП для построения протоколов „множественной подписи“ [7], что составляет самостоятельную задачу дальнейшего развития протоколов на основе понятия коллективного открытого ключа.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант № 08-07-90100-Мол_а.
СПИСОК ЛИТЕРАТУРЫ
1. Венбо Мао. Современная криптография. Теория и практика. М. — СПб. — Киев: Изд. дом „Вильямс“, 2005. 763 с.
2. Молдовян Н. А. Введение в криптосистемы с открытым ключом. СПб.: БХВ-Петербург, 2005. 286 с.
3. Min-Shiang Hawng, Cheng-Chi Lee. Research issues and challenges for multiple digital signature // Intern. J. of Network Security. 2005. Vol. 1, N 1. P. 1—7.
4. Способ генерации и проверки подлинности электронной цифровой подписи, заверяющей электронный документ / А. А. Молдовян, Н. А. Молдовян. Пат. заявка № 2007130982, РФ. Заявл. 13.08.2007.
5. ГОСТ Р 34.10–94. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. М.: Госстандарт Российской Федерации, 1994.
6. ГОСТ Р 34.10–2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. М.: Госстандарт России, 2001.
7. Schneier B. Applied Cryptography: Protocol, Algorithms, and Source Code. N. Y.: John Wiley & Sons, 1996. 758 p.
Сведения об авторах
Михаил Юрьевич Ананьев
— аспирант; Санкт-Петербургский государственный университет водных
коммуникаций; E-mail: nmold@cobra.ru
Лидия Вячеславовна Гортинская — канд. физ.-мат. наук; Научный филиал ФГУП НИИ „Вектор“ — Спе-
циализированный центр программных систем „Спектр“, Санкт-
Петербург; E-mail: lydia@cobra.ru
Андрей Алексеевич Костин
— канд. техн. наук; Научный филиал ФГУП НИИ „Вектор“ — Специа-
лизированный центр программных систем „Спектр“, Санкт-
Петербург; E-mail: anya@hotbox.ru
Николай Андреевич Молдовян
— д-р техн. наук; Научный филиал ФГУП НИИ „Вектор“ — Специали-
зированный центр программных систем „Спектр“, Санкт-Петербург;
E-mail: nmold@cobra.ru
Рекомендована НИИ „Вектор“
Поступила в редакцию 04.10.07 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 1