如果 Miller-Selfridge-Rabin-Test 失敗會發生什麼
MRT 是一種機率測試，即使是確定性版本也依賴於黎曼假設的正確性。
當測試失敗並且我在例如公鑰加密方法中使用非質數時：會發生什麼？我的公鑰會不會起作用，會不會有點不安全，或者會完全不安全，還是其他什麼？
順便說一句：確定性版本的使用有多普遍？
當測試失敗並且我在例如公鑰加密方法中使用非質數時：會發生什麼？
這取決於非質數的用途以及它的特性。
在RSA中，密鑰的任何使用（用於加密/解密或簽名/驗證）都構成了對可能是主要因素的費馬測試 $ p $ 和 $ q $ 公共模數的 $ n $ . 所以：
- 如果非質數 $ p $ 是一個Carmichael 數，或乘以 1¹ $ q $ 或其某些因素，以及公式 $ d=e^{-1}\bmod((p-1)(q-1)) $ 用於計算私有指數或[它被使用 $ d=e^{-1}\bmod(\operatorname{lcm}(p-1,q-1)) $ 和 $ q $ 是素數]，和 $ \gcd(p,q)=1 $ ，則該密鑰將正常工作。然而 $ n=p,q $ 將很容易考慮（相對於使用大小可比的適當 RSA 模數），因此密碼系統相對不安全。這不太可能是偶然發生的，因為卡邁克爾數字非常罕見。
- 否則，幾乎所有密鑰的使用都會失敗。特別是，如果將密鑰送出給證書頒發機構，證書籤名請求幾乎肯定無法驗證²，因此密鑰不會被認證。
確定性版本的使用有多普遍？
在生成橢圓曲線等長期參數時，通常會執行確定性素性檢驗，例如 Bernstein 的AKS的本質四次（在數學計算中，2007 年）變體（在數學分析中，2004 年）。對於單個（通常是 RSA）密鑰，生成隨機播種的可證明素數整數更為常見（因為它更快）。參見例如FIPS 186-4 附錄 B.3.3或 Marc Joye、Pascal Paillier 和 Serge Vaudenay：Efficient Generation of Prime Numbers，在CHES 2000 的程序中。
¹我懷疑如果其他因素會發生這種情況 $ q $ 是素數並且與非素數大小相同 $ p $ . 但它可能會發生，如果 $ q $ 也是複合的。例子： $$ \begin{align} p&=(6\cdot84205+1)(36\cdot84205+1)=&1531547654011\ q&=(12\cdot84205+1)(18\cdot84205+1)=&1531546643551\ n&=p,q=&2345636668938955292433061\ e&=&65537\ d&=e^{-1}\bmod((p-1)(q-1))=&748712536086026655061973 \end{align} $$ 形成一個有效的 RSA 密鑰！和 $ d=e^{-1}\bmod(\operatorname{lcm}(p-1,q-1))=1170861048741587873 $ ，情況不再如此。
² 回想一下，CSR 是使用要認證的公鑰的私鑰簽署的，並由認證機構根據該公鑰進行驗證。