Множественная подпись: новые решения на основе понятия коллективного открытого ключа

КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ X

УДК 681.3

МНОЖЕСТВЕННАЯ ПОДПИСЬ: НОВЫЕ РЕШЕНИЯ НА ОСНОВЕ ПОНЯТИЯ КОЛЛЕКТИВНОГО ОТКРЫТОГО КЛЮЧА

А. И. Галанов,

научный сотрудник Н. А. Молдовян,

доктор техн. наук, профессор

ФГУП НИИ «Вектор» — специализированный центр программных систем «Спектр» М. А. Еремеев,

доктор техн. наук, доцент

Военно-космическая академия им. А. Ф. Можайского

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

Введение

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

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

В ряде работ предложены протоколы формирования и проверки коллективной электронной циф-

ровой подписи [1-4]. Данные протоколы построены на основе комбинирования электронных подписей в едином уравнении проверки ЭЦП. В ряде из них не все пользователи вносят свой вклад в коллективную подпись в одинаковых условиях. Это вызывает ограничения, сужающие рамки практического применения.

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

Протоколы множественной подписи

Для получения множественной подписи 2 пользователей сети следует осуществить следующую последовательность действий.

1. Каждым пользователем формируются подписи (Л1, 51), (Д2, &2), —, (^г, £г) к хэш-функциям документов Н1, Н2, ..., Нг соответственно.

2. Вычисляются хэш-функции от всех документов Н£ = *Н<Н1|Н2 1|.|Нг).

3. Формируется подпись (Ry, Sy) к хэш-функции Hy.

Множественная подпись (R1s S^, (R2, S2), ..., (Rz, Sz), (Ry, Sy) устраняет недостатки предыдущих схем подписи.

Сформулируем расширенную задачу формирования и проверки множественной подписи. Расширение состоит в том, что в кортеж подписей входят ЭЦП, относящиеся к различным пользователям, т. е. проверяемый в едином уравнении кортеж подписей относится к некоторому множеству пользователей. Каждый пользователь подписывает свой документ. С использованием случайных рандомизирующих значений формируется композиционная подпись №комп, S^^). Множественной подписью является кортеж (R1, S1), (R2, S2), ...,

(Rz, ^ (Rкомп, Sкомп).

Замечания:

а) избыточная подпись (Ry, Sy) или (R^n, Sкомп) незначительно увеличивает сложность процедур формирования и проверки множественной подписи;

б) решается расширенная задача;

в) устраняются проблемы в известных решениях по построению схем множественной подписи.

Алгоритм формирования композиционной подписи.

1. Каждый j-й пользователь генерирует случайное число tj и вычисляет рандомизирующий элемент ЭЦП Rf. Rj = аjmod p, j=1, 2, ..., z.

z

2. Вычисляется Rк0мп = П Rj mod p.

j=1

3. Каждый j-й пользователь вычисляет свою долю Sj, вносимую во вторую часть композиционной подписи: Sj = t} -kjR^nSH, где ^ < z, ^ —

i=1

количество документов, подписываемых j-м пользователем, а kj — секретный ключ j-го пользователя.

4. Формируется композиционная подпись

m

Sкомn = SSjmod «, где q(P - 1).

j=1

Проверка композиционной подписи осуществляется с помощью решения следующего проверочного уравнения: Rкомп = a51” mod p, где ис-

пользуется композиционный открытый ключ, оп-

j

A S H

ределяемый формулой Укомп = П yf1 mod p.

j=1

Особенности введенного расширенного понятия множественной подписи:

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

• в рамках композиционной подписи ^комп, S^m) каждый пользователь подписывает свой личный кортеж документов;

• возможна реализация в различных вариантах;

• в случае z = 1 мы имеем обычную множественную подпись, где вместо (Ry, Sy) в кортеж подписей вносится ^комп, S^n);

• композиционный открытый ключ Укомп может быть предварительно вычислен. Именно то, как вычисляется Ткомп, и определяет распределение документов H1, H2, ..., Hz по пользователям. Это, естественно, должно быть описано как спецификация кортежа, иначе неизвестно, что надо проверять;

• протокол, использующий параметр Hy = = Fh(H1\\H2 ||...||Hz), можно построить таким образом, чтобы документы, стоящие на пересечении i-го пользователя и j-го документа (рисунок), подписывались с помощью коллективной ЭЦП.

По аналогии предлагаемым протоколом можно достаточно просто реализовать множественную подпись с использованием математического аппарата эллиптических кривых. В этом случае R^^ является точкой эллиптической кривой, вычисляемой по формуле R^^ = R1 + R2 + ... + Rz, где Rj = tjG, G — точка эллиптической кривой, значение порядка которой равно достаточно большому числу q. Элемент подписи екомп вычисляется по формуле

бкомп = XRm mod «, где ^омп — одна из координат

точки R^^. Композиционный открытый ключ формируется по формуле -Ркомп = h1P1 + h-2P 2 + ••• + + hzPz, где Pi — точка эллиптической кривой, являющаяся открытым ключом i-го субъекта, Pj = = kjG. Вторая часть подписи Si определяется по формуле St = tt - екомп^^ mod q. При проверке подписи (екомп, Sк0мn) вычисляется точка эллиптической кривой R' = eк0мnP + Sк0мnG, затем значение e' = xR mod q, которое сравнивается с екомп.

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

]

1 2 3 4 5 6 7 8 9 10

1

2

3

4

Компози- 1 1 1 1 3 2 1 1 1 2

ционная 2 2 3 3 2 3 2 4

ЭЦП 3 4 3 4 4 4

Формирование кортежа коллективных подписей: I — 1-й пользователь;} — ]-й документ; | | — под-

писываемый документ

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

Заключение

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

Литература

1. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: ТРИУМФ, 2002. 816 с.

2. Галанов А. Н., Гортинская Л. В., Гурьянов Д. Ю., Молдовян А. А. Протокол коллективной электронной цифровой подписи на основе сложности извлечения корней по модулю // Инновационная деятельность в Вооруженных силах Российской Федерации: Тр. всеармейской науч.-практ. конф. / ВАС. СПб., 2007.С.179-183.

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

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

3. Молдовяну П. А., Молдовян Н. А., Доронин С. Е. Схемы коллективной подписи на основе задач дискретного логарифмирования // Инновационная деятельность в Вооруженных силах Российской Федерации: Тр. всеармейской науч.-практ. конф. / ВАС. СПб., 2007. С.243-246.

4. Дернова Е. С., Еремеев М. А., Молдовяну П. А. Протоколы композиционной подписи // Инновационная деятельность в Вооруженных силах Российской Федерации: Тр. всеармейской науч.-практ. конф. / ВАС. СПб., 2007. С. 224-229.