Rsa
驗證 RSA 公鑰
可以對公鑰執行哪些類型的測試來檢查它是否可能是有效的密鑰？測試應該相對較快 - 即不是計算密集型 - 並且不包括模冪運算。
我問這個問題是因為開發人員通常按照fail fast的原則工作（或應該工作） ，其中一旦檢測到錯誤就會拋出。
作為一個例子，我可以指出公鑰不應該包括模數和公共指數的負整數。請假設 RSA 公鑰由兩個整數值組成；編碼相關的問題應該被忽略。
給定一對整數 $ (n,e) $ ，如果以下任何一項成立（並且我們應該停在第一個）：
- $ e $ 甚至。
- $ n $ 是偶數（從技術上講，教科書 RSA 適用於偶數 $ n $ ，但是明文的奇偶校驗就是密文的奇偶校驗，這太糟糕了，它不被認為是 RSA）。
- $ e<3 $
- $ n<\ell $ , 對於某些限制 $ \ell $ 這取決於安全上下文：
- $ n<15 $ 不值 RSA 密鑰的名稱。
- 我從來沒見過 $ n<2^{320} $ 在生產環境中使用（自 1983 年以來，當我開始監視該領域時），但是 $ n<2^{321} $ 位在 2000 年代初期仍在使用。 $ n<2^{511} $ 然後是不安全的，並且不再在新應用程序中大量使用。
- 到 2022 年： $ n<2^{639} $ 提供很少的安全性，它已被公開展示 $ n<2^{829} $ 不安全，也許 $ n<2^{1024} $ 對州級攻擊者來說是不安全的。在實踐中， $ n<2^{1023} $ 即使在低安全性應用程序 AFAIK 中也不再使用，並且 $ n<2^{2047} $ 不再推薦在新應用程序中使用。
- 此外，一些安全標準要求 $ n $ 在一個精確的集合中；例如FIPS 186-4，嚴格要求 $ n\in[2^{1023},2^{1024}]\cup[2^{2047},2^{2048}]\cup[2^{3071},2^{3072}] $ .
- $ e\ge n $ （因為這不符合PKCS#1）。如果與舊實現的互操作性很重要，則可以將其更改為 $ e\ge2^{32} $ （或者 $ e\ge2^{256} $ 對於 FIPS 186-4)。但更大 $ e $ 數學上沒問題（ $ e=n $ 在數學上總是可以的，甚至在 RSA 出版之前就由 Clifford Cocks 提出，參見參考文獻 2s那裡）。
- 它被使用 $ \ell\ge2^{128} $ 大約在測試 4 中（這意味著我們甚至很少關心安全性），並且 $ \gcd(n,a)\ne1 $ 為方便的最高固定常數 $ a $ A070826的成員，例如 $ a=3710369067405<2^{32} $ （第一個產品 $ 11 $ 奇數素數）或 $ a=16294579238595022365<2^{64} $ （第一個產品 $ 15 $ 奇數素數）。這發現了一些小因素 $ n $ 單次掃描完整 $ n $ ， 計算 $ n’=n\bmod a $ .
- $ n $ 是一個正方形（這使得教科書 RSA 對於某些明文是不可逆的，並且使得 $ n $ 容易考慮）。執行此測試的標準方法在FIPS 186-4 附錄 C.4中。但我們只能將其用作最後的手段。通過測試 2 確定 $ n $ 很奇怪， $ n $ 只能是正方形，如果 $ n\bmod8=1 $ ，即三個低位 $ n $ 是
001。現在假設它們是：如果以及何時發現一些奇怪的素數 $ r $ 和 $ \left(\frac rn\right)=-1 $ （這是雅可比符號）， $ n $ 不能是正方形。每增加 $ r $ 測試有近 50% 的機會證明非病理性生成的非方形 $ n $ . 此外，如果我們計算 $ n’=n\bmod a $ 在測試 6 中，我們可以使用 $ n’ $ 執行這個 $ \left(\frac rn\right)=-1 $ 測試素數 $ r $ 劃分 $ a $ 無需掃描 $ n $ 再次，非常快。這使得相對昂貴的全面方形測試很少需要。注意：可以用比 6 中說明的更多的小素數來測試可除性；也許，測試 $ \gcd(n,e)\ne1 $ ; 和/或，根據*“不包括模冪運算”*的解釋，某種程度的Pollard 的 rho或其他因式分解方法可能是一種選擇；但是對於其中任何一個，我們都會受到收益遞減的打擊。此外，測試它是有意義的 $ n $ 不是素數（這會使 RSA 不安全），但這似乎需要某種形式的模冪運算。