М. И. Анохин, Н. П. Варновский, В. М. Сидельников, В. В. Ященко "КРИПТОГРАФИЯ В БАНКОВСКОМ ДЕЛЕ"

Геовикипедия
wiki.web.ru

Поиск

Главная страница

Конференции: Календарь / Материалы

Каталог ссылок

Словарь

Форумы

В помощь студенту

Последние поступления

Геология | Курсы лекций

Обсудить в форуме

Добавить новое сообщение

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

9.3.3 Пассивная атака на протокол RSA-S1

В описании пассивной атаки предполагается, что противнику известна пара значений такая, что $y=x^d\bmod n$ . Например, в случае схемы электронной подписи RSA противнику нужно получит пару (сообщение, подпись).

1. Вычисляются значения $z_i=x^{d_i}\bmod n$ , $i=1\dots m$ .

2. Вычисляются произведения $y_F=\prod_{i=1}^mz_i^{f_i}\bmod n$ для всех векторов таких, что $\qopname\relax o{Weight}(F)\leqslant\lceil L/2\rceil$ .

3. Вычисляются значения $y_F*=yy_F^{-1}\bmod n$ для всех векторов .

4. Значения сортируются и сравниваются со значениями . Если $y_{F_1}=y_{F_2}*$ и $F_1\neq F_2$ , то вектор включается в список "кандидатов", содержащий секретный вектор .

5. Если вектор не определен однозначно при помощи данной процедуры, необходимо повторить ее для новой пары значений . При этом на шаге 2 вектора выбираются из списка, оставшегося после предыдущей итерации.

Эта процедура является корректной, так как

$\displaystyle y\equiv\prod_{i=1}^mz_i^{f_i}\equiv \prod_{i=1}^mz_i^{f_{1,i}+f_{2,i}}\equiv y_{F_1}y_{F_2}\mkern5mu({\rm mod}\,\,n).$

Таким образом $y_{F_1}\equiv yy_{F_2}^{-1}\equiv y_{F_2}*\mkern5mu({\rm mod}\,\,n)$ .

Количество значений ограничено сверху величиной $N=\sum_{i=0}^{\lceil L/2\rceil}\binom mi$ , их сортировка и дальнейшие вычисления потребуют не более, чем $N\log N$ операций.

Михаил Анохин

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