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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Необходимо сгенерировать случайное k, 1 < k < q;
2. R = (${\displaystyle \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. 0 < R < q или 0 < S < q. Если хотя бы одно из двух условий не выполнено, то подпись недействительна. Иначе:
2. R' = (${\displaystyle \alpha ^{R/H}y^{S/H}}$ mod p) mod q, где y — открытый ключ;
3. Если R = R', то подпись действительна^[9].

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

1. Необходимо сгенерировать случайное k такое, что 1 < k < q и вычислить ${\displaystyle R=a^{k}}$. Эти действия выполняет подписывающий. Далее он передаёт число R пользователю;
2. Пользователь генерирует случайные числа ε и τ такие, что 1 < ε, τ < q и затем вычисляет ${\displaystyle R'=R*y^{\tau }*a^{\epsilon }}$, ${\displaystyle 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 — открытый ключ^[9].

Пусть ${\displaystyle {\overline {y_{1},y_{s}}}}$ — открытые ключи, которыми владеют s пользователей. Пусть есть сообщение M, которое хотят подписать m из них. В таком случае все подписи можно объединить в одну, длина которой равна длине подписи одного пользователя и не зависит от m. Это реализуется по правилам следующего 1протокола:

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

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

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

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

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

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

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

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

Алгоритм RSA может являться объектом атаки, благодаря которой становится возможным расшифровать ранее подписанное вслепую сообщение, выдав его за сообщение, которое только ещё предстоит подписать. Исходя из того, что процесс подписи эквивалентен расшифровке подписывающей стороной (с использованием её секретного ключа), атакующий может подложить для подписи уже подписанную вслепую версию сообщения ${\displaystyle m}$, зашифрованного с помощью открытого ключа подписывающей стороны, то есть подложить сообщение ${\displaystyle m'}$.

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

где ${\displaystyle m'}$ — это зашифрованная версия сообщения. Когда сообщение подписано, открытый текст ${\displaystyle m}$ легко извлекаем:

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

где ${\displaystyle \phi (n)}$ — это Функция Эйлера. Теперь сообщение легко получить.

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

Атака работает, потому что в этой схеме подписывающая сторона подписывает непосредственно само сообщение. Напротив, в обычных схемах подписи подписывающая сторона обычно подписывает, например, криптографическую хеш-функцию. Поэтому из-за этого мультипликативного свойства RSA, один ключ никогда не должен использоваться одновременно для шифрования и подписания вслепую^[8].

• Кольцевая подпись
• Ослепление (криптография)
• Проблема обедающих криптографов
• Доказательство с нулевым разглашением
• GNU Taler

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