RSA試題如何選擇e？

我知道我不應該要求答案，但我不是。我有解決方案，但我不明白如何選擇“e”，請參閱下面的解釋。

我正在為我的網路安全論文做練習題。

我遇到的一個問題是：“使用 RSA 技術，Alice 想向 Bob 發送數字 10。Alice 選擇了 p = 7，q = 3。為 Alice 生成。

1. 私鑰
2. 公鑰
3. 密碼

基於上述，“e”的選擇可以是

$$ 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71 $$ 為問題提供的解決方案為 e 選擇了 7，為 d 選擇了 31。這將使密碼 = 10，純文字也是 10。

解決方案是錯誤的還是我錯過了什麼？

我為 e 選擇了 5，為 d 選擇了 29，這將使密碼 82 和純文字 10。

除了詢問解決方案是否錯誤之外，是否有關於如何選擇“e”的指南？

下面是我為圖 e 和 d 編寫的程式碼。它並不完美，因為現在我需要手動更改變數的值。把它放在這裡作為我如何計算 RSA 值的參考。

#Private Key is (d, n)
#Public key is (e, n)

p = 7
q = 13
m = 10
e = 5
d = 29


n = p*q
print("n = " + str(n) + "\n")

range_n = [i for i in range(1, n + 1)]
print("Range of n")
print(range_n)
print(" ")

co_prime_n = []
for j in range_n:
   if j % p != 0 and j % q != 0:
       co_prime_n.append(j)
print("Co-Prime with n. Share no common factor with n")
print(co_prime_n)
print(" ")

totient = (p-1)*(q-1)
print("totient: " + str(totient) + "\n")

range_e = [i for i in range(2, totient+1)] #1 < e < totient
print("Range for e")
print(range_e)
print(" ")

even = 0
odd = 0
if totient % 2 == 0:
   even = 2
else:
   even = 3

if totient % 3 == 0:
   odd = 3
else:
   odd = 2

print("even: " + str(even))
print("odd: " + str(odd))
print(" ")


choices_for_e = []
for k in range_e:
   if totient % k != 0 and k % even != 0 and k % odd != 0:
       choices_for_e.append(k)
print("n = " + str(n))
print("totient: " + str(totient))
print("Choices for e. e shares no common factor with n and totient")
print(choices_for_e)
print(" ")



#d = 0
#de(mod totient) = 1

multiples_e = [x for x in range(1, 10000) if x % e == 0]

for num in multiples_e:
   if num % totient == 1:
       print(str(num), "d =", str(num/e))
print(" ")




Cipher = 0
Cipher = (m**e)%n
print("Cipher: " + str(Cipher))

PlainText = 0
PlainText = (Cipher**d)%n
print("Plain Text: " + str(PlainText))

RSA 只有在難以分解公共模數時才能安全 $ n $ ，這需要個體因素 $ n $ 大（大約數百個十進制數字）。因此選擇 $ p $ 和 $ q $ （我假設： $ p=7 $ , $ q=13 $ ) 在問題陳述中暗示我們不關心問題上下文中的安全性。

是的，選擇 $ e=7 $ 使 $ 10 $ 教科書 RSA 加密的所謂“定點”：密文等於明文。總有至少 $ 9 $ （見雨披的回答）。和 $ (e,n)=(7,7\times 13) $ ， 有 $ 49 $ 在……之外 $ 91 $ . 只是少了一點 $ (e,n)=(5,7\times 13) $ ： $ 15/91 $ . 這是一個相當大的比例，這將是一個安全問題。幸運的是，當 $ n $ 成長；例如對於 $ (e,n)=(5, 307\times 313) $ ： $ 15/96091 $ .

但同樣，問題陳述要求我們無視安全性。因此答案 $ e=7 $ 沒有“錯誤”：課堂上講的規則都沒有被打破！甚至按照這個標準 $ e=13 $ 應該是可以接受的¹，儘管它使每一個價值 $ [0,91) $ 一個固定點。

我選擇了 $ 5 $ 為了 $ e $ 和 $ 29 $ 為了 $ d $ 這將使密碼 $ 82 $ 和純文字 $ 10 $ .

對，那是正確的; 和 $ e=5 $ 似乎是一個更好（至少，更具教學性）的選擇，特別是如果問題陳述提到明文 $ 10 $ . 一些備註：

• 密碼是一種轉換。你想寫：“製作密文 $ 82 $ 和明文 $ 10 $ 。”
• 你可能會注意到提升權力 $ e=5 $ 或者 $ d=29 $ 模數 $ n=91 $ 做同樣的事情，因為 $ e\equiv d\pmod{p-1} $ 和 $ e\equiv d\pmod{q-1} $ . 因此解密和加密一樣，加密是公開的！孩子氣的低是不可避免的 $ n $ 在問題中。因此 $ n $ 是說明 RSA 的一個糟糕的教學選擇。
• 如果你想知道為什麼公式 $ d=e^{-1}\bmod((p-1)(q-1)) $ 在課程中不屈服 $ d=5 $ 什麼時候 $ d=5 $ 會工作：這個公式產生幾個工作的私人指數之一 $ d $ （假設 $ P $ 和 $ q $ 是不同的素數）。最低的積極工作 $ d $ 獲得為 $ d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1) $ . 隨著價值觀 $ p $ 和 $ q $ 手頭的產量 $ d=e\bmod12 $ 對於每一個可接受的 $ e $ .

---

如何指導 $ e $ 應該選擇？

在教科書 RSA 的此類練習中，選擇最小的 $ e $ 遵守課程設定的所有規定（就像您所做的那樣）。在你的情況下，這些處方是 $ \gcd(e,p-1)=1 $ 和 $ \gcd(e,q-1)=1 $ [或類似的東西 $ \gcd(e,(p-1)(q-1))=1 $ ]， 和 $ e>1 $ 也許還有一些上限 $ e $ 我們在選擇最低的時候不需要考慮 $ e $ . 這是選擇最低有效值的幾個優點之一 $ e $ . 另一個包括在加密成本方面經常是最優的並且總是接近最優的。

沒有唯一的數學有效範圍 $ e $ ：接受公鑰的最常見標準是 $ [3,n) $ ; 另一個生成 RSA 密鑰的標準使用 $ [65537,2^{256}) $ ; 原始的RSA 文章間接使它 $ [1,\varphi(n)) $ （它實際上計算 $ e $ 從 $ d $ ，但有缺點）；教科書 RSA 的早期實例（參見那裡的連結 2s ）使用 $ e=n $ ; 消極的 $ e $ 工作，太。

注意：驗證的程式碼部分j與 $ n $ 不需要。也許它的存在是因為您已經獲得了 RSA 正確性的部分證明，假設明文與 $ n $ . 但該條件不是必需的，可以用以下方式代替該條件進行證明： $ n $ 是不同質因數的乘積。無論如何，後面的條件通常在 RSA 中被假設（特別是在計算 totient 時）。

不要被愚弄：這個測試不是關於 RSA 實際可用或使用的。如果測試對於課程來說是足夠的，那麼對於嘗試在現實生活中使用 RSA 或實施它的人來說，該課程是不夠的。

---

其他註釋（題外話，因為我們不是程式碼審查網站）：

我對確定可能值的程式碼邏輯感到困惑 $ e $ （包括為什麼odd和even需要）。我敢打賭這是錯誤的，並且不適用於某些有效的選擇 $ p $ 和 $ q $ .

(Cipher**d)%n不適用於稍微逼真的參數，因為Cipher**d會超出電腦的容量。相反，您希望在計算中執行模組化減少。在現代 Python中，按照那裡pow(Cipher,d,n)的原則來做。

$ d $ 是通過蠻力搜尋找到的，並且無法在可接受的時間內工作以獲得更大的規模 $ p $ 和 $ q $ . 一種更有效的查找方法 $ d $ 正在計算乘法逆 $ e $ 通過（一半）擴展歐幾里得算法。事實證明，在許多現代 Python 中，必要的數學都內置在pow中，它處理負的第二個參數。

左側的程式碼#1 < e < totient與該註釋不匹配。

---

¹我的意思是從在問題設置的人為情況中獲得最高分的角度來看是可以接受的，在技術上不推薦：問題陳述中沒有任何內容！

fgrieu 的回答是正確的；我只是想補充一點：微小的 RSA 模數往往表現得很奇怪；也就是說，以大模量沒有表現出來的方式。

例如，所有 RSA 模數（由兩個不同的奇質數組成）對於任何允許的 $ e $ ，其中三個是明顯的（0, 1, n-1），但至少有六個不明顯的。對於較大的模數，碰到這樣一個固定點的機率很小；對於一個小的模數，選擇一個的機率是相當不錯的。

而且，您在問題中提到的模數 $ n = 3 \times 7 $ 更糟；任何 $ e $ 這不是 2 或 3 個作品的倍數；然而對於任何 $ e \equiv 1 \bmod 6 $ ，所有點都是一個不動點（因此對於 $ e=7 $ ，不僅 10 是您觀察到的固定點，而且所有其他消息也是如此）。而如果 $ e \equiv 5 \bmod 6 $ （唯一的另一種可能性），並非所有消息都是固定點，而是 $ e=d $ 在這種情況下有效。

底線：試圖用如此小的值來學習 RSA 可能會產生很大的誤導……

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