Документ взят из кэша поисковой машины. Адрес оригинального документа : http://geo.web.ru/db/msg.html?mid=1161287&uri=node132.html
Дата изменения: Unknown
Дата индексирования: Wed Apr 13 13:05:33 2016
Кодировка: koi8-r
Поисковые слова: ускорение
М. И. Анохин, Н. П. Варновский, В. М. Сидельников, В. В. Ященко "КРИПТОГРАФИЯ В БАНКОВСКОМ ДЕЛЕ" - Все о Геологии (geo.web.ru)
Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: IV. Теоретические основы Вверх: 9.3 Анализ возможностей использования интеллектуальными карточками вспомогательных вычислителей Назад: 9.3.4 Активная атака на протокол RSA-S1   Содержание   Предметный указатель


9.3.5 Ускорение операций в схемах подписи типа DSS

В работе [BQ94] предлагается метод ускорения операций в схемах подписи DSS [DSS], Шнорра [Sch], и в других подобных протоколах (в том числе, в схеме подписи ГОСТ Р 34.10-94), который является, по утверждению авторов, безопасным как против пассивных, так и против активных атак, когда сервер посылает ложные сообщения для получения полезной для себя информации.

В дальнейшем модулярные умножения будут рассматриваться как умножение 512-битовых чисел. Пусть $ \vert a\vert$ -- длина числа $ a$ в битах, то есть $ \vert a\vert=\lfloor\log_2a\rfloor+1$.


Вычисление $ a*b\bmod c$. Пусть $ a$, $ b$, $ c$ -- неотрицательные целые числа и $ a,b<c$. Карточка передает серверу значения $ a$, $ b$, $ c$. Сервер должен вычислить $ a*b\bmod c$, а интеллектуальная карточка -- убедиться, что результат корректен с высокой вероятностью.


Протокол M     1. Интеллектуальная карточка выбирает $ k$ секретных простых чисел $ p_1,\ldots,p_k$ таких, что для всех $ i$ $ \vert p_i\vert=N_v$.

    2. Интеллектуальная карточка отсылает $ a$, $ b$, $ c$ серверу.

    3. Сервер вычисляет $ \alpha=\lfloor(a*b)/c\rfloor$ и $ r=a*b\bmod c$ и отсылает $ \alpha $ и $ r$ интеллектуальной карточке.

    4. Интеллектуальная карточка проверяет, что $ \alpha<c$ и $ r<c$, а затем для каждого $ p_i$ проверяет выполнение равенства

$\displaystyle [(a\bmod p_i)*(b\bmod p_i)]\bmod p_i= [(\alpha\bmod p_i)*(c\bmod p_i)+(r\bmod p_i)]\bmod p_i. $

О корректности данного протокола говорит следующая теорема [BQ94].

Теорема 2.  Пусть $ a$, $ b$, $ c$ -- неотрицательные целые числа такие, что $ \vert a\vert,\vert b\vert,\vert c\vert\leqslant N$ и $ a,b<c$. Если интеллектуальная карточка выбирает секретно $ k$ случайных простых чисел размера $ N_v$, то вероятность принятия неправильного значения не превышает $ \left.\binom{\lfloor2N/N_v-1\rfloor}k\right/\binom Mk$, где $ M$ -- число простых чисел размера $ N_v$.


Вычисление $ a^t\bmod c$. Пусть $ a<c$ и $ t=t_0+t_12+\ldots+t_k2^k=2^{i_1}+\ldots+2^{i_v}$. Пусть $ \qopname\relax o{VER}[a,b,\alpha,r,p_v]$ -- процедура, проверяющая, что $ [a*b]\bmod p_v=[(\alpha\bmod p_v)*(c\bmod p_v)+(r\bmod p_v)]\bmod p_v$.


Протокол E     1. Интеллектуальная карточка выбирает случайным образом простое число $ p_v$, $ \vert p_v\vert=N_v$.

    2. Интеллектуальная карточка отсылает серверу $ a$, $ t$, $ c$.

    3. Сервер вычисляет и выдает интеллектуальной карточке значения векторов $ A=[\alpha_1,\ldots,\alpha_k]$, $ R=[r_1,\ldots,r_k]$, $ B=[\beta_2,\ldots,\beta_\nu]$, $ S=[s_2,\ldots,s_\nu]$ такие, что

  • для каждого $ i\geqslant 1$

    $\displaystyle \alpha_i=\lfloor(r_{i-1}*r_{i-1})/c\rfloor,\quad r_i=r_{i-1}*r_{i-1}\bmod c,$   где $\displaystyle r_0=a; $

  • для каждого $ j\geqslant 2$

    $\displaystyle \beta_j=\left\lfloor\left(r_{i_j}*s_{j-1}\right)/c\right\rfloor,\quad s_j=r_{i_j}*s_{j-1}\bmod c,$   где $\displaystyle s_1=r_{i_1}. $

    4. Интеллектуальная карточка выполняет процедуры $ \qopname\relax o{VER}[r_{i-1},r_{i-1},\alpha_i,r_i,p_v]$ для всех $ i\geqslant 1$ и $ \qopname\relax o{VER}\!\left[r_{i_j},s_{j-1},\beta_j,s_j,p_v\right]$ для всех $ j\geqslant 2$.

Если на 4 шаге все проверки завершены успешно, то $ a^t\bmod c=s_\nu$.

Теорема 3.  Если $ a$ и $ c$ -- неотрицательные целые числа длиной не более 512 битов и такие что $ a<c$, то вероятность того, что интеллектуальная карточка примет ложное значение $ a^t\bmod c$, не более $ 1/2^{20}$, если $ N_v=32$ (случай a)), и не более $ 1/2^{64}$, если $ N_v=75$ (случай b)).

Понятно, что в обоих указанных случаях обеспечивается корректность протоколов, но не секретность в отношении каких-либо аргументов вычисляемых функций, в то время как для генерации, например DSS-подписи, требуется, чтобы секретная экспонента $ t$ не была разглашена серверу или прослушивающему канал противнику. В работе [BQ94] приводится также протокол, который, по утверждению авторов, обладает обоими этими свойствами, то есть свойствами корректности и секретности в отношении экспоненты.

В этом протоколе интеллектуальной карточке необходим вспомогательный алгоритм вычисления значения функции $ a^x\bmod p$ при помощи сервера. Пусть $ x=\sum_{i=0}^{m-1}x_ib_i$, где $ 0\leqslant x_i\leqslant h$ и пусть $ a^{b_i}$ известны для каждого $ i$, тогда $ a^x$ вычисляется при помощи алгоритма, показанного на рис. 15. В этом алгоритме умножения являются модулярными, значения $ a_i=a^{b_i}$ вычисляются сервером, значение $ A$ вычисляется интеллектуальной карточкой.

Рис. 15
\begin{figure}\par\centerline{\it Алгоритм BGCW}\par\bigskip\centerline{\vbox{\t... ...ce*{0em}end; \symbol{''7B}\textrm{результат~--- $A$}\symbol{''7D}}}}\end{figure}

Ниже приводится протокол, предлагаемый [BQ94] для использования в схемах подписи.


Протокол DE

Пусть $ x\in\{0,\ldots,N\}$, например, $ \vert N\vert=$160 битов для DSS и $ \vert N\vert=$256 битов для ГОСТ Р 34.10-94. Предположим также, что $ x=\sum_{i=0}^{m-1}x_ib^i$, где $ x_i\in\{0,\ldots,b-1\}$.     1. Интеллектуальная карточка выбирает случайным образом простое число $ p_v$ размера $ N_v$ и посылает серверу $ a$, $ b$, $ p$ и $ m$.

    2. Сервер посылает интеллектуальной карточке значения $ a_i=a^{b^i}\bmod p$, где $ i=0,\ldots,m-1$ и $ a_0=a$. Так как интеллектуальная карточка знает $ a$ и $ b$, она может проверить $ a_1$ так же, как в протоколе E, затем таким же образом проверить $ a_2$ и т. д. В случае корректного завершения этих проверок интеллектуальная карточка может вычислить $ a^x\bmod p$, используя алгоритм BGCW.

Теорема 4.  Пусть $ a$ и $ p$ -- неотрицательные целые числа длиной не более 512 битов и такие что $ a<p$. Тогда вероятность того, что интеллектуальная карточка примет ложное значение $ a^x\bmod p$, не более $ 1/2^{20}$ в случае a) и не более $ 1/2^{64}$ в случае b).

Доказательство корректности основывается на теоремах 2 и 3. Безопасность протокола авторами работы [BQ94] обосновывается следующим образом. Поскольку значения параметров, полученные интеллектуальной карточкой от сервера, независимы от $ x$, протокол безопасен относительно пассивной атаки. Если сервер посылает некоторые ложные сообщения с целью получения какой-либо полезной для себя информации, то интеллектуальная карточка обнаружит это с вероятностью не менее $ 1-1/2^{20}$ или $ 1-1/2^{64}$. Следовательно, интеллектуальная карточка просто не будет использовать значение $ a^x\bmod p$. Поэтому протокол безопасен и против активной атаки.

Таким образом, ускорение безопасным образом вычислений для генерации цифровых подписей типа DSS осуществляется за счет реализации криптографических протоколов в системе "интеллектуальная карточка -- сервер". При этом коэффициент ускорения находится в диапазоне от 2,8 до 4 без снижения уровня безопасности вычислений [BQ94].

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

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