Кільцевий підпис

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

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

Множинний підпис став електронним аналогом паперового підпису по колу. У 1991 році Девід Чаум (англ. David Chaum) і Євген Ван Хейст (англ. Eugene Van Heyst) запропонували схему групового підпису, де підписантом є хтось із членів групи, яку сформував адміністратор. Перевіряючий може переконатися, що підписант член групи, але не може дізнатися, хто саме. Адміністратор може встановити підписанта[4].

Кільцеві підписи по суті схожі з груповими, але, на відміну від останніх, немає можливості встановлення особи підписувача, немає адміністратора або координатора. Всі члени списку, за винятком самого підписанта, можуть не знати змісту повідомлення[1].

Передбачається, що існує певний перелік, де вказаний однозначний зв'язок людини з його відкритим (публічним) ключем (наприклад, сервер криптографічних ключів). Причина появи відкритого ключа в цьому переліку не має значення. Наприклад, людина могла створити ключі RSA тільки для покупок через Інтернет, і може зовсім не знати, що його відкриті ключі використовуються кимось для створення кільцевого підпису на повідомленні, яке він ніколи не бачив і не хотів підписувати. Загальний алгоритм кільцевого підпису припускає одночасне використання ключів, сформованих різними системами підпису з відкритим ключем, в тому числі мають різні розміри ключів і підписи.

При створенні кільцевого підпису для повідомлення m підписувач на власний розсуд формує список відкритих ключів (P₁, P₂, …, P_n), який включає і свій під номером i (його порядковий номер у списку не має значення). Все це разом з секретним ключем підписувача S_i як параметри подається на вхід функції накладання підпису (m, S_i, P₁, …, P_n), отримуючи на виході результат σ. Хоча кожному відкритому ключу зі списку відповідає свій унікальний закритий ключ і використовується тільки один з них (що належить підписувачу), але по підпису який вийшов неможливо впізнати, який саме з закритих ключів використовувався при її створенні. Навіть маючи необмежену кількість кільцевих підписів, виконаних одним і тим же підписантом, немає можливості його ідентифікувати або гарантовано встановити, що деякі підписи були накладені з використанням одного закритого ключа.

Справжність кільцевого підпису можна перевірити, використовуючи тільки σ, m і відкриті ключі P₁, …, P_n.[5].

У своїй статті Рівест, Шамір і Тауман описали кільцевий підпис як спосіб організувати витік секретної інформації без втрати її достовірності. Наприклад, кільцевий підпис «високопоставленого чиновника Білого дому» не розкриє його особистість, але гарантує, що повідомлення підписав хтось із зазначеного списку офіційних осіб, підтвердивши таким чином рівень компетентності. При цьому список осіб для кільцевого підпису можна легко скласти, узявши публічні ключі з відкритих джерел.

Інше застосування, також описане авторами ідеї, призначене для створення неоднозначних (спірних) підписів. У найпростішому випадку для такого використання кільцевого підпису формується на основі ключів відправника і одержувача повідомлення. Тоді підпис значущий для одержувача, він упевнений, що повідомлення створив відправник. Але для сторонньої людини такий підпис втрачає переконливість і однозначність — не буде впевненості, хто саме сформував і підписав повідомлення, адже це міг бути і сам одержувач. Такий підпис, наприклад, не може використовуватися у суді для ідентифікації відправника.

Пізніше з'явилися роботи, в яких були запропоновані нові сфери застосування кільцевих підписів і альтернативні алгоритми їх формування[6].

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

Останнім часом з'явилися більш ефективні алгоритми. Існують схеми з сублінійним розміром підпису[15], а також з постійним розміром[16]..

Схема кільцевого підпису

Суть алгоритму кільцевого підпису, запропонованого Рівестом, Шаміром і Тауман, полягає в наступному (див. малюнок схеми).

Кільцевий підпис для деякого повідомлення буде сформований на основі списку з ${\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}}$

Компоненти готового кільцевого підпису:

• повідомлення яке підписується ;
• список використаних відкритих ключів;
• значення всіх інформаційних блоків ${\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.
• С. В. Запечников и другие Кольцевые подписи и их приложения в Энциклопедии теоретической и прикладной криптографии, МИФИ