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

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

Нехай ${\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}$-го користувача за його індивідуальної ЕЦП, сформованої в рамках базового алгоритму ЕЦП. Це доводить пропозицію про те, що запропонований протокол КЕЦП не знижує стійкості базового алгоритму ЕЦП.

Згідно стандарту ГОСТ Р 34.10−2001[5] накладаються обмеження на просте число p  яке використовується, просте число q и точку 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 користувачів є справжньою, так як вона могла бути сформована тільки за участю кожного користувача з цієї групи, так як для формування КЭЦП потрібна наявність секретного ключа кожного з учасників.

Схема подвійний цифрового підпису розширює звичайну схему 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}$.