使用 CRT 進行 RSA 解密：它如何影響複雜性？
有一個使用 CRT 的 RSA 的有效變體：
$$ \begin{align*} d_p &= d \pmod{p-1}\ d_q &= d \pmod{p-1} \ q_{\operatorname{inv}} &= q^{-1} \pmod{p} \end{align*} $$
其中解密如下：
$$ \begin{align*} c_p &= c \pmod{p} \ c_q &= c \pmod{q} \ m_p &= c_p^{d_p} \pmod{p} \ m_q &= c_q^{d_q} \pmod{q} \ h &= q_{\operatorname{inv}}(m_p - m_q) \pmod{p} \end{align*} $$
我的第一個問題相當籠統：我在哪裡使用 CRT 算法（因為它寫在那裡）？我的意思是 RSA 的設置已經定義了我 $ p,q,d,c $ 所以我沒有一致性系統。
我的第二個問題涉及復雜性。認為 $ \log d = \log n = B $ 和 $ \log p = \log q = \frac{B}{2} $ 和 $ d, d_p, d_q $ 有同樣多的 $ 0 $ 沙 $ 1 $ s。關於 size 的操作次數我能說什麼 $ B $ 這個變種？
有一個使用 CRT 的 RSA 的有效變體
實際上，按照我們通常使用術語的方式，它不是“變體”，而是替代實現。也就是說，對 RSA 算法所做的唯一更改是私有操作的完成方式（以及私有密鑰的格式）；任何只做公共操作的人都不需要知道私有（簽名生成或公鑰解密）實現正在做什麼。
我在哪裡使用 CRT 算法（因為它寫在那裡）？
每當您想要更高的效率（4 倍）並且不介意一點點額外的複雜性時。大多數情況下，這是一個值得權衡的選擇。
我的意思是 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 $ 有同樣多的 0 和 1。關於 size 的操作次數我能說什麼 $ B $ 這個變種？
實際上，0 和 1 的數量幾乎是不相關的，我們可以對一個 $ B $ 位值與 $ (1 + o(1)) \log_2 B $ 模乘法（與指數的漢明權重無關）；在 B 的考慮範圍內，這可能是 $ (1 + 1/6) \log_2 B $ .
使用教科書的 RSA 私有操作，這涉及到單個模冪 $ B $ 位值由 a $ B $ 位指數；這是關於 $ (1 + 1/6) \log_2 B $ 倍增。如果我們使用 $ O(n^2) $ 模乘算法（這對於我們討論的 B 的範圍是最優的 - 存在具有較低漸近複雜度但具有更大的比例常數的乘法常式），我們正在談論 $ (1 + 1/6) (\log_2 B)^3 $
現在，對於 CRT，有兩個模冪 $ B/2 $ 一點一點 $ B/2 $ 位指數（加上之前和之後的一些操作 - 這些都相對較快）。使用相同的邏輯，這大約需要 $ 2 (1 + 1/6) (\log_2 B/2)^3 = 1/4 (1 + 1/6) (\log_2 B) $ ，也就是快4倍左右（是的，這是忽略了一些小因素）；然而，即使我們考慮到這些小因素，CRT 仍然要快得多