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

Не следует путать с мультиподписью.

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

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

Введение

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

Концепция коллективного открытого ключа

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

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

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

Стандарт ЭЦП — ГОСТ Р 34.10−94

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

Алгоритм вычисления ЭЦП

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

Алгоритм проверки подлинности ЭЦП

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

Реализация протокола КЭЦП

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

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

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

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

Вычисляется

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

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

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

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

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

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

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

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

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

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

Возможность подделки КЭЦП

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

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

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

Стандарт ЭЦП — ГОСТ Р 34.10−2001

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

Формирование подписи

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

Проверка подписи

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

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

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

Реализация протокола КЭЦП

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

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

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

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

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

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

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

$S_{i}=\left(Rd_{i}+k_{i}e\right){\bmod {q}}$

Проверка КЭЦП

Вычисляют

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

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

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

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

Реализация множественной подписи на основе RSA

Схема двойной подписи

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

Расширение схемы двойной подписи на $n$ участников

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