Эта статья входит в число добротных статей

Множественная подпись

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Множественная (коллективная) подпись (англ. Aggregate signature) — схема (протокол) реализации электронной подписи (ЭЦП), которая позволяет нескольким пользователям подписывать единый документ.

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

Введение[править | править код]

Термин «коллективная подпись» созвучен с термином «групповая подпись», однако эти понятия различны. В протоколе групповой ЭЦП решается задача обеспечения возможности любому пользователю из некоторой группы сформировать подпись от имени всей группы. В протоколе групповой ЭЦП также регламентируется наличие конкретных лиц, которые могут определять список людей, сформировавших подпись (тем самым последние имеют гипотетическую возможность подписаться за любого из членов группы). В случае коллективной работы с электронными документами необходимо иметь возможность их подписи многими пользователями[2]. Вариант схемы с генерацией набора индивидуальных ЭЦП пользователей, подписывающих один электронный документ, обладает несколькими выраженными недостатками — линейным увеличением размера коллективной ЭЦП (КЭЦП) с увеличением числа подписантов, а также необходимостью дополнительных проверок целостности и полноты коллективной цифровой подписи для исключения возможности подмены количества и поимённого состава участников, подписавших документ[1].

Концепция коллективного открытого ключа[править | править код]

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

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

Реализация протоколов на основе стандартов ЭЦП[править | править код]

Стандарт ЭЦП — ГОСТ Р 34.10−94[править | править код]

Согласно стандарту ГОСТ Р 34.10−94[4] накладываются ограничения на используемое простое число p. Разрядность простого числа p в двоичном представлении: бит либо бит. Число должно содержать большой простой делитель такой, что для либо для . Для генерации и проверки ЭЦП используют число , такое что , где  — генератор подгруппы достаточно большого простого порядка .

Алгоритм вычисления ЭЦП[править | править код]

1. Генерируется случайное число . 
2. Вычисляется значение , являющееся первой частью подписи. 
3. По ГОСТ Р 34.11–94 вычисляется хеш-функция  от подписываемого сообщения. 
4. Вычисляется вторая часть подписи: , где  — секретный ключ. Если 
   , процедура генерации подписи повторяется.

Алгоритм проверки подлинности ЭЦП[править | править код]

1. Поверяется выполнение условий  и . Если условия не выполняются, то подпись не является действительной. 
2. Вычисляется значение 
,где  — открытый ключ пользователя, сформировавшего проверяемую подпись. 
3. Сравниваются значения  и . Если , то подпись является действительной

Реализация протокола КЭЦП[править | править код]

Каждый -й пользователь формирует открытый ключ вида , где  — личный (секретный) ключ, = , , … , .

Коллективным открытым ключом является произведение

 

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

Вычисляется

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

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

 
 - часть подписи. 

Коллективной подписью будет пара величин , где  — сумма всех по модулю [3].

Проверка коллективной электронной цифровой подписи[править | править код]

Проверка коллективной подписи осуществляется по формуле

 

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

Доказательство корректности предложенного алгоритма КЭЦП[править | править код]

В уравнение подставляем полученную подпись — пару (R,S), где R — произведение Ri по модулю q, S — сумма Si по модулю q: Убеждаемся, что оно выполняется: [3] Рассмотрим формальное доказательство стойкости протокола КЭЦП при использовании проверочного уравнения , регламентируемого стандартом ЭЦП ГОСТ Р 34.10-94.

Возможность подделки КЭЦП[править | править код]

Очевидно, что для нарушителей сложность подделки КЭЦП определяется сложностью подделки индивидуальной подписи отдельного участника группы. Возможности возникают у пользователей, объединяющих свои усилия, чтобы сформировать КЭЦП, относящееся к коллективу, в котором кроме них входит ещё один или несколько других пользователей, которые об этом не оповещаются (доказательство для обоих случаев аналогично). Пусть m-1 пользователей хотят сформировать КЭЦП, проверяемую по коллективному открытому ключу , где , то есть пользователей объединяют свои усилия, чтобы сформировать пару чисел такую, что . То есть они могут подделать подпись под открытый ключ , то есть вычислить значения и , удовлетворяющих уравнению . Из этого следует возможность подделать цифровую подпись в базовой схеме ЭЦП, так как имеет случайное значение[3].

Атака на вычисление секретного ключа другого совладельца КЭЦП[править | править код]

Пусть -это ЭЦП, сформированная -м пользователем к документу, соответствующему хеш-функции (атаку производят пользователей). Тогда выполняется: Атакующие генерируют случайные значения и вычисляют . для . Затем вычисляются параметры и , удовлетворяющие уравнениям , где . Вводя обозначение . Имеем , где и . Это означает, что атакующие получили правильное значение коллективной подписи , в которой участвуют они и ещё один пользователь, обладающий открытым ключом . Согласно допущению из полученной коллективной подписи атакующие могут вычислить секретный ключ . Из выражения для и формулы легко получить: . Атакующие вычислили секретный ключ -го пользователя по его индивидуальной ЭЦП, сформированной в рамках базового алгоритма ЭЦП. Это доказывает предложение о том, что предложенный протокол КЭЦП не снижает стойкости базового алгоритма ЭЦП.[3]

Стандарт ЭЦП — ГОСТ Р 34.10−2001[править | править код]

Согласно стандарту ГОСТ Р 34.10−2001[5] накладываются ограничения на используемое простое число , простое число и точку . Простое число  — модуль эллиптической кривой (ЭК), которая задается в декартовой системе координат уравнением с коэффициентами и : ( — поле Галуа порядка ). Простое число  — порядок циклической подгруппы точек эллиптической кривой. Точка  — точка на эллиптической кривой с координатами , отличная от точки начала координат, но для которой точка совпадает с началом координат. Секретным ключом является довольно большое целое число . Открытым ключом является точка .

Формирование подписи[править | править код]

1. Генерируется случайное целое число . 
2. Вычисляются координаты точки ЭК  и определяется значение , где  — координата точки . 
3. Вычисляется значение , где . 
Подписью является пара чисел .[5]

Проверка подписи[править | править код]

Проверка подписи заключается в вычислении координат точки ЭК:

а также в определении значения и проверке выполнения равенства .[5]

Реализация протокола КЭЦП[править | править код]

Каждый участник группы формирует открытый ключ вида

, где - личный (секретный) ключ, .

Коллективным открытым ключом является сумма

Каждый участник группы вырабатывает число  — разовый случайный секретный ключ. При помощи это разового случайного ключа вычисляются координаты точки . Результат вычисления рассылается всем участникам группы для коллективного использования. Вычисляется сумма

Из полученной суммы вычисляется значение . Каждый участник группы вычисляет свою часть подписи:

[3]

Проверка КЭЦП[править | править код]

Вычисляют

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

Если , то КЭЦП совокупности m пользователей является подлинной, так как она могла быть сформирована только при участии каждого пользователя из этой группы, так как для формирования КЭЦП требуется наличие секретного ключа каждого из участников[3].

Реализация множественной подписи на основе RSA[править | править код]

Схема двойной подписи[править | править код]

Схема двойной цифровой подписи расширяет обычную схему RSA. В схеме двойной цифровой подписи генерируется не пара ключей (открытый/закрытый ключ), а тройка (два приватных и один публичный). По аналогии с обычной схемой RSA участники выбирают модуль вычисления  — произведение двух простых длинных чисел. Выбираются 2 случайных приватных ключа и в диапазоне от 1 до , которые будут взаимно простые с , где  — функция Эйлера. Выработка открытого ключа осуществляется по формуле . Величина будет публичным ключом. Для того, чтобы подписать величину , первый участник вычисляет . Результат вычисления передаётся на вход второму участнику группы. У второго участника появляется возможность увидеть, что он будет подписывать. Для этого он получает величину из величины . После того, как второй участник будет готов подписать величину , ему необходимо будет вычислить . Проверка подписи осуществляется с помощью .[6]

Расширение схемы двойной подписи на участников[править | править код]

Генерируются случайных приватных ключей . Публичный ключ будет вычисляться по формуле . Каждый -й участник подписывает сообщение M по формуле . Затем вычисляется величина . Проверка подписи осуществляется по формуле .[6]

Примечания[править | править код]

  1. 1 2 Молдовян Николай Андреевич, Еремеев Михаил Алексеевич, Галанов Алексей Игоревич. МНОЖЕСТВЕННАЯ ПОДПИСЬ: НОВЫЕ РЕШЕНИЯ НА ОСНОВЕ ПОНЯТИЯ КОЛЛЕКТИВНОГО ОТКРЫТОГО КЛЮЧА (рус.) // Журнал "Информационно-управляющие системы". — 2008. — Вып. 1.
  2. B. Schneier. Прикладная криптография (рус.) // John Wiley & Sons. — 1996. — С. 98. Архивировано 18 декабря 2018 года.
  3. 1 2 3 4 5 6 7 8 9 Николай Андреевич Молдовян, Андрей Алексеевич Костин, Лидия Вячеславовна Гортинская, Михаил Юрьевич Ананьев. РЕАЛИЗАЦИЯ ПРОТОКОЛА КОЛЛЕКТИВНОЙ ПОДПИСИ НА ОСНОВЕ СТАНДАРТОВ ЭЦП (рус.) // Журнал "Информационно-управляющие системы". — 2005.
  4. ГОСТ Р 34.10–94. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи (рус.) // Госстандарт Российской Федерации. — 1994. — 25 мая.
  5. 1 2 3 ГОСТ Р 34.10–2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи (рус.) // Госстандарт Российской Федерации. — 2001. — 12 сентября.
  6. 1 2 Mihir Bellare,Gregory Neven. Digital Multi Signature Schemes (англ.) // Springer-Verlag Berlin Heidelberg. — 2007. — С. 145–162. (недоступная ссылка)