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

4.2.1 Схема Эль Гамаля [EG85]

Пусть обоим участникам протокола известны некоторое простое число $ p$, некоторый порождающий $ g$ группы $ \mathbb{Z}_p*$ и некоторая хэш-функция $ h$. Подписывающий выбирает секретный ключ $ x\in_{\mbox{\tiny\rm R}}\mathbb{Z}_{p-1}$ и вычисляет открытый ключ $ y=g^{-x}\bmod p$. Пространством сообщений в данной схеме является $ \mathbb{Z}_{p-1}$. Для генерации подписи нужно сначала выбрать $ u\in_{\mbox{\tiny\rm R}}\mathbb{Z}_{p-1}$. Если $ u\notin\mathbb{Z}_{p-1}*$ (что проверяется эффективно), то необходимо выбрать новое $ u$. Если же $ u\in\mathbb{Z}_{p-1}*$, то искомой подписью для сообщения $ m$ является пара $ (r,s)$, где $ r=g^u\bmod p$ и $ s=u^{-1}(h(m)+xr)\bmod(p-1)$. Параметр $ u$ должен быть секретным и может быть уничтожен после генерации подписи.

Для проверки подписи $ (r,s)$ для сообщения $ m$ необходимо сначала проверить условия $ r\in\mathbb{Z}_p*$ и $ s\in\mathbb{Z}_{p-1}$. Если хотя бы одно из них ложно, то подпись отвергается. В противном случае подпись принимается тогда и только тогда, когда $ g^{h(m)}\equiv y^rr^s\mkern5mu({\rm mod}\,\,p)$.

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

Идеи схемы Эль Гамаля послужили основой для создания многих других схем электронной подписи, включая схемы Шнорра, DSA, ГОСТ и другие. В этих схемах элемент $ g$ иногда порождает не всю группу $ \mathbb{Z}_p*$, а некоторую ее подгруппу простого порядка.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 4.2.2 Схема Шнорра [Sch] Вверх: 4.2 Примеры схем электронной подписи Назад: 4.2 Примеры схем электронной подписи   Содержание   Предметный указатель

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