Кольцевая подпись

Кольцева́я по́дпись (англ. ring signature) — вариант реализации электронной подписи, при котором известно, что сообщение подписано одним из членов списка потенциальных подписантов, но не раскрывается, кем именно. Подписант самостоятельно формирует список из произвольного числа различных лиц, включая в него и себя. Для наложения подписи подписывающему не требуются разрешение, содействие или помощь со стороны включённых в список лиц — используются только открытые ключи всех членов списка и закрытый ключ лишь самого подписывающего.

Математический алгоритм кольцевой подписи разработали Рональд Ривест, Ади Шамир и Яэль Тауман (англ. Yael Tauman), представив в 2001 году на международной конференции Asiacrypt^[en][1]. По утверждению авторов, они старались в названии подчеркнуть отсутствие центральной или координирующей структуры при формировании такой подписи: «…кольца представляют собой геометрические фигуры с однородной периферией и без центра».

История[править | править код]

Идея групповой подписи под прошениями или жалобами, подтверждающей, что все подписанты поддерживают обращение, но не позволяющей выявить её автора или инициатора, берёт начало в прошлом. Так, английский термин «round-robin» известен с XVII столетия и обозначает петицию, которую подписывали по кругу без соблюдения иерархии, чтобы избежать наказания для подписавшегося первым^[2], — своеобразный вариант круговой поруки. В 1898 году после осады города Сантьяго-де-Куба во время испано-американской войны высокопоставленные офицеры 5-го армейского корпуса подписали по кругу письмо в штаб-квартиру армии в Вашингтоне с требованием вернуть корпус в Соединённые Штаты для лечения и отдыха. Письмо попало в прессу и получило широкую известность, а также вызвало резонанс в правительстве президента Мак-Кинли^[3].

Множественная подпись стала электронным аналогом бумажной подписи по кругу. В 1991 году Дэвид Чом и Юджин ван Хейст (англ. Eugene Van Heyst) предложили схему групповой подписи^[1], где подписантом является кто-то из членов группы, которую сформировал администратор. Проверяющий может убедиться, что подписант член группы, но не может узнать, кто именно. При этом администратор имеет возможность идентифицировать подписанта^[4].

Кольцевые подписи, по существу, схожи с групповыми, но, в отличие от последних, нет возможности установления личности подписанта, нет администратора или координатора. Все члены списка, за исключением самого подписанта, могут не знать ни содержания сообщения, ни даже факта использования их открытого ключа для формирования кем-то кольцевой подписи^[1].

Общее описание механизма создания и проверки кольцевой подписи[править | править код]

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

При создании кольцевой подписи для сообщения m подписывающий по своему усмотрению формирует список из открытых ключей (P₁, P₂, …, P_n), в который включает и свой под номером i (его порядковый номер в списке не имеет значения). Всё это вместе с секретным ключом подписывающего S_i как параметры подаётся на вход функции наложения подписи (m, S_i, P₁, …, P_n), получая на выходе результат σ. Хотя каждому открытому ключу из списка соответствует свой уникальный закрытый ключ и используется только один из них (принадлежащий подписывающему), но по получившейся подписи невозможно узнать, какой именно из закрытых ключей использовался при её создании. Даже имея неограниченное число кольцевых подписей, выполненных одним и тем же подписантом, нет возможности его идентифицировать или хотя бы гарантированно установить, что некоторые подписи были наложены с использованием одного и того же закрытого ключа^[1].

Подлинность кольцевой подписи можно проверить, используя σ, m и только открытые ключи P₁, …, P_n^[5].

Варианты реализации[править | править код]

В своей статье Ривест, Шамир и Тауман описали кольцевую подпись как способ организовать утечку секретной информации без потери её достоверности. Например, кольцевая подпись «высокопоставленного чиновника Белого дома» не раскроет его личность, но гарантирует, что сообщение подписал кто-то из указанного списка официальных лиц, подтвердив таким образом уровень компетентности. При этом список лиц для кольцевой подписи можно легко составить, взяв публичные ключи из открытых источников^[1].

Другое применение, также описанное авторами идеи, предназначено для создания неоднозначных (спорных) подписей. В простейшем случае для такого использования кольцевая подпись формируется на основе ключей отправителя и получателя сообщения. Тогда подпись значима для получателя, он уверен, что сообщение создал отправитель. Однако для постороннего человека такая подпись теряет убедительность и однозначность — не будет уверенности, кто именно сформировал и подписал сообщение, ведь это мог быть и сам получатель. Такая подпись, например, не может использоваться в суде для идентификации отправителя^[1].

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

Пороговые кольцевые подписи[править | править код]

В отличие от стандартной пороговой подписи «t-out-of-n», когда t из n пользователей должны сотрудничать для дешифрования сообщения, этот вариант кольцевой подписи требует, чтобы t пользователей сотрудничали в процессе подписания. Для этого t участников (i₁, i₂, …, i_t) должны вычислить сигнатуру σ для сообщения m, подав t закрытых и n открытых ключей на вход (m, S_i1, S_i2, …, S_it, P₁, …, P_n)^[8].

Связываемые кольцевые подписи[править | править код]

Свойство связности позволяет определить, были ли созданы какие-либо две кольцевые подписи одним и тем же человеком (использовался ли один и тот же закрытый ключ), но без указания, кто именно. Одним из возможных применений может быть автономная система электронных денег^[9].

Прослеживаемая кольцевая подпись[править | править код]

В дополнение к связываемой подписи при повторном использовании может раскрываться открытый ключ подписанта. Такой протокол позволяет реализовать системы тайного электронного голосования, которые позволяют поставить анонимно только одну подпись, но раскрывают участника, проголосовавшего дважды^[10].

Криптовалюты[править | править код]

Система CryptoNote допускает кольцевые подписи^[11]. Впервые это было использовано в июле 2012 года в криптовалюте Bytecoin^[12][13] (не путать с Bitcoin).

Криптовалюта ShadowCash использует прослеживаемую кольцевую подпись для анонимности отправителя транзакции^[14]. Однако первоначальная реализация была ошибочной, что привело к частичной деанонимизации ShadowCash с первой реализации до февраля 2016 года^[15].

Эффективность[править | править код]

Большинство предложенных алгоритмов имеют асимптотический размер результата ${\displaystyle O(n)}$, то есть размер результирующей подписи прямо пропорционален количеству использованных открытых ключей. Каждый использованный открытый ключ при наложении или проверке кольцевой подписи требует фиксированного объёма вычислений, что значительно лучше аналогов, имевшихся на момент создания протокола^[1]. Например, технология CryptoNote реализует кольцевые подписи в платежах p2p, чтобы обеспечить анонимность отправителя^[10].

В последнее время появились более эффективные алгоритмы. Существуют схемы с сублинейным размером подписи^[16], а также с постоянным размером^[17].

Алгоритм[править | править код]

Суть алгоритма кольцевой подписи, предложенной Ривестом, Шамиром и Тауман, состоит в следующем^[1] (см. рисунок схемы).

Кольцевая подпись для некоторого сообщения будет сформирована на основе списка из ${\displaystyle r}$ открытых ключей (обозначены на схеме как ${\displaystyle pk_{1},\ldots ,pk_{r}}$), среди которых ключ подписывающего имеет порядковый номер ${\displaystyle s}$ . Открытые ключи позволяют зашифровать произвольную информацию (информационный блок ${\displaystyle x_{1}}$, зашифрованный ключом ${\displaystyle pk_{1}}$, обозначен на схеме как ${\displaystyle \mathrm {Enc} _{pk_{1}}(x_{1})}$). «Информационные блоки» здесь и далее не являются частью или результатом обработки подписываемого сообщения и не имеют самостоятельного значения, это сгенерированные случайные данные, становящиеся компонентами подписи.

Имеется комбинационная функция от произвольного количества аргументов, по значению которой и значениям всех аргументов, кроме одного, можно однозначно восстановить один недостающий аргумент. Примером такой функции является последовательное суммирование: если известна итоговая сумма и все слагаемые, кроме одного, то недостающее слагаемое можно вычислить (вычитая из итоговой суммы величину всех известных слагаемых).

В качестве комбинационной функции авторы алгоритма предложили следующую последовательность действий: берётся некоторое стартовое значение (на схеме обозначено ${\displaystyle v}$, формируется случайно), над которым и первым аргументом выполняется побитовое исключающее «или» (обозначено на схеме символом ${\displaystyle \oplus }$). Затем к результату применяется определённое обратимое преобразование (обозначенное на схеме как ${\displaystyle E_{\sigma }}$), взаимно однозначно связанное с хеш-суммой подписываемого сообщения. Полученный результат участвует в операции побитового исключающего «или» со вторым аргументом, снова применяется преобразование ${\displaystyle E_{\sigma }}$ и так далее. В качестве аргументов используются зашифрованные открытыми ключами соответствующие информационные блоки ${\displaystyle x_{1},\ldots ,x_{r}}$.

Выбранное случайное значение ${\displaystyle v}$ является одновременно и стартовым, и целевым (конечным) значением комбинационной функции: результат всех преобразований должен «пройти по кольцу» и стать равным начальному значению. Информационные блоки ${\displaystyle x_{1},\ldots ,x_{r}}$ для каждого из ключей, кроме блока ${\displaystyle x_{s}}$, соответствующего ключу самого подписывающего, задаются как случайные значения. Подписывающий шифрует информационные блоки соответствующими открытыми ключами. Теперь у подписывающего имеется целевое значение комбинационной функции и все аргументы, кроме одного — того, что соответствует его собственному ключу. Благодаря свойствам комбинационной функции, подписывающий может узнать недостающий аргумент и, использовав собственный закрытый ключ (${\displaystyle sk_{s}}$), «расшифровать» этот аргумент (${\displaystyle \mathrm {Dec} _{sk_{s}}}$), получив недостающий информационный блок ${\displaystyle x_{s}}$.

Компоненты готовой кольцевой подписи^[1]:

• подписываемое сообщение;
• список всех использованных открытых ключей;
• значения всех информационных блоков ${\displaystyle x_{1},\ldots ,x_{r}}$;
• значение комбинационной функции ${\displaystyle v}$.

Для проверки подписи нужно^[1]:

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

Пример реализации[править | править код]

В качестве примера приведена реализация на языке Python базового алгоритма с использованием ключей RSA.

import os import hashlib import random import Crypto.PublicKey.RSA  class Ring:     def __init__(self, k, L=1024):         self.k = k         self.l = L         self.n = len(k)         self.q = 1 << (L - 1)      def sign(self, m, z):         self.permut(m)         s = [None] * self.n         u = random.randint(0, self.q)         c = v = self.E(u)          for i in (range(z+1, self.n) + range(z)):             s[i] = random.randint(0, self.q)             e = self.g(s[i], self.k[i].e, self.k[i].n)             v = self.E(v^e)              if (i+1) % self.n == 0:                 c = v         s[z] = self.g(v^u, self.k[z].d, self.k[z].n)         return [c] + s      def verify(self, m, X):         self.permut(m)         def _f(i):             return self.g(X[i+1], self.k[i].e, self.k[i].n)         y = map(_f, range(len(X)-1))         def _g(x, i):             return self.E(x^y[i])         r = reduce(_g, range(self.n), X[0])         return r == X[0]      def permut(self, m):         self.p = int(hashlib.sha1('%s' % m).hexdigest(),16)      def E(self, x):          msg = '%s%s' % (x, self.p)         return int(hashlib.sha1(msg).hexdigest(), 16)      def g(self, x, e, n):         q, r = divmod(x, n)         if ((q + 1) * n) <= ((1 << self.l) - 1):             rslt = q * n + pow(r, e, n)         else:             rslt = x         return rslt 

Подпись и проверка 2 сообщений при кольце из 4 пользователей:

size = 4 msg1 = 'hello' msg2 = 'world!'  def _rn(_):     return Crypto.PublicKey.RSA.generate(1024, os.urandom)  key = map(_rn, range(size)) r = Ring(key) for i in range(size):     s1 = r.sign(msg1, i)     s2 = r.sign(msg2, i)     assert r.verify(msg1, s1) and r.verify(msg2, s2) and not r.verify(msg1, s2) 

Примечания[править | править код]

Литература[править | править код]

• Чикишев Г. О. Одноразовая кольцевая подпись и её применение в электронной наличности // Прикладная дискретная математика». — 2012. — № 5. — С. 56—58. — Приложение.
• Запечников С. В. и другие. Кольцевые подписи и их приложения в Энциклопедии теоретической и прикладной криптографии, МИФИ

Эта статья входит в число хороших статей русскоязычного раздела Википедии.