Электронные монеты. 
Криптографические методы защиты информации

Общие сведения. Термин «электронная монета» впервые применялся в некоторых работах в качестве названия электронных денег, находящихся в обращении в централизованных системах электронных платежей. Поскольку в то время иных систем электронных платежей не было известно, это не создавало никаких проблем. Первая автономная платежная система была предложена в работе Чома, Фиата и Наора^[1]. После этого термин «электронные монеты» употребляют в основном в отношении электронных денег, используемых в автономных системах.

В автономных системах электронных платежей используются три основные транзакции.

• 1. Снятие со счета. Эта транзакция по своему назначению не отличается от аналогичной транзакции в централизованных системах.
• 2. Платеж. Один клиент (покупатель) передает другому (продавцу) электронную монету. Последний проверяет подлинность монеты без обращения к банку.
• 3. Депозит. Алиент кладет электронную монету на свой счет в банке. В отличие от централизованных систем, транзакцию депозита выполняет, вообще говоря, продавец.

В литературе, посвященной электронным монетам, идет дискуссия о тех требованиях, которым должна удовлетворять автономная система электронных платежей. Но следующие основные требования, являются, по существу, общепринятыми.

Безопасность для банка. После^{-кратного} выполнения транзакции снятия со счета, клиент не может создать более k различных электронных монет.

Неотслеживаемость. Наблюдая только транзакции снятия со счета и депозита, банк не может связать эти транзакции между собой, т. е. определить, кто из клиентов получил какую монету и кому ее заплатил.

Невозможность потратить монету дважды. Если клиент дважды расплатится одной и той же монетой, он будет идентифицирован банком, как только для обеих копий будет выполнена транзакция депозита.

Защита от ложных обвинений. Клиенты должны быть защищены от ошибочных обвинений в повторном платеже одной и той же монетой.

Третье из этих требований отражает существенное отличие автономной системы электронных платежей от централизованной.

Централизованная система не позволяет клиентам потратить одну и ту же банкноту дважды, а автономная лишь идентифицирует нарушителя в какой-то момент после повторного использования монеты. Разумеется, банк попытается снять соответствующую сумму со счета нарушителя, но при этом может обнаружить, что последнему нечем платить. Такова плата за эффективность. Но в ответ на возражения, разработчики автономных систем обычно просто отмечают, что подобный риск не является чем-то новым; он принят во многих ныне действующих платежных системах. Кроме того, повторная трата может быть предотвращена с помощью так называемых электронных бумажников с наблюдателями (см. далее).

Из дополнительных требований к автономной системе обычно выделяют следующие два.

Возможность перевода. Электронные монеты, полученные в одном платеже, могут использоваться для нового платежа (без промежуточного выполнения транзакций депозита и снятия со счета).

Возможность размена. Электронные монеты могут быть разделены на более мелкие части, которые можно тратить по отдельности.

Как нетрудно видеть, все эти требования сформулированы достаточно неформально. Такая ситуация, как отмечается в той же статье, типична для данной области исследований. Можно сказать, что математически строгую теорию банковских криптографических протоколов еще только предстоит разрабатывать.

Схема Якоби. Автономная система электронных платежей, предложенная Якоби^[2], интересна тем, что в ее конструкции задействованы как широко используемые на практике схемы электронной подписи RSA и Эль-Гамаля, так и системы доказательств с нулевым разглашением^[3]. При этом доказательства с нулевым разглашением используются только в тех транзакциях, которые будут выполняться достаточно редко, что обеспечивает высокую эффективность системы.

В системе имеются четыре участника: центр сертификации (ЦС), банк, покупатель и продавец, и шесть транзакций: выдача начального сертификата, обновление сертификата, снятие со счета, платеж, депозит и обмен монет.

Банк и ЦС используют схему электронной подписи RSA, а клиенты — схему Эль-Гамаля. Пусть e_b, d_h, N_b и e_c1 d_c, N_c — соответственно открытая и секретная экспоненты и модуль банка и ЦС. Пусть у — целое число, 30 < у < 50 и 0^У обозначает строку из у нулей.

Через р обозначается модуль схемы Эль-Гамаля (который, вообще говоря, может быть различным для различных клиентов). Пусть /(/?) = log₂(р) = у, Z = {0; 1}^/(/,) и/: X —? X — общедоступная хэшфункция с труднообнаружимыми коллизиями^[4].

Секретный ключ S_i клиента i представляет собой конкатенацию его имени /, и случайной строки R_jy а его открытый ключ есть P_i = = a^[5]'(modр)_у где, а — общедоступный порождающий элемент^[6][7][8] для Z*.

Выдача начального сертификата. Клиент i выбирает х e_R Z*_N, вычисляет z = x^e,f (P_jy 0^Y)(mod JV₍.) и посылает ЦС z и I_r Затем клиент i доказывает ЦС с нулевым разглашением, что S_i содержит Поскольку соответствующий предикат принадлежит классу NP существование такого доказательства гарантируется известной теоремой Гольдрайха, М икал и и Вигдерсона^[4]. Это же замечание справедливо и для протоколов доказательства в следующих двух транзакциях.

Если ЦС принимает доказательство, он подписывает Z, т. е. вычисляет z^{d (}(modN₍.) и посылает это значение клиенту который вычисляет сертификат Cert (i) = /(Р, 0^y)^{d (}(modAQ.

Обновление сертификата. Клиент i посылает ЦС сертификат Cert (i), заготовку с% = x^ecf (P', 0^Y)(mod N_c), где Р/ — новое значение открытого ключа, и доказывает с нулевым разглашением, что соответствующие секретные ключи (старый и новый) содержат одно и то же имя /.

Если ЦС принимает доказательство, то он вычисляет с% = = (с?)*(modN_c) и посылает это значение клиенту, который вычисляет новый сертификат evr^-1(mod Л^.).

Снятие со счета. Клиент i выбирает наудачу число г, вычисляет и = a' (modр), w = x^ehf (P_if и, 0^Y)(mod N_h) посылает w банку и доказывает с нулевым разглашением, что w построено правильно. В частности, клиент должен доказать, что секретный ключ, соответствующий Р_р содержит его имя /.

Если банк принимает доказательство, он вычисляет a^'(modA^) и посылает это значение клиенту i, который вычисляет с = =f (Pp и, 0^y)^di(modN_h). Тройка (Р, и, с) является электронной монетой.

Платеж. Покупатель посылает продавцу монету (P_jy и, с). Продавец проверяет подпись банка и, если она корректна, требует от покупателя подписать выбранное наудачу значение т, используя.

Pi и и, входящие в состав монеты (т.е. он требует подпись v = = r~m — Sjju (moAp — 1)), которую проверяет, используя открытый ключ Р,).

Депозит. Продавец передает банку полученную от покупателя электронную монету, запрос т и подпись s = (и, v). Банк проверяет по специальному регистру, не была ли эта монета потрачена ранее. Если будет обнаружено такое нарушение, то у банка будут две различные подписи, вычисленные с помощью одной и той же пары (S_jy и) для двух различных запросов т. По известному свойству подписи Эль-Гамаля этой информации достаточно, чтобы вычислить г, а значит, и S_r Поскольку секретный ключ содержит имя нарушитель будет идентифицирован.

Если никаких нарушений не обнаружено, банк заносит полученную монету в регистр и кладет соответствующую сумму на счет продавца.

Обмен монет. Клиент обращается в банк анонимно, посылает старые монеты и просит обменять их на новые монеты на ту же сумму. Банк проверяет полученные монеты по регистру и если какая-либо монета была потрачена дважды, идентифицирует нарушителя таким же образом, как это делается в транзакции депозита. Если никаких нарушений не обнаружено, клиент предъявляет сертификат ((Pi), f (P_i} O^y)^(l<(modN_c) и для каждой запрашиваемой монеты высылает значение и = a'(mod/?). Банк проверяет сертификат и, если сертификат подлинный, подписывает монеты [с = =f (P_jy и, 0'^fY^(lh)(nodN_h)] и передает их клиенту. Поскольку здесь не использовался затемняющий множитель, банк всегда узнает эти монеты в дальнейшем, но он не имеет никакой информации о том, кому из клиентов они были выданы.

Схема может быть очевидным образом обобщена на случай, когда в обращении находятся монеты различного номинала. В таком случае, каждому номиналу соответствует своя секретная экспонента d_h.

Чтобы избежать неограниченного возрастания длины регистра, в который банк заносит все полученные монеты, предлагается ввести для монет срок действия, по истечении которого они не принимаются ни в какие платежи. Транзакция обмена монет позволяет каждому клиенту анонимно обменивать выходящие из обращения монеты на новые.

Главный недостаток данной схемы заключается в крайней неэффективности транзакции снятия со счета. Однако автор относит эту транзакцию к числу редко используемых. Другими словами, схема может быть эффективна в том случае, если клиенты редко обращаются в банк, чтобы снять деньги со счета, а в основном расплачиваются электронными монетами друг с другом и периодически меняют в банке старые монеты на новые.

Схема Брандса. Данная схема^[10] выделяется из всех автономных систем электронных платежей благодаря, во-первых, своей высокой эффективности, а во-вторых, попыткой обосновать ее стойкость. В работе же сформулирован ряд результатов, утверждающих стойкость этой системы. Мы оцениваем их осторожно, как попытку обоснования стойкости, поскольку в работе нет достаточно формальных определений, а за доказательствами автор отсылает к своему техническому отчету.

Всюду ниже мы будем обозначать покупателя через U, а продавца — через S.

Инициализация системы. Банк выбирает тройку порождающих (g, g_v g₂) группы G_q простого порядка и число х e_R Z_q. Кроме того, он выбирает две хэш-функции с труднообнаружимыми коллизиями Н и Я₀. Н отображает пятерки элементов группы G_q в Z*, а Я₀ — пары элементов G_(f в Z_q. Кроме того, Н_{) зависит, например, от некоторого значения ID, идентифицирующего S, а также от времени и даты t выполнения транзакции. Этот формат функции Н₀ выбран лишь для примера. Банк публикует описание группы G (простые числа р и q, если G_q(Z*)), тройку (g, g_v g₂) и функции Я, Я₀ в качестве своего открытого ключа. Секретным ключом банка является число х. В описаниях протоколов появляется также еще некоторое значение h = g^x, которое должно публиковаться как часть открытого ключа.

Подпись Sign (A, В) банка для пары А, В е G_q есть четверка (z, а, b, г), где z, a, be G_q, г g Z_q, такая 4T0g^r = h^{H{A, B, z, a, b)}a, A^r = _z^H{A'^B'^ZM'^b)b.

Открытие счета. U выбирает число u_{ e Z_q и вычисляет I = g" ^!. Если /" 1, to U передает значение / банку, a u_x храпит в секрете.

Для безопасности банка существенно, чтобы значения / были различными для разных клиентов. Банк вычисляет z = (7^)^v и передает это значение U.

Снятие со счета. Прежде чем снять электронную монету со счета, и должен пройти аутентификацию, т. е. доказать банку, что он является владельцем данного счета. Затем выполняется следующий протокол.

• 1. Банк выбирает число w e_RZ_q и посылает а = g^w и Ь = клиенту U.
• 2. U выбирает три числа s e_R Z*, x_v x₂ e_R Z_q и вычисляет A = = (I_gi)^s, В = gf’gZ^[11] и z' = z^s. Кроме того, U выбирает числа u, ve_R Z_q и вычисляет а' = a^ug^v и b' = Ь™А*. Затем он вычисляет с' = Н (А, В, z', я', //)

с'.

и посылает запрос с = —-:—банку.

и (mod q)

3. Банк посылает ответ г = (сх + w) (mod q) и снимает со счета U соответствующую сумму.

U принимает ответ тогда и только тогда, когда g^r = к а и (I_g)^г = = z^cb. Если эти условия выполнены, U вычисляет г' = (ru + v) (mod#). Пара (Л, В) и подпись банка z', а!, //, г' для нее образуют электронную монету.

Платеж. В транзакции платежа U и S выполняют следующий протокол.

• 1. U посылает S электронную монету: Л, В, Sign (A, В).
• 2. Если Л ^ 1, то S вычисляет запрос D = Я₀(Л, В, ID, Т), где ID — идентификатор S, а Т — дата и время транзакции. S посылает U значение D.
• 3. U вычисляет ответы В, = (D ( t/, 5) + х_{) (mod Q) и r₂ = (DS + x₂) (modg) и посылает их S.

S принимает монету тогда и только тогда, когда Sign (A, В) является подписью для (Л, В) и = Л'⁷В.

Депозит. S посылает банку Л, В, Sign (A, В), (В_р г₂), а также дату и время транзакции платежа Т. Если Л = 1, то банк не принимает монету. В противном случае он вычисляет Д используя полученные данные и идентификатор ID продавца S. Затем банк проверяет, что g^gp ⁼ А⁽¹В и что Sign (A, В) является подписью для (Л, В). Если все корректно, то банк проверяет, не была ли монета потрачена ранее. Если нет, то банк запоминает (Л, Т, R_v г₂) и кладет монету на счет S.

Если данная электронная монета уже была потрачена ранее, то банк имеет в своем распоряжении две несовпадающие тройки (D, В, г₂) и (d', г', г₂) и может вычислить идентификатор наруши;

П ~^г

теля g?~^r

Из утверждений, сформулированных в работе Брандса, вытекает, что в предположении трудности задачи дискретного логарифмирования и стойкости протокола аутентификации Шнорра обеспечивается стойкость вышеприведенных протоколов для всех участников. Это означает, что:

• • клиенты не могут создавать электронные монеты без участия банка; если продавец действует в транзакции платежа согласно протоколу, то покупатель не может обмануть его, заплатив фальшивой монетой;
• • если покупатель действует согласно протоколам, то банк не может ложно обвинить его, предоставив в арбитраж сфабрикованное доказательство повторной траты одной и той же электронной монеты;
• • сообщения, посылаемые в ходе выполнения протоколов, не требуют шифрования, т. е. противник, подслушивающий транзакции снятия со счета, не может сам создать электронную монету, а подслушивание транзакции платежа не помогает выполнить депозит «перехваченной» монеты на другой счет.

Кроме того, при некотором предположении доказывается, что нарушитель, дважды потративший монету, всегда будет идентифицирован.

Переводимые электронные монеты. В схеме Якоби, приведенной выше, электронная монета не является переводимой (т.е. единственное, что может сделать продавец с полученной монетой, — это положить ее на свой счет в банке). Бумажные же и металлические деньги имеют то ценное свойство, что монеты и купюры, полученные в одном платеже, можно использовать для нового платежа непосредственно.

В работе ван Антверпена^[12] предлагает общий способ преобразования платежных систем с электронной монетой в системы с переводимой монетой. Вначале очень кратко опишем общую конструкцию системы электронных платежей с непереводимой монетой. Для лучшего понимания полезно сравнивать элементы этой системы с их реализацией в схеме Якоби.

Банк имеет два секретных ключа S₀ и S_v которым соответствуют открытые ключи Р₍₎ и Р,. Эти ключи используются в двух схемах подписи, которые могут быть как однотипными, так и различных типов, но обе эти схемы должны обеспечивать возможность получения затемненных подписей. Подпись сообщения т с ключом S_i будет для простоты обозначаться через S^rri). По соглашению подпись с ключом 5, соответствует номиналу, скажем, в 1 цент, а подпись с ключом S₀ никакого денежного содержания не имеет. Кроме того, банк выбирает и публикует некоторую однонаправленную функцию /.

Ниже приводятся описания транзакций платежной системы.

Снятие со счета. Клиент Р создает сообщение т_р, имеющее требуемую для данной платежной системы структуру, и, используя схему затемненной подписи, получает подпись банка на этом сообщении, т. е. он получает монету S_{(m) достоинством в 1 цент.

Платеж. Р посылает т_р и 5,(m) клиенту R. Последний проверяет подпись, выбирает случайный запрос с_р и посылает его Р. Клиент Р вычисляет ответ г_р и передает его R, который, используя с_р и т_р, проверяет корректность ответа.

Депозит. R посылает m_pi S_{(m_p) и r_p в банк. Банк проверяет подпись и корректность ответа г_р на запрос с_р. Кроме того, банк проверяет, не была ли данная монета потрачена ранее, и если да, то идентифицирует нарушителя.

Для преобразования этой платежной системы в систему с переводимой монетой в нее вносятся следующие изменения. Прежде чем принимать платеж, клиент R обращается в банк и выполняет с ним протокол, аналогичный протоколу снятия со счета, но получает подпись с другим ключом, т. е. ^₀(/гг_к), где т_к — сообщение, сформированное R таким же образом, как Р формирует т_р.

Когда R получает монету от Р в транзакции платежа, он не выбирает запрос случайным образом, а вычисляет его в виде с_р = ⁼ f (m_R1 p_R), где p_R — специальным образом подобранный параметр, зависящий от конкретной системы электронных платежей.

В дальнейшем R может заплатить полученную монету третьему клиенту Т с помощью следующей транзакции.

Перевод монеты. R высылает Т т_р, S^{m_p)_y /*_р, m_Ry S₀(m_R) и p_R. Т проверяет подписи, а также корректность ответа г_р на запрос f (m_Ry p_R). Затем он вычисляет запрос c_R и посылает его R. Получив ответ r_Ry клиент Т проверяет его корректность, используя c_R и m_R.

Чтобы положить полученную монету на свой счет, Т должен выслать банку всю информацию, полученную от R в процессе выполнения транзакции перевода монеты, а также свой запрос c_R. В свою очередь, Т может действовать описанным выше образом и получить монету, которую можно использовать для дальнейших платежей. Этот процесс перевода монеты в принципе может продолжаться сколь угодно долго, однако, как нетрудно видеть, при этом размер монеты возрастает. С интуитивной точки зрения это представляется естественным, поскольку монета должна содержать информацию, позволяющую банку идентифицировать нарушителя, потратившего монету дважды.

• [1] Chaum D., Fiat A., Naor M. Untraceable electronic cash // Adv. in Cryptology. CRYPTO'88: LNCS. 1990. Vol. 403. P. 319−327.
• [2] Yacobi Y. A key distribution «paradox» // Adv. in Cryptology — CRYPTO'90 :LNCS. 1991. Vol. 537. P. 268−273.
• [3] См. параграф 3.7.
• [4] См. параграф 3.4.
• [5] Proc. of the XIX annual ACM symposium on Theory of computing. 1987. P. 218—229.
• [6] См. приложение В.
• [7] См. приложение Д.
• [8] 1 Goldreich О., Micali S., Wigderson A. How to play any mental game // STOC ‘87
• [9] См. параграф 3.4.
• [10] Brands S. Untraceable off-line cash in wallets with observers // CRYPTO ‘93.
• [11] Proceedings of the 13th Annual International Cryptology Conference on Adv. inCryptology. 1993. P. 302—318.
• [12] Van Antverpen И. Electronic cash, Master’s Thesis. CWI, 1990.