Существует эффективный вариант RSA с использованием CRT.
На самом деле, как мы обычно используем термины, это не «вариант», а альтернативная реализация. То есть единственные изменения, внесенные в алгоритм RSA, касаются того, как выполняется частная операция (и формат закрытых ключей); любой, кто выполняет только публичные операции, не должен знать, что делает частная реализация (генерация подписи или расшифровка открытого ключа).
Где использовать CRT-алгоритм (как там написано)?
Всякий раз, когда вы хотите немного больше эффективности (4x) и не возражаете против дополнительной сложности. В большинстве случаев это выгодный компромисс.
Я имею в виду, что установка RSA уже определяет меня p, q, d, c, и поэтому у меня нет системы соответствий.
Собственно, все дополнительные параметры $d_p, d_q, qinv$ легко вычисляются во время генерации ключа, что мы обычно и делаем.
Предполагать $\log d = \log n=B$ и $\log p = \log q = B/2$ и $d,d_p,d_q$ имеют одинаковое количество нулей и единиц. Что уж говорить о количестве операций размером $В$ этого варианта?
На самом деле количество нулей и единиц в основном не имеет значения, мы можем выполнить модульное возведение в степень $В$ битовое значение с $(1 + о(1)) \log_2 В$ модульные умножения (не зависящие от веса Хэмминга показателя степени); в рассматриваемом диапазоне B это может быть $(1 + 1/6) \log_2 В$.
В частной операции учебника RSA это включает в себя одно модульное возведение в степень $В$ битовое значение на $В$ битовая экспонента; это о $(1 + 1/6) \log_2 В$ умножается. Если мы используем $ О (п ^ 2) $ модульный алгоритм умножения (который является оптимальным для обсуждаемого нами диапазона B - существуют процедуры умножения с меньшей асимптотической сложностью, но с гораздо большими константами пропорциональности), мы говорим о $(1 + 1/6) (\log_2 В)^3$
Теперь, с ЭЛТ, есть два модульных возведения в степень двух $B/2$ бит за $B/2$ битовая экспонента (плюс некоторые операции до и после - они оба относительно быстрые). Используя ту же логику, это занимает около $2 (1 + 1/6) (\log_2 B/2)^3 = 1/4 (1 + 1/6) (\log_2 B)$, то есть примерно в 4 раза быстрее (да, это без учета некоторых мелких факторов); однако, даже если мы учтем эти небольшие факторы, ЭЛТ по-прежнему значительно Быстрее
