Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.3.3 Пассивная атака на протокол RSA-S1 Вверх: 9.3 Анализ возможностей использования интеллектуальными карточками вспомогательных вычислителей Назад: 9.3.1 Предположения и общая модель вычислений для ускорения RSA-преобразований для схемы из [MKI]   Содержание   Предметный указатель

9.3.2 Протокол ускорения вычислений для RSA-преобразований

Пусть в интеллектуальной карточке хранятся целые числа $ x$, $ d$, $ n$ и необходимо вычислить $ y=x^d\bmod n$, причем $ d$ является секретным параметром интеллектуальной карточки, в то время как целые $ n$ и $ e$, такие что $ ed\equiv1\mkern5mu({\rm mod}\,\,\varphi(n))$, -- общедоступны. Целое $ n$ есть произведение секретных простых $ p$ и $ q$.


Протокол RSA-S1     0. Интеллектуальная карточка генерирует случайным образом целочисленный вектор $ D=[d_1,d_2 ,\ldots,d_m]$ и двоичный вектор $ F_0=[f_1,f_2,\ldots,f_m]$ такие, что

$\displaystyle d\equiv(f_1d_1+f_2d_2+\ldots+f_md_m)\mkern5mu({\rm mod}\,\,\varphi(n)), $

где $ 1\leqslant d_i<n$ и вес Хэмминга вектора $ F_0$: $ \qopname\relax o{Weight}(F_0)=\sum_{i=1}^mf_i\leqslant L$, где $ L$ и $ m$ -- некоторые общедоступные целочисленные параметры, выбираемые интеллектуальной карточкой.

    1. Интеллектуальная карточка отсылает $ n$, $ D$ и $ x$ серверу.

    2. Сервер вычисляет $ z_i=x^{d_i}\bmod n$ и возвращает интеллектуальной карточке вектор $ Z=[z_1,z_2,\ldots,z_m]$.

    3. Интеллектуальная карточка вычисляет $ y=y_m$ с помощью алгоритма, показанного на рис. 14.

Рис. 14. Вычисление $ y$ в протоколе RSA-S1
\begin{figure}\par\centerline{\it }\par\bigskip\centerline{\vbox{\tt \hbox{\hsp... ...*{0em}end; \symbol{''7B}\textrm{результат~--- $y_m$}\symbol{''7D}}}}\end{figure}

Так как шаг 0 может быть выполнен предварительно, то для каждого $ x$ интеллектуальной карточке достаточно сделать не более $ L-1$ умножений по модулю $ n$. Коммуникационная сложность оценивается как $ 2(m+1)$ целых чисел длиной не более $ \lfloor \log n\rfloor$ битов.

В работе [MKI] утверждается, что если криптосистема RSA является стойкой (однако не указывается, в отношении какой атаки и угрозы криптосистема является стойкой), протокол является безопасным в том смысле, что для вычисления $ d$ противнику потребуются выполнить перебор не менее $ \sum_{i=1}^L\binom mi>\binom mL$ векторов. Однако, как мы увидим далее, эта граница может быть значительно снижена.

Протокол RSA-S2 из работы [MKI] является усовершенствованием протокола RSA-S1 на основе китайской теоремы об остатках.

В работе [PW92] исследуется безопасность протоколов из работы [MKI]. В частности, говорится, что утверждение о том, что если криптосистема RSA является стойкой, то наилучшая возможная атака эквивалентна полному перебору всех векторов веса не выше $ L$, некорректно. На самом деле объем перебора может быть значительно меньше. Кроме того, в [MKI] не рассматривались активные атаки (при этом под активной атакой понимается ситуация, когда сервер отклоняется от протокола, то есть посылает интеллектуальной карточке ложный вектор $ Z*=[z_1',z_2',\ldots,z_m']$ взамен $ z_i=x^{d_i}\bmod n$, а под пассивной атакой понимается ситуация, когда сервер никогда не отклоняется от протокола, то есть всегда посылает корректные степени $ x^{d_i}\bmod n$).

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.3.3 Пассивная атака на протокол RSA-S1 Вверх: 9.3 Анализ возможностей использования интеллектуальными карточками вспомогательных вычислителей Назад: 9.3.1 Предположения и общая модель вычислений для ускорения RSA-преобразований для схемы из [MKI]   Содержание   Предметный указатель

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