Множинний (колективний) підпис (англ. Aggregate signature) — схема (протокол) реалізації електронного підпису (ЕЦП), що дозволяє декільком користувачам підписувати єдиний документ.
Колективний підпис надає можливість одночасного підписання електронного документа, оскільки формується в результаті єдиного неподільного перетворення і не може бути розділена на індивідуальні підпису; крім цього, її можна розширити, тобто вбудувати в неї додаткову підпис ще одного або декількох осіб.
Введення
Термін «колективний підпис» співзвучний з терміном «груповий підпис», однак ці поняття різні. У протоколі групової ЕЦП вирішується завдання забезпечення можливості будь-якому користувачеві з деякої групи сформувати підпис від імені всієї групи. У протоколі групової ЕЦП також регламентується наявність конкретних осіб, які можуть визначати список людей, які сформували підпис (тим самим останні мають гіпотетичну можливість підписатися за будь-якого з членів групи). У разі колективної роботи з електронними документами необхідно мати можливість їх підписи багатьма користувачами. Варіант схеми з генерацією набору індивідуальних користувачів ЕЦП, що підписують один електронний документ, володіє кількома вираженими недоліками — лінійним збільшенням розміру колективної ЕЦП (КЭЦП) із збільшенням числа підписантів, а також необхідністю додаткових перевірок цілісності і повноти колективної цифрового підпису для виключення можливості підміни кількості та поіменного складу учасників, що підписали документ.
Концепція колективного відкритого ключа
На основі відкритих ключів учасників виробляється колективний відкритий ключ, що дозволяє виробити і перевірити справжність колективної електронного цифрового підпису. На колективний відкритий ключ накладається ряд обмежень за розміром, цілісності, незалежності від користувачів, одночасності генерації колективного відкритого ключа і нерозривності. Іншими словами — з КЕЦП не можна обчислити валідність КЕЦП для будь-якого іншого набору учасників з безлічі поточних, КЕЦП не прив'язана до складу учасників — будь-які користувачі можуть об'єднуватися в групи і виробити свою КЕЦП. Колективний відкритий ключ — функція відкритих ключів користувачів — є базисом, на якому будується весь протокол колективної підпису.
КЕЦП виробляється у відповідності з перерахованими вимогами за допомогою алгоритмів, стабільність яких забезпечується за рахунок наступних обчислювально-важких завдань: дискретне логарифмування в мультиплікативної групи великої простого порядку, витяг коренів великий простий ступеня за великим простому модулю, дискретне логарифмування в групі точок еліптичної кривої спеціального виду..
Реалізація протоколів на основі стандартів ЕЦП
Стандарт ЕЦП — ГОСТ Р 34.10−94
Згідно стандарту ГОСТ Р 34.10−94 накладаються обмеження на просте число p в двійковоиму представленні яке використовується: біт або біт. Число такий, що для або для . Для генерації і перевірки ЕЦП використовують число , таке що , де — генератор підгрупи досить великого простого порядку .
Алгоритм обчислення ЕЦП
1. Генерується випадкове число . 2. Обчислюється значення що є першою частиною підпису. 3. По ГОСТ Р 34.11–94 обчислюється хеш-функція від підписуваного повідомлення. 4. Обчислюється друга частина підпису: , де — секретний ключ. Якщо , процедура генерації підпису повторюється.
Алгоритм перевірки достовірності ЕЦП
1. Повіряється виконання умов і . Якщо умови не виконуються, то підпис не є дійсним. 2. Обчислюється значення ,де — відкритий ключ користувача, формування перевірочного підпису. 3. Порівнюються значення і . Якщо , то підпис є дійсним
Реалізація протоколу КЕЦП
Кожен -й користувач формує відкритий ключ виду , де — особистий (секретний) ключ, = , , … , .
Колективним відкритим ключем є добуток
Кожен користувач вибирає випадковий секретний ключ — число, яке використовується лише один раз.
Обчислюється
є доступним для всіх учасників колективу, що виробляють КЕЦП
Потім кожен з учасників колективу, що виробляють КЕЦП, по визначеній ним значенням і результату обчислює
- частина підпису.
Колективнмим підписом буде пара величин , де — сума всіх по модулю .
Перевірка колективного електронного цифрового підпису
Перевірка колективного підпису здійснюється за формулою:
Якщо , то КЕЦП сукупності користувачів є справжньою, так як вона могла бути сформована тільки за участю кожного користувача з цієї групи, оскільки для її формування потрібно використання секретного ключа кожного з них. Зазначимо, що аутентифікація значень здійснюється автоматично при перевірці достовірності колективної ЕЦП. Якщо порушник спробує підмінити будь-яке з цих значень або замінити на раніше використані значення, то факт втручання в протокол буде відразу виявлено при перевірці достовірності ЕЦП, тобто буде отримано . Очевидно, що розмір КЕЦП не залежить від .
Доказ коректності запропонованого алгоритму КЕЦП
В рівнянні підставляємо отриману підпис - пару (R,S), де R — добуток Ri по модулю q, S — сумма Si по модулю q: Переконуємося, що воно виконується: Розглянемо формальний доказ стійкості протоколу КЕЦП при використанні перевірочного рівняння
, регламентується стандартом ЕЦП ГОСТ Р 34.10-94.
Можливість підробки КЕЦП
Очевидно, що для порушників складність підробки КЕЦП визначається складністю підробки індивідуального підпису окремого учасника групи. Можливості виникають у користувачів, які об'єднують свої зусилля, щоб сформувати КЕЦП, що відноситься до колективу, в якому крім них входить ще один або кілька інших користувачів, які про це не сповіщаються (доказ для обох випадків аналогічно).
Нехай m-1 користувачів хочуть сформувати КЕЦП, перевіряється за колективним відкритого ключа , де , тобто користувачів об'єднують свої зусилля, щоб сформувати пару чисел таку, що . Тобто вони можуть підробити підпис під відкритий ключ , тобто обчислити значення і , які задовольняють рівняння . З цього випливає можливість підробити цифровий підпис в базовій схемі ЕЦП, так як .
Атака на обчислення секретного ключа іншого співвласника КЕЦП
Нехай - це ЕЦП, сформована -м користувачем до документу, який відповідає хеш-функції (атаку виконують користувачів). Тоді виконується: і обчислюють . для . Потім обчислюються параметри и , які задовільняють рівнянням , де . Вводячи позначення . Маємо , де и . Це означає, що атакуючі отримали правильне значення колективного підпису , в якій беруть участь вони і ще один користувач, що володіє відкритим ключем . Згідно допущенню з отриманої колективного підпису атакуючі можуть обчислити секретний ключ .З виразу для і формули легко отримати: . Атакуючі вирахували секретний ключ -го користувача за його індивідуальної ЕЦП, сформованої в рамках базового алгоритму ЕЦП. Це доводить пропозицію про те, що запропонований протокол КЕЦП не знижує стійкості базового алгоритму ЕЦП.
Стандарт ЕЦП — ГОСТ Р 34.10−2001
Згідно стандарту ГОСТ Р 34.10−2001 накладаються обмеження на просте число p яке використовується, просте число q и точку G. Просте число — модуль еліптичної кривої (ЕК), яка задається в декартовій системі координат рівнянням з коефіцієнтами і : ∈ ( — поле Галуа порядка ). Просте число — порядок циклічної підгрупи точок еліптичної кривої. Точка — точка на еліптичній кривій з координатами , відмінна від точки початку координат, але для якої точка збігається з початком координат. Секретним ключем є досить велике ціле число . Відкритим ключем є точка .
Формування підпису
1. Генерується випадкове ціле число . 2. Обчислюються координати точки ЕК і визначається значення , де — координата точки . 3. Обчислюється значення , де . Підписом є пара чисел .
Перевірка підпису
Перевірка підпису полягає у обчисленні координат точки ЕК:
а також у визначенні значення та перевірці виконання рівності .
Реалізація протоколу КЕЦП
Кожен учасник групи формує відкритий ключ виду
- , де - особистий (секретний) ключ, .
Колективним відкритим ключем є сума
Кожен учасник групи виробляє число — разовий випадковий секретний ключ. За допомогою це разового випадкового ключа обчислюються координати точки . Результат обчислення розсилається всім учасникам групи для колективного використання. Обчислюється сума
З одержаної суми обчислюється значення . Кожен учасник групи обчислює свою частину підписи:
Перевірка КЕЦП
Обчислюють
По отриманому результату обчислюється
Якщо , то КЭЦП сукупності m користувачів є справжньою, так як вона могла бути сформована тільки за участю кожного користувача з цієї групи, так як для формування КЭЦП потрібна наявність секретного ключа кожного з учасників.
Реалізація множинного підпису на основі RSA
Схема подвійного підпису
Схема подвійний цифрового підпису розширює звичайну схему RSA. У схемі подвійний цифрового підпису генерується не пара ключів (відкритий / закритий ключ), а трійка (два приватних і один публічний). За аналогією зі звичайною схемою RSA учасники вибирають модуль обчислення — добуток двох простих довгих чисел. Вибираються 2 випадкових приватних ключа і в діапазоні від 1 до , кякі будуть взаємно прості з , де — функция Ейлера.Вироблення відкритого ключа здійснюється за формулою . Величина буде публічним ключем. Для того, щоб підписати величину , перший учасник обчислює. Результат обчислення передається на вхід другого учасника групи. У другого учасника з'являється можливість побачити, що він буде підписувати. Для цього він отримує величину з величини ,йому необхідно буде обчислити . Перевірка підпису здійснюється за допомогою .
Розширення схеми подвійного підпису на учасників
Генеруються . Публічний ключ буде обчислюватися по формулі. Кожний -й учасник підписує повідомлення M по формулі . Потім обчислюється величина . Перевірка підпису здійснюється за формулою .
Примітки
- Молдовян Николай Андреевич, Еремеев Михаил Алексеевич, Галанов Алексей Игоревич. МНОЖЕСТВЕННАЯ ПОДПИСЬ: НОВЫЕ РЕШЕНИЯ НА ОСНОВЕ ПОНЯТИЯ КОЛЛЕКТИВНОГО ОТКРЫТОГО КЛЮЧА : ( )[] // Журнал "Информационно-управляющие системы". — 2008. — Вип. 1.
- B. Schneier. Прикладная криптография : [ 18 грудня 2018] : ( )[] // John Wiley & Sons. — 1996. — С. 98.
- Николай Андреевич Молдовян, Андрей Алексеевич Костин, Лидия Вячеславовна Гортинская, Михаил Юрьевич Ананьев. РЕАЛИЗАЦИЯ ПРОТОКОЛА КОЛЛЕКТИВНОЙ ПОДПИСИ НА ОСНОВЕ СТАНДАРТОВ ЭЦП : [ 21 листопада 2016] : ( )[] // Журнал "Информационно-управляющие системы". — 2005.
- ГОСТ Р 34.10–94. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи : ( )[] // Госстандарт Российской Федерации. — 1994. — 25 травня.
- ГОСТ Р 34.10–2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи : ( )[] // Госстандарт Российской Федерации. — 2001. — Помилка: неправильний час.
- Mihir Bellare,Gregory Neven. .
Це незавершена стаття з інформаційної безпеки. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття потребує додаткових для поліпшення її . (квітень 2018) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Mnozhinnij kolektivnij pidpis angl Aggregate signature shema protokol realizaciyi elektronnogo pidpisu ECP sho dozvolyaye dekilkom koristuvacham pidpisuvati yedinij dokument Kolektivnij pidpis nadaye mozhlivist odnochasnogo pidpisannya elektronnogo dokumenta oskilki formuyetsya v rezultati yedinogo nepodilnogo peretvorennya i ne mozhe buti rozdilena na individualni pidpisu krim cogo yiyi mozhna rozshiriti tobto vbuduvati v neyi dodatkovu pidpis she odnogo abo dekilkoh osib VvedennyaTermin kolektivnij pidpis spivzvuchnij z terminom grupovij pidpis odnak ci ponyattya rizni U protokoli grupovoyi ECP virishuyetsya zavdannya zabezpechennya mozhlivosti bud yakomu koristuvachevi z deyakoyi grupi sformuvati pidpis vid imeni vsiyeyi grupi U protokoli grupovoyi ECP takozh reglamentuyetsya nayavnist konkretnih osib yaki mozhut viznachati spisok lyudej yaki sformuvali pidpis tim samim ostanni mayut gipotetichnu mozhlivist pidpisatisya za bud yakogo z chleniv grupi U razi kolektivnoyi roboti z elektronnimi dokumentami neobhidno mati mozhlivist yih pidpisi bagatma koristuvachami Variant shemi z generaciyeyu naboru individualnih koristuvachiv ECP sho pidpisuyut odin elektronnij dokument volodiye kilkoma virazhenimi nedolikami linijnim zbilshennyam rozmiru kolektivnoyi ECP KECP iz zbilshennyam chisla pidpisantiv a takozh neobhidnistyu dodatkovih perevirok cilisnosti i povnoti kolektivnoyi cifrovogo pidpisu dlya viklyuchennya mozhlivosti pidmini kilkosti ta poimennogo skladu uchasnikiv sho pidpisali dokument Koncepciya kolektivnogo vidkritogo klyuchaNa osnovi vidkritih klyuchiv uchasnikiv viroblyayetsya kolektivnij vidkritij klyuch sho dozvolyaye virobiti i pereviriti spravzhnist kolektivnoyi elektronnogo cifrovogo pidpisu Na kolektivnij vidkritij klyuch nakladayetsya ryad obmezhen za rozmirom cilisnosti nezalezhnosti vid koristuvachiv odnochasnosti generaciyi kolektivnogo vidkritogo klyucha i nerozrivnosti Inshimi slovami z KECP ne mozhna obchisliti validnist KECP dlya bud yakogo inshogo naboru uchasnikiv z bezlichi potochnih KECP ne priv yazana do skladu uchasnikiv bud yaki koristuvachi mozhut ob yednuvatisya v grupi i virobiti svoyu KECP Kolektivnij vidkritij klyuch funkciya vidkritih klyuchiv koristuvachiv ye bazisom na yakomu buduyetsya ves protokol kolektivnoyi pidpisu KECP viroblyayetsya u vidpovidnosti z pererahovanimi vimogami za dopomogoyu algoritmiv stabilnist yakih zabezpechuyetsya za rahunok nastupnih obchislyuvalno vazhkih zavdan diskretne logarifmuvannya v multiplikativnoyi grupi velikoyi prostogo poryadku vityag koreniv velikij prostij stupenya za velikim prostomu modulyu diskretne logarifmuvannya v grupi tochok eliptichnoyi krivoyi specialnogo vidu Realizaciya protokoliv na osnovi standartiv ECPStandart ECP GOST R 34 10 94 Zgidno standartu GOST R 34 10 94 nakladayutsya obmezhennya na proste chislo p v dvijkovoimu predstavlenni yake vikoristovuyetsya 510 p 512 displaystyle 510 leq p leq 512 bit abo 1022 p 1024 displaystyle 1022 leq p leq 1024 bit Chislo p 1 displaystyle p 1 q displaystyle q takij sho 2255 q 2256 displaystyle 2 255 leq q leq 2 256 dlya 510 p 512 displaystyle 510 leq p leq 512 abo 2511 q 2512 displaystyle 2 511 leq q leq 2 512 dlya 1022 p 1024 displaystyle 1022 leq p leq 1024 Dlya generaciyi i perevirki ECP vikoristovuyut chislo a 1 displaystyle alpha neq 1 take sho aqmodp 1 displaystyle alpha q bmod p 1 de a displaystyle alpha generator pidgrupi dosit velikogo prostogo poryadku q displaystyle q Algoritm obchislennya ECP 1 Generuyetsya vipadkove chislo k 1 lt k lt q displaystyle k 1 lt k lt q 2 Obchislyuyetsya znachennya R akmodp modq displaystyle R alpha k bmod p bmod q sho ye pershoyu chastinoyu pidpisu 3 Po GOST R 34 11 94 obchislyuyetsya hesh funkciya H displaystyle H vid pidpisuvanogo povidomlennya 4 Obchislyuyetsya druga chastina pidpisu S kH zRmodq displaystyle S kH zR bmod q de z displaystyle z sekretnij klyuch Yaksho S 0 displaystyle S 0 procedura generaciyi pidpisu povtoryuyetsya Algoritm perevirki dostovirnosti ECP 1 Poviryayetsya vikonannya umov r lt q displaystyle r lt q i s lt q displaystyle s lt q Yaksho umovi ne vikonuyutsya to pidpis ne ye dijsnim 2 Obchislyuyetsya znachennya R aS Hy R Hmodp modq displaystyle R alpha S H y R H bmod p bmod q de y displaystyle y vidkritij klyuch koristuvacha formuvannya perevirochnogo pidpisu 3 Porivnyuyutsya znachennya R displaystyle R i R displaystyle R Yaksho R R displaystyle R R to pidpis ye dijsnim Realizaciya protokolu KECP Kozhen i displaystyle i j koristuvach formuye vidkritij klyuch vidu yi azimodp displaystyle y i alpha z i bmod p de zi displaystyle z i osobistij sekretnij klyuch i displaystyle i 1 displaystyle 1 2 displaystyle 2 m displaystyle m Kolektivnim vidkritim klyuchem ye dobutok y y1y2y3 ymmodp displaystyle y y 1 y 2 y 3 y m bmod p Kozhen koristuvach vibiraye vipadkovij sekretnij klyuch ki displaystyle k i chislo yake vikoristovuyetsya lishe odin raz Obchislyuyetsya Ri akimodp modq displaystyle R i left alpha k i bmod p right bmod q R R1R2R3 Rmmodq displaystyle R R 1 R 2 R 3 R m bmod q Ri displaystyle R i ye dostupnim dlya vsih uchasnikiv kolektivu sho viroblyayut KECP Potim kozhen z uchasnikiv kolektivu sho viroblyayut KECP po viznachenij nim znachennyam Ri displaystyle R i i rezultatu H displaystyle H obchislyuye Si kiH ziRmodq displaystyle S i k i H z i R bmod q Si displaystyle S i chastina pidpisu Kolektivnmim pidpisom bude para velichin S R displaystyle S R de S displaystyle S suma vsih Si displaystyle S i po modulyu q displaystyle q Perevirka kolektivnogo elektronnogo cifrovogo pidpisu Perevirka kolektivnogo pidpisu zdijsnyuyetsya za formuloyu R aS Hy R Hmodp modq displaystyle R left alpha S H y R H bmod p right bmod q Yaksho R R displaystyle R R to KECP sukupnosti m displaystyle m koristuvachiv ye spravzhnoyu tak yak vona mogla buti sformovana tilki za uchastyu kozhnogo koristuvacha z ciyeyi grupi oskilki dlya yiyi formuvannya potribno vikoristannya sekretnogo klyucha kozhnogo z nih Zaznachimo sho autentifikaciya znachen Ri displaystyle R i zdijsnyuyetsya avtomatichno pri perevirci dostovirnosti kolektivnoyi ECP Yaksho porushnik sprobuye pidminiti bud yake z cih znachen abo zaminiti na ranishe vikoristani znachennya to fakt vtruchannya v protokol bude vidrazu viyavleno pri perevirci dostovirnosti ECP tobto bude otrimano R R displaystyle R neq R Ochevidno sho rozmir KECP ne zalezhit vid m displaystyle m Dokaz korektnosti zaproponovanogo algoritmu KECP V rivnyanni R aS Hy R Hmodp modq displaystyle R left alpha S H y R H bmod p right bmod q pidstavlyayemo otrimanu pidpis paru R S de R dobutok Ri po modulyu q S summa Si po modulyu q Perekonuyemosya sho vono vikonuyetsya R a i 1mSi H i 1myi R Hmodp modq 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 i 1maSi H i 1myi R Hmodp modq 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 i 1m aSi Ha ziR Hmodp modq displaystyle left prod i 1 m left alpha displaystyle S i H alpha displaystyle z i R H bmod p right right bmod q i 1m a ki ziR HaziR Hmodp modq 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 i 1makimodp modq displaystyle left prod i 1 m alpha displaystyle k i bmod p right bmod q i 1m akimodp modq modq displaystyle left prod i 1 m left alpha displaystyle k i bmod p right bmod q right bmod q i 1mRi modq displaystyle left prod i 1 m displaystyle R i right bmod q Rozglyanemo formalnij dokaz stijkosti protokolu KECP pri vikoristanni perevirochnogo rivnyannya R aS Hy R Hmodp modq displaystyle R left alpha S H y R H bmod p right bmod q reglamentuyetsya standartom ECP GOST R 34 10 94 Mozhlivist pidrobki KECP Ochevidno sho dlya porushnikiv skladnist pidrobki KECP viznachayetsya skladnistyu pidrobki individualnogo pidpisu okremogo uchasnika grupi Mozhlivosti vinikayut u koristuvachiv yaki ob yednuyut svoyi zusillya shob sformuvati KECP sho vidnositsya do kolektivu v yakomu krim nih vhodit she odin abo kilka inshih koristuvachiv yaki pro ce ne spovishayutsya dokaz dlya oboh vipadkiv analogichno Nehaj m 1 koristuvachiv hochut sformuvati KECP pereviryayetsya za kolektivnim vidkritogo klyucha y y ymmodp displaystyle y y y m bmod p de y i 1m 1yimodp displaystyle y prod i 1 m 1 y i bmod p tobto m 1 displaystyle m 1 koristuvachiv ob yednuyut svoyi zusillya shob sformuvati paru chisel R S displaystyle left R S right taku sho R aS H y ym R Hmodp modq displaystyle R left alpha S H left y y m right R H bmod p right bmod q Tobto voni mozhut pidrobiti pidpis pid vidkritij klyuch y y ymmodp displaystyle y y y m bmod p tobto obchisliti znachennya R displaystyle R i S displaystyle S yaki zadovolnyayut rivnyannya R aS H y R Hmodp modq displaystyle R left alpha S H left y right R H bmod p right bmod q Z cogo viplivaye mozhlivist pidrobiti cifrovij pidpis v bazovij shemi ECP tak yak y displaystyle y Ataka na obchislennya sekretnogo klyucha inshogo spivvlasnika KECP Nehaj R S displaystyle left R S right ce ECP sformovana m displaystyle m m koristuvachem do dokumentu yakij vidpovidaye hesh funkciyi H displaystyle H ataku vikonuyut m 1 displaystyle m 1 koristuvachiv Todi vikonuyetsya R aS H ym R Hmodp modq displaystyle R left alpha S H left y m right R H bmod p right bmod q ti displaystyle t i i obchislyuyut Ri atimodp modq displaystyle R i left alpha t i bmod p right bmod q dlya i 1 2 m 1 displaystyle i 1 2 m 1 Potim obchislyuyutsya parametriR R i 1m 1Rimodp modq displaystyle R left R prod i 1 m 1 R i bmod p right bmod q i Si displaystyle S i yaki zadovilnyayut rivnyannyam Ri aSi Hyi R Hmodp modq displaystyle R i left alpha S i H y i R H bmod p right bmod q de i 1 2 m 1 displaystyle i 1 2 m 1 Vvodyachi poznachennya y ymR Rmodp displaystyle y y m R R bmod p Mayemo R aS H Y R Hmodp modq displaystyle R left alpha S H left Y right R H bmod p right bmod q de S S i 1m 1Si modp displaystyle S left S displaystyle sum i 1 m 1 S i right bmod p i Y y i 1m 1yi modp displaystyle Y left y displaystyle prod i 1 m 1 y i right bmod p Ce oznachaye sho atakuyuchi otrimali pravilne znachennya kolektivnogo pidpisu R S displaystyle left R S right v yakij berut uchast voni i she odin koristuvach sho volodiye vidkritim klyuchem y ak modp displaystyle y a k bmod p Zgidno dopushennyu z otrimanoyi kolektivnogo pidpisu atakuyuchi mozhut obchisliti sekretnij klyuch k displaystyle k Z virazu dlya y displaystyle y i formuli y akmodp displaystyle y alpha k bmod p legko otrimati k RK R modq displaystyle k RK R bmod q Atakuyuchi virahuvali sekretnij klyuch m displaystyle m go koristuvacha za jogo individualnoyi ECP sformovanoyi v ramkah bazovogo algoritmu ECP Ce dovodit propoziciyu pro te sho zaproponovanij protokol KECP ne znizhuye stijkosti bazovogo algoritmu ECP Standart ECP GOST R 34 10 2001 Zgidno standartu GOST R 34 10 2001 nakladayutsya obmezhennya na proste chislo p yake vikoristovuyetsya proste chislo q i tochku G Proste chislo p displaystyle p modul eliptichnoyi krivoyi EK yaka zadayetsya v dekartovij sistemi koordinat rivnyannyam y2 x3 ax bmodp displaystyle y 2 x 3 ax b bmod p z koeficiyentami a displaystyle a i b displaystyle b a b displaystyle a b GFp displaystyle GF p GFp displaystyle GF p pole Galua poryadka p displaystyle p Proste chislo q displaystyle q poryadok ciklichnoyi pidgrupi tochok eliptichnoyi krivoyi Tochka G displaystyle G tochka na eliptichnij krivij z koordinatami xG yG displaystyle x G y G vidminna vid tochki pochatku koordinat ale dlya yakoyi tochka qG displaystyle qG zbigayetsya z pochatkom koordinat Sekretnim klyuchem ye dosit velike cile chislo d displaystyle d Vidkritim klyuchem ye tochka Q dG displaystyle Q dG Formuvannya pidpisu 1 Generuyetsya vipadkove cile chislo k 0 lt k lt q displaystyle k 0 lt k lt q 2 Obchislyuyutsya koordinati tochki EK C kP displaystyle C kP i viznachayetsya znachennya R xCmodq displaystyle R x C bmod q de xC displaystyle x C koordinata tochki C displaystyle C 3 Obchislyuyetsya znachennya S Rd ke modq displaystyle S Rd ke bmod q de e Hmodq displaystyle e H bmod q Pidpisom ye para chisel R S displaystyle R S Perevirka pidpisu Perevirka pidpisu polyagaye u obchislenni koordinat tochki EK C Se 1 modq G q R e 1modq Q displaystyle C left left Se 1 right bmod q right G left left q R right e 1 bmod q right Q a takozh u viznachenni znachennya R xCmodq displaystyle R x C bmod q ta perevirci vikonannya rivnosti R R displaystyle R R Realizaciya protokolu KECP Kozhen uchasnik grupi formuye vidkritij klyuch vidu Q diG displaystyle Q d i G de di displaystyle d i osobistij sekretnij klyuch i 1 2 m displaystyle i 1 2 m Kolektivnim vidkritim klyuchem ye suma Q Q1 Q2 Qm displaystyle Q Q 1 Q 2 Q m Kozhen uchasnik grupi viroblyaye chislo ki displaystyle k i razovij vipadkovij sekretnij klyuch Za dopomogoyu ce razovogo vipadkovogo klyucha obchislyuyutsya koordinati tochki Ci kiG displaystyle C i k i G Rezultat obchislennya rozsilayetsya vsim uchasnikam grupi dlya kolektivnogo vikoristannya Obchislyuyetsya suma C C1 C2 Cm displaystyle C C 1 C 2 C m Z oderzhanoyi sumi obchislyuyetsya znachennya R displaystyle R Kozhen uchasnik grupi obchislyuye svoyu chastinu pidpisi Si Rdi kie modq displaystyle S i left Rd i k i e right bmod q Perevirka KECP Obchislyuyut C Se 1 modq G q R e 1modq Q displaystyle C left left Se 1 right bmod q right G left left q R right e 1 bmod q right Q Po otrimanomu rezultatu obchislyuyetsya R xCmodq displaystyle R x C bmod q Yaksho R R displaystyle R R to KECP sukupnosti m koristuvachiv ye spravzhnoyu tak yak vona mogla buti sformovana tilki za uchastyu kozhnogo koristuvacha z ciyeyi grupi tak yak dlya formuvannya KECP potribna nayavnist sekretnogo klyucha kozhnogo z uchasnikiv Realizaciya mnozhinnogo pidpisu na osnovi RSAShema podvijnogo pidpisu Shema podvijnij cifrovogo pidpisu rozshiryuye zvichajnu shemu RSA U shemi podvijnij cifrovogo pidpisu generuyetsya ne para klyuchiv vidkritij zakritij klyuch a trijka dva privatnih i odin publichnij Za analogiyeyu zi zvichajnoyu shemoyu RSA uchasniki vibirayut modul obchislennya n displaystyle n dobutok dvoh prostih dovgih chisel Vibirayutsya 2 vipadkovih privatnih klyucha r displaystyle r i s displaystyle s v diapazoni vid 1 do n displaystyle n kyaki budut vzayemno prosti z f n displaystyle varphi n de f n displaystyle varphi n funkciya Ejlera Viroblennya vidkritogo klyucha zdijsnyuyetsya za formuloyu r s t 1modf n displaystyle r s t 1 bmod varphi n Velichina t displaystyle t bude publichnim klyuchem Dlya togo shob pidpisati velichinu C displaystyle C pershij uchasnik obchislyuyeS1 Crmodn displaystyle S 1 C r bmod n Rezultat obchislennya peredayetsya na vhid drugogo uchasnika grupi U drugogo uchasnika z yavlyayetsya mozhlivist pobachiti sho vin bude pidpisuvati Dlya cogo vin otrimuye velichinu C displaystyle C z velichini S1 displaystyle S 1 C displaystyle C jomu neobhidno bude obchisliti S2 S1smodn displaystyle S 2 S 1 s bmod n Perevirka pidpisu zdijsnyuyetsya za dopomogoyu C S2tmodn displaystyle C S 2 t bmod n Rozshirennya shemi podvijnogo pidpisu na n displaystyle n uchasnikiv Generuyutsya n displaystyle n k1 k2 kn displaystyle k 1 k 2 k n Publichnij klyuch bude obchislyuvatisya po formuli k1 k2 kn t 1modf n displaystyle left k 1 k 2 k n right t 1 bmod varphi n Kozhnij i displaystyle i j uchasnik pidpisuye povidomlennya M po formuli Si Mkimodn displaystyle S i M k i bmod n Potim obchislyuyetsya velichina S S1 S2 S3 Snmodn displaystyle S S 1 S 2 S 3 S n bmod n Perevirka pidpisu zdijsnyuyetsya za formuloyuStmodn S1 S2 S3 Sn tmodn displaystyle S t bmod n left S 1 S 2 S 3 S n right t bmod n M k1 k2 k3 kn tmodn M displaystyle M left k 1 k 2 k 3 k n right t bmod n M PrimitkiMoldovyan Nikolaj Andreevich Eremeev Mihail Alekseevich Galanov Aleksej Igorevich MNOZhESTVENNAYa PODPIS NOVYE REShENIYa NA OSNOVE PONYaTIYa KOLLEKTIVNOGO OTKRYTOGO KLYuChA Zhurnal Informacionno upravlyayushie sistemy 2008 Vip 1 B Schneier Prikladnaya kriptografiya 18 grudnya 2018 John Wiley amp Sons 1996 S 98 Nikolaj Andreevich Moldovyan Andrej Alekseevich Kostin Lidiya Vyacheslavovna Gortinskaya Mihail Yurevich Ananev REALIZACIYa PROTOKOLA KOLLEKTIVNOJ PODPISI NA OSNOVE STANDARTOV ECP 21 listopada 2016 Zhurnal Informacionno upravlyayushie sistemy 2005 GOST R 34 10 94 Informacionnaya tehnologiya Kriptograficheskaya zashita informacii Processy formirovaniya i proverki elektronnoj cifrovoj podpisi Gosstandart Rossijskoj Federacii 1994 25 travnya GOST R 34 10 2001 Informacionnaya tehnologiya Kriptograficheskaya zashita informacii Processy formirovaniya i proverki elektronnoj cifrovoj podpisi Gosstandart Rossijskoj Federacii 2001 Pomilka nepravilnij chas Mihir Bellare Gregory Neven Ce nezavershena stattya z informacijnoyi bezpeki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno kviten 2018