www.wikidata.uk-ua.nina.az

Множинний підпис Множинний колективний підпис англ Aggregate signature схема протокол реалізації електронного підпису ЕЦ

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

Множинний (колективний) підпис (англ. 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 по формулі . Потім обчислюється величина . Перевірка підпису здійснюється за формулою .

Примітки ред.

  1. Молдовян Николай Андреевич, Еремеев Михаил Алексеевич, Галанов Алексей Игоревич. МНОЖЕСТВЕННАЯ ПОДПИСЬ: НОВЫЕ РЕШЕНИЯ НА ОСНОВЕ ПОНЯТИЯ КОЛЛЕКТИВНОГО ОТКРЫТОГО КЛЮЧА : [ ][] // Журнал "Информационно-управляющие системы". — 2008. — Вип. 1.
  2. B. Schneier. Прикладная криптография : [ 18 грудня 2018] : [ ][] // John Wiley & Sons. — 1996. — С. 98.
  3. ↑ Николай Андреевич Молдовян, Андрей Алексеевич Костин, Лидия Вячеславовна Гортинская, Михаил Юрьевич Ананьев. РЕАЛИЗАЦИЯ ПРОТОКОЛА КОЛЛЕКТИВНОЙ ПОДПИСИ НА ОСНОВЕ СТАНДАРТОВ ЭЦП : [ 21 листопада 2016] : [ ][] // Журнал "Информационно-управляющие системы". — 2005.
  4. ГОСТ Р 34.10–94. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи : [ ][] // Госстандарт Российской Федерации. — 1994. — 25 травня.
  5. ↑ ГОСТ Р 34.10–2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи : [ ][] // Госстандарт Российской Федерации. — 2001. — Помилка: неправильний час.
  6. Mihir Bellare,Gregory Neven. .


Це незавершена стаття з інформаційної безпеки.
Ви можете допомогти проєкту, виправивши або дописавши її.
Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (квітень 2018)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
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 1 Zmist 1 Vvedennya 2 Koncepciya kolektivnogo vidkritogo klyucha 3 Realizaciya protokoliv na osnovi standartiv ECP 3 1 Standart ECP GOST R 34 10 94 3 1 1 Algoritm obchislennya ECP 3 1 2 Algoritm perevirki dostovirnosti ECP 3 1 3 Realizaciya protokolu KECP 3 1 4 Perevirka kolektivnogo elektronnogo cifrovogo pidpisu 3 1 5 Dokaz korektnosti zaproponovanogo algoritmu KECP 3 1 6 Mozhlivist pidrobki KECP 3 1 7 Ataka na obchislennya sekretnogo klyucha inshogo spivvlasnika KECP 3 2 Standart ECP GOST R 34 10 2001 3 2 1 Formuvannya pidpisu 3 2 2 Perevirka pidpisu 3 2 3 Realizaciya protokolu KECP 3 2 4 Perevirka KECP 4 Realizaciya mnozhinnogo pidpisu na osnovi RSA 4 1 Shema podvijnogo pidpisu 4 2 Rozshirennya shemi podvijnogo pidpisu na UNIQ postMath 00000092 QINU uchasnikiv 5 PrimitkiVvedennya red Termin 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 2 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 klyucha red Na 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 3 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 3 Realizaciya protokoliv na osnovi standartiv ECP red Standart ECP GOST R 34 10 94 red Zgidno standartu GOST R 34 10 94 4 nakladayutsya obmezhennya na proste chislo p v dvijkovoimu predstavlenni yake vikoristovuyetsya 510 p 512 displaystyle 510 leq p leq 512 nbsp bit abo 1022 p 1024 displaystyle 1022 leq p leq 1024 nbsp bit Chislo p 1 displaystyle p 1 nbsp q displaystyle q nbsp takij sho 2 255 q 2 256 displaystyle 2 255 leq q leq 2 256 nbsp dlya 510 p 512 displaystyle 510 leq p leq 512 nbsp abo 2 511 q 2 512 displaystyle 2 511 leq q leq 2 512 nbsp dlya 1022 p 1024 displaystyle 1022 leq p leq 1024 nbsp Dlya generaciyi i perevirki ECP vikoristovuyut chislo a 1 displaystyle alpha neq 1 nbsp take sho a q mod p 1 displaystyle alpha q bmod p 1 nbsp de a displaystyle alpha nbsp generator pidgrupi dosit velikogo prostogo poryadku q displaystyle q nbsp Algoritm obchislennya ECP red 1 Generuyetsya vipadkove chislo k 1 lt k lt q displaystyle k 1 lt k lt q nbsp 2 Obchislyuyetsya znachennya R a k mod p mod q displaystyle R alpha k bmod p bmod q nbsp sho ye pershoyu chastinoyu pidpisu 3 Po GOST R 34 11 94 obchislyuyetsya hesh funkciya H displaystyle H nbsp vid pidpisuvanogo povidomlennya 4 Obchislyuyetsya druga chastina pidpisu S k H z R mod q displaystyle S kH zR bmod q nbsp de z displaystyle z nbsp sekretnij klyuch Yaksho S 0 displaystyle S 0 nbsp procedura generaciyi pidpisu povtoryuyetsya Algoritm perevirki dostovirnosti ECP red 1 Poviryayetsya vikonannya umov r lt q displaystyle r lt q nbsp i s lt q displaystyle s lt q nbsp Yaksho umovi ne vikonuyutsya to pidpis ne ye dijsnim 2 Obchislyuyetsya znachennya R a S H y R H mod p mod q displaystyle R alpha S H y R H bmod p bmod q nbsp de y displaystyle y nbsp vidkritij klyuch koristuvacha formuvannya perevirochnogo pidpisu 3 Porivnyuyutsya znachennya R displaystyle R nbsp i R displaystyle R nbsp Yaksho R R displaystyle R R nbsp to pidpis ye dijsnim Realizaciya protokolu KECP red Kozhen i displaystyle i nbsp j koristuvach formuye vidkritij klyuch vidu y i a z i mod p displaystyle y i alpha z i bmod p nbsp de z i displaystyle z i nbsp osobistij sekretnij klyuch i displaystyle i nbsp 1 displaystyle 1 nbsp 2 displaystyle 2 nbsp m displaystyle m nbsp Kolektivnim vidkritim klyuchem ye dobutok y y 1 y 2 y 3 y m mod p displaystyle y y 1 y 2 y 3 y m bmod p nbsp Kozhen koristuvach vibiraye vipadkovij sekretnij klyuch k i displaystyle k i nbsp chislo yake vikoristovuyetsya lishe odin raz Obchislyuyetsya R i a k i mod p mod q displaystyle R i left alpha k i bmod p right bmod q nbsp R R 1 R 2 R 3 R m mod q displaystyle R R 1 R 2 R 3 R m bmod q nbsp R i displaystyle R i nbsp ye dostupnim dlya vsih uchasnikiv kolektivu sho viroblyayut KECP Potim kozhen z uchasnikiv kolektivu sho viroblyayut KECP po viznachenij nim znachennyam R i displaystyle R i nbsp i rezultatu H displaystyle H nbsp obchislyuye S i k i H z i R mod q displaystyle S i k i H z i R bmod q nbsp S i displaystyle S i nbsp chastina pidpisu Kolektivnmim pidpisom bude para velichin S R displaystyle S R nbsp de S displaystyle S nbsp suma vsih S i displaystyle S i nbsp po modulyu q displaystyle q nbsp 3 Perevirka kolektivnogo elektronnogo cifrovogo pidpisu red Perevirka kolektivnogo pidpisu zdijsnyuyetsya za formuloyu R a S H y R H mod p mod q displaystyle R left alpha S H y R H bmod p right bmod q nbsp Yaksho R R displaystyle R R nbsp to KECP sukupnosti m displaystyle m nbsp 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 R i displaystyle R i nbsp 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 nbsp Ochevidno sho rozmir KECP ne zalezhit vid m displaystyle m nbsp 3 Dokaz korektnosti zaproponovanogo algoritmu KECP red V rivnyanni R a S H y R H mod p mod q displaystyle R left alpha S H y R H bmod p right bmod q nbsp 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 1 m S i H i 1 m y i R H mod p mod 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 nbsp i 1 m a S i H i 1 m y i R H mod p mod 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 nbsp i 1 m a S i H a z i R H mod p mod 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 nbsp i 1 m a k i z i R H a z i R H mod p mod 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 nbsp i 1 m a k i mod p mod q displaystyle left prod i 1 m alpha displaystyle k i bmod p right bmod q nbsp i 1 m a k i mod p mod q mod q displaystyle left prod i 1 m left alpha displaystyle k i bmod p right bmod q right bmod q nbsp i 1 m R i mod q displaystyle left prod i 1 m displaystyle R i right bmod q nbsp 3 Rozglyanemo formalnij dokaz stijkosti protokolu KECP pri vikoristanni perevirochnogo rivnyannyaR a S H y R H mod p mod q displaystyle R left alpha S H y R H bmod p right bmod q nbsp reglamentuyetsya standartom ECP GOST R 34 10 94 Mozhlivist pidrobki KECP red 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 y m mod p displaystyle y y y m bmod p nbsp de y i 1 m 1 y i mod p displaystyle y prod i 1 m 1 y i bmod p nbsp tobto m 1 displaystyle m 1 nbsp koristuvachiv ob yednuyut svoyi zusillya shob sformuvati paru chisel R S displaystyle left R S right nbsp taku sho R a S H y y m R H mod p mod q displaystyle R left alpha S H left y y m right R H bmod p right bmod q nbsp Tobto voni mozhut pidrobiti pidpis pid vidkritij klyuch y y y m mod p displaystyle y y y m bmod p nbsp tobto obchisliti znachennya R displaystyle R nbsp i S displaystyle S nbsp yaki zadovolnyayut rivnyannya R a S H y R H mod p mod q displaystyle R left alpha S H left y right R H bmod p right bmod q nbsp Z cogo viplivaye mozhlivist pidrobiti cifrovij pidpis v bazovij shemi ECP tak yak y displaystyle y nbsp Ataka na obchislennya sekretnogo klyucha inshogo spivvlasnika KECP red Nehaj R S displaystyle left R S right nbsp ce ECP sformovana m displaystyle m nbsp m koristuvachem do dokumentu yakij vidpovidaye hesh funkciyi H displaystyle H nbsp ataku vikonuyut m 1 displaystyle m 1 nbsp koristuvachiv Todi vikonuyetsya R a S H y m R H mod p mod q displaystyle R left alpha S H left y m right R H bmod p right bmod q nbsp t i displaystyle t i nbsp i obchislyuyut R i a t i mod p mod q displaystyle R i left alpha t i bmod p right bmod q nbsp dlya i 1 2 m 1 displaystyle i 1 2 m 1 nbsp Potim obchislyuyutsya parametriR R i 1 m 1 R i mod p mod q displaystyle R left R prod i 1 m 1 R i bmod p right bmod q nbsp i S i displaystyle S i nbsp yaki zadovilnyayut rivnyannyam R i a S i H y i R H mod p mod q displaystyle R i left alpha S i H y i R H bmod p right bmod q nbsp de i 1 2 m 1 displaystyle i 1 2 m 1 nbsp Vvodyachi poznachennya y y m R R mod p displaystyle y y m R R bmod p nbsp Mayemo R a S H Y R H mod p mod q displaystyle R left alpha S H left Y right R H bmod p right bmod q nbsp de S S i 1 m 1 S i mod p displaystyle S left S displaystyle sum i 1 m 1 S i right bmod p nbsp i Y y i 1 m 1 y i mod p displaystyle Y left y displaystyle prod i 1 m 1 y i right bmod p nbsp Ce oznachaye sho atakuyuchi otrimali pravilne znachennya kolektivnogo pidpisu R S displaystyle left R S right nbsp v yakij berut uchast voni i she odin koristuvach sho volodiye vidkritim klyuchem y a k mod p displaystyle y a k bmod p nbsp Zgidno dopushennyu z otrimanoyi kolektivnogo pidpisu atakuyuchi mozhut obchisliti sekretnij klyuch k displaystyle k nbsp Z virazu dlya y displaystyle y nbsp i formuli y a k mod p displaystyle y alpha k bmod p nbsp legko otrimati k R K R mod q displaystyle k RK R bmod q nbsp Atakuyuchi virahuvali sekretnij klyuch m displaystyle m nbsp 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 red Zgidno standartu GOST R 34 10 2001 5 nakladayutsya obmezhennya na proste chislo p yake vikoristovuyetsya proste chislo q i tochku G Proste chislo p displaystyle p nbsp modul eliptichnoyi krivoyi EK yaka zadayetsya v dekartovij sistemi koordinat rivnyannyam y 2 x 3 a x b mod p displaystyle y 2 x 3 ax b bmod p nbsp z koeficiyentami a displaystyle a nbsp i b displaystyle b nbsp a b displaystyle a b nbsp G F p displaystyle GF p nbsp G F p displaystyle GF p nbsp pole Galua poryadka p displaystyle p nbsp Proste chislo q displaystyle q nbsp poryadok ciklichnoyi pidgrupi tochok eliptichnoyi krivoyi Tochka G displaystyle G nbsp tochka na eliptichnij krivij z koordinatami x G y G displaystyle x G y G nbsp vidminna vid tochki pochatku koordinat ale dlya yakoyi tochka q G displaystyle qG nbsp zbigayetsya z pochatkom koordinat Sekretnim klyuchem ye dosit velike cile chislo d displaystyle d nbsp Vidkritim klyuchem ye tochka Q d G displaystyle Q dG nbsp Formuvannya pidpisu red 1 Generuyetsya vipadkove cile chislo k 0 lt k lt q displaystyle k 0 lt k lt q nbsp 2 Obchislyuyutsya koordinati tochki EK C k P displaystyle C kP nbsp i viznachayetsya znachennya R x C mod q displaystyle R x C bmod q nbsp de x C displaystyle x C nbsp koordinata tochki C displaystyle C nbsp 3 Obchislyuyetsya znachennya S R d k e mod q displaystyle S Rd ke bmod q nbsp de e H mod q displaystyle e H bmod q nbsp Pidpisom ye para chisel R S displaystyle R S nbsp 5 Perevirka pidpisu red Perevirka pidpisu polyagaye u obchislenni koordinat tochki EK C S e 1 mod q G q R e 1 mod q Q displaystyle C left left Se 1 right bmod q right G left left q R right e 1 bmod q right Q nbsp a takozh u viznachenni znachennya R x C mod q displaystyle R x C bmod q nbsp ta perevirci vikonannya rivnosti R R displaystyle R R nbsp 5 Realizaciya protokolu KECP red Kozhen uchasnik grupi formuye vidkritij klyuch vidu Q d i G displaystyle Q d i G nbsp de d i displaystyle d i nbsp osobistij sekretnij klyuch i 1 2 m displaystyle i 1 2 m nbsp Kolektivnim vidkritim klyuchem ye suma Q Q 1 Q 2 Q m displaystyle Q Q 1 Q 2 Q m nbsp Kozhen uchasnik grupi viroblyaye chislo k i displaystyle k i nbsp razovij vipadkovij sekretnij klyuch Za dopomogoyu ce razovogo vipadkovogo klyucha obchislyuyutsya koordinati tochki C i k i G displaystyle C i k i G nbsp Rezultat obchislennya rozsilayetsya vsim uchasnikam grupi dlya kolektivnogo vikoristannya Obchislyuyetsya suma C C 1 C 2 C m displaystyle C C 1 C 2 C m nbsp Z oderzhanoyi sumi obchislyuyetsya znachennya R displaystyle R nbsp Kozhen uchasnik grupi obchislyuye svoyu chastinu pidpisi S i R d i k i e mod q displaystyle S i left Rd i k i e right bmod q nbsp 3 Perevirka KECP red Obchislyuyut C S e 1 mod q G q R e 1 mod q Q displaystyle C left left Se 1 right bmod q right G left left q R right e 1 bmod q right Q nbsp Po otrimanomu rezultatu obchislyuyetsya R x C mod q displaystyle R x C bmod q nbsp Yaksho R R displaystyle R R nbsp 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 RSA red Shema podvijnogo pidpisu red 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 nbsp dobutok dvoh prostih dovgih chisel Vibirayutsya 2 vipadkovih privatnih klyucha r displaystyle r nbsp i s displaystyle s nbsp v diapazoni vid 1 do n displaystyle n nbsp kyaki budut vzayemno prosti z f n displaystyle varphi n nbsp de f n displaystyle varphi n nbsp funkciya Ejlera Viroblennya vidkritogo klyucha zdijsnyuyetsya za formuloyu r s t 1 mod f n displaystyle r s t 1 bmod varphi n nbsp Velichina t displaystyle t nbsp bude publichnim klyuchem Dlya togo shob pidpisati velichinu C displaystyle C nbsp pershij uchasnik obchislyuyeS 1 C r mod n displaystyle S 1 C r bmod n nbsp 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 nbsp z velichini S 1 displaystyle S 1 nbsp C displaystyle C nbsp jomu neobhidno bude obchisliti S 2 S 1 s mod n displaystyle S 2 S 1 s bmod n nbsp Perevirka pidpisu zdijsnyuyetsya za dopomogoyu C S 2 t mod n displaystyle C S 2 t bmod n nbsp 6 Rozshirennya shemi podvijnogo pidpisu na n displaystyle n nbsp uchasnikiv red Generuyutsya n displaystyle n nbsp k 1 k 2 k n displaystyle k 1 k 2 k n nbsp Publichnij klyuch bude obchislyuvatisya po formuli k 1 k 2 k n t 1 mod f n displaystyle left k 1 k 2 k n right t 1 bmod varphi n nbsp Kozhnij i displaystyle i nbsp j uchasnik pidpisuye povidomlennya M po formuli S i M k i mod n displaystyle S i M k i bmod n nbsp Potim obchislyuyetsya velichina S S 1 S 2 S 3 S n mod n displaystyle S S 1 S 2 S 3 S n bmod n nbsp Perevirka pidpisu zdijsnyuyetsya za formuloyuS t mod n S 1 S 2 S 3 S n t mod n displaystyle S t bmod n left S 1 S 2 S 3 S n right t bmod n nbsp M k 1 k 2 k 3 k n t mod n M displaystyle M left k 1 k 2 k 3 k n right t bmod n M nbsp Primitki red Moldovyan 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 arh 18 grudnya 2018 John Wiley amp Sons 1996 S 98 a b v g d e Nikolaj Andreevich Moldovyan Andrej Alekseevich Kostin Lidiya Vyacheslavovna Gortinskaya Mihail Yurevich Ananev REALIZACIYa PROTOKOLA KOLLEKTIVNOJ PODPISI NA OSNOVE STANDARTOV ECP arh 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 a b v 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 nbsp 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 Otrimano z https uk wikipedia org w index php title Mnozhinnij pidpis amp oldid 39698917