Перегляд вихідного коду сторінки Множинний підпис

'''Множинний''' (колективний) '''підпис''' ({{Lang-en|Aggregate signature}}) — схема (протокол) реалізації [[Електронний цифровий підпис|електронного підпису]] (ЕЦП), що дозволяє декільком користувачам підписувати єдиний документ.

Колективний підпис надає можливість одночасного підписання електронного документа, оскільки формується в результаті єдиного неподільного перетворення і не може бути розділена на індивідуальні підпису; крім цього, її можна розширити, тобто вбудувати в неї додаткову підпис ще одного або декількох осіб<ref name="second">{{статья|автор=Молдовян Николай Андреевич, Еремеев Михаил Алексеевич, Галанов Алексей Игоревич|заглавие=МНОЖЕСТВЕННАЯ ПОДПИСЬ: НОВЫЕ РЕШЕНИЯ НА ОСНОВЕ ПОНЯТИЯ КОЛЛЕКТИВНОГО ОТКРЫТОГО КЛЮЧА|ссылка=http://cyberleninka.ru/article/n/mnozhestvennaya-podpis-novye-resheniya-na-osnove-ponyatiya-kollektivnogo-otkrytogo-klyucha|язык=Русский|издание=Журнал "Информационно-управляющие системы"|тип=|год=2008|выпуск=1|номер=|страницы=|doi=|issn=}}</ref>.

== Введення ==
Термін «колективний підпис» співзвучний з терміном «<nowiki/>[[груповий підпис]]<nowiki/>», однак ці поняття різні. У протоколі групової ЕЦП вирішується завдання забезпечення можливості будь-якому користувачеві з деякої групи сформувати підпис від імені всієї групи. У протоколі групової ЕЦП також регламентується наявність конкретних осіб, які можуть визначати список людей, які сформували підпис (тим самим останні мають гіпотетичну можливість підписатися за будь-якого з членів групи). У разі колективної роботи з електронними документами необхідно мати можливість їх підписи багатьма користувачами<ref name="eng_second">{{статья|автор=B. Schneier|заглавие=Прикладная криптография|ссылка=http://htrd.su/wiki/_media/zhurnal/2012/03/23/todo_prikladnaja_kriptografija/cryptoshn.pdf|язык=Русский|издание=John Wiley & Sons|тип=|год=1996|месяц=|число=|том=|номер=|страницы=98|doi=|issn=|archiveurl=https://web.archive.org/web/20181218010928/https://htrd.su/wiki/_media/zhurnal/2012/03/23/todo_prikladnaja_kriptografija/cryptoshn.pdf|archivedate=18 грудня 2018}}</ref>. Варіант схеми з генерацією набору індивідуальних користувачів ЕЦП, що підписують один електронний документ, володіє кількома вираженими недоліками — лінійним збільшенням розміру колективної ЕЦП (КЭЦП) із збільшенням числа підписантів, а також необхідністю додаткових перевірок цілісності і повноти колективної цифрового підпису для виключення можливості підміни кількості та поіменного складу учасників, що підписали документ.

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

КЕЦП виробляється у відповідності з перерахованими вимогами за допомогою алгоритмів, стабільність яких забезпечується за рахунок наступних обчислювально-важких завдань: [[Дискретний логарифм|дискретне логарифмування в мультиплікативної групи великої простого порядку]], витяг коренів великий простий ступеня за великим простому модулю, [[Дискретне логарифмування на еліптичній кривій|дискретне логарифмування в групі точок еліптичної кривої]] спеціального виду.<ref name= first/>.

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

=== Стандарт ЕЦП — ГОСТ Р 34.10−94 ===
Згідно стандарту ГОСТ Р 34.10−94<ref name="Gost94">{{статья|автор=ГОСТ Р 34.10–94|заглавие=Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи|ссылка=http://docs.cntd.ru/document/1200004855|язык=Русский|издание=Госстандарт Российской Федерации|тип=|год=1994|месяц=05|число=25|том=|номер=|страницы=|doi=|issn=}}</ref> накладаються обмеження на просте число p в двійковоиму представленні яке використовується: <math> 510 \leq |p| \leq 512</math> біт або <math>1022 \leq |p| \leq1024</math> біт. Число <math>(p-1)</math><math>q</math> такий, що <math>2^{255} \leq q \leq 2^{256}</math> для <math>510 \leq |p| \leq 512</math> або <math>2^{511} \leq q \leq 2^{512}</math> для <math>1022 \leq |p| \leq 1024</math>. Для генерації і перевірки ЕЦП використовують число <math>\alpha\ne 1</math>, таке що <math>\alpha^q \bmod p = 1</math>, де <math>\alpha</math> — генератор підгрупи досить великого простого порядку <math>q</math>.

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

==== Алгоритм перевірки достовірності ЕЦП ====
 1. Повіряється виконання умов <math> r < q</math> і  <math> s < q</math>. Якщо умови не виконуються, то підпис не є дійсним. 
 2. Обчислюється значення 
 <math>R' = (\alpha^{S/H} y^{-R/H} \bmod p) \bmod q</math>,де <math>y</math> — відкритий ключ користувача, формування перевірочного підпису. 
 3. Порівнюються значення <math>R</math> і <math> R'</math>. Якщо <math>R = R'</math>, то підпис є дійсним

==== Реалізація протоколу КЕЦП ====
Кожен <math>i</math>-й користувач формує відкритий ключ виду
<math> y_i = \alpha^{z_i}\bmod p</math>, де <math>z_i</math> — особистий (секретний) ключ, <math>i</math> = <math>1</math>, <math>2</math>, … , <math>m</math>.

Колективним відкритим ключем є добуток
 <math> y = y_1 y_2 y_3 ... y_m \bmod p.</math> 
Кожен користувач вибирає випадковий секретний ключ <math>k_i</math> — число, яке використовується лише один раз.

Обчислюється
 <math>R_i = \left( \alpha ^{k_i} \bmod p \right) \bmod q</math> 
 <math>R = R_1 R_2 R_3 ... R_m \bmod q </math> 
 <math>R_i</math> є доступним для всіх учасників колективу, що виробляють КЕЦП 
Потім кожен з учасників колективу, що виробляють КЕЦП, по визначеній ним значенням <math>R_i</math> і результату <math>H</math> обчислює
 <math>S_i = k_i H + z_i R \bmod q</math> 
 <math>S_i</math> - частина підпису. 
Колективнмим підписом буде пара величин <math>(S,R)</math>,  де <math>S</math>— сума всіх <math>S_i</math> по модулю <math>q</math><ref name= first/>.

==== Перевірка колективного електронного цифрового підпису ====
Перевірка колективного підпису здійснюється за формулою:
 <math> R'=\left(\alpha^{S/H} y^{-R/H} \bmod p\right) \bmod q</math> 
Якщо <math>R = R'</math>, то КЕЦП сукупності <math>m</math> користувачів є справжньою, так як вона могла бути сформована тільки за участю кожного користувача з цієї групи, оскільки для її формування потрібно використання секретного ключа кожного з них. Зазначимо, що аутентифікація значень <math>R_i</math> здійснюється автоматично при перевірці достовірності колективної ЕЦП. Якщо порушник спробує підмінити будь-яке з цих значень або замінити на раніше використані значення, то факт втручання в протокол буде відразу виявлено при перевірці достовірності [[Електронний цифровий підпис|ЕЦП]], тобто буде отримано <math>R' \ne R</math>. Очевидно, що розмір КЕЦП не залежить від <math>m</math><ref name= first/>.

==== Доказ коректності запропонованого алгоритму КЕЦП ====
В рівнянні <math>R = \left(\alpha^{S/ H} y^{-R/H} \bmod p\right) \bmod q </math> підставляємо отриману підпис - пару (R,S), де R — добуток R<sub>i</sub> по модулю q, S — сумма S<sub>i</sub> по модулю q:
Переконуємося, що воно виконується:
<math>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 = </math>
<math> \left(\prod_{i=1}^{m} \alpha^{\displaystyle S_i / H}\prod_{i=1}^{m} y_i^{\displaystyle -R / H}\bmod p\right) \bmod q = </math>
<math> \left[\prod_{i=1}^{m} \left(\alpha^{\displaystyle S_i / H}\alpha^{\displaystyle -z_iR / H} \bmod p\right)\right] \bmod q = </math>
<math> \left[\prod_{i=1}^{m} \left(\alpha^{\displaystyle (k_i - z_iR) / H}\alpha^{\displaystyle z_iR / H}\bmod p\right)\right] \bmod q = </math>
<math> \left(\prod_{i=1}^{m}\alpha^{\displaystyle k_i} \bmod p \right) \bmod q = </math>
<math> \left[\prod_{i=1}^{m} \left(\alpha^{\displaystyle k_i}\bmod p\right)\bmod q \right] \bmod q = </math>
<math> \left(\prod_{i=1}^{m}{\displaystyle R_i}\right) \bmod q </math><ref name="first">{{статья|автор=Николай Андреевич Молдовян, Андрей Алексеевич Костин, Лидия Вячеславовна Гортинская, Михаил Юрьевич Ананьев|заглавие=РЕАЛИЗАЦИЯ ПРОТОКОЛА КОЛЛЕКТИВНОЙ ПОДПИСИ НА ОСНОВЕ СТАНДАРТОВ ЭЦП|ссылка=http://pnzzi.kpi.ua/15/15_p82.pdf|язык=Русский|издание=Журнал "Информационно-управляющие системы"|тип=|год=2005|месяц=|число=|том=|номер=|страницы=|doi=|issn=|archivedate=2016-11-21|archiveurl=https://web.archive.org/web/20161121170420/http://pnzzi.kpi.ua/15/15_p82.pdf}}</ref>
Розглянемо формальний доказ стійкості протоколу КЕЦП при використанні перевірочного рівняння

<math>R = \left(\alpha^{S/ H} y^{-R/H} \bmod p\right) \bmod q </math>, регламентується стандартом ЕЦП ГОСТ Р 34.10-94.

==== Можливість підробки КЕЦП ====
Очевидно, що для порушників складність підробки КЕЦП визначається складністю підробки індивідуального підпису окремого учасника групи. Можливості виникають у користувачів, які об'єднують свої зусилля, щоб сформувати КЕЦП, що відноситься до колективу, в якому крім них входить ще один або кілька інших користувачів, які про це не сповіщаються (доказ для обох випадків аналогічно).

'''Нехай m-1''' користувачів хочуть сформувати КЕЦП, перевіряється за колективним відкритого ключа <math> y=y'y_m \bmod p </math>, де <math> y'= \prod_{i=1}^{m-1} y_i \bmod p </math>, тобто <math>m-1</math> користувачів об'єднують свої зусилля, щоб сформувати пару чисел <math> \left( R,S \right) </math> таку, що <math> R =\left(\alpha^{S/ H} \left( y'y_m \right)^{-R/H} \bmod p\right) \bmod q </math>. Тобто вони можуть підробити підпис під відкритий ключ <math>y^{*}=y'y_m\bmod p </math>, тобто обчислити значення <math>R</math> і <math>S</math>, які задовольняють рівняння  <math> R =\left(\alpha^{S/ H} \left( y^{*} \right)^{-R/H} \bmod p\right) \bmod q </math>. З цього випливає можливість підробити цифровий підпис в базовій схемі ЕЦП, так як <math>y^{*}</math>.

==== Атака на обчислення секретного ключа іншого співвласника КЕЦП ====
Нехай <math> \left(R^{*},S^{*}\right) </math> - це ЕЦП, сформована <math>m</math>-м користувачем до документу, який відповідає хеш-функції <math>H</math> (атаку виконують <math>m-1</math> користувачів). Тоді виконується: <math> R^{*}=\left(\alpha^{S^{*}/ H} \left( y_m \right)^{-R^{*}/H} \bmod p\right) \bmod q </math><math>t_i</math> і обчислюють <math> R_i=\left(\alpha^{t_i}\bmod p\right)\bmod q</math>. для <math> i = 1,2, ... ,m-1</math>. Потім обчислюються параметри<math> R=\left( R^{*} \prod_{i=1}^{m-1} R_i \bmod p \right) \bmod q</math> и <math>S_i</math>, які задовільняють рівнянням <math> R_i=\left(\alpha^{S_i/ H} y_i ^{-R/H} \bmod p\right) \bmod q </math>, де <math>i=1,2, ... , m-1</math>. Вводячи позначення <math>y^{*} = y_m^{R ^{*} / R}\bmod p </math>.
Маємо <math> R=\left(\alpha^{S/ H} \left( Y\right)^{-R/H} \bmod p\right) \bmod q </math>, де <math> S = \left( S^{*} + \displaystyle \sum_{i=1}^{m-1} S_i \right) \bmod p </math> и <math>Y=\left(y^{*} \displaystyle \prod_{i=1}^{m-1} y_i\right) \bmod p </math>. Це означає, що атакуючі отримали правильне значення колективного підпису <math>\left(R,S\right)</math>, в якій беруть участь вони і ще один користувач, що володіє відкритим ключем <math>y^{*}=a^{k^{*}}\bmod p </math>. Згідно допущенню з отриманої колективного підпису атакуючі можуть обчислити секретний ключ <math>k^{*}</math>.З виразу для <math>y^{*}</math> і формули <math>y=\alpha^{k}\bmod p</math> легко отримати:
<math>k=RK^{*}/R^{*}\bmod q</math>.
Атакуючі вирахували секретний ключ <math>m</math>-го користувача за його індивідуальної ЕЦП, сформованої в рамках базового алгоритму ЕЦП. Це доводить пропозицію про те, що запропонований протокол КЕЦП не знижує стійкості базового алгоритму ЕЦП.

=== Стандарт ЕЦП — ГОСТ Р 34.10−2001 ===
Згідно стандарту ГОСТ Р 34.10−2001<ref name="Gost2001">{{статья|автор=ГОСТ Р 34.10–2001|заглавие=Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи|ссылка=http://www.e-nigma.ru/stat/gost/|язык=Русский|издание=Госстандарт Российской Федерации|тип=|год=2001|месяц=сентября|число=12|том=|номер=|страницы=|doi=|issn=}}</ref> накладаються обмеження на просте число p  яке використовується, просте число q и точку G. Просте число <math>p</math> — модуль [[Еліптична крива|еліптичної кривої]] (ЕК), яка задається в декартовій системі координат рівнянням <math>y^2 = x^3 + ax +b \bmod p</math> з коефіцієнтами <math>a</math> і <math>b</math>: <math>a,b</math> ∈ <math>GF_p</math> (<math>GF_p</math> — [[поле Галуа]] порядка <math>p</math>). Просте число <math>q</math> — порядок циклічної підгрупи точок еліптичної кривої. Точка <math>G</math> — точка на еліптичній кривій з координатами <math>(x_G,y_G)</math>, відмінна від точки початку координат, але для якої точка <math>qG</math> збігається з початком координат. Секретним ключем є досить велике ціле число <math>d</math>. Відкритим ключем є точка <math>Q = dG</math>.

==== Формування підпису ====
 1. Генерується випадкове ціле число <math>k, 0 < k < q</math>. 
 2. Обчислюються координати точки ЕК <math>C = kP</math> і визначається значення <math>R = x_C \bmod q</math>, де <math>x_C</math> — координата точки <math> C </math>. 
 3. Обчислюється значення <math>S = (Rd + ke) \bmod q</math>, де <math>e=H \bmod q</math>. 
 Підписом є пара чисел <math>(R, S)</math>.<ref name= Gost2001/>

==== Перевірка підпису ====
Перевірка підпису полягає у обчисленні координат точки ЕК:

: <math>C = \left(\left(Se^{-1}\right) \bmod q\right)G + \left(\left(q - R\right)e^{-1} \bmod q\right)Q </math> 

а також у визначенні значення <math>R' = x_C \bmod q</math> та перевірці виконання рівності <math>R' = R </math>.<ref name= Gost2001/>

==== Реалізація протоколу КЕЦП ====
Кожен учасник групи формує відкритий ключ виду

:<math>Q = d_i G</math>, де <math>d_i</math> - особистий (секретний) ключ, <math>i = 1,2, ... ,m</math>. 

Колективним відкритим ключем є сума

: <math>Q = Q_1 + Q_2 + ... + Q_m</math> 

Кожен учасник групи виробляє число  <math>k_i</math> — разовий випадковий секретний ключ. За допомогою це разового випадкового ключа обчислюються координати точки <math>C_i = k_i G</math>. Результат обчислення розсилається всім учасникам групи для колективного використання.
Обчислюється сума

: <math>C = C_1 + C_2 + ... + C_m</math> 

З одержаної суми обчислюється значення <math>R</math>.
Кожен учасник групи обчислює свою частину підписи:

: <math> S_i = \left( Rd_i + k_ie\right) \bmod q </math> <ref name= first/>

==== Перевірка КЕЦП ====
Обчислюють
: <math>C' = \left(\left(Se^{-1}\right) \bmod q\right)G + \left(\left(q - R\right)e^{-1} \bmod q\right)Q </math> 
По отриманому результату обчислюється

: <math>R' = x_C \bmod q </math> 

Якщо <math>R' = R</math>, то КЭЦП сукупності m користувачів є справжньою, так як вона могла бути сформована тільки за участю кожного користувача з цієї групи, так як для формування КЭЦП потрібна наявність секретного ключа кожного з учасників.

== Реалізація множинного підпису на основі RSA ==

=== Схема подвійного підпису ===
Схема подвійний цифрового підпису розширює звичайну схему [[RSA]]. У схемі подвійний цифрового підпису генерується не пара ключів (відкритий / закритий ключ), а трійка (два приватних і один публічний). За аналогією зі звичайною схемою RSA учасники вибирають модуль обчислення <math>n</math> — добуток двох простих довгих чисел. Вибираються 2 випадкових приватних ключа <math>r</math> і <math>s</math> в діапазоні від 1 до <math>n</math>, кякі будуть взаємно прості з <math>\varphi(n)</math>, де <math>\varphi(n)</math> — [[Функція Ейлера|функция Ейлера]].Вироблення відкритого ключа здійснюється за формулою <math> r*s*t = 1 \bmod \varphi(n) </math>. Величина <math>t</math>буде публічним ключем. Для того, щоб підписати величину <math>C</math>, перший учасник обчислює<math>S_1 = C^{r} \bmod n</math>. Результат обчислення передається на вхід другого учасника групи. У другого учасника з'являється можливість побачити, що він буде підписувати. Для цього він отримує величину <math>C</math> з величини <math>S_1</math><math>C</math>,йому необхідно буде обчислити
<math> S_2 = S_1^{s}\bmod n</math>.
Перевірка підпису здійснюється за допомогою
<math> C = S_2 ^{t}\bmod n</math>.<ref name="eng_first">{{Стаття|автор=Mihir Bellare,Gregory Neven|Автор=Mihir Bellare,Gregory Neven}}</ref>

=== Розширення схеми подвійного підпису на <math>n</math> учасників ===
Генеруються <math>n</math><math>k_1,k_2,...,k_n</math>. Публічний ключ буде обчислюватися по формулі<math>\left( k_1 + k_2 + ... + k_n \right) * t = 1 \bmod \varphi(n) </math>.
Кожний <math>i</math>-й учасник підписує повідомлення ''M'' по формулі <math>S_i = M_ki\bmod n</math>. Потім обчислюється величина <math>S = S_1 * S_2 * S_3 * ... * S_n\bmod n</math>.
Перевірка підпису здійснюється за формулою<math>S^{t} \bmod n = \left( S_1 * S_2 * S_3 * ... * S_n\right) ^{t}\bmod n</math>
<math> = M ^{\left(k_1 + k_2 + k_3 + ... + k_n\right) * t}\bmod n = M</math>.

== Примітки ==
{{reflist|2}}

{{Computer-security-stub}}
{{Мало джерел|дата=квітень 2018}}<!-- слід доповнити інформацією про інші стандарти й протоколи -->
{{ВП-портали|Програмування|Інформаційні технології}}

[[Категорія:Автентифікація]]
[[Категорія:Криптографія]]