是否有一種可行的方法來手動生成 RSA 密鑰，就像生成 ECC 密鑰一樣？
在橢圓曲線中，私鑰只是一個隨機數，與其他加密系統相比是一個相對較小的數字（例如，ECC 為 256 位，RSA 為 4096 位）。
假設我不信任硬體隨機數生成器（電子生成器），並且我想要一種可審計的方式來生成私鑰。對於橢圓曲線，拋硬幣 256 次並標註結果形成 256 位隨機數是可行的。您可以通過 n 面骰子切換它以加快該過程。
現在，對於 RSA，密鑰不僅僅是一個隨機數。它是兩個隨機素數的乘積。我不知道如何找到這些隨機素數的細節。它們是由隨機數生成的嗎？如果有，這個數字有多長？
如果這個數字仍然很長，您知道手動生成 4096 位 RSA 密鑰的可行方法嗎？
PS：我知道在這兩種情況下手動從私鑰進行公鑰數學運算都需要數年時間。我只想手動生成密鑰（在 ECC 的情況下）或密鑰種子（在 RSA 的情況下），所以我可以插入 2 台完全不同的氣隙電腦並查看公鑰是否匹配，這將是一個非常信號好。
您可以通過僅翻轉 256 個硬幣隨機或多或少均勻地選擇一個 1024 位素數。但它有額外的計算成本。這是一個在初始硬幣翻轉後具有確定性的簡單算法：
- 翻轉 256 個硬幣，產生一個比特串 $ s $ .
- 計算 $ p_0 = \operatorname{SHAKE128-1024}(s) \mathbin| 1 $ 並將其解釋為 little-endian 位順序的整數。（這 $ \cdots \mathbin| 1 $ 迫使它變得奇數，省去了為素數測試大偶數的浪費精力。）
- 計算素數證書 $ p_0 $ ，例如Pratt 證書（需要計算 $ p_0 - 1 $ ) 或Pocklington-Lehmer 證書（需要計算 $ p_0 - 1 $ , 直到下面的複合因子 $ \sqrt{p_0 - 1} $ ) 或Atkin–Goldwasser–Kilian–Morain橢圓曲線素數證明證書（需要約 512 位素數，並在橢圓曲線上進行一些算術運算）。
- 如果事實證明 $ p_0 $ 是複合的，然後再試一次 $ p_1 = p_0 \pm 2 $ ， 等等。如果你打 $ 2^{1024} $ 或者 $ 2^{1023} $ ，你可能犯了一個錯誤。
生成 RSA 密鑰。 您可以使用相同的 256 位種子 $ s $ 選擇兩個主要因素 $ p $ 和 $ q $ RSA 模數的 $ n $ ，例如通過拆分輸出 $ \operatorname{SHAKE128-2048}(s) $ 成兩個 1024 位整數 $ p_0 $ 和 $ q_0 $ 而不是步驟（2）。如果你得到了，你也會想和下一個候選人再試一次 $ \gcd(e, \operatorname{lcm}(p - 1, q - 1)) \ne 1 $ ， 在哪裡 $ e $ 是你最喜歡的指數，它應該是 3 或 65537，除非你對指數有不拘一格的品味。
效率。 主題有多種變化：例如，您可以使用試驗劃分來節省一些工作，或者以較小的成本使用更快的試驗序列來實現分佈的均勻性（但要小心，否則您可能會犯十億歐元的錯誤在你的手上）。
顯然，步驟 (3) 的計算量比隨機均勻地生成橢圓曲線標量要多得多，即使您進行了必要的拒絕採樣以避免（可忽略的）模偏差。計算和硬幣翻轉之間的匯率是多少？
您可以通過首先進行快速機率素數測試來節省大量計算，例如 128 個獨立的拉賓測試，這可以相當高地確定您找到了素數，但這會花費更多的硬幣翻轉成本。
如果您相信擴展的黎曼假設，您甚至可以避免額外的硬幣翻轉並使用確定性變體，即米勒檢驗（無付費牆），它以首次重新發布俄羅斯數學家 М.М 小說結果的人的名字命名. Артюхов英文。它甚至可能比找到一個 ECPP 證書表現得更好。
素數與素數測試的選擇。 所有這一切都需要筆和紙的計算能力付出相當大的努力。 但是你可以編寫一個電腦程序來完成步驟 (1) 中拋硬幣之後的所有事情，並將拋硬幣的結果提供給該電腦程序。 即使它使用機率素數測試，素數的選擇也將是（除非素數測試失控）擲硬幣結果的確定性函式。
使用素數證書，作為獎勵，您可以獲得可驗證的證明，證明它是素數，您可以獨立驗證，以防萬一有宇宙射線槍的神對您的計算傲慢感到憤怒，決定破壞您的速度比紙筆還快電腦。
（您可能也希望對證書保密。）