Rsa
具有多個素數模積的 RSA
我想問一下如果我們建構一個模數大於 2 個素數乘積的 RSA 系統會發生什麼，例如讓 $ n=p_{1}p_{2}…p_{L} $ . 我只知道經典的 RSA 系統 $ n=pq $ 和 $ p $ 和 $ q $ 大素數。我猜模數 $ n=p_{1}p_{2}…p_{L} $ 這不是一個好主意，因為可以使用中國剩餘定理輕鬆解密消息？
誰能解釋我們如何處理許多素數的模乘積？
PKCS#1 標準支持具有兩個以上的質因數。這稱為“多素數”鍵。
從好的方面來說，這可能會提供一些性能改進。中國剩餘定理仍然適用（例如參見第5.1.2節，該描述包含兩個以上的素數）。例如，如果您有一個 1536 位模數，它是三個 512 位素數的乘積，那麼 CRT 將一個 1536 位求冪替換為三個 512 位求冪，這三個 512 位求冪分別快 27 倍（假設經典三次模冪算法），總加速為 9，與通常的 4 相比，有兩個因素。更一般地，與 $ k $ 因素，預期的 CRT 加速大約在 $ k^2 $ .
不利的一面是，使用太小的因子可能會削弱模量。最知名的因式分解算法的成本取決於模數大小，而不是單個因子的大小，因此使用更多更小的因子應該沒有影響……除非這些因子小到足以進入可行的範圍ECM：該算法的成本（主要）取決於最小因子的大小。對於正常的雙質 RSA 模數，ECM 與 GNFS 沒有競爭力；但是，如果您將因素設置得太小，則會降低您的安全性。
底線是，對於通常的尺寸，三個或四個素數應該是可以容忍的，並且可以提供很好的性能提升，但不要超出這個範圍。公鑰操作不會受到任何影響。另請注意，其他一些相關的密碼系統（例如Rabin）可能不接受多素數模數。