具有 3 個素數的 RSA
我試圖了解具有 3 個素數的 RSA 是如何工作的。我檢查了維基百科，但我並不完全理解他們的解決方案。我想知道你如何加密 $ n=pqr $
你如何解密它，為什麼它仍然被證明有效？
我想知道你如何加密 $ n=pqr $ ?
加密的工作原理與正常 RSA 完全相同；你填充消息 $ m $ ，然後計算 $ m^e \bmod n $ . 事實上，加密器不需要知道這是多素數 RSA，而不是正常 RSA。
你如何解密它？
好吧，你可以像普通的教科書 RSA 一樣，計算 $ m = c^d \bmod n $ 為解密指數 $ d $ .
但是，這很愚蠢；multiprime RSA 的全部意義在於它比正常 RSA 更快，而上述不是。
相反，我們首先計算三個值：
$$ m_p = (c \bmod p)^{d_p} \bmod p $$ $$ m_q = (c \bmod q)^{d_q} \bmod q $$ $$ m_r = (c \bmod r)^{d_r} \bmod r $$ 然後找到值 $ m $ 和 $ m \equiv m_p \pmod p $ , $ m \equiv m_q \pmod q $ , $ m \equiv m_r \pmod r $
這實際上比聽起來容易。使用正常的 RSA CRT，我們有 $ m_p, m_q $ , 並將它們組合成 $ m $ . 在這裡，我們做樣本，除了我們兩次兩次；首先，我們可以結合 $ m_p, m_q $ 進入 $ m_{pq} $ （和 $ m \equiv m_{pq} \pmod {pq} $ ，然後結合 $ m_{pq} $ 和 $ m_r $ 來形成 $ m $ .
為什麼它仍然被證明有效
RSA 工作的原因相同。我們有加密的結果 $ m $ 然後解密結果是相同的值模 $ p $ ; 那是因為我們設置 $ d_p = e^{-1} \pmod {p-1} $ ， 所以 $ (m^e)^{d_p} \equiv m^{e \cdot d_p} \equiv m \bmod p $ , 同樣對於 $ q $ 和 $ r $ . 因此，作為 $ p, q, r $ 是互質的，那麼如果兩者 $ m $ 最終結果介於 $ 0 $ 和 $ pqr-1 $ ，那麼它們必須相同。