9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках

Алгоритмические и криптографические проблемы, возникающие при разработке систем, основанных на использовании интеллектуальных карточек очень тесно связаны. Действительно, от того, насколько эффективно можно реализовать тот или иной алгоритм (например, теоретико-числовой), зависит выбор криптографической техники, а, значит, в конечном счете, и решение многих системотехнических задач. Рассмотрим некоторые из алгоритмических проблем, которые возникают при использовании интеллектуальных карточек, в частности, в качестве средства аутентификации информации.

Большинство известных криптоалгоритмов [RSA], [Sch], [FS86], [DSS], ГОСТ Р 34.10-94, пригодных для реализации в интеллектуальных карточках в качестве основной криптографической операции, используют дискретное возведение в степень (причем степень в данном случае может быть и 2). Стойкость соответствующих криптографических схем основывается (как правило, гипотетически) или на сложности извлечения корней в кольце ,  -- произведение двух больших простых чисел, или на трудности вычисления дискретных логарифмов в поле ,  -- большое простое число. Чтобы противостоять известным на данный момент методам решения этих задач операнды должны иметь длину порядка 512 или 1024 битов. Понятно, что выполнение вычислений над операндами повышенной разрядности (еще будет употребляться термин "операнды многократной точности" по аналогии с операндами однократной и двукратной точности [Кнут]) требует высокого быстродействия рабочих алгоритмов криптографических схем. Современный микрокомпьютер обеспечивает, например, шифрование одного блока из 200 десятичных цифр в криптосистеме RSA со скоростью всего лишь несколько битов в секунду. Однако специализированные СБИС, разрабатываемые для этой криптосистемы, поднимают потолок быстродействия до нескольких Кбитов/сек и выше.

Основной операцией в указанных криптографических схемах, как уже было сказано, является операция дискретного возведения в степень. Разработкой быстрых и эффективных алгоритмов для реализации операции такого типа активно занимаются специалисты большинства промышленно развитых стран (см. таблицу 1). Полученные результаты вызывают определенный оптимизм. Так, в работе [Se] ведется разговор уже о скорости шифрования порядка 3 Мбитов/сек.

• 9.2.1 Представление чисел
• 9.2.2 Ускоренное вычисление A*B modulo N
• 9.2.3 Методы ускорения операции сложения
• 9.2.4 Ускоренное вычисление A^e modulo N
• 9.2.5 Альтернативный подход