Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.3 Анализ возможностей использования интеллектуальными карточками вспомогательных вычислителей Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках Назад: 9.2.4 Ускоренное вычисление A^e modulo N   Содержание   Предметный указатель

9.2.5 Альтернативный подход

Все обсуждавшиеся до сих пор методы ускорения вычислений основывались на следующем очевидном подходе: разрабатывается некоторая криптографическая схема, а затем ищутся эффективные алгоритмы выполнения операций, требуемых для ее реализации. Альтернативный и менее очевидный подход состоит в поиске эффективно вычислимых операций и в построении криптографических схем, использующих эти операции. В литературе имеется пример применения этого подхода, основанный на алгоритмах Монтгомери [Montg].

Опишем сначала алгоритмы Монтгомери [Montg]. Первый алгоритм $ M_n(A,B)$ (рис. 12) вычисляет $ AB2^{-l(n)}\bmod n$, где $ l(n)$ -- длина числа $ n$ в битах, $ n$ нечетно.

Рис. 12
\begin{figure}\par\centerline{\it Алгоритм $M_n(A,B)$}\par\bigskip\centerline{\v...
...
\hbox{\hspace*{0em}if $R<n$\ then return($R$) else return($R-n$)}}}\end{figure}

Алгоритм $ E_n(A,p)$ (рис. 13) вычисляет $ A^p2^{-l(n)(p-1)}\bmod n$, где опять $ l(n)$ -- длина $ n$ в битах и $ n$ нечетно.

Рис. 13
\begin{figure}\par\centerline{\it Алгоритм $E_n(A,p)$}\par\bigskip\centerline{\v...
...ox{\hspace*{1em}$e\gets M_n(e,e)$}
\hbox{\hspace*{0em}return($z$)}}}\end{figure}

Возникающие в результате выполнения этих алгоритмов паразитные множители обычно предлагается подавлять с помощью дополнительной операции модулярного умножения. Однако, это снижает выигрыш, полученный от применения ускоренных алгоритмов. В работе [NM'RR] предложена остроумная идея модифицировать вместо этого сами криптографические схемы таким образом, чтобы основными операциями в них стали $ M_n(A,B)$ и(или) $ E_n(A,p)$. Такие модификации даны для ряда схем, включая криптосистему RSA, схему Диффи-Хеллмана, подпись Эль Гамаля и т.д.

Например, в криптосистеме RSA модификация состоит в вычислении шифртекста в виде $ c=E_n(m,e)=m^eN^{e-1}$, где $ N=2^{-l(n)}$, $ (n,e)$ -- открытый ключ, $ m$ -- сообщение. Получатель выполняет операцию дешифрования в виде:

$\displaystyle E_n(c,d)=c^dN^{d-1}=(m^eN^{e-1})^dN^{d-1}=m^{ed}N^{ed-1}=m\bmod
n,
$

где $ d$ -- секретный ключ.

В статье [NM'RR] со ссылкой на неопубликованную работу Арази (B. Arazi) приводятся два любопытных замечания. В первом из них, без дальнейших пояснений, указывается, что Арази доказал следующий факт: сложность (в смысле аппаратуры, памяти и времени) операции $ M_n(A,B)$ такая же как и у операции $ AB$ (без приведения по модулю). Во втором замечании более конкретно указывается следующий результат Арази: операция $ M_n$ может быть выполнена за $ l(n)+1$ цикл, т.е., с той же скоростью, что и обычное умножение.

Предварительный анализ показывает, что стойкость всех модифицированных криптографических схем такая же, как у исходных. Учитывая все сказанное выше, это означает, по существу, возможность реализации криптографических схем с такой же эффективностью, как если бы все операции выполнялись в $ \mathbb{Z}$.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.3 Анализ возможностей использования интеллектуальными карточками вспомогательных вычислителей Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках Назад: 9.2.4 Ускоренное вычисление A^e modulo N   Содержание   Предметный указатель


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