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


4.3.2 Схемы конфиденциальной (неотвергаемой) подписи

Идея конфиденциальной подписи появилась в работе Шаума и ван Антверпена [CvA] в 1989 г. В отличие от обычной электронной подписи, которая может быть проверена в любой момент времени всяким желающим (поскольку открытый ключ подписывающего общедоступен, а подпись вместе с сообщением передается по незащищенным каналам связи, во многих теоретических работах авторы просто пишут, что подпись публикуется вместе с сообщением), конфиденциальная подпись не может быть проверена без участия сгенерировавшего ее лица. Иными словами, схемы конфиденциальной подписи могут найти применение в тех случаях, когда сам факт подписания какого-либо документа определенным лицом не подлежит огласке. В работах Шаума [Ch90], [Ch91] приводятся некоторые сценарии использования конфиденциальных подписей (см. также [CvA], [BCDP]), однако все они представляются не слишком убедительными. Поэтому, мы считаем, что практическая значимость этих схем требует дополнительного анализа, выходящего, однако, за рамки математических исследований. С математической же точки зрения схемы конфиденциальной подписи представляют несомненный интерес как новый криптографический примитив.

В дальнейшем участник протокола, подписавший некоторое сообщение конфиденциальной подписью, будет обозначаться через $ S$, а участник, который желает проверить эту подпись -- через $ V$. Для установления подлинности подписи $ S$ и $ V$ выполняют интерактивный протокол, называемый протоколом верификации, в котором $ S$ доказывает, что подпись была сгенерирована им. Конфиденциальная подпись предназначается ограниченному кругу лиц, поэтому естественно считать, что всякому выполнению протокола верификации предшествует выполнение протокола идентификации, в котором $ V$ доказывает свою аутентичность. В случае, если $ S$ не признает своей ту подпись, которую ему предъявил $ V$, участники выполняют отвергающий протокол, в котором $ S$ доказывает, что он не является автором предъявленной подписи.

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

С практической точки зрения, схемы конфиденциальной подписи желательно строить на основе того же математического аппарата, что и схемы обычной подписи. В работе [BCDP] описана схема конфиденциальной подписи, полученная путем модификации схемы Эль Гамаля, и предложены наброски доказательств свойства нулевого разглашения для протокола верификации и для отвергающего протокола. В данном подразделе рассматривается схема конфиденциальной подписи, построенная на основе отечественного стандарта на электронную подпись (см. подраздел 4.2.5).

Описываемая ниже схема предполагает наличие схемы ЭЦП, описанной в стандарте (см. также подраздел 4.2.5).

Помимо этого, каждый подписывающий имеет дополнительную пару (секретный ключ, открытый ключ), причем секретный ключ $ x_1$ выбирается наудачу из $ \mathbb{Z}_q$, а открытый ключ $ y_1$ вычисляется по формуле $ y_1=g^{x_1}\bmod p$.

Тройка $ (g,y,y_1)$ публикуется в общедоступном сертифицированном справочнике.

Всюду в дальнейшем предполагается, что подписываемое сообщение $ m$ имеет требуемую для схемы ЭЦП длину. Это сделано исключительно с целью упрощения изложения (на практике, разумеется, можно использовать значение хэш-функции от сообщения). Кроме того, в описаниях протоколов опущены проверки принадлежности различных величин, получаемых от другого участника, циклической группе, порождаемой $ g$. Очевидно, что каждый из участников может выполнять все эти проверки за полиномиальное время.

Подпись сообщения $ m$ вычисляется следующим образом. Выбирается $ u\in_{\mbox{\tiny\rm R}}\mathbb{Z}_q$ и вычисляется $ r=g^u\bmod p$. Затем вычисляется $ s=(xr+mx_1u)\bmod q$. Пара $ (r,s)$ является подписью для сообщения $ m$. Подпись считается корректной тогда и только тогда, когда $ r^{x_1}\equiv g^{sw}y^{-rw}\mkern5mu({\rm mod}\,\,p)$, где $ w=m^{-1}\bmod q$. Отметим одно очень существенное отличие этой схемы подписи от стандарта -- как при вычислении $ r$, так и в проверочном соотношении выполняется приведение только по одному модулю ($ p$).

Всюду ниже предполагается, что все вычисления проводятся в $ \mathbb{Z}_p$, поэтому модуль $ p$ в формулах, как правило, будет опускаться. $ DL(a,b)$ обозначает число $ c$ такое, что $ b^c\equiv a\mkern5mu({\rm mod}\,\,p)$. Для применения теоретико-сложностных подходов, все задачи, связанные со схемами подписи, должны рассматриваться как массовые. Параметром безопасности служит длина модуля $ p$. Принимается следующая гипотеза: любой полиномиальный алгоритм может по заданным $ a$, $ b$ и $ p$ вычислить $ DL(a,b)$ лишь с пренебрежимо малой вероятностью.

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


Протокол верификации

Проверяющий (абонент $ V$) вычисляет $ \gamma=g^{sw}y^{-rw}\bmod p$ и просит подписывающего (абонент $ S$) доказать, что пара $ (r,s)$ есть его подпись под сообщением $ m$. Эта задача эквивалентна доказательству, что дискретный логарифм $ \gamma$ по основанию $ r$ равен (по модулю $ p$) дискретному логарифму $ y_1$ по основанию $ g$, т. е. $ DL(y_1,g)=DL(\gamma,r)$. Для этого:     1. Абонент $ V$ выбирает $ a,b\in_{\mbox{\tiny\rm R}}\mathbb{Z}_q$, вычисляет $ \delta=r^ag^b\bmod p$ и посылает $ \delta$ абоненту $ S$.

    2. Абонент $ S$ выбирает $ t\in_{\mbox{\tiny\rm R}}\mathbb{Z}_q$, вычисляет $ h_1=\delta g^t\bmod p$, $ h_2=h_1^{x_1}\bmod p$ и посылает $ h_1$ и $ h_2$ абоненту $ V$.

    3. Абонент $ V$ высылает параметры $ a$ и $ b$.

    4. Если $ \delta=r^ag^b\bmod p$, то абонент $ S$ посылает $ V$ параметр $ t$; в противном случае -- останавливается.

    5. Абонент $ V$ проверяет выполнение равенств $ h_1=r^ag^{b+t}\bmod p$ и $ h_2=\gamma^ay_1^{b+t}\bmod p$. Если проверка завершена успешно, то подпись принимается как корректная.

Теорема 1.  Протокол верификации является протоколом доказательства с абсолютно нулевым разглашением.

В отвергающем протоколе $ S$ доказывает $ V$, что $ DL(y_1,g)\ne DL(\gamma,r)$.


Отвергающий протокол

Следующие шаги выполняются в цикле $ l$ раз.     1. $ V$ выбирает $ d,e\in_{\mbox{\tiny\rm R}}\mathbb{Z}_q$, $ d\ne 1$, $ \beta\in_{\mbox{\tiny\rm R}}\{0,1\}$. Вычисляет $ a=g^e$, $ b=y_1^e$, если $ \beta=0$ и $ a=r^e$, $ b=\gamma^e$, если $ \beta=1$. Посылает $ S$ значения $ a$, $ b$, $ d$.

    2. $ S$ проверяет соотношение $ a^{x_1}=b$. Если оно выполняется, то $ \alpha=0$, иначе $ \alpha=1$. Выбирает $ R\in_{\mbox{\tiny\rm R}}\mathbb{Z}_q$, вычисляет $ c=d^\alpha g^R$ и посылает $ V$ значение $ c$.

    3. $ V$ посылает $ S$ значение $ e$.

    4. $ S$ проверяет, что выполняется одно из соотношений $ (a,b)=(g^e,y_1^e)$ или $ (a,b)=(\gamma^e,r^e)$. Если да, то посылает $ V$ значение $ R$. Иначе останавливается.

    5. $ V$ проверяет, что $ d^\beta g^R=c$.

Если во всех $ l$ циклах проверка в п. 5 выполнена, то $ V$ принимает доказательство.

Теорема 2.  Отвергающий протокол является протоколом доказательства с абсолютно нулевым разглашением.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 4.3.3 Схемы, в которых подделка подписи может быть доказана Вверх: 4.3 Разновидности схем электронной подписи Назад: 4.3.1 Схемы мультиподписи   Содержание   Предметный указатель

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