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

'''Сліпий підпис''' ({{Lang-en|blind signature}}) — різновид [[Електронний цифровий підпис|електронного цифрового підпису]], особливістю якого є те, що сторона, яка підписує, не може точно знати вміст підписаного документа. Поняття «сліпий підпис» придумано {{нп|текст=Девідом Чаумом|треба=Девід Чаум|мова=en|є=David Chaum}}<ref name=":1">Брюс Шнайер, «Прикладная криптография. 2-е издание. Протоколы, алгоритмы и исходные тексты на языке С», издательство «Триумф», 2002 г.</ref> в 1982 році, ним же запропонована перша реалізація через алгоритм [[RSA]]. Безпека схеми сліпого підпису ґрунтувалася на складності факторизації великих [[Складене число|складених чисел]]. З тих пір було запропоновано велику кількість інших схем<ref>Жан Каменич, Жан-Марк Пивето, Маркус Штадлер, «Слепые подписи, основанные на задаче дискретного логарифмирования», журнал «Eurocrypt», страницы 428—432, издательство «Springer-Verlag», 1995 г.</ref><ref>{{cite journal
|first1 = Каліан
|last1 = Чакраборту
|first2 = Жан
|last2 = Мехта
|title = A stamped blind signature scheme based on elliptic curve discrete logarithm problem
|journal =  International Journal of Network Security
|issue = 14
|pages = 316—319
|year = 2012
|language = en}}</ref>.

== Опис ==
Основна ідея сліпих підписів полягає в наступному:

* Відправник '''А''' шифрує документ і надсилає його стороні '''В'''.
* Сторона, не бачачи вміст документа, підписує його і повертає назад стороні '''А'''.
* Сторона '''А''' знімає свій шифр, залишаючи на документі тільки підпис сторони '''В'''.

По завершенні цього протоколу сторона '''В''' нічого не знає ні про повідомлення t, ні про підписи під цим повідомленням.

Цю схему можна порівняти з конвертом, в якому розміщений документ і копіювальний лист. Якщо підписати конверт, то підпис віддрукується на документі, і при розтині конверта документ вже буде підписаний.

Мета сліпого підпису полягає в тому, щоб перешкодити підписувачу В ознайомитися з повідомленням сторони А, яку він підписує, і з відповідним підписом під цим повідомленням. Тому надалі підписане повідомлення неможливо пов'язати зі стороною А.

Схема безпечного сліпого підпису повинна задовольняти 3 властивостям, а саме:

# '''Нульове розголошування'''. Ця властивість допомагає користувачеві отримати підпис на даному повідомленні, не розкриваючи самого повідомлення підписуючій стороні.
# '''Невідстежуваність'''. Підписуюча сторона не може відстежити пару підпис-повідомлення після того, як користувач оприлюднив підпис на повідомленні.
# '''Непідкладність'''. Тільки підписуча сторона може сгенерувати дійсний підпис. Ця властивість найважливіша і повинна задовольнятися для всіх схем підписів.

Завдяки властивостям [[Доведення з нульовим пізнанням|нульового розголошення]] і невідстежуваності, схема сліпого підпису може бути широко задіяна в додатках, де необхідна [[конфіденційність]], наприклад, в [[Електронне голосування|системах електронного голосування]]<ref>Лун-Чанг Лин, Мин-Шианг Ханг, Чин-Чен Чанг «Повышение безопасности для анонимного электронного голосования через сеть», журнал «Computer Standards and Interfaces», выпуск 25, страницы 131—139, 2003 г.</ref><ref>Татсуаки Окамото, «Эффективная слепая и частично-слепая подписи без случайных предсказаний», сборник статей «Теория Криптографии», страницы 80-99, издательство «Springer-Verlag», 2006 г.</ref><ref>Маркус Рукерт, «Слепая подпись на основе решеток», сборник статей конференции Asiacrypt, страницы 413—430, издательство «Springer-Verlag», 2010 г.</ref><ref>Даниэль Ортис-Арройо, Клаудия Гарсия-Самора, «Очередное улучшение протокола электронного голосования Му-Варадараджана», журнал «Computer Standards and Interfaces», выпуск 29, страницы 471—480, 2007 г.</ref>.

== Алгоритми сліпого підпису ==

=== Повністю сліпий підпис ===
Дана ситуація: Боб — [[нотаріус]]. Алісі потрібно, щоб він підписав документ, не маючи ніякого уявлення про його зміст. Боб лише завірює, що документ нотаріально засвідчений в зазначений час. Тоді вони діють за таким алгоритмом:

[[Файл:BlindSignature.jpg]]

У цій схемі [[Аліса і Боб|Аліса]] хоче, щоб Боб наосліп підписав повідомлення <math>m</math>. Для цього:

# Аліса [[Шифрування|зашифровує]] повідомлення <math>m</math> функцією <math>f</math>., отримуючи зашифроване повідомлення <math>c = f (m)</math>.
# Аліса відсилає зашифроване повідомлення Бобу.
# Боб наосліп (так як не знає, що знаходиться всередині) підписує повідомлення <math>c</math> функцією <math>g</math>, отримуючи <math>c^{'} = g (c) = g (f (m))</math>.
# Боб посилає <math>c^{'}</math> назад Алісі.
# Аліса отримує <math>c^{'}</math> і прибирає своє шифрування, отримуючи:  <math>c^{''}=g(f(m))*f^{-1}=g(m)</math>.

Цей протокол працює, тільки якщо функції підпису та шифрування [[Комутативність|комутативні]].

=== Сліпий підпис ===

# ''Боб готує n документів на кожному з яких написано деяке унікальне слово (чим більше n, тим менше у Боба шансів зшахраювати).''
# ''Боб маскує кожен документ унікальним маскуючим множником і відправляє їх Алісі.''
# ''Аліса отримує всі документи і випадковим чином вибирає n-1 з них.''
# ''Аліса просить Боба вислати маскуючі множники для вибраних документів.''
# ''Боб робить це.''
# ''Аліса розкриває n-1 документів і переконується, що вони коректні.''
# ''Аліса підписує останній документ і відсилає Бобу.''
# ''Тепер у Боба є підписаний Алісою документ з унікальним словом, яке Аліса не знає.''

==== Протокол RSA ====
Перша реалізація сліпих підписів була здійснена Чаумом з допомогою криптосистеми RSA:

Припустимо, що спочатку у Боба є відкритий ключ <math>(p, e)</math> , де <math>p</math> — це модуль, а <math>e</math> — публічна експонента ключа.

# Аліса вибирає [[Генератор псевдовипадкових чисел|випадковий]] маскуючий множник <math>r</math>, взаємно простий з <math>p</math>, і обчислює <math>m^{'}\equiv m r^{e} \bmod p</math>.
# Аліса відсилає <math>m^{'}</math> по відкритому каналу Бобу.
# Боб обчислює <math>s^{'}\equiv (m^{'})^{d} \bmod p</math>, використовуючи свій закритий ключ<math>(p, d)</math>.
# Боб відсилає <math>s^{'}</math> назад Алісі.
# Аліса прибирає своє початкове маскування і отримує підписане Бобом вихідне повідомлення <math>m</math> наступним чином: <math>s \equiv s^{'}* r^{-1} \bmod p \equiv m^{d} \bmod p</math>.

Чаум придумав ціле сімейство більш складних алгоритмів сліпого підпису під загальною назвою '''несподівані сліпі підписи'''. Їх схеми ще складніше, але вони дають більше можливостей.

==== Сліпа підпис на основі ЕЦП Шнорра ====
Нехай Аліса хоче підписати повідомлення <math>m</math> у Боба таким чином, щоб, по-перше, Боб не міг ознайомитися з повідомленням в ході підпису, по-друге, щоб Боб не міг згодом при отриманні повідомлення <math>m</math> і відповідного підпису ідентифікувати користувача, ініціював протокол сліпий підписи для даного конкретного повідомлення (Алісу). Даний протокол реалізується наступним чином:

# Аліса ініціює взаємодію з Бобом.
# Боб відправляє Алісі значення <math> R = a^k \mod p</math>.
# Аліса обчислює значення<math> R^{'} = Ra^{-w}y^{-t} \mod y</math> (w і t — випадкові числа, що не перевищують <math>y</math>), <math> E^{'} = H(m||R^{'})</math> і <math> E = E^{'}+t \mod y</math>, після чого відправляє Бобу значення <math>E</math>.
# Боб обчислює значення <math>S</math>, таке що <math> R = a^S y^{E} \mod p</math>, і відправляє <math>S</math> Алісі.
# Аліса обчислює підпис <math>(E^{'},S^{'})</math>, де <math> E^{'} = E^{- t} \mod y</math> і <math> S^{'} = S-w \mod y</math>, яка є справжньою по відношенню до повідомлення <math>m</math><ref name=":2">{{Книга-ру|автор=Молдовян Н.А.|заглавие=Практикум по криптосистемам с открытым ключом|ответственный=|издание=|место=|издательство=|год=2007|страницы=|страниц=304|isbn=5-9775-0024-6}}</ref>.
{{Доведення1|Справжність підпису доводиться наступним чином. З<math> R = a^S y^{E} \mod p</math> випливає <math> Ra^{-w}y^{-t} = a^{S-w} y^{E-t} mod p</math> і <math> R^{'} = a^{S^{'<nowiki>}}</nowiki>y^{E^{'<nowiki>}}</nowiki> \mod p</math>. При цьому проблема анонімності вирішується, оскільки будь-яка трійка (R, S, E) з безлічі таких трійок, які формувалися Бобом, може бути порівняна з підписом <math>(E^{'},S^{'})</math> до цього документа <math>m</math>.
Дійсно, маємо: <math>R = a^S y^{E} \mod p</math> і <math> R^{'} = a^{S^{'<nowiki>}}</nowiki>y^{E^{'<nowiki>}}</nowiki> \mod p</math><math> \Rightarrow</math>  <math> R^{'}/R \equiv a^{S^{'}-S}y^{E^{'}-E} \mod p \equiv a^{-w}y^{-t} \mod p</math>, тобто при рівновипадковому випадковому виборі доданків <math>w</math><math>t</math> підпис <math>(E^{'},S^{'})</math> соднаковою ймовірністю була породжена з будь-якої трійки, що входить в множину трійок, сформованих підписувачем. Відзначимо також, що Боб не має навіть можливості довести, що на момент формування підпису даного документа <math>m</math> він не був ознайомлений з ним.|qed=&nbsp;}}

==== Сліпий підпис на основі ГОСТ Р 34.10-94 ====

===== Параметри =====
''p'' — [[просте число]], 510 ≤ |''p''| ≤ 512 (або 1022 ≤ |''p''| ≤ 1024), де |p| — розрядність [[Двійкова система числення|двійкового]] подання числа ''p.''

q — великий простий [[дільник]] числа p-1, 255 ≤ |''q''| ≤ 256 (або 511 ≤ |''q''| ≤ 512)

''α'' ≠ 1, ''α'' < ''p'', <math>\alpha^q</math> ''mod p'' = 1.

===== Обчислення =====

# Необхідно згенерувати випадкове ''k'', 1 < ''k'' < ''q'';
# R = (<math>\alpha^k</math> ''mod p'') ''mod q'' — перша частина підпису;
# ''H = Hash(m)'', де ''Hash'' — [[хеш-функція]], описана в стандарті ГОСТ Р 34.11-94, ''m'' — повідомлення, яке підписується ;
# ''S = kH + zR mod q'', де ''z'' — закритий ключ.
# Якщо S=0, то повторити операції 1-4.

===== Перевірка =====

# Якщо R < q або S < q, то підпис недійсний. Інакше:
# R' = (<math>\alpha^{R/H}y^{S/H}</math> ''mod p'') ''mod q'', де ''y'' — [[Асиметричні алгоритми шифрування|відкритий ключ]];
# Якщо ''R = R''', то підпис дійсний<ref name=":0" />.

==== Сліпа підпис на основі стандарту СТБ 1176.2-99 ====
Стандарт [[Білорусь|Білорусі]] передбачає наступний протокол генерації сліпого підпису до документа ''M'':

# Необхідно згенерувати випадкове ''k'' таке, що 1 < ''k'' < ''q'' і обчислити  <math>R = a^k</math>. Ці дії виконує підписувач. Далі він передає число ''R'' користувачеві;
# Користувач генерує випадкові числа ''ε'' і ''τ'' такі, що 1 < ''ε, τ'' < ''q'' і потім обчислює <math>R'= R*y^{\tau}*a^{\epsilon}</math>, <math>E'=F_H(R'||M)</math> і ''E'' = ''E''' — ''τ mod q''; ''E'' — перший елемент підпису — направляється підписувачу;
# Підписує обчислює другий елемент підпису ''S = (k — xE) mod q'' і передає ''S'' користувачеві;
# Користувач обчислює ''S' = S +'' ''ε mod q''.

В даному описі використані наступні параметри: ''q'' — модуль, за яким ведуться обчислення, просте; ''a'' — породжує елемент; ''x'' — закритий ключ; ''y'' — відкритий ключ<ref name=":0" />.

=== Колективний сліпий підпис ===
Нехай <math>\overline{y_1, y_s}</math> — відкриті ключі, якими володіють ''s'' користувачів. Нехай є повідомлення ''M'', яке хочуть підписати ''m'' з них. У такому разі всі підписи можна об'єднати в один, довжина якої дорівнює довжині підпису одного користувача і не залежить від ''m''. Це реалізується за правилами наступного протокола:

# Кожний з m користувачів генерує випадкове число <math>t_{\alpha_j}  </math> < ''p'', де j = <math>\overline{1, m}</math>, ''p'' — велике просте число. Далі кожний з m користувачів обчислює <math>R_{\alpha_j} = (t_{\alpha_j})^k </math> ''mod p'' (''k'' — велика проста ступінь) і розсилає це число всім іншим користувачам даної групи.
# Кожен користувач обчислює <math>R = \prod_{j=1}^mR_{\alpha_j}</math> ''mod p''. Далі обчислюється ''e = f(R,M) = RH mod q'', де ''q'' — велике просте число, відмінне від ''p'', ''H = Hash(M)'' — хеш-функція. Число ''e'' буде першим елементом колективного підпису.
# <math>S_{\alpha_j} = x_{\alpha_j}^et_{\alpha_j}</math> ''mod p'' — частка користувача. Цю частку кожен користувач обчислює і надає іншим.
# Кожен з користувачів далі обчислює <math>S = \prod_{j=1}^mS_{\alpha_j}</math> ''mod p''. Це другий елемент колективного підпису.

==== Перевірка колективного сліпого підпису ====
<math>y = \prod_{j=1}^my_{\alpha_j}</math> ''mod p'' — колективний відкритий ключ. На його основі відбувається перевірка колективного сліпого підпису за наступним алгоритмом:

# Обчислюється<math>R = S^ky^{-e}</math> ''mod p''.
# Обчислюється ''e' = f(R,M) = RH mod q''
# Якщо ''e''' ''= e'', то підпис дійсний<ref name=":0">{{Книга-ру|автор=Н.А. Молдовян|заглавие=Теоретический минимум и алгоритмы цифровой подписи|ответственный=|издание=|место=|издательство=БВХ-Петербург|год=2010|страницы=|страниц=304|isbn=978-5-9775-0585-7}}</ref>.

== Застосування ==

=== Банківські системи ===
Найбільш широке застосування протокол сліпих підписів знайшов у сфері [[Електронні гроші|цифрових грошей]]. Наприклад, щоб вкладник не обдурив банк, може використовуватися такий протокол: вкладник пише однаковий номінал купюр на ста документах з різними номерами і депонує в зашифрованому вигляді у банку. Банк вибирає випадковим чином і вимагає розкрити 99 (або n-1) конвертів, переконується, що скрізь написано $10, а не $1000, тоді підписує конверт, що залишився наосліп, не бачачи номера купюри.

Може бути передбачений більш простий варіант: за кожним номіналом купюр у банку закріплена своя пара відкритих ключів. Тоді під підпис надсилається тільки номер купюри, і необхідність перевірки номіналу перед підписом відпадає<ref name=":1" />.

=== Таємне голосування ===
Сліпі підписи використовуються для [[Таємне голосування|таємного голосування]]. У [[Протоколи таємного голосування#Протокол Фудзіоки — Окамото — Оти|протоколі Фуджіока, Окамото і Охта]], виборець готує виборчий бюлетень зі своїм вибором, який він зробив, шифрує його секретним ключем, і маскує його. Далі виборець підписує виборчий бюлетень і посилає його валідатору. Валідатор перевіряє, що підпис належить зареєстрованому виборцю, який ще не голосував.

Якщо виборчий бюлетень дійсний, валідатор підписує виборчий бюлетень і повертає його виборцю. Виборець видаляє маскування, розкриваючи таким чином зашифрований виборчий бюлетень, підписаний валідатором. Далі виборець посилає в результаті отриманий підписаний, зашифрований виборчий бюлетень лічильнику, який перевіряє підпис на зашифрованому виборчому бюлетені.

Якщо виборчий бюлетень дійсний, лічильник розміщує його в списку, який буде виданий після всього голосування. Після того, як список виданий, виборці перевіряють, що їх виборчі бюлетені знаходяться в списку і посилають лічильнику ключі розшифрування, необхідні, щоб відкрити їх виборчі бюлетені. Лічильник використовує ці ключі для розшифрування виборчих бюлетенів і додає голос до загального числа. Після виборів лічильник видає ключі розшифрування поряд з зашифрованими виборчими бюлетенями, щоб виборці могли незалежно перевірити вибір<ref>{{Cite web|url=https://sites.google.com/site/anisimovkhv/learning/kripto/lecture/tema15/tema15_3#p1535|title=Протоколы двух агентств Фудзиока-Окамото-Охта и Sensus|date=|publisher=|author=Анисимов В.В.|work=Криптографические методы защиты информации}}</ref>.

== Уразливості підпису наосліп ==
Алгоритм [[RSA]] може бути об'єктом атаки, завдяки якій стає можливим розшифрувати раніше підписане наосліп повідомлення, видавши його за повідомлення, яке тільки ще треба підписати. Виходячи з того, що процес підпису еквівалентний розшифровці підписуючою стороною (з використанням секретного ключа), атакуючий може підкласти для підпису вже підписану наосліп версію повідомлення <math>m</math>, зашифрованого за допомогою відкритого ключа підписуючої сторони, тобто підкласти повідомлення <math>m</math>.

: <math>
\begin{align}
m'' & = m' r^e\pmod n \\
    & = (m^e\pmod n \cdot r^e)\pmod n \\
    & = (mr)^e \pmod n \\
\end{align}
</math>

де <math>m'</math> — це зашифрована версія повідомлення. Коли повідомлення підписане, відкритий текст <math>m</math> легко отримуємо:

: <math>
\begin{align}
s' & = m''^d\pmod n \\
   & = ((mr)^e\pmod n)^d\pmod n \\
   & = (mr)^{ed} \pmod n \\
   & = m \cdot r \pmod n  \mbox{, since } ed \equiv 1 \pmod{\phi(n)}\\
\end{align}
</math>

де <math>\phi(n)</math> — це [[Функція Ейлера]]. Тепер повідомлення легко отримати.

: <math>
\begin{align}
m = s' \cdot r^{-1} \pmod{n}
\end{align}
</math>

Атака працює, тому що в цій схемі підписуюча сторона підписує безпосередньо саме повідомлення. Навпаки, у звичайних схемах підпису підписуюча сторона зазвичай підписує, наприклад, [[Криптографічна геш-функція|криптографічну хеш-функцію]]. Тому через цю мультиплікативну властивість [[RSA]], один ключ ніколи не повинен використовуватися одночасно для шифрування і підписання наосліп.

== Дивись також ==
* [[Кільцевий підпис]]
* [[Проблема криптографів які обідають]]
* [[Доведення з нульовим розголошенням]]

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

== Література ==

* ''Шнайер, Б.'' Прикладная криптография. 2-е издание. Протоколы, алгоритмы и исходные тексты на языке С — «Триумф», 2002 г.
* ''Клюжев А.'' Электронное голосование, 2003 г.
* ''Шаньгин, В. Ф.'', ''Соколов, А. В.'' Защита информации в распределенных корпоративных сетях и системах — «ДМК», 2002 г..
* ''Чаум, Д.'' Blind signatures for untraceable payments — «Springer-Verlag», 1998 г..
* ''Молдовян Н. А.'' Практикум по криптосистемам с открытым ключом, 2007 г.
* ''Молдовян Н. А.'' Теоретический минимум и основы цифровой подписи, 2010 г.

[[Категорія:Криптографія]]