RSA 的多個私鑰

在 RSA 加密場景中，Bob 的公鑰對 $ (n, e) $ 是 $ (143, 43) $ . 攻擊者馬洛里嘗試蠻力並來到 $ d = 7 $ 作為私鑰。

的價值 $ φ(143) = 120 $ 馬洛里不知道。

然而從 $ 43 \cdot d \equiv 1 \pmod{120} $ , 可以計算出第一個正元素 $ d = 67 $ 從全等類 $ d = 67 + 120n $ 和 $ n \in \mathbb{Z} $

$ d = 7 $ 顯然不適合那個同餘類，那麼它怎麼能成功解密加密呢？

這個問題可以概括為：攻擊者發現了一個 $ d $ 不滿足 $ e \cdot d \equiv 1 \pmod{ \phi(n) } $ ，但它有效；這是怎麼回事。

事實證明 $ e \cdot d \equiv 1 \pmod{ \phi(n) } $ 沒有必要（足夠了）。

充分必要條件是：

$$ e \cdot d \equiv 1 \pmod{p-1} $$ $$ e \cdot d \equiv 1 \pmod{q-1} $$

如果這兩個都成立，那麼 $ d $ 將永遠有效

$$ 1 $$; 相反，如果 $ d $ 總是有效，那麼這兩個都成立。 這兩個條件可以概括為一個關係：

$$ e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)} $$

這個 $ \text{lcm}(p-1, q-1) $ 模量被稱為 Carmichael 函式 $ n $ .

在你的具體例子中， $ \text{lcm}(p-1, q-1) = 60 $ ，我們有 $ 7 \cdot 43 \equiv 1 \pmod{60} $ ， 因此 $ d = 7 $ 作品

---

$$ 1 $$： 假設 $ p, q $ 是不同的素數。

可以通過兩種方式找到 RSA 私鑰 $ n = p\cdot q $ , $ p = 11 $ 和 $ q = 13 $

1. 如果在RSA 論文中使用Euler 的 totient 函式：$$ \varphi(n)= (p-1)(q-1) = 120 $$然後使用

• $ d = 67 = e^{-1} \bmod 120 $

2. 如果按照FIPS 180.4的要求 使用Carmichael 函式並在PKCS#1 v2.2 標準中允許：$$ \lambda(n) = \text{LCM}(p-1,q-1) = 60 $$然後使用

• $ d= 7 = e^{-1} \bmod 60 $

兩者都是有效的，並且 Carmichael 函式始終提供最小的 $ d $ . 他們兩個之間的簡單關係是 $ \lambda(n)| \varphi(n) $ . 因此，這表明在某些設置中，我們可以擁有多個有效的私鑰，其中每個 $ \leq \varphi(n) $ . 實際上，在兩個不同的素數情況下，我們有關係；

$$ \varphi(n) = \lambda(n) \cdot \gcd(p-1,q-1). $$這是因為$$ a \cdot b = \operatorname{lcm}(a,b) \times \gcd(a,b) $$

由於 RSA 素數是不同的奇素數 $ p $ 和 $ q $ ， 然後 $ \gcd(p-1,q-1) \geq 2 $ 這意味著總是至少有兩個 $ d $ 在範圍內 $ [1,\varphi(n)] $ 和 $ \lambda(n) \neq \varphi(n) $ .

這是你的情況，你有 $ \varphi(n) $ 攻擊者有 $ \lambda(n) $ .

---

PKCS#1 標準要求使用 Carmichael 函式計算 $ d $ . 原始RSA 論文使用了歐拉的 totient 函式。使用更短的 $ d $ 將減少簽名時間和較少使用的解密時間。

---

Carmichael 函式：對於一個正整數 $ n $ , $ \lambda(n) $ 被定義為最小的正整數 $ k $ 這樣 $$ a^k \equiv 1 \pmod n $$ 對所有人 $ a $ 這樣 $ \gcd(a,n)=1 $

---

小證明 $ \lambda(n)| \varphi(n) $ :

證明依賴於群論的指數定義。

讓 $ G $ 是組然後是理想的非負生成器 $ {z \in \mathbb{Z}: \forall g \in G (g^z=1)} $ 被稱為群的指數 $ G $ . 對於RSA群這樣的有限群，它是有限正的，然後是最小的正自然數 $ z $ 這樣 $ g^z=1 $ 對所有人 $ g \in G $ .

任何有限群的指數必須整除群的階。 $ \lambda(n) $ 是定義的指數，組的階是 $ \varphi(n) $ 也根據定義。這清楚地暗示 $ \lambda(n)| \varphi(n) $ .

---

2個以上私鑰範例；

• $ n = 6901 $
• 因素 $ 6901 = 103 \cdot 67 $ , $ p=103,q=67 $
• $ \varphi(n) = 6732 $
• $ \lambda(n) = 1122 $
• $ e = 43 $
• $ g =\gcd(p-1,q-1)=6 $
• 倒數 $ e $ 經過 $ d = \varphi(n) = 5323 $
• 倒數 $ e $ 經過 $ d’ =\lambda(n) = 835 $

現在都 $ d+k\cdot \lambda(n) $ 是有效的私鑰，其中 $ k \in [0,g] $ ， 清單;

1. 835
2. 1957
3. 3079
4. 4201
5. 5323
6. 6445

---

SageMath 程式碼找到上面的例子；

p = random_prime(200, 400) #upper and lower range
q = random_prime(200, 400)
n = p*q
e = 43
print("n = ",n)
print("factors %s = " % n, factor(n))

phi = (p-1)*(q-1) # or call euler_phi(n)
print("phi    = ",phi)

if gcd(e,phi) != 1:
   print( gcd(e,phi))
   
lmd = lcm(p-1,q-1) #or call carmichael_lambda(n)

print("lambda = ",lmd)

print("gcd(%s,%s) = " % (p-1,q-1), gcd(p-1,q-1))

print("inverse of %s by phi   " %e, inverse_mod(e,phi))
print("inverse of %s by lambda" %e, inverse_mod(e,lmd))

d = inverse_mod(e,lmd)

for k in range(gcd(p-1,q-1)):
   print(d+k*lmd)

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