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

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

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

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

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

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

Согласно стандарту ГОСТ Р 34.10−94^[4] накладываются ограничения на используемое простое число p. Разрядность простого числа p в двоичном представлении: ${\displaystyle 510\leq |p|\leq 512}$ бит либо ${\displaystyle 1022\leq |p|\leq 1024}$ бит. Число ${\displaystyle (p-1)}$ должно содержать большой простой делитель ${\displaystyle q}$ такой, что ${\displaystyle 2^{255}\leq q\leq 2^{256}}$ для ${\displaystyle 510\leq |p|\leq 512}$ либо ${\displaystyle 2^{511}\leq q\leq 2^{512}}$ для ${\displaystyle 1022\leq |p|\leq 1024}$. Для генерации и проверки ЭЦП используют число ${\displaystyle \alpha \neq 1}$, такое что ${\displaystyle \alpha ^{q}{\bmod {p}}=1}$, где ${\displaystyle \alpha }$ — генератор подгруппы достаточно большого простого порядка ${\displaystyle q}$.

1. Генерируется случайное число ${\displaystyle k,1<k<q}$. 
2. Вычисляется значение ${\displaystyle R=(\alpha ^{k}{\bmod {p}}){\bmod {q}}}$, являющееся первой частью подписи. 
3. По ГОСТ Р 34.11–94 вычисляется хеш-функция ${\displaystyle H}$ от подписываемого сообщения. 
4. Вычисляется вторая часть подписи: ${\displaystyle S=kH+zR{\bmod {q}}}$, где ${\displaystyle z}$ — секретный ключ. Если 
   ${\displaystyle S=0}$, процедура генерации подписи повторяется.

1. Поверяется выполнение условий ${\displaystyle r<q}$ и ${\displaystyle s<q}$. Если условия не выполняются, то подпись не является действительной. 
2. Вычисляется значение 
${\displaystyle R'=(\alpha ^{S/H}y^{-R/H}{\bmod {p}}){\bmod {q}}}$,где ${\displaystyle y}$ — открытый ключ пользователя, сформировавшего проверяемую подпись. 
3. Сравниваются значения ${\displaystyle R}$ и ${\displaystyle R'}$. Если ${\displaystyle R=R'}$, то подпись является действительной

Каждый ${\displaystyle i}$-й пользователь формирует открытый ключ вида ${\displaystyle y_{i}=\alpha ^{z_{i}}{\bmod {p}}}$, где ${\displaystyle z_{i}}$ — личный (секретный) ключ, ${\displaystyle i}$ = ${\displaystyle 1}$, ${\displaystyle 2}$, … , ${\displaystyle m}$.

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

${\displaystyle y=y_{1}y_{2}y_{3}...y_{m}{\bmod {p}}.}$ 

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

Вычисляется

${\displaystyle R_{i}=\left(\alpha ^{k_{i}}{\bmod {p}}\right){\bmod {q}}}$ 
${\displaystyle R=R_{1}R_{2}R_{3}...R_{m}{\bmod {q}}}$ 
${\displaystyle R_{i}}$ является доступным для всех участников коллектива, вырабатывающих КЭЦП 

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

${\displaystyle S_{i}=k_{i}H+z_{i}R{\bmod {q}}}$ 
${\displaystyle S_{i}}$ - часть подписи. 

Коллективной подписью будет пара величин ${\displaystyle (S,R)}$, где ${\displaystyle S}$ — сумма всех ${\displaystyle S_{i}}$ по модулю ${\displaystyle q}$^[3].

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

${\displaystyle R'=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}}$ 

Если ${\displaystyle R=R'}$, то КЭЦП совокупности ${\displaystyle m}$ пользователей является подлинной, так как она могла быть сформирована только при участии каждого пользователя из этой группы, поскольку для её формирования требуется использование секретного ключа каждого из них. Отметим, что аутентификация значений ${\displaystyle R_{i}}$ осуществляется автоматически при проверке подлинности коллективной ЭЦП. Если нарушитель попытается подменить какое-либо из этих значений или заменить на ранее использованные значения, то факт вмешательства в протокол будет сразу же выявлен при проверке подлинности ЭЦП, то есть будет получено ${\displaystyle R'\neq R}$. Очевидно, что размер КЭЦП не зависит от ${\displaystyle m}$^[3].

В уравнение ${\displaystyle R=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}}$ подставляем полученную подпись — пару (R,S), где R — произведение R_i по модулю q, S — сумма S_i по модулю q: Убеждаемся, что оно выполняется: ${\displaystyle R=\left[\alpha ^{\displaystyle \sum _{i=1}^{m}S_{i}/H}\left(\prod _{i=1}^{m}y_{i}\right)^{-R/H}{\bmod {p}}\right]{\bmod {q}}=}$${\displaystyle \left(\prod _{i=1}^{m}\alpha ^{\displaystyle S_{i}/H}\prod _{i=1}^{m}y_{i}^{\displaystyle -R/H}{\bmod {p}}\right){\bmod {q}}=}$${\displaystyle \left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle S_{i}/H}\alpha ^{\displaystyle -z_{i}R/H}{\bmod {p}}\right)\right]{\bmod {q}}=}$${\displaystyle \left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle (k_{i}-z_{i}R)/H}\alpha ^{\displaystyle z_{i}R/H}{\bmod {p}}\right)\right]{\bmod {q}}=}$${\displaystyle \left(\prod _{i=1}^{m}\alpha ^{\displaystyle k_{i}}{\bmod {p}}\right){\bmod {q}}=}$${\displaystyle \left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle k_{i}}{\bmod {p}}\right){\bmod {q}}\right]{\bmod {q}}=}$${\displaystyle \left(\prod _{i=1}^{m}{\displaystyle R_{i}}\right){\bmod {q}}}$^[3] Рассмотрим формальное доказательство стойкости протокола КЭЦП при использовании проверочного уравнения ${\displaystyle R=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}}$, регламентируемого стандартом ЭЦП ГОСТ Р 34.10-94.

Очевидно, что для нарушителей сложность подделки КЭЦП определяется сложностью подделки индивидуальной подписи отдельного участника группы. Возможности возникают у пользователей, объединяющих свои усилия, чтобы сформировать КЭЦП, относящееся к коллективу, в котором кроме них входит ещё один или несколько других пользователей, которые об этом не оповещаются (доказательство для обоих случаев аналогично). Пусть m-1 пользователей хотят сформировать КЭЦП, проверяемую по коллективному открытому ключу ${\displaystyle y=y'y_{m}{\bmod {p}}}$, где ${\displaystyle y'=\prod _{i=1}^{m-1}y_{i}{\bmod {p}}}$, то есть ${\displaystyle m-1}$ пользователей объединяют свои усилия, чтобы сформировать пару чисел ${\displaystyle \left(R,S\right)}$ такую, что ${\displaystyle R=\left(\alpha ^{S/H}\left(y'y_{m}\right)^{-R/H}{\bmod {p}}\right){\bmod {q}}}$. То есть они могут подделать подпись под открытый ключ ${\displaystyle y^{*}=y'y_{m}{\bmod {p}}}$, то есть вычислить значения ${\displaystyle R}$ и ${\displaystyle S}$, удовлетворяющих уравнению ${\displaystyle R=\left(\alpha ^{S/H}\left(y^{*}\right)^{-R/H}{\bmod {p}}\right){\bmod {q}}}$. Из этого следует возможность подделать цифровую подпись в базовой схеме ЭЦП, так как ${\displaystyle y^{*}}$ имеет случайное значение^[3].

Пусть ${\displaystyle \left(R^{*},S^{*}\right)}$ -это ЭЦП, сформированная ${\displaystyle m}$-м пользователем к документу, соответствующему хеш-функции ${\displaystyle H}$ (атаку производят ${\displaystyle m-1}$ пользователей). Тогда выполняется: ${\displaystyle R^{*}=\left(\alpha ^{S^{*}/H}\left(y_{m}\right)^{-R^{*}/H}{\bmod {p}}\right){\bmod {q}}}$ Атакующие генерируют случайные значения ${\displaystyle t_{i}}$ и вычисляют ${\displaystyle R_{i}=\left(\alpha ^{t_{i}}{\bmod {p}}\right){\bmod {q}}}$. для ${\displaystyle i=1,2,...,m-1}$. Затем вычисляются параметры ${\displaystyle R=\left(R^{*}\prod _{i=1}^{m-1}R_{i}{\bmod {p}}\right){\bmod {q}}}$ и ${\displaystyle S_{i}}$, удовлетворяющие уравнениям ${\displaystyle R_{i}=\left(\alpha ^{S_{i}/H}y_{i}^{-R/H}{\bmod {p}}\right){\bmod {q}}}$, где ${\displaystyle i=1,2,...,m-1}$. Вводя обозначение ${\displaystyle y^{*}=y_{m}^{R^{*}/R}{\bmod {p}}}$. Имеем ${\displaystyle R=\left(\alpha ^{S/H}\left(Y\right)^{-R/H}{\bmod {p}}\right){\bmod {q}}}$, где ${\displaystyle S=\left(S^{*}+\displaystyle \sum _{i=1}^{m-1}S_{i}\right){\bmod {p}}}$ и ${\displaystyle Y=\left(y^{*}\displaystyle \prod _{i=1}^{m-1}y_{i}\right){\bmod {p}}}$. Это означает, что атакующие получили правильное значение коллективной подписи ${\displaystyle \left(R,S\right)}$, в которой участвуют они и ещё один пользователь, обладающий открытым ключом ${\displaystyle y^{*}=a^{k^{*}}{\bmod {p}}}$. Согласно допущению из полученной коллективной подписи атакующие могут вычислить секретный ключ ${\displaystyle k^{*}}$. Из выражения для ${\displaystyle y^{*}}$ и формулы ${\displaystyle y=\alpha ^{k}{\bmod {p}}}$ легко получить: ${\displaystyle k=RK^{*}/R^{*}{\bmod {q}}}$. Атакующие вычислили секретный ключ ${\displaystyle m}$-го пользователя по его индивидуальной ЭЦП, сформированной в рамках базового алгоритма ЭЦП. Это доказывает предложение о том, что предложенный протокол КЭЦП не снижает стойкости базового алгоритма ЭЦП.^[3]

Согласно стандарту ГОСТ Р 34.10−2001^[5] накладываются ограничения на используемое простое число ${\displaystyle p}$, простое число ${\displaystyle q}$ и точку ${\displaystyle G}$. Простое число ${\displaystyle p}$ — модуль эллиптической кривой (ЭК), которая задается в декартовой системе координат уравнением ${\displaystyle y^{2}=x^{3}+ax+b{\bmod {p}}}$ с коэффициентами ${\displaystyle a}$ и ${\displaystyle b}$: ${\displaystyle a,b}$ ∈ ${\displaystyle GF_{p}}$ (${\displaystyle GF_{p}}$ — поле Галуа порядка ${\displaystyle p}$). Простое число ${\displaystyle q}$ — порядок циклической подгруппы точек эллиптической кривой. Точка ${\displaystyle G}$ — точка на эллиптической кривой с координатами ${\displaystyle (x_{G},y_{G})}$, отличная от точки начала координат, но для которой точка ${\displaystyle qG}$ совпадает с началом координат. Секретным ключом является довольно большое целое число ${\displaystyle d}$. Открытым ключом является точка ${\displaystyle Q=dG}$.

1. Генерируется случайное целое число ${\displaystyle k,0<k<q}$. 
2. Вычисляются координаты точки ЭК ${\displaystyle C=kP}$ и определяется значение ${\displaystyle R=x_{C}{\bmod {q}}}$, где ${\displaystyle x_{C}}$ — координата точки ${\displaystyle C}$. 
3. Вычисляется значение ${\displaystyle S=(Rd+ke){\bmod {q}}}$, где ${\displaystyle e=H{\bmod {q}}}$. 
Подписью является пара чисел ${\displaystyle (R,S)}$.[5]

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

${\displaystyle C=\left(\left(Se^{-1}\right){\bmod {q}}\right)G+\left(\left(q-R\right)e^{-1}{\bmod {q}}\right)Q}$

а также в определении значения ${\displaystyle R'=x_{C}{\bmod {q}}}$ и проверке выполнения равенства ${\displaystyle R'=R}$.^[5]

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

${\displaystyle Q=d_{i}G}$, где ${\displaystyle d_{i}}$ - личный (секретный) ключ, ${\displaystyle i=1,2,...,m}$.

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

${\displaystyle Q=Q_{1}+Q_{2}+...+Q_{m}}$

Каждый участник группы вырабатывает число ${\displaystyle k_{i}}$ — разовый случайный секретный ключ. При помощи это разового случайного ключа вычисляются координаты точки ${\displaystyle C_{i}=k_{i}G}$. Результат вычисления рассылается всем участникам группы для коллективного использования. Вычисляется сумма

${\displaystyle C=C_{1}+C_{2}+...+C_{m}}$

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

${\displaystyle S_{i}=\left(Rd_{i}+k_{i}e\right){\bmod {q}}}$ ^[3]

Вычисляют

${\displaystyle C'=\left(\left(Se^{-1}\right){\bmod {q}}\right)G+\left(\left(q-R\right)e^{-1}{\bmod {q}}\right)Q}$

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

${\displaystyle R'=x_{C'}{\bmod {q}}}$

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

Схема двойной цифровой подписи расширяет обычную схему RSA. В схеме двойной цифровой подписи генерируется не пара ключей (открытый/закрытый ключ), а тройка (два приватных и один публичный). По аналогии с обычной схемой RSA участники выбирают модуль вычисления ${\displaystyle n}$ — произведение двух простых длинных чисел. Выбираются 2 случайных приватных ключа ${\displaystyle r}$ и ${\displaystyle s}$ в диапазоне от 1 до ${\displaystyle n}$, которые будут взаимно простые с ${\displaystyle \varphi (n)}$, где ${\displaystyle \varphi (n)}$ — функция Эйлера. Выработка открытого ключа осуществляется по формуле ${\displaystyle r*s*t=1{\bmod {\varphi }}(n)}$. Величина ${\displaystyle t}$ будет публичным ключом. Для того, чтобы подписать величину ${\displaystyle C}$, первый участник вычисляет ${\displaystyle S_{1}=C^{r}{\bmod {n}}}$. Результат вычисления передаётся на вход второму участнику группы. У второго участника появляется возможность увидеть, что он будет подписывать. Для этого он получает величину ${\displaystyle C}$ из величины ${\displaystyle S_{1}}$. После того, как второй участник будет готов подписать величину ${\displaystyle C}$, ему необходимо будет вычислить ${\displaystyle S_{2}=S_{1}^{s}{\bmod {n}}}$. Проверка подписи осуществляется с помощью ${\displaystyle C=S_{2}^{t}{\bmod {n}}}$.^[6]

Генерируются ${\displaystyle n}$ случайных приватных ключей ${\displaystyle k_{1},k_{2},...,k_{n}}$. Публичный ключ будет вычисляться по формуле ${\displaystyle \left(k_{1}+k_{2}+...+k_{n}\right)*t=1{\bmod {\varphi }}(n)}$. Каждый ${\displaystyle i}$-й участник подписывает сообщение M по формуле ${\displaystyle S_{i}=M_{k}i{\bmod {n}}}$. Затем вычисляется величина ${\displaystyle S=S_{1}*S_{2}*S_{3}*...*S_{n}{\bmod {n}}}$. Проверка подписи осуществляется по формуле ${\displaystyle S^{t}{\bmod {n}}=\left(S_{1}*S_{2}*S_{3}*...*S_{n}\right)^{t}{\bmod {n}}}$${\displaystyle =M^{\left(k_{1}+k_{2}+k_{3}+...+k_{n}\right)*t}{\bmod {n}}=M}$.^[6]