Кодирование идентификаторов в монетах.

Существо метода заключается в следующем: т необходимо представить в форме т = gf • g2, где gb g2 - образующие элементы, которые отличаются от g, использовавшегося до сих пор, т. е. ?і ф І2 ф S Е Gq > и плательщик должен знать id. Тогда, если затем-нение осуществлено корректно, результат будет таким: т = msg' = gf 's • gs2 ¦ g'. Протокол платежа будет каким-то образом принуждать плательщика продемонстрировать знание экспонент jci, Лі, таких, что т - gf1 ¦ g,1. Кроме того, можно показать, что тройное экспоненцирование, т.е. функция (х,,х2,:Сз)—»gf'gpg*, не имеет коллизий. Таким образом, два представления т', используя тройки (id-s,s,t) и (л',,х2,0), должны быть одними и теми же. Следова-тельно, для затемнения плательщик должен выбрать / = 0. Тогда мы имеем: (xvxz) = (id -s,s). Отсюда видно, что идентификатор id вы-

числяется таким образом: id = — . Теперь повторная трата будет

разглашать все секретные величины, в частности jcb х2, и следова-тельно id.

Основные протоколы СЭП Брандса. Эта система электронных платежей полностью описывается комплектом из шести протоколов, которые мы и рассмотрим ниже.

Протокол инициализации выполняется однократно при вводе СЭП в эксплуатацию.

Банк также генерирует два случайных образующих элемента gx и g2. Каждый из участников системы должен доверять банку в том, что последний не умеет вычислять дискретные логарифмы по осно- 208 Запечников С. В. Криптографические протоколы и их применение

ванию gx. Если банк выбирает p,q,g\ случайным образом, то можно верить, что это условие соблюдается. Однако можно дополнительно гарантировать их случайность, используя произвольную случайную строку г, пользующуюся публичным доверием (например, выбирае-мую из таблиц случайных чисел), и генерируя желаемые величины из г посредством детерминированных процедур. В частности, gi мо- р-1

жет выбираться как і] ч , где г, - подстрока г, интерпретируемая как элемент Z*.

Протокол открытия счета (табл. 3.4) выполняется однажды для каждого нового плательщика при вводе его в СЭП. Протокол состоит из следующих шагов.

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

Таблица 3.4. Протокол открытия счета Банк В Плательщик Р 0 Cert(pkf>) (skP, pkP) - секр. и откр. ключ любой схемы цифровой подписи 1 id еЛ Zq - идентификатор плательщика (секр. случайное число), Л, = g'f - должно быть уникально для каждого плательщика 2 Протокол аутентификации Шнорра: (V) (Р) [id] 3 ^Sig+im)} т = h\gi На шаге (1) плательщик выбирает секретное случайное число id (mod q) и передает 1\ = gf в банк.

3. Системы электронных платежей 209

На шаге (2) плательщик доказывает банку, что он знает id с

К = Si"' ¦ Для этого используется протокол аутентификации Шнорра, где плательщик выступает в роли доказывающего, банк - в роли проверяющего.

На шаге (3) этого протокола плательщик подписывает (применяя skp) сообщение т, которое впоследствии будет использовано для снятия им своих средств со счета. Если банк позднее сможет показать величину id с gf g2 - т > это будет служить доказательством того, что монета этого плательщика потрачена дважды.

Протокол регистрации получателя платежа (табл. 3.5). Как отмечалось ранее, каждый получатель платежа в СЭП Брандса должен обязательно использовать запрос, отличный от другого получа-теля. Для этого желательно построить протокол так, чтобы каждый получатель регистрировался под уникальным идентификатором klRe. сір!ш. Получатель в СЭП Брандса не нуждается в каких-либо крипто-графических ключах.

Таблица 3.5. Протокол регистрации получателя платежа Банк В Получатель R [ IdRt,ripieM ] IdRerjpim - должно быть уникально для каждого получателя платежа

Протокол снятия со счета (табл. 3.6). Для каждого плательщика банк всегда подписывает (при помощи затемненной подписи) одно и то же сообщение /и, которое было согласовано выше, в протоколе открытия счета. Так как при этом г получается одним и тем же для каждого выполнения протокола, плательщик может хранить эту ве-личину у себя и шаг (0.0) становится ненужен. Но, конечно, новые величины w и (s,t,u,v) должны выбираться заново при каждом вы-полнении протокола снятия со счета. На шаге (0.1) плательщик ге-нерирует два дополнительных случайных числа - yvy2 (modg).

Вместе с (х^) существует уже четыре секретных переменных, для которых каждый платеж разглашает два линейных уравнения. В то же самое время набор величин (хі^УьУз) можно рассматривать как секретный ключ монеты skcoin> которым плательщик (как анонимный владелец этой монеты) может впоследствии подписывать свои платежи.

сматривать как открытый ключ монеты, соответствующий skcoUi. Чтобы зафиксировать принадлежность pkcoin определенной монете, эта величина включается в запрос плательщика банку путем вычис-ления хеш-кода: с -hash{in\pklY)in,z,a\b'). Для разрешения кон-фликтных ситуаций предусмотрено, что плательщик, используя свой skp, подписывает расходный ордер, куда включает нужный ему но-минал монеты и величину с , для которой он хочет получить ответ. Этот расходный ордер должен быть послан в банк на шаге (2) рас-сматриваемого протокола. Результатом выполнения протокола является получается плательщиком готовой «электронной монеты» coin = (т\ pkcojn, а'), где т называется идентификатором монеты,

а' = (z,a\h\c , /) - подписью монеты.

Таблица 3.6. Протокол снятия со счета Банк В Общедост. величины: P,Q,g,lhgt>g2 ПлателъщикР 0.0 z = тх 0.1 s,u,v,yl,y2ell zq,(t = 0), л-[ = id ¦ s (mod q), X2 = S ; m = ms (mod /?)[= g* ¦ g22 (mod />)]; z' = z* (mod p);

sKoi„ ~ > - У\»У г)- секР-101104 монеты; ['». рК„ш = [g\ • Si )]- откр. ключ монеты 1 а = gw, Ь = />Г [а,ЬП a=augv',b' = bM-(m'y 2 <-[ с, W.O.] с = hash(m, pkcoiu, z\a\b'), с = с'-и'1,

W.O. = [Sigskp {«withdraw», номинал, С ] 3 Г = W+CX М-» 7 f

gr =ahc; mr-bzc,

r-ur + v, coin = (m\ pkcoin, 0у),

где с/ =(z,ci,b,c,r)

3. Системы электронных платежей 211

Протокол платежа (табл. 3.7). Здесь плательщик, во-первых, посылает получателю имеющуюся у него монету coin (компоненты см. выше), а получатель проверяет, что она корректно подписана подписью Шаума - Педерсена. Оставшаяся часть протокола платежа следует рассмотренным ранее идеям. В частности, каждый ответ R разглашает два линейных уравнения в четырех переменных (дгіЛ.УьУг)- Как проверить, что ответы корректны? Как и ранее, это делается проверкой соответствующих уравнений «по экспонентам».

Таблица 3.7.

Следует обратить внимание, что протокол имеет такую же структуру, как и протокол аутентификации Шнорра (и вообще любой протокол аутентификации, основанный на доказательствах с нулевым разглашением знания), за исключением того, что «случайный вариант» (xltx2) уже дан в виде (уу.у?)- Соответствующие открытые

величины - т = g*1 ¦ gx2> и pkcoin - g['' ¦ g^1 . Величина n в протоколе - это элемент числовой последовательности, который гарантирует получателю, что тот не сможет принять одну и ту же монету дважды с одним и тем же запросом. Линейная комбинация в ответе дос-тигается скалярным умножением и сложением пар: 7? = С (jc, , х,) +

+ (>>,,у2). Если все вычисления проведены корректно, мы должны получить

Мс РК„,„ = (с -GPF- (sf • «Г )= tfс+я ¦ *?с+й •

Протокол депонирования монеты (табл. 3.8). В депозите полу-чатель пересылает всю свою информацию из платежа, включая IdReCiPient и п. Получив этот пакет данных, банк прежде всего проверяет действительность монеты точно так же, как это делал получатель монеты в шагах (1) и (3) протокола платежа. При дальнейшем вы-полнении проверок он может обнаружить факт повторной траты монеты или повторного депонирования монеты, вводя монету в свою базу данных для сравнения с предыдущими депозитами других по-лучателей. Это может быть сделано банком в автономном режиме, причем монеты остаются в базе данных до истечения установленного для них срока годности.

Таблица 3.8. Депозит и идентификация повторной траты монеты Получатель R Банк В 1 2 Проверка действительности монеты: с'^ hash (in , pkcom,i gr^~a'-hc\ (mj = //¦(z'f, mVl, gfg' -st2 =(m'f ' PKnu, - где С = hash'(m\pkcoin, ldRtcjpienl,n) 3 sig2-sigl 8 id m - gi,lig2

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

* ' 1 О 1 6 I

R , вычисляет идентификатор id = и устанавливает, ка-

sig2~sig2

кому плательщику принадлежит т = g"'gi. Этот плательщик, следо-вательно, совершил повторную трату монеты.

Корректность вычисления id может быть выведена непосредственно из проверочных уравнений. В самом деле, мы. имеем:

g?s> ¦ gf3 = (mf ¦ pk' и gf* ¦ gf2 = {m'Y • pk', следовательно, . gWz-щі _ (jn)C~C . Это означает, что плательщик знает

/ хх *

представление т в виде Ig,' • g2' с х1 = ;— и

С с

sig2-sig* TJ

х2 = —^—^ . Из рассмотренного ранее свойства удержания

Х1 V/

идентичности следует, что — — id .