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

4.2.2 Схема Шнорра [Sch]

Пусть участникам протокола известны некоторые простые числа $ p$, $ q$ такие, что $ q\mid p-1$, $ q\geqslant 2^{140}$, $ p\geqslant 2^{512}$, а также случайный элемент $ g$ порядка $ q$ группы $ \mathbb{Z}_p*$ и криптографически стойкая односторонняя хэш-функция $ h\colon\mathbb{Z}_p\times\mathbb{Z}\to\left\{0,\ldots,2^t-1\right\}$. Параметры $ p$, $ q$, $ g$ и хэш-функция $ h$ могут быть выбраны центром обеспечения безопасности. Подписывающий выбирает секретный ключ $ x\in_{\mbox{\tiny\rm R}}\mathbb{Z}_q$ и вычисляет открытый ключ $ y=g^{-x}\bmod
p$. Пространством сообщений в данной схеме является $ \mathbb{Z}$. Для генерации подписи для сообщения $ m$ нужно выбрать $ u\in_{\mbox{\tiny\rm R}}\mathbb{Z}_q$ и вычислить $ r=g^u\bmod p$, $ e=h(r,m)$ и $ s=(u+xe)\bmod q$. Искомой подписью является пара $ (e,s)$. Параметр $ u$ должен быть секретным и может быть уничтожен после генерации подписи. Проверка подписи $ (e,s)$ для сообщения $ m$ сводится к проверке равенства $ h\left(\left(g^sy^e\right)\bmod p,m\right)=e$.

Наиболее сложная операция, выполняемая при вычислении и проверке подписей в схемах типа Эль Гамаля -- это дискретное экспоненцирование $ z\to g^z\bmod p$. Преимущество схемы Шнорра перед схемой Эль Гамаля заключается в том, что $ u$ выбирается из меньшего множества (длина $ u$ -- порядка 140 битов). Это повышает эффективность вычисления дискретных экспонент.

Кроме того, заметим, что использование в схеме Шнорра хэш-функции при вычислении $ e$ и приведение подписи $ s$ по модулю $ q$ сокращают длину подписи по сравнению со схемой Эль Гамаля. Длина подписи -- один из важнейших показателей эффективности схемы.

Автор [Sch] предлагает также метод ускорения генерации подписей в вышеописанной схеме. Этот метод заключается в том, чтобы хранить (например, на интеллектуальной карточке) несколько пар $ (u_i,r_i)$, где $ u_i\in_{\mbox{\tiny\rm R}}\mathbb{Z}_q$, а $ r_i=g^{u_i}\bmod p$ (разные $ u_i$ выбираются независимо друг от друга). При генерации подписи пара $ (u,r)$ не вычисляется согласно вышеописанной схеме, а порождается как некоторая псевдослучайная комбинация пар $ (u_i,r_i)$. После этого набор $ (u_i,r_i)$ обновляется псевдослучайным образом. Этот метод позволяет сократить количество вычислений дискретных экспонент. Однако конкретные алгоритмы его реализации должны быть секретными и различными для каждой интеллектуальной карточки.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 4.2.3 Схема Брикелла - МакКарли [BM91] Вверх: 4.2 Примеры схем электронной подписи Назад: 4.2.1 Схема Эль Гамаля [EG85]   Содержание   Предметный указатель


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

TopList Rambler's Top100