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

4.2.8 О схемах, основанных на функциях с секретом

В данном подразделе мы приводим некоторые сведения [GMRiv] о стойкости схем электронной подписи, построенных на основе функций с секретом. В этом анализе предполагается, что подписывается само сообщение $ m$, а не значение какой-либо хэш-функции на этом сообщении.

Говоря неформально, функция $ f\colon A\to B$ называется функцией с секретом (trapdoor function), если она легко вычислима и существует некоторая информация, называемая секретом, знание которой позволяет легко инвертировать $ f$, но в то же время инвертирование $ f$ без знания секрета является вычислительно трудной задачей (см. главу 14). Если имеется некоторая функция с секретом $ f\colon A\to B$, то можно построить схему электронной подписи следующим образом. Пространством сообщений в этой схеме является $ B$. Роль открытого ключа играет функция $ f$, а секретного -- информация, позволяющая легко ее инвертировать. Подписью для произвольного сообщения $ m\in B$ является любой прообраз $ m$ относительно $ f$. По предположению эти прообразы можно вычислять эффективно, лишь владея секретным ключом. Проверка же подписи $ s$ для сообщения $ m$ заключается в проверке равенства $ f(s)=m$. По существу, такую схему можно получить из любой криптосистемы с открытым ключом, основанной на функции с секретом: отправитель подписывает сообщение, применяя к нему секретный алгоритм дешифрования, а получатель проверяет подпись, применяя к ней общедоступный алгоритм шифрования.

Очевидно, что любая схема электронной подписи, построенная описанным выше методом, является нестойкой против экзистенциальной подделки на основе атаки с открытым ключом, так как произвольный элемент $ a\in A$ является допустимой подписью для сообщения $ f(a)$. Для предотвращения такой угрозы часто рекомендуют сделать пространство сообщений " редким" во множестве значений $ f$, т. е. чтобы для случайно выбранного $ a$ вероятность того, что $ f(a)$ представляет собой допустимое сообщение, была бы мала. Однако эта рекомендация представляется сомнительной: функция с секретом может тем не менее легко инвертироваться на этом "редком" пространстве и без знания секрета.

Схема RSA является нестойкой против селективной подделки на основе направленной атаки с выбором сообщений, так как для любых сообщений $ m_1,m_2\in\mathbb{Z}_n*$ $ s((m_1m_2)\bmod n)=(s(m_1)s(m_2))\bmod n$.

Схема Рабина является нестойкой против полного раскрытия на основе направленной атаки с выбором сообщений [GMRiv]. С другой стороны, доказано, что для противника, который может провести лишь атаку с известными сообщениями, селективная подделка столь же сложна, как задача факторизации целых чисел. При этом, правда, предполагается, что пространство сообщений не является "редким".


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


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

TopList Rambler's Top100