SSH 如何為 RSA 算法生成密鑰？
據我了解，RSA算法的核心是有2個（大）素數’p’和’q’，所以’n=pq’。然後’n’是公鑰，‘p’是私鑰。安全性來自這樣一個事實，即給定 ’n’ 不容易獲得 ‘p’ 和 ‘q’，而檢查 ‘p’ 是否分解了 ’n’ 是微不足道的。
我的問題是，SSH 如何在不到一秒的時間內獲得這些數字？它有“素數庫”嗎？它如何確保您的“p”和“q”對您來說是獨一無二的？有這麼多“大素數”可以滿足算法的要求而沒有明顯的衝突嗎？
假設您希望“n”為 2048 位 (RSA 2048)。那麼“p”和“q”將分別為 1024 位。
電腦生成一個隨機的 1024 位數字（幾乎是瞬時的）並測試它的素數。有不同種類的素性檢驗，其中大多數是統計的。它們非常快（我知道這不是量化的，但我在沒有記憶體的 100MHz 嵌入式微控制器上工作，所以我不知道桌面上的速度）。
因此，生成一堆 1024 位數字，最終您將找到一個通過多次素性測試迭代的數字。（這裡不詳細介紹統計數據以及什麼是“足夠好”，這一切都很容易找到）。做同樣的事情來得到你的“q”，將它們相乘，你就有了你的模數“n”。“n”加上你的“e”（可能是 65537）是你的公鑰。
可以想像，質數密度會隨著數字變大而降低。有一些方法可以根據您嘗試生成的素數的大小來估計素數密度。10 歲以下的數字中有 40% 是素數，但 100 歲以下的數字只有 25% 的密度，而 1024 位數字的密度更低。如果我沒記錯的話，平均而言，您必須嘗試生成/素數測試循環約 360 次才能找到測試為素數的 1024 位數字。這不是數千或數百萬。對於 512 位數字，它可能少於 100 次嘗試。
因為數字空間 2^1024 是如此巨大，所以您的 p & q 與其他人的匹配是非常不可能的。事實上，這些 1024 位字元串中的每一個都可能在地球歷史上的任何電腦上都不存在。
我希望這能讓你充分了解它是如何工作的。基本上就是這麼簡單。我省略了一些細節，對強素數的討論等，因為它涉及超出您問題範圍的細節。