RSA - 是e=d和=de = d一個問題？
我正在大學從事小型 RSA 項目。此刻我已經這樣做了：
- 從選定的範圍生成素數數組。
- $ p $ 和 $ q $ 從這個數組中隨機選擇
- $ n $ 計算出來的
- $ \phi(n) $ 計算出來的
- $ e $ 計算出來的
- $ d $ 計算出來的
你有什麼想法 $ e $ 和 $ d $ 在這種情況下？
- $ p = 29 $
- $ q = 53 $
- $ n = 1537 $
- $ \phi(n) = 1456 $
- $ e = 545 $
- $ d = 545 $
如果 RSA 密鑰生成過程以相當大的機率結束，那將是災難性的 $ e=d $ ，因為在這種情況下，公鑰會洩露私鑰，從安全形度來看，私鑰必須是保密的。
但 $ e=d $ 是密鑰生成過程的第 1 步和第 2 步中存在的一個更大問題的症狀：只有在以下情況下，RSA 才能安全 $ p $ 和 $ q $ 以一種方式選擇，使得因式分解 $ n $ 很難，這意味著 $ p $ 和 $ q $ 應該是大素數。現代基線是 $ n $ 的 $ 2048 $ 位，即 $ 617 $ 十進制數字，不是 $ 4 $ 十進制數字。為了這， $ p $ 和 $ q $ 是在一個相當大的素數子集中隨機選擇的 $ 309 $ 位數。大約有結束 $ 10^{305} $ 這樣的素數，因此生成它們然後在其中挑選是不可行的。正確的程序是直接生成 $ p $ 和 $ q $ .
和 $ p $ 和 $ q $ 隨機素數這麼大，隨機選擇 $ e $ 這樣 $ \gcd(e,\phi(n))=1 $ （或隨機選擇的素數 $ p $ 和 $ q $ 唯一依賴於 $ e $ 那 $ \gcd(e,p-1)=1 $ 和 $ \gcd(e,q-1)=1 $ ，按照慣例），這是極不可能的 $ d=e $ ，或更一般地說，一個或幾個重新加密會導致解密。看看這些 關於 騎行攻擊的 問題。
FIPS 186-4 附錄 B.3中有 RSA 密鑰生成過程。忽略建議 $ 1024 $ -bit 密鑰大小，已過時。提議的 $ 2048 $ 是基線， $ 3072 $ 越來越普遍，延伸到 $ 4096 $ - 位不無道理。這些程序與問題中使用的程序有幾點不同，包括：
- 生成大素數 $ p $ 和 $ q $ 在規定的時間間隔內不可預測地 $ [2^{(k-1)/2},2^{k/2}] $ ， 在哪裡 $ k $ 是所需的位大小 $ n $ （例如 $ 3072 $ )
- 要求奇數 $ e $ 和 $ 2^{16}<e<2^{256} $ （越低，因為它可以防止 RSA 填充的錯誤選擇，互操作性越高，並且使其他一些錯誤的選擇成為不可能）
- 使用 $ d=e^{-1}\bmod\lambda(n) $ （在哪裡 $ \lambda $ 是Carmichael 函式) 而不是 $ d=e^{-1}\bmod\phi(n) $ . 兩者在數學上都很好，但使用 $ \lambda $ 確保產生最小的正私人指數 $ d $ 為給定的工作 $ (n,e) $ .
- 要求最小尺寸 $ d $ （遠大於 $ 2^{256} $ , 順便保證 $ d>e $ )，更多是為了防止錯誤，而不是出於數學上的需要。