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

Кільцевий підпис (англ. 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 з першої реалізації до лютого 2016 року.

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

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

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

Алгоритм

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

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

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

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

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

Реалізація

Нижче наведена реалізація описаного алгоритму на мові 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 користувачів:

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) 

Примітки

1. Рон Рівест, Аді Шамір, . How to leak a secret. — Volume 2248 of Lecture Notes in Computer Science. — Asiacrypt, 2001. — С. 552—565.
2. . Фоносемантический анализ речи. — Изд-во Санкт-Петербургского университета, 2001. — 290 с.
3. Donald H. Dyal, Brian B. Carpenter, and Mark A. Thomas, eds. Historical Dictionary of the Spanish American War. — Westport, Conn. — Greenwood Press, 1996.
4. B. Schneier. Прикладная криптография : [ 18 грудня 2018] : ( )[] // John Wiley & Sons. — 1996. — С. 98.
5. Debnath, Ashmita; Singaravelu, Pradheepkumar; Verma, Shekhar (19 грудня 2012), Efficient spatial privacy preserving scheme for sensor network, Central European Journal of Engineering, 3 (1): 1—10, doi:10.2478/s13531-012-0048-7
6. Lingling Wang, Guoyin Zhang, Chunguang Ma. A survey of ring signature // Frontiers of Electrical and Electronic Engineering in China. — 2008. — Vol. 3, no. 1. — P. 10–19. — DOI:10.1007/s11460-008-0012-8.
7. E. Bresson; J. Stern; M. Szydlo (2002), Threshold ring signatures and applications to ad-hocgroups, Advances in Cryptology: Crypto 2002: 465—480, doi:10.1007/3-540-45708-9_30
8. Liu, Joseph K.; Wong, Duncan S. (2005), Linkable ring signatures: Security models and new schemes, ICCSA, 2: 614—623, doi:10.1007/11424826_65
9. Eiichiro Fujisaki, Koutarou Suzuki. Traceable Ring Signature. — Public Key Cryptography, 2007. — P. 181–200.
10. . CryptoNoteTech. Архів оригіналу за 24 листопада 2017. Процитовано 24 листопада 2017.
11. (англ.). 2015. Архів оригіналу за 13 липня 2017. Процитовано 29 листопада 2017.
12. . 23 червня 2014. Архів оригіналу за 1 грудня 2017. Процитовано 29 листопада 2017.
13. Rynomster, Tecnovert. HShadowCash: Zero­knowledge Anonymous Distributed E­Cash via Traceable Ring Signatures. — www.shadow.cash, 2015.
14. Crypto Fun (13.02.2016). (англ.). Архів оригіналу за 27 вересня 2016. Процитовано 29 листопада 2017. {{}}: Недійсний |deadlink=404 ()
15. Fujisaki, Eiichiro (2011), Sub-linear size traceable ring signatures without random oracles, CTRSA: 393—415
16. Au, Man Ho; Liu, Joseph K.; Susilo, Willy; Yuen, Tsz Hon (2006), Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature, Lecture Notes in Computer Science, 4329: 364—378, doi:10.1007/11941378_26

Література

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