Насколько быстр алгоритм RSA?
«Операция RSA», будь то шифрование, дешифрование, подпись или проверка, по существу является модульным возведением в степень. Это вычисление выполняется серией модульных умножений.
В практических приложениях обычно выбирают небольшой открытый показатель для открытого ключа. На самом деле целые группы пользователей могут использовать один и тот же общедоступный показатель, каждый с разным модулем. (Существуют некоторые ограничения на простые множители модуля, когда общедоступная экспонента фиксирована.) Это делает шифрование быстрее, чем дешифрование, и проверку быстрее, чем подпись. С типичными алгоритмами модульного возведения в степень, используемыми для реализации алгоритма RSA, операции с открытым ключом выполняются за O(k^2) шагов, операции с закрытым ключом выполняются за O(k^3) шагов , а генерация ключа занимает O(k^4) шагов, где k — количество битов в модуле. Методы «быстрого умножения», такие как методы, основанные на быстром преобразовании Фурье (БПФ), требуют асимптотически меньшего количества шагов. На практике, однако, они не так распространены из-за их большей сложности программного обеспечения и того факта, что они могут быть медленнее для типичных размеров ключей.
Скорость и эффективность многих коммерчески доступных программных и аппаратных реализаций алгоритма RSA быстро растут; последние данные см. на http://www.rsasecurity.com/.
Для сравнения, DES (см. раздел 3.2) и другие блочные шифры намного быстрее, чем алгоритм RSA. DES обычно как минимум в 100 раз быстрее в программном обеспечении и от 1000 до 10000 раз быстрее в аппаратном, в зависимости от реализации. Реализации алгоритма RSA, вероятно, немного сократят разрыв в ближайшие годы из-за высокого спроса, но блочные шифры также станут быстрее.
