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

4.2.7 Схемы RSA и Рабина

В данном подразделе мы приводим описание схем подписи, основанных на криптосистемах RSA [RSA] и Рабина [Rab79]. В схеме RSA подписывающий выбирает два различных больших простых числа $ p$ и $ q$, которые играют роль секретного ключа, и публикует соответствующий открытый ключ $ (n,e)$, где $ n=pq$, а $ e$ -- некоторое число, взаимно простое с $ \varphi(n)=(p-1)(q-1)$ ($ \varphi$ -- функция Эйлера). Подписью для сообщения $ m$ является $ s(m)=h(m)^d\bmod
n$, где $ d=e^{-1}\bmod\varphi(n)$ (очевидно, что, зная $ p$ и $ q$, можно эффективно вычислить $ d$) и $ h$ -- хэш-функция. Проверка подписи $ s$ для сообщения $ m$ состоит в проверке сравнения $ s^e\equiv h(m)\mkern5mu({\rm mod}\,\,n)$.

Схема Рабина основана на том, что, зная различные простые числа $ p$ и $ q$, можно эффективно извлекать квадратные корни по модулю $ n=pq$, тогда как без знания этих простых чисел вышеуказанная задача вычислительно сложна. Секретный ключ в этой схеме тот же, что и в схеме RSA, а открытым ключом является $ n=pq$. В качестве пространства сообщений выступает множество всех квадратов элементов группы $ \mathbb{Z}_n*$. Подписью для сообщения $ m$ является произвольный квадратный корень из $ h(m)$ по модулю $ n$, а проверка подписи $ s$ для сообщения $ m$ состоит в проверке сравнения $ s^2\equiv h(m)\mkern5mu({\rm mod}\,\,n)$.

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


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 4.2.8 О схемах, основанных на функциях с секретом Вверх: 4.2 Примеры схем электронной подписи Назад: 4.2.6 Схема Фиата - Шамира   Содержание   Предметный указатель


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