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

Сліпий підпис (англ. blind signature) — різновид електронного цифрового підпису, особливістю якого є те, що сторона, яка підписує, не може точно знати вміст підписаного документа. Поняття «сліпий підпис» придумано Девідом Чаумом в 1982 році, ним же запропонована перша реалізація через алгоритм RSA. Безпека схеми сліпого підпису ґрунтувалася на складності факторизації великих складених чисел. З тих пір було запропоновано велику кількість інших схем.

Опис

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

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

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

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

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

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

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

Завдяки властивостям нульового розголошення і невідстежуваності, схема сліпого підпису може бути широко задіяна в додатках, де необхідна конфіденційність, наприклад, в системах електронного голосування.

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

Повністю сліпий підпис

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

У цій схемі Аліса хоче, щоб Боб наосліп підписав повідомлення $m$. Для цього:

1. Аліса зашифровує повідомлення $m$ функцією $f$., отримуючи зашифроване повідомлення $c=f(m)$.
2. Аліса відсилає зашифроване повідомлення Бобу.
3. Боб наосліп (так як не знає, що знаходиться всередині) підписує повідомлення $c$ функцією $g$, отримуючи $c^{'}=g(c)=g(f(m))$.
4. Боб посилає $c^{'}$ назад Алісі.
5. Аліса отримує $c^{'}$ і прибирає своє шифрування, отримуючи: $c^{''}=g(f(m))*f^{-1}=g(m)$.

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

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

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

Протокол RSA

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

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

1. Аліса вибирає випадковий маскуючий множник $r$, взаємно простий з $p$, і обчислює $m^{'}\equiv mr^{e}{\bmod {p}}$.
2. Аліса відсилає $m^{'}$ по відкритому каналу Бобу.
3. Боб обчислює $s^{'}\equiv (m^{'})^{d}{\bmod {p}}$, використовуючи свій закритий ключ$(p,d)$.
4. Боб відсилає $s^{'}$ назад Алісі.
5. Аліса прибирає своє початкове маскування і отримує підписане Бобом вихідне повідомлення $m$ наступним чином: $s\equiv s^{'}*r^{-1}{\bmod {p}}\equiv m^{d}{\bmod {p}}$.

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

Сліпа підпис на основі ЕЦП Шнорра

Нехай Аліса хоче підписати повідомлення $m$ у Боба таким чином, щоб, по-перше, Боб не міг ознайомитися з повідомленням в ході підпису, по-друге, щоб Боб не міг згодом при отриманні повідомлення $m$ і відповідного підпису ідентифікувати користувача, ініціював протокол сліпий підписи для даного конкретного повідомлення (Алісу). Даний протокол реалізується наступним чином:

1. Аліса ініціює взаємодію з Бобом.
2. Боб відправляє Алісі значення $R=a^{k}\mod p$.
3. Аліса обчислює значення$R^{'}=Ra^{-w}y^{-t}\mod y$ (w і t — випадкові числа, що не перевищують $y$), $E^{'}=H(m||R^{'})$ і $E=E^{'}+t\mod y$, після чого відправляє Бобу значення $E$.
4. Боб обчислює значення $S$, таке що $R=a^{S}y^{E}\mod p$, і відправляє $S$ Алісі.
5. Аліса обчислює підпис $(E^{'},S^{'})$, де $E^{'}=E^{-t}\mod y$ і $S^{'}=S-w\mod y$, яка є справжньою по відношенню до повідомлення $m$.

Доведення  

Справжність підпису доводиться наступним чином. З$R=a^{S}y^{E}\mod p$ випливає $Ra^{-w}y^{-t}=a^{S-w}y^{E-t}modp$ і $R^{'}=a^{S^{'<nowiki>}}</nowiki>y^{E^{'<nowiki>}}</nowiki>\mod p$. При цьому проблема анонімності вирішується, оскільки будь-яка трійка (R, S, E) з безлічі таких трійок, які формувалися Бобом, може бути порівняна з підписом $(E^{'},S^{'})$ до цього документа $m$. Дійсно, маємо: $R=a^{S}y^{E}\mod p$ і $R^{'}=a^{S^{'<nowiki>}}</nowiki>y^{E^{'<nowiki>}}</nowiki>\mod p$$\Rightarrow$ $R^{'}/R\equiv a^{S^{'}-S}y^{E^{'}-E}\mod p\equiv a^{-w}y^{-t}\mod p$, тобто при рівновипадковому випадковому виборі доданків $w$$t$ підпис $(E^{'},S^{'})$ соднаковою ймовірністю була породжена з будь-якої трійки, що входить в множину трійок, сформованих підписувачем. Відзначимо також, що Боб не має навіть можливості довести, що на момент формування підпису даного документа $m$ він не був ознайомлений з ним. 

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

Параметри

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

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

α ≠ 1, α < p, $\alpha ^{q}$ mod p = 1.

Обчислення

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

Перевірка

1. Якщо R < q або S < q, то підпис недійсний. Інакше:
2. R' = ($\alpha ^{R/H}y^{S/H}$ mod p) mod q, де y — відкритий ключ;
3. Якщо R = R', то підпис дійсний.

Сліпа підпис на основі стандарту СТБ 1176.2-99

Стандарт Білорусі передбачає наступний протокол генерації сліпого підпису до документа M:

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

В даному описі використані наступні параметри: q — модуль, за яким ведуться обчислення, просте; a — породжує елемент; x — закритий ключ; y — відкритий ключ.

Колективний сліпий підпис

Нехай ${\overline {y_{1},y_{s}}}$ — відкриті ключі, якими володіють s користувачів. Нехай є повідомлення M, яке хочуть підписати m з них. У такому разі всі підписи можна об'єднати в один, довжина якої дорівнює довжині підпису одного користувача і не залежить від m. Це реалізується за правилами наступного протокола:

1. Кожний з m користувачів генерує випадкове число $t_{\alpha _{j}}$ < p, де j = ${\overline {1,m}}$, p — велике просте число. Далі кожний з m користувачів обчислює $R_{\alpha _{j}}=(t_{\alpha _{j}})^{k}$ mod p (k — велика проста ступінь) і розсилає це число всім іншим користувачам даної групи.
2. Кожен користувач обчислює $R=\prod _{j=1}^{m}R_{\alpha _{j}}$ mod p. Далі обчислюється e = f(R,M) = RH mod q, де q — велике просте число, відмінне від p, H = Hash(M) — хеш-функція. Число e буде першим елементом колективного підпису.
3. $S_{\alpha _{j}}=x_{\alpha _{j}}^{e}t_{\alpha _{j}}$ mod p — частка користувача. Цю частку кожен користувач обчислює і надає іншим.
4. Кожен з користувачів далі обчислює $S=\prod _{j=1}^{m}S_{\alpha _{j}}$ mod p. Це другий елемент колективного підпису.

Перевірка колективного сліпого підпису

$y=\prod _{j=1}^{m}y_{\alpha _{j}}$ mod p — колективний відкритий ключ. На його основі відбувається перевірка колективного сліпого підпису за наступним алгоритмом:

1. Обчислюється$R=S^{k}y^{-e}$ mod p.
2. Обчислюється e' = f(R,M) = RH mod q
3. Якщо e' = e, то підпис дійсний.

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

Банківські системи

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

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

Таємне голосування

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

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

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

Уразливості підпису наосліп

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

${\begin{aligned}m''&=m'r^{e}{\pmod {n}}\\&=(m^{e}{\pmod {n}}\cdot r^{e}){\pmod {n}}\\&=(mr)^{e}{\pmod {n}}\\\end{aligned}}$

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

${\begin{aligned}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{aligned}}$

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

${\begin{aligned}m=s'\cdot r^{-1}{\pmod {n}}\end{aligned}}$

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

Дивись також

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

Література

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