Слепая подпись

Слепая подпись (англ. blind signature) — разновидность ЭЦП, особенностью которой является то, что подписывающая сторона не может точно знать содержимое подписываемого документа. Понятие слепой подписи придумано Дэвидом Чаумом^[1] в 1982 году, им же предложена первая реализация через алгоритм RSA. Безопасность схемы слепой подписи основывалась на сложности факторизации больших составных чисел. С тех пор было предложено большое количество других схем^[2]^[3].

Описание

Основная идея слепых подписей заключается в следующем:

Отправитель А шифрует документ и посылает его стороне В.
Сторона В, не видя содержимого документа, подписывает его и возвращает обратно стороне А.
Сторона А снимает свой шифр, оставляя на документе только подпись стороны В.

По завершении этого протокола сторона В ничего не знает ни о сообщении t, ни о подписи под этим сообщением.

Эту схему можно сравнить с конвертом, в котором размещён документ и копировальный лист. Если подписать конверт, то подпись отпечатается на документе, и при вскрытии конверта документ уже будет подписан.

Цель слепой подписи состоит в том, чтобы воспрепятствовать подписывающему лицу В ознакомиться с сообщением стороны А, которое он подписывает, и с соответствующей подписью под этим сообщением. Поэтому в дальнейшем подписанное сообщение невозможно связать со стороной А.

Схема безопасной слепой подписи должна удовлетворять 3 свойствам, а именно:

Нулевое разглашение. Это свойство помогает пользователю получить подпись на данном сообщении, не раскрывая самого сообщения подписывающей стороне.
Непрослеживаемость. Подписывающая сторона не может отследить пару подпись-сообщение после того, как пользователь обнародовал подпись на своем сообщении.
Неподложность. Только подписывающая сторона может сгенерировать действительную подпись. Это свойство самое важное и должно удовлетворяться для всех схем подписей.

Благодаря свойствам нулевого разглашения и непрослеживаемости схема слепой подписи может быть широко задействована в приложениях, где необходима конфиденциальность, например, в системах электронного голосования^[4]^[5]^[6]^[7].

Алгоритмы слепой подписи

Полностью слепая подпись

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

В этой схеме Алиса хочет, чтобы Боб вслепую подписал сообщение $m$ . Для этого:

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

Этот протокол работает, только если функции подписи и шифрования коммутативны.

Слепая подпись

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

Протокол RSA

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

Допустим, что изначально у Боба есть открытый ключ $(p,e)$ , где $p$ — это модуль, а $e$ — публичная экспонента ключа.

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

Чаум придумал целое семейство более сложных алгоритмов слепой подписи под общим названием неожиданные слепые подписи. Их схемы ещё сложнее, но они дают больше возможностей^[1].

Слепая подпись на основе ЭЦП Шнорра

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

Алиса инициирует взаимодействие с Бобом.
Боб отправляет Алисе значение $R=a^{k}\mod p$ .
Алиса вычисляет значения $R^{'}=Ra^{-w}y^{-t}\mod y$ (w и t — случайные числа, не превосходящие $y$ ), $E^{'}=H(m||R^{'})$ и $E=E^{'}+t\mod y$ , после чего отправляет Бобу значение $E$ .
Боб вычисляет значение $S$ , такое что $R=a^{S}y^{E}\mod p$ , и отправляет $S$ Алисе.
Алиса вычисляет подпись $(E^{'},S^{'})$ , где $E^{'}=E^{-t}\mod y$ и $S^{'}=S-w\mod y$ , которая является подлинной по отношению к сообщению $m$ ^[8].

Доказательство

Подлинность подписи доказывается следующим образом. Из $R=a^{S}y^{E}\mod p$ следует $Ra^{-w}y^{-t}=a^{S-w}y^{E-t}modp$ и $R^{'}=a^{S^{'}}y^{E^{'}}\mod p$ . При этом проблема анонимности решается, поскольку любая тройка $(R,S,E)$ из множества таких троек, которые формировались Бобом, может быть сопоставлена с подписью $(E^{'},S^{'})$ к данному документу $m$ . Действительно, имеем: $R=a^{S}y^{E}\mod p$ и $R^{'}=a^{S^{'}}y^{E^{'}}\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.

Вычисление

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

Проверка

0 < R < q или 0 < S < q. Если хотя бы одно из двух условий не выполнено, то подпись недействительна. Иначе:
R' = ( $\alpha ^{R/H}y^{S/H}$ mod p) mod q, где y — открытый ключ;
Если R = R', то подпись действительна^[9].

Слепая подпись на основе стандарта СТБ 1176.2-99

Стандарт Белоруссии предусматривает следующий протокол генерации слепой подписи к документу M:

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

В данном описании использованы следующие параметры: q — модуль, по которому ведутся вычисления, простое; a — порождающий элемент; x — закрытый ключ; y — открытый ключ^[9].

Коллективная слепая подпись

Пусть ${\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 — большая простая степень) и рассылает это число всем остальным пользователям из данной группы.
Каждый пользователь вычисляет $R=\prod _{j=1}^{m}R_{\alpha _{j}}$ mod p. Далее вычисляется e = f(R,M) = RH mod q, где q — большое простое число, отличное от p, H = Hash(M) — хеш-функция. Число e будет первым элементом коллективной подписи.
$S_{\alpha _{j}}=x_{\alpha _{j}}^{e}t_{\alpha _{j}}$ mod p — доля пользователя. Эту долю каждый пользователь вычисляет и предоставляет остальным.
Каждый из пользователей далее вычисляет $S=\prod _{j=1}^{m}S_{\alpha _{j}}$ mod p. Это второй элемент коллективной подписи.

Проверка коллективной слепой подписи

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

Вычисляется $R=S^{k}y^{-e}$ mod p.
Вычисляется e' = f(R,M) = RH mod q
Если e' = e, то подпись действительна^[9].

Применение

Банковские системы

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

Может быть предусмотрен более простой вариант: за каждым номиналом купюры у банка закреплена своя пара открытых ключей. Тогда под подпись присылается только номер купюры, и необходимость проверки номинала перед подписью отпадает^[1].

Тайное голосование

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

Если избирательный бюллетень действителен, валидатор подписывает избирательный бюллетень и возвращает его избирателю. Избиратель удаляет маскировку, раскрывая таким образом зашифрованный избирательный бюллетень, подписанный валидатором. Далее избиратель посылает полученный таким образом подписанный и зашифрованный избирательный бюллетень счётчику, который проверяет подпись на зашифрованном избирательном бюллетене.

Если избирательный бюллетень действителен, счётчик размещает его в списке, который будет издан после всего голосования. После того, как список издан, избиратели проверяют, что их избирательные бюллетени находятся в списке и посылают счётчику ключи расшифровки, необходимые, чтобы открыть их избирательные бюллетени. Счётчик использует эти ключи для расшифровки избирательных бюллетеней и добавляет голос к общему числу. После выборов счётчик издает ключи расшифровки наряду с зашифрованными избирательными бюллетенями, чтобы избиратели могли независимо проверить выбор^[10].

Уязвимости подписи вслепую

Алгоритм 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, один ключ никогда не должен использоваться одновременно для шифрования и подписания вслепую^[8].

См. также

Примечания

↑ ¹ ² ³ Брюс Шнайер, «Прикладная криптография. 2-е издание. Протоколы, алгоритмы и исходные тексты на языке С», издательство «Триумф», 2002 г.
↑ Жан Каменич, Жан-Марк Пивето, Маркус Штадлер, «Слепые подписи, основанные на задаче дискретного логарифмирования», журнал «Eurocrypt», страницы 428—432, издательство «Springer-Verlag», 1995 г.
↑ Калиан Чакраборту, Жан Мехта, «A stamped blind signature scheme based on elliptic curve discrete logarithm problem», журнал «International Journal of Network Security», выпуск 14, страницы 316—319, 2012 г.
↑ Лун-Чанг Лин, Мин-Шианг Ханг, Чин-Чен Чанг «Повышение безопасности для анонимного электронного голосования через сеть», журнал «Computer Standards and Interfaces», выпуск 25, страницы 131—139, 2003 г.
↑ Татсуаки Окамото, «Эффективная слепая и частично-слепая подписи без случайных предсказаний», сборник статей «Теория Криптографии», страницы 80-99, издательство «Springer-Verlag», 2006 г.
↑ Маркус Рукерт, «Слепая подпись на основе решеток», сборник статей конференции Asiacrypt, страницы 413—430, издательство «Springer-Verlag», 2010 г.
↑ Даниэль Ортис-Арройо, Клаудия Гарсия-Самора, «Очередное улучшение протокола электронного голосования Му-Варадараджана», журнал «Computer Standards and Interfaces», выпуск 29, страницы 471—480 , 2007 г.
↑ ¹ ² Молдовян Н.А. Практикум по криптосистемам с открытым ключом. — 2007. — 304 с. — ISBN 5-9775-0024-6.
↑ ¹ ² ³ Н.А. Молдовян. Теоретический минимум и алгоритмы цифровой подписи. — БВХ-Петербург, 2010. — 304 с. — ISBN 978-5-9775-0585-7.
↑ Анисимов В. В. Протоколы двух агентств Фудзиока-Окамото-Охта и Sensus (неопр.). Криптографические методы защиты информации. Дата обращения: 16 ноября 2016. Архивировано 17 ноября 2016 года.

Литература

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

[:1-1] ¹ ² ³ Брюс Шнайер, «Прикладная криптография. 2-е издание. Протоколы, алгоритмы и исходные тексты на языке С», издательство «Триумф», 2002 г.

[2] Жан Каменич, Жан-Марк Пивето, Маркус Штадлер, «Слепые подписи, основанные на задаче дискретного логарифмирования», журнал «Eurocrypt», страницы 428—432, издательство «Springer-Verlag», 1995 г.

[3] Калиан Чакраборту, Жан Мехта, «A stamped blind signature scheme based on elliptic curve discrete logarithm problem», журнал «International Journal of Network Security», выпуск 14, страницы 316—319, 2012 г.

[4] Лун-Чанг Лин, Мин-Шианг Ханг, Чин-Чен Чанг «Повышение безопасности для анонимного электронного голосования через сеть», журнал «Computer Standards and Interfaces», выпуск 25, страницы 131—139, 2003 г.

[5] Татсуаки Окамото, «Эффективная слепая и частично-слепая подписи без случайных предсказаний», сборник статей «Теория Криптографии», страницы 80-99, издательство «Springer-Verlag», 2006 г.

[6] Маркус Рукерт, «Слепая подпись на основе решеток», сборник статей конференции Asiacrypt, страницы 413—430, издательство «Springer-Verlag», 2010 г.

[7] Даниэль Ортис-Арройо, Клаудия Гарсия-Самора, «Очередное улучшение протокола электронного голосования Му-Варадараджана», журнал «Computer Standards and Interfaces», выпуск 29, страницы 471—480 , 2007 г.

[:2-8] ¹ ² Молдовян Н.А. Практикум по криптосистемам с открытым ключом. — 2007. — 304 с. — ISBN 5-9775-0024-6.

[:0-9] ¹ ² ³ Н.А. Молдовян. Теоретический минимум и алгоритмы цифровой подписи. — БВХ-Петербург, 2010. — 304 с. — ISBN 978-5-9775-0585-7.

[10] Анисимов В. В. Протоколы двух агентств Фудзиока-Окамото-Охта и Sensus (неопр.). Криптографические методы защиты информации. Дата обращения: 16 ноября 2016. Архивировано 17 ноября 2016 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]