Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 8.3.3 Схема Брандса Вверх: 8.3 Электронная монета Назад: 8.3.1 Общие сведения   Содержание   Предметный указатель


8.3.2 Схема Якоби

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

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

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

Замечание 1.  В работе нигде не поясняется, какой смысл имеет эта нулевая строка.

Через $ p$ обозначается модуль схемы Эль Гамаля (который, вообще говоря, может быть различным для различных клиентов). Пусть $ l(p)=\log_2(p)=\gamma$, $ \Sigma=\{0,1\}^{l(p)}$ и $ f\colon\Sigma\to\Sigma$ -- общедоступная хэш-функция с трудно обнаружимыми коллизиями (в работе -- collision free one way hash function; представляется, что в качестве $ f$ можно использовать одностороннюю перестановку). Иногда требуется такая же функция для $ \Sigma=\{0,1\}^{l\left(p^2\right)}$; она обозначается той же буквой.

Секретный ключ $ S_i$ клиента $ i$ представляет собой конкатенацию его имени $ I_i$ и случайной строки $ R_i$, а его открытый ключ есть $ P_i=\alpha^{S_i}\bmod p$, где $ \alpha $ -- общедоступный порождающий для $ \mathbb{Z}_p*$.


Выдача начального сертификата. Клиент $ i$ выбирает $ x\in_{\mbox{\tiny\rm R}}\mathbb{Z}_{N_c}*$, вычисляет $ z=x^{e_c}f(P_i,0^{\gamma})\bmod N_c$ и посылает ЦС $ z$ и $ I_i$. Затем клиент $ i$ доказывает ЦС с нулевым разглашением, что $ S_i$ содержит $ I_i$. Поскольку соответствующий предикат принадлежит NP, существование такого доказательства гарантируется известной теоремой Гольдрайха, Микали и Вигдерсона [GMW2]. Это же замечание справедливо и для протоколов доказательства в следующих двух транзакциях.

Если ЦС принимает доказательство, он подписывает $ z$, т. е. вычисляет $ z^{d_c}\bmod N_c$ и посылает это значение клиенту $ i$, который вычисляет сертификат $ \qopname\relax o{Cert}(i)=f(P_i,0^{\gamma})^{d_c}\bmod N_c$.

Обновление сертификата. Клиент $ i$ посылает ЦС сертификат $ \qopname\relax o{Cert}(i)$, заготовку $ c_2^{e_c}=x^{e_c}f(P_i',0^{\gamma})\bmod N_c$, где $ P_i'$ -- новое значение открытого ключа, и доказывает с нулевым разглашением, что соответствующие секретные ключи (старый и новый) содержат одно и то же имя $ I_i$.

Если ЦС принимает доказательство, то он вычисляет $ c_2=(c_2^{e_c})^{d_c}\bmod N_c$ и посылает это значение клиенту, который вычисляет новый сертификат $ c_2x^{-1}\bmod
N_c$.

Снятие со счета. Клиент $ i$ выбирает наудачу число $ r$, вычисляет $ u=\alpha^r\bmod p$, $ w=x^{e_b}f(P_i,u,0^{\gamma})\bmod N_b$, посылает $ w$ банку и доказывает с нулевым разглашением, что $ w$ построено правильно. В частности, клиент должен доказать, что секретный ключ, соответствующий $ P_i$, содержит его имя $ I_i$.

Если банк принимает доказательство, он вычисляет $ w^{d_b}\bmod N_b$ и посылает это значение клиенту $ i$, который вычисляет $ c=f(P_i,u,0^{\gamma})^{d_b}\bmod N_b$. Тройка $ (P_i,u,c)$ является электронной монетой.

Платеж. Покупатель посылает продавцу монету $ (P_i,u,c)$. Продавец проверяет подпись банка и, если она корректна, требует от покупателя подписать выбранное наудачу значение $ m$, используя $ P_i$ и $ u$, входящие в состав монеты. Т. е., он требует подпись $ v=r^{-1}(m-S_iu)\bmod(p-1)$, которую проверяет, используя открытый ключ $ P_i$.

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

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

Обмен монет. Клиент обращается в банк анонимно, посылает старые монеты и просит обменять их на новые монеты на ту же сумму. Банк проверяет полученные монеты по регистру и если какая-либо монета была потрачена дважды, идентифицирует нарушителя таким же образом, как это делается в транзакции депозита. Если никаких нарушений не обнаружено, клиент предъявляет сертификат $ (P_i,f(P_i,0^{\gamma})^{d_c}\bmod N_c)$ и для каждой запрашиваемой монеты высылает значение $ u=\alpha^r\bmod p$. Банк проверяет сертификат и, если сертификат подлинный, подписывает монеты $ c=f(P_i,u,0^{\gamma})^{d_b}\bmod N_b$ и передает их клиенту. Поскольку здесь не использовался затемняющий множитель, банк всегда узнает эти монеты в дальнейшем, но он не имеет никакой информации о том, кому из клиентов они были выданы.


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

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

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


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 8.3.3 Схема Брандса Вверх: 8.3 Электронная монета Назад: 8.3.1 Общие сведения   Содержание   Предметный указатель


Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ
   
TopList Rambler's Top100