Множинний підпис

Множинний (колективний) підпис (англ. Aggregate signature) — схема (протокол) реалізації електронного підпису (ЕЦП), що дозволяє декільком користувачам підписувати єдиний документ.

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

Введення

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

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

На основі відкритих ключів учасників виробляється колективний відкритий ключ, що дозволяє виробити і перевірити справжність колективної електронного цифрового підпису. На колективний відкритий ключ накладається ряд обмежень за розміром, цілісності, незалежності від користувачів, одночасності генерації колективного відкритого ключа і нерозривності. Іншими словами — з КЕЦП не можна обчислити валідність КЕЦП для будь-якого іншого набору учасників з безлічі поточних, КЕЦП не прив'язана до складу учасників — будь-які користувачі можуть об'єднуватися в групи і виробити свою КЕЦП. Колективний відкритий ключ — функція відкритих ключів користувачів — є базисом, на якому будується весь протокол колективної підпису.

КЕЦП виробляється у відповідності з перерахованими вимогами за допомогою алгоритмів, стабільність яких забезпечується за рахунок наступних обчислювально-важких завдань: дискретне логарифмування в мультиплікативної групи великої простого порядку, витяг коренів великий простий ступеня за великим простому модулю, дискретне логарифмування в групі точок еліптичної кривої спеціального виду..

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

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

Згідно стандарту ГОСТ Р 34.10−94 накладаються обмеження на просте число 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$.