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

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

В этой схеме Алиса хочет, чтобы Боб вслепую подписал сообщение ${\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}}}$.

Чаум придумал целое семейство более сложных алгоритмов слепой подписи под общим названием неожиданные слепые подписи. Их схемы ещё сложнее, но они дают больше возможностей[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].