Аппаратно RSA примерно в 1000 раз медленнее DES. Скорость работы самой быстрой СБИС-реализации RSA с 512-битовым модулем - 64 килобита в секунду [258]. Существуют также микросхемы, которые выполня-
ют 1024-битовое шифрование RSA. В настоящее время разрабатываются микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1 Мбит/с. Возможно, они появятся в 1995 году. Производители также применяют RSA в интеллектуальных карточках, но эти реализации медленнее .
Программно DES примерно в 100 раз быстрее RSA. Эти числа могут незначительно измениться при измен е-нии технологии, но RSA никогда не достигнет скорости симметричных алгоритмов . В 15-й приведены примеры скоростей программного шифрования RSA [918].
Табл. 19-4. Скорости RSA для различных длин модулей при 8-битовом открытом ключе (на SPARC II)
| 512 битов | 768 битов | 1024 бита | |
| Шифрование | 0.03 с | 0.05 с | 0.08 с |
| Дешифрирование | 0.16 с | 0.48 с | 0.93 с |
| Подпись | 0.16 с | 0.52 с | 0.97 с |
| Проверка | 0.02 с | 0.07 с | 0.08 с |
Программные Speedups
Шифрование RSA выполняется намного быстрей, если вы правильно выберете значение е. Тремя наиболее частыми вариантами являются 3, 17 и 65537 (216 + 1). (Двоичное представление 65537 содержит только две единицы, поэтому для возведения в степень нужно выполнить только 17 умножений.) Х.509 советует 65537 [304], РЕМ рекомендует 3 [76], a PKCS #1 (см. раздел 24.14) - 3 или 65537 [1345]. Не существует никаких проблем безопасности, связанных с использованием в качестве е любого из этих трех значений (при условии, что вы дополняете сообщения случайными числами - см. раздел ниже), даже если одно и то же значение е используется целой группой пользователей.
Операции с закрытым ключом можно ускорить при помощи китайской теоремы от остатках, если вы сохр а-нили значениям и д, а также дополнительные значения: d mod (р - 1), d mod (д - 1) и д1 mod p [1283, 1276]. Эти дополнительные числа можно легко вычислить по закрытому и открытому ключам .
Безопасность RSA
Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел . Технически, это утверждение о безопасности лживо. Предполагается, что безопасность RSA зависит от проблемы разложения на множители больших чисел. Никогда не было доказано математически, что нужно разложить п на множители, чтобы восстановить от по с и е. Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Я не слишком волнуюсь об этом.
Также можно вскрыть RSA, угадав значение (p-l)(q-l). Это вскрытие не проще разложения п на множители [1616].
Для сверхскептиков: доказано, что некоторые варианты RSA также сложны, как и разложение на множители (см. раздел 19.5). Загляните также в [361, где показано, что раскрытие даже нескольких битов информации по зашифрованному RSA шифротексту не легче, чем дешифрирование всего сообщения .
Самым очевидным средством вскрытия является разложение п на множители. Любой противник сможет получить открытый ключ е и модуль п. Чтобы найти ключ дешифрирования d, противник должен разложить п на множители. Современное состояние технологии разложения на множители рассматривалось в разделе 11.4. В настоящее время передним краем этой технологии является число, содержащее 129 десятичных цифр . Значит, п должно быть больше этого значения. Рекомендации по выбору длины открытого ключа приведены в разделе 7.2.
Конечно, криптоаналитик может перебирать все возможные d, пока он не подберет правильное значение. Но такое вскрытие грубой силой даже менее эффективно, чем попытка разложить п на множители.
Время от времени появляются заявления о том, что найден простой способ вскрытия RSA, но пока ни одно из подобных заявлений не подтвердилось. Например, в 1993 году в черновике статьи Вильяма Пейна (William Payne) был предложен метод, основанный на малой теореме Ферма [1234]. К сожалению, этот метод оказался медленнее разложения на множители
Существует еще один повод для беспокойства. Большинство общепринятых алгоритмов вычисления простых чисел р и д вероятностны, что произойдет, если р или д окажется составным? Ну, во первых, можно свести вероятность такого события до нужного минимума. И даже если это произойдет, скорее всего такое событие будет
сразу же обнаружено - шифрование и дешифрирование не будут работать . Существует ряд чисел, называемых числами Кармайкла (Carmichael), которые не могут обнаружить определенные вероятностные алгоритмы пои с-ка простых чисел. Они небезопасны, но чрезвычайно редки [746]. Честно говоря, меня бы это не обеспокоило.