WikiSort.ru - Не сортированное

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

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

История

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

Множественная подпись стала электронным аналогом бумажной подписи по кругу. В 1991 году Дэвид Чом (англ. David Chaum) и Юджин Ван Хейст (англ. 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].

Эффективность

Большинство предложенных алгоритмов имеют асимптотический размер результата ${\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}$ .

import os, hashlib, random, 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

size = 4
msg1, msg2 = 'hello', '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)

Примечания

Литература

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

Эта статья входит в число добротных статей и является кандидатом в хорошие с 8 февраля 2019.