(Перекрестный список на математическом стеке, ответов не получил)
Для контекста, это вопрос домашнего задания из уже сданного задания. Я ищу лучшего понимания задействованных концепций, в основном теории сложности, поскольку я не видел ее раньше за пределами этого класса (и предполагалось предварительное знание).
Меня просят оценить сложность расшифровки RSA с использованием и без использования CRT, без использования асимптотической сложности. Вместо этого используйте $c_1$ как константа модульного умножения, $c_2$ для модульного возведения в степень и $c_3$ для нахождения мультипликативного обратного.
Моя попытка: пусть $s_1$ быть длиной $р$, $s_2$ быть длиной $q$, $s$ длина $n$, и $х$ длина $д$. Обратите внимание на следующие сложности:
| вычисление |
сложность |
| $m_1=c^d\mod p$ |
$c_2s_1^2x$ |
| $m_2=c^d\мод д$ |
$c_2s_2^2x$ |
| $q^{-1}\mod p$ |
$c_3s_1$ |
| $p^{-1}\mod q$ |
$c_3s_2$ |
Таким образом, сложность использования ЭЛТ для вычисления $m=m_1(q^{-1}\mod p)q+m_2(p^{-1}\mod q)p\mod n$ является $c_1^2c_2c_3s_1^3x+c_1^2c_2c_3s_2^3x=c_1^2c_2c_3x(s_1^3+s_2^3)$.
При этом сложность вычисления $m=c^d\мод п$ является $c_2s^2x$, поэтому разница $c_2x(s^2-c_1^2c_3(s_1^3+s_2^3))$.
Я считаю, что это неправильно, так как я не думаю, что в целом верно, что $s^2\geq s_1^3+s_2^3$ (CRT должен ускорить расшифровку), и я не знаю, можем ли мы делать какие-либо предположения о константах.
