Вперед: 9.3 Анализ возможностей использования интеллектуальными карточками вспомогательных вычислителей
Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках
Назад: 9.2.4 Ускоренное вычисление A^e modulo N
  Содержание
  Предметный указатель
Все обсуждавшиеся до сих пор методы ускорения вычислений
основывались на следующем очевидном подходе: разрабатывается
некоторая криптографическая схема, а затем ищутся эффективные
алгоритмы выполнения операций, требуемых для ее реализации.
Альтернативный и менее очевидный подход состоит в поиске
эффективно вычислимых операций и в построении криптографических
схем, использующих эти операции. В литературе имеется пример
применения этого подхода, основанный на алгоритмах
Монтгомери [Montg].
Опишем сначала алгоритмы Монтгомери [Montg]. Первый
алгоритм (рис. 12) вычисляет
, где -- длина числа в
битах, нечетно.
Рис. 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}](http://images.geo.web.ru/pubd/2001/10/10/0001161287/img1136.gif) |
Алгоритм (рис. 13) вычисляет
, где опять -- длина
в битах и нечетно.
Рис. 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}](http://images.geo.web.ru/pubd/2001/10/10/0001161287/img1139.gif) |
Возникающие в результате выполнения этих алгоритмов
паразитные
множители обычно предлагается подавлять с помощью
дополнительной
операции модулярного умножения. Однако, это снижает выигрыш,
полученный от применения ускоренных алгоритмов. В работе
[NM'RR] предложена остроумная идея модифицировать вместо
этого сами криптографические схемы таким образом, чтобы
основными операциями в них стали и(или)
.
Такие модификации даны для ряда схем, включая криптосистему
RSA,
схему Диффи-Хеллмана, подпись Эль Гамаля и т.д.
Например, в криптосистеме RSA модификация состоит в вычислении
шифртекста в виде
, где
, -- открытый ключ, --
сообщение. Получатель выполняет операцию дешифрования в
виде:
где -- секретный ключ.
В статье [NM'RR] со ссылкой на неопубликованную работу
Арази (B. Arazi) приводятся два любопытных замечания. В первом из
них, без дальнейших пояснений, указывается, что Арази доказал
следующий факт: сложность (в смысле аппаратуры, памяти и
времени) операции такая же
как и у операции (без приведения по модулю). Во втором
замечании более конкретно указывается следующий результат
Арази: операция может быть выполнена за
цикл, т.е., с той же скоростью, что и обычное умножение.
Предварительный анализ показывает, что стойкость всех
модифицированных криптографических схем такая же, как у
исходных. Учитывая все сказанное выше, это означает, по
существу, возможность реализации криптографических схем с такой
же эффективностью, как если бы все операции выполнялись в
.
Вперед: 9.3 Анализ возможностей использования интеллектуальными карточками вспомогательных вычислителей
Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках
Назад: 9.2.4 Ускоренное вычисление A^e modulo N
  Содержание
  Предметный указатель
|