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

4.2.6 Схема Фиата -- Шамира

Эта схема была предложена в работе [FS86]. Для ее использования центр обеспечения безопасности должен выбрать псевдослучайную функцию $ f$, криптографически стойкую хэш-функцию $ h$, а также выбрать различные большие простые числа $ p$, $ q$ и вычислить $ n=pq$. Число $ n$ и функции $ f$ и $ h$ являются общедоступными и публикуются центром, а числа $ p$ и $ q$ должны быть секретными. Кроме того, схема использует два натуральных параметра $ l$ и $ t$.

Для каждого пользователя центр обеспечения безопасности генерирует идентификационную информацию $ I$, содержащую, например, имя пользователя, его адрес, идентификационный номер и. т. п., и для каждого $ j=1,\ldots,l$ вычисляет $ y_j=f(I,j)$, отбирает среди них квадратичные вычеты по модулю $ n$ (изменив обозначения, мы считаем, что $ y_j$ для всех $ j=1,\ldots,l$ являются квадратичными вычетами по модулю $ n$), и вычисляет $ x_j$ -- наименьший квадратный корень по модулю $ n$ из $ y_j^{-1}\bmod n$. Числа $ y_j$ играют роль открытого ключа, а $ x_j$ -- секретного. Так как эти ключи вычисляются с использованием $ I$, схема Фиата -- Шамира относится к схемам, основанным на идентификационной информации (identity based). В другом варианте схемы Фиата -- Шамира сразу выбираются (псевдослучайным образом) параметры $ y_j$. На практике идентификационная информация $ I$ и/или открытый ключ $ (y_1,\ldots,y_l)$ каждого пользователя помещаются в некоторый справочник, доступный всем пользователям для чтения, но недоступный для записи. Для обеспечения аутентичности данные в этом справочнике заверяются подписью центра обеспечения безопасности. Секретный ключ $ (x_1,\ldots,x_l)$ и идентификационная информация $ I$ могут быть помещены на интеллектуальную карточку пользователя.

Для генерации подписи для сообщения $ m$ подписывающий     1) выбирает $ u_i\in_{\mbox{\tiny\rm R}}\mathbb{Z}_n$ (каждое $ u_i$ -- независимо друг от друга) и вычисляет $ r_i=u_i^2\bmod n$ для $ i=1,\ldots ,t$;

    2) вычисляет $ h(m,r_1,\ldots,r_t)$ и полагает биты $ e_{ij}$ ( $ i=1,\ldots ,t$, $ j=1,\ldots,l$) равными первым $ lt$ битам $ h(m,r_1,\ldots,r_t)$;

    3) вычисляет $ v_i=u_i\prod\limits_{j=1}^lx_j^{e_{ij}}\bmod n$ для $ i=1,\ldots ,t$. Искомой подписью для сообщения $ m$ является набор $ (e_{ij},v_i\,\vert\,i=1,\ldots,t,\,j=1,\ldots,l)$

Для проверки подписи $ (e_{ij},v_i\,\vert\,i=1,\ldots,t,\,j=1,\ldots,l)$ для сообщения $ m$ подписывающий     1) вычисляет $ v_j=h(I,j)$ для $ j=1,\ldots,l$ или берет их из общедоступного справочника и сравнивает их с имеющимися в подписи (если обнаружено несовпадение -- подпись отвергается);

    2) вычисляет $ z_i=v_i^2\prod\limits_{j=1}^ly_j^{e_{ij}}\bmod n$ для $ i=1,\ldots ,t$. Подпись принимается тогда и только тогда, когда первые $ lt$ битов $ h(m,z_1,\ldots,z_t)$ равны $ e_{ij}$.

Несомненным достоинством схемы Фиата -- Шамира является отсутствие операций дискретного экспоненцирования, что делает данную схему весьма эффективной. Но с другой стороны, в этой схеме длины ключей и подписи значительно больше, чем в схемах типа Эль Гамаля.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 4.2.7 Схемы RSA и Рабина Вверх: 4.2 Примеры схем электронной подписи Назад: 4.2.5 Схема стандарта электронной подписи ГОСТ   Содержание   Предметный указатель

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