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

«Прошение о свободе» (1623 год), подписанное по кругу главами 56 семей Валлонии

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

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. — Приложение.
• Запечников С. В. и другие. Кольцевые подписи и их приложения в Энциклопедии теоретической и прикладной криптографии, МИФИ