使用 CRT 使用多個素數模數進行 RSA 加密和解密
我在網際網路上找到的關於 RSA-CRT 加密/解密的每條資訊都只使用兩個素數。我對使用多個（最多 8 個）素數的項目感興趣。
總體構想是計算 $ d_p = d\bmod(p-1) $ , $ d_q = d\bmod(q-1) $ ， 和 $ q_\text{inv} = q^{-1}\bmod p $ ， 在哪裡 $ p $ 和 $ q $ 是素數。
加密和解密是基於之間的“邏輯關係” $ p $ 和 $ q $ 而且我無法將其擴展到兩個以上的素數。誰能解釋如何使用多個素數？
RSA 私鑰操作（用於解密和簽名生成）相當於解決 $ x $ 方程 $ y\equiv x^e\pmod N $ , 知道 $ y $ , 公共模數的因式分解 $ N $ 進入 $ k\ge2 $ 不同的素數 $ N=r_1\dots r_k $ , 公共指數 $ e $ 這樣 $ \gcd(e,r_i-1)\ne1 $ ， 然後 $ 0\le x<N $ .
為了有效地實現，我們可以解這個方程模 $ r_i $ ; 然後使用CRT將我們已經有解決方案的模數產品之間的解決方案組合起來，直到達到一個解決方案模數 $ N $ . 自 2.1 版以來隱含在PKCS#1v2中的常用方法是：
預先計算以下數量 $ d_i $ （CRT 指數）和 $ t_i $ （CRT 逆/係數），例如在密鑰生成時，包括私鑰中的結果：
- 為了 $ i\in{1,\dots,k} $
- $ d_i\gets e^{-1}\bmod(r_i-1) $ , 或等效地 $ d_i\gets d\bmod(r_i-1) $
- $ m\gets r_1 $
- 為了 $ i $ 從 $ 2 $ 至 $ k $
- $ t_i\gets m^{-1}\bmod r_i $
- $ m\gets m\cdot r_i $
當需要使用私鑰並解決時 $ y\equiv x^e\pmod N $
為了 $ i\in{1,\dots,k} $ $$ note: should be parallelized if possible $$
- $ x_i\gets(y\bmod r_i)^{d_i}\bmod r_i $
$ x\gets x_1 $ , $ m\gets r_1 $
為了 $ i $ 從 $ 2 $ 至 $ k $ [循環不變數： $ 0\le x<m $ , $ y\equiv x^e\pmod m $ ]
- $ x\gets x+m\cdot((x_i-x\bmod r_i)\cdot t_i\bmod r_i) $
- $ m\gets m\cdot r_i $
正確性來自循環不變數。有關歸因，請參見此問題。請參閱另一個以了解位大小的 $ N $ 與最大合理數量的素數有關。這被稱為 Garner 算法，請參閱應用密碼學手冊，第14.5.2節。
具有 3 個素數的人為小範例：
e=5 r1=931164518537359 r2=944727352543879 r3=982273258722607 N=864102436520313334659779717201860718296307527 d1=558698711122415 d2=566836411526327 d3=785818606978085 t2=360227672914825 t3=882117903741868 y=529481440313141057262802385309623737292746309 x1=436496882968258 x2=903092574358267 x3=806961802724 x=710532117316769399313215266414 (when i=2) x=111222333444555666777888999000000000000000042與標準（非 CRT）實施相比，節省的工作量最多（和接近）一個因素 $ k^2 $ , 如果模乘有成本 $ \mathcal O(n^2) $ 對於論據 $ n $ 位。節省的時間可以更高，最多（和接近）一個因素 $ k^3 $ 如果使用並行化 $ k $ 獨立的 modexp 單位。
進行最終檢查至關重要 $ y\equiv x^e\pmod N $ ，且不透露 $ x $ 否則。如果不採取這種預防措施，實施將容易受到主要的“Bellcore”故障攻擊：D. Boneh、RA DeMillo、R. Lipton；關於消除密碼計算錯誤的重要性（密碼學雜誌 14(2)，2001 年）。
應充分保護實現免受各種其他攻擊，包括時序、功率分析和其他邊通道攻擊。
該問題還提到了加密，其中只有公鑰 $ (N,e) $ 是已知的，而不是因式分解 $ N $ . 因此，對於那個 RSA 公鑰操作（也用於簽名驗證），沒有類似的快捷方式適用於計算 $ y\gets x^e\bmod N $ . 但是，通常情況下，與 RSA 私鑰操作相比，這仍然是低成本的，因為 $ e $ 通常很小。
後期添加： $ e $ 必須與每個 $ r_i-1 $ . 通常它首先選擇一個奇數 $ e $ , 和 $ r_i $ 來匹配這個條件。範圍為 $ e $ 是一個有爭議的話題，請參閱此處和此處的討論。我的觀點是，除了實施攻擊之外，還有具有安全證明的填充（RSA-KEM、RSAES-OAEP、RSASSA-PSS、ISO/IEC 9796-2 方案 2 或 3），沒有充分的理由要求最低限度 $ e $ 比大 $ 3 $ ; 並且不會因為使用而被解僱 $ e=2^{16}+1 $ , 符合處方 $ 2^{16}<e<2^{256} $ FIPS 186-4的，並且是一個費馬數 $ F_i=2^{\left(2^i\right)}+1 $ 這使得給定尺寸的最佳效率 $ e $ , 和 prime 選擇 $ r_i $ 稍微容易一些，而且範圍更廣。