RSA 中的 lcm 與 phi
在教科書 RSA 中，歐拉[Math Processing Error] $ \varphi $ 功能
$$ \varphi(pq) = (p-1)(q-1) $$ 用於定義私有指數[Math Processing Error] $ d $ . 另一方面，現實世界的密碼規範需要 Carmichael lcm 函式 $$ \lambda(pq) = \operatorname{lcm}(p-1,q-1) $$ 界定[Math Processing Error] $ d´ $ . 很明顯， $ d´ $ 劃分[Math Processing Error] $ d $ ，因此使用 $ d´ $ 可能比使用更有效[Math Processing Error] $ d $ .
我的問題是：是否還有其他原因，例如關於安全性，為什麼不應該使用[Math Processing Error] $ d $ ?
我將使用這些常見的定義和符號：
- [Math Processing Error] $ a\equiv b\pmod c $ 表示 $ c>0 $ 且 $ c $ 除以 $ b-a $
- [Math Processing Error] $ a\equiv b^{-1}\pmod{c} $ 表示 $ a\cdot b\equiv 1\pmod{c} $
- $ a=b\bmod c $ 表示 $ a\equiv b\pmod{c} $ 和 $ 0\le a<c $
- $ a=b^{-1}\bmod c $ 表示 $ a\equiv b^{-1}\pmod c $ 和 $ 0\le a<c $
- [Math Processing Error] $ \varphi $ 是歐拉函式（也註明[Math Processing Error] $ \phi $ ）
- [Math Processing Error] $ \lambda $ 是Carmichael 函式
我限制為不同素數的[Math Processing Error] $ N $ 乘積；對於兩個這樣的素數， $ \varphi(N)=(p-1)\cdot(q-1) $ ， $ \lambda(N)=\operatorname{lcm}(p-1,q-1) $ 和 $ \varphi(N)=\lambda(N)\cdot\gcd(p-1,q-1) $ 。
加密標準PKCS#1要求私有指數[Math Processing Error] $ d $ 是一個整數，其中 $ 0<d<N $ 和 $ e\cdot d \equiv1\pmod{\lambda(N)} $ 。使用後面的條件是因為它恰好是[Math Processing Error] $ d $ 上的充分必要條件，因此教科書 RSA 可以工作，即：
$$ \forall x\in{0,\dots,n-1}, y=x^e\bmod N\implies x=y^d\bmod N $$ 請注意， $ e\cdot d \equiv1\pmod{\lambda(N)} $ 或等效的 $ d\equiv e^{-1}\pmod{\lambda(N)} $ 沒有唯一地定義[Math Processing Error] $ d $ 。如果[Math Processing Error] $ d $ 是一個有效的私有指數，那麼從數學的角度來看 $ k\cdot\lambda(N)+d $ 也是一個有效的私有指數[Math Processing Error] $ \forall k\in\mathbb Z $ ，並且從 PKCS#1 的角度來看，當 $ 0<d<N $ 。
使用 $ d=e^{-1}\bmod\varphi(N) $ 符合 PKCS#1 標準；它唯一地定義了[Math Processing Error] $ d $ 的值，其中 $ 0<d<N $ 因為 $ \varphi(N)\le N $ 和 $ d\equiv e^{-1}\pmod{\lambda(N)} $ 因為 $ \lambda(N) $ 除 $ \varphi(N) $ 。d的這種常見選擇將導致與使用任何其他有效d在取模N的d次[Math Processing Error] $ d $ 冪時完全相同的結果。據我們所知，即使考慮到側通道攻擊，它也不比使用d=e^{-1}\bmod\lambda(N)安全。[Math Processing Error] $ d $ [Math Processing Error] $ d $ [Math Processing Error] $ N $ $ d=e^{-1}\bmod\lambda(N) $
使用 $ d=e^{-1}\bmod\lambda(N) $ 而不是 $ d\equiv e^{-1}\pmod{\varphi(N)} $ 不是一個好的速度優化：如果對速度感興趣，一個根本不使用[Math Processing Error] $ d $ ！相反，人們使用中國剩餘定理 (CRT) 來實現 RSA ，其中求冪以每個素數[Math Processing Error] $ p $ 除以N為模[Math Processing Error] $ N $ ，使用可以計算為 $ d_p=e^{-1}\bmod{(p-1)} $ 的指數無論選擇哪個[Math Processing Error] $ d $ 。
更新：正如評論中所指出的，FIPS 186-4標準需要[Math Processing Error] $ 2^{\lceil\log_2(N)\rceil/2}<d<\lambda(N) $ 。使用 $ \lambda(N) $ 而不是 $ \varphi(N) $ 限制為單個私有指數，從而簡化用於認證的已知答案測試；以數學上最令人滿意的方式做到這一點；並且恰好簡化了要求 $ 2^{\lceil\log_2(N)\rceil/2}<d $ ，旨在排斥使用為低d設計的 $ p $ 、 $ q $ 和/或e的一些危險想法，否則需要表示為繁瑣的2^{\lceil\log_2(N)\rceil/2}<\big(d\bmod\lambda(N)\big)。 $ e $ [Math Processing Error] $ d $ [Math Processing Error] $ 2^{\lceil\log_2(N)\rceil/2}<\big(d\bmod\lambda(N)\big) $