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

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

Математичний алгоритм кільцевого підпису був розроблений Рональдом Рівестом, Аді Шаміром і Яелью Тауман (англ. Yael Tauman) і представлений в 2001 році на міжнародній конференції Asiacrypt. Автори намагалися в назві підкреслити відсутність центральної або координуючої структури при формуванні такого підпису: «кільце являє собою геометричну фігуру з однорідною периферією і без центру».

Історія

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

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

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

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

Загальний опис механізму створення і перевірки кільцевого підпису

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

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

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

Варіанти реалізації

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

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

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

Порогові кільцеві підпису

На відміну від стандартного порогового підпису «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).

Пов'язані кільцеві підписи

Властивість зв'язності дозволяє визначити, чи були створені якісь два кільцевих підписи однию і тою ж людиною (використовувався один і той ж закритий ключ), але без вказівки, хто саме. Одним з можливих застосувань може бути автономна система електронних грошей.

Простежуваний кільцевий підпис

На додаток до компонування підпису при повторному використанні може розкриватися відкритий ключ підписувача. Такий протокол дозволяє реалізувати системи таємного електронного голосування, які дозволяють поставити анонімно тільки один підпис, але розкривають учасника, який проголосував двічі..

Криптовалюти

Система CryptoNote допускає кільцеві підписи. Вперше це було використано в липні 2012 року в криптовалюте Bytecoin (не плутати з Bitcoin).

Криптовалюта ShadowCash використовує простежуваний кільцевий підпис анонімності відправника транзакції. Однак первісна реалізація була помилковою, що призвело до часткової де-анонімізації ShadowCash з першої реалізації до лютого 2016 року.

Ефективність

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

Алгоритм

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

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

Кільцевий підпис для деякого повідомлення буде сформований на основі списку з ${\displaystyle }$ відкритих ключів (позначені на схемі як ${\displaystyle }$), серед яких ключ підписувача має порядковий номер ${\displaystyle }$ . Відкриті ключі дозволяють зашифрувати довільну інформацію (інформаційний блок ${\displaystyle }$, зашифрований ключем ${\displaystyle }$, позначений на схемі як ${\displaystyle }$). «Інформаційні блоки» тут і далі не є частиною або результатом обробки підписуваного повідомлення і не мають самостійного значення, це згенеровані випадкові дані, що стають компонентами підпису.

Є комбінаційна функція від довільної кількості аргументів, за значенням якої і значень усіх аргументів, крім одного, можна однозначно відновити один відсутній аргумент. Прикладом такої функції є послідовне підсумовування. Якщо відома підсумкова сума і всі складові, крім одної, то відсутній доданок можна обчислити.

Як комбінаційної функції автори алгоритму запропонували наступну послідовність дій: береться деякий стартове значення (на схемі позначено ${\displaystyle }$формується випадково), над яким і першим аргументом виконується побітове виключне або (позначено на схемі символом ${\displaystyle }$). Потім до результату застосовується певне оборотне перетворення (позначена на схемі як ${\displaystyle }$), взаємно однозначно пов'язане з хеш-сумою підписаного повідомлення. Отриманий результат бере участь в операції побітового виключного «або» з другим аргументом, знову застосовується перетворення ${\displaystyle }$, і так далі. В якості аргументів використовуються зашифровані відкритими ключами відповідні інформаційні блоки ${\displaystyle }$.

Вибране випадкове значення ${\displaystyle }$ є одночасно і стартовим, і цільовим (кінцевим) значенням комбінаційної функції: результат всіх перетворень має «пройти по кільцю» і стати рівним початкового значення. Інформаційні блоки ${\displaystyle }$ для кожного з ключів, крім блоку ${\displaystyle }$, відповідного самого ключа підписувача, задаються як випадкові значення. Підписує шифрує інформаційні блоки відповідними відкритими ключами. Тепер у підписує є цільове значення комбінаційної функції і всі аргументи, крім одного — того, що відповідає його власним ключем. Завдяки властивостям комбінаційної функції, користувач може дізнатися відсутній аргумент і, використавши власний закритий ключ${\displaystyle }$), «розшифрувати» цей аргумент (${\displaystyle }$), отримавши відсутній інформаційний блок ${\displaystyle }$.

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

• повідомлення яке підписується ;
• список використаних відкритих ключів;
• значення всіх інформаційних блоків ${\displaystyle }$;
• значення комбінаційної функції ${\displaystyle }$.

Для перевірки підпису потрібно:

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

Реалізація

Нижче наведена реалізація описаного алгоритму на мові Python з використанням ключів RSA.

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

Підпис і перевірка 2 повідомлень при кільці з 4 користувачів:

Література

• Г. О. Чикишев. {{{Заголовок}}}.
• С. В. Запечников та інші Кільцеві підписи та їх застосування в Енциклопедії теоретичної і прикладної криптографії, МИФИ