RSA 加密密鑰條件

我最近閱讀了 RSA 密碼系統，但現在我在密鑰生成階段感到困惑。根據歐拉定理，我們只有一個條件：

ed = k.φ (N) + 1

在哪裡：

• “e”是加密密鑰。
• “d”是解密密鑰。
• “N”是一個 p*q 形式的數字，其中 p 和 q 都是素數。
• “φ(N)”等於(p-1)(q-1)。

但一些文件將新條件規定為：

1. e 應該很小。
2. gcd(φ(N),e)=1。
3. e 應該是奇數

現在，我的問題是為什麼我應該滿足這三個條件？

我認為第二個和第三個條件只是為了確保**“d”**也是一個整數，因為d = (k.φ(N) + 1)/e. 我對麼？

最後，我認為第一個條件是為了確保**“d”**足夠大。我對麼？

為什麼我要滿足這些？

1. $ e $ 應該很小。

有3個原因

• 這是為了提高公鑰操作（加密和簽名驗證）的速度，在 RSA 中，這需要的時間大致與 $ \log e $ .
• 它確保與某些實現的兼容性，這限制了 $ e $ 到 32（或者是 31）位。
• 它使得不可能使用一個小的 $ d $ ，這會破壞安全性。問題的最後一段是正確的。

請注意，出於歷史原因，您還會發現一些建議 $ e $ 是不是太小了。確實， $ e\le1 $ 這將是一個可怕的想法。歸根結底，最常見和最令人反感的是 $ e=F_4=2^{(2^4)}+1=65537 $ ， 在哪裡 $ F_4 $ 是已知的最大的費馬素數。

2. $ \gcd(\varphi(N),e)=1 $ .

在這， $ \varphi(N) $ 僅在符號上有所不同 $ \phi(N) $ 或者是 $ \Phi(N) $ 在問題的“ $ \phi(N) $ 等於 $ (p-1)(q-1) $ ”。這就是歐拉方程。 $ \varphi(N)=(p-1)(q-1) $ 持有時 $ N=p\cdot q $ 和 $ p $ 和 $ q $ 不同的素數，當 $ p $ 和 $ q $ 是足夠隨機選擇的素數。

和 $ \gcd(\varphi(N),e)=1 $ 對於（整數）的存在是必要的 $ k $ 和 $ d $ 這樣 $ e\cdot d=k\cdot\varphi(N)+1 $ .

$ e $ 應該是奇數。

除非 $ p $ 或者 $ q $ 是 $ 2 $ ，這將是一個壞主意，從 $ e\cdot d = k\cdot(p-1)(q-1)+1 $ .

我認為第二和第三個條件只是為了確保 $ d $ 也是一個整數，因為 $ d=(k\cdot\varphi(N)+1)/e $ .

呃，沒有。整數和位串是密碼學中唯一的數據表示形式，而在 RSA 中，它們通常按照大端約定同化，所以一切都是整數。

那存在 $ k $ 和 $ e\cdot d=k\cdot\varphi(N)+1 $ 或（等效地） $ d=(k\cdot\varphi(N)+1)/e $ 可以注意到 $ d\equiv e^{-1}\pmod{\varphi(N)} $ ， 這意味著 $ d $ 是（一個整數代表）的倒數 $ e $ 在整數模的乘法群中 $ \varphi(N) $ .

引用自：https://crypto.stackexchange.com/questions/91414