Diffie-Hellman 私鑰使用非素數模數恢復
假設我們有一個經典的 Diffie-Hellman 密鑰交換。我們有以下公鑰參數：
p,g,y在哪裡 $ p $ 是模數， $ g $ 是基礎， $ y $ 是公鑰，並且 $ x $ 是以下等式中的私鑰：
$ y = g^x \bmod p $
碰巧模數是一個複合數，可以分解為素數。
怎麼會有人找到 $ x $ ，從而解決離散對數問題（DLP），通過將模分解為素數，並用素數求解較小的DLP，然後將它們與中國剩餘定理結合？
我們首先找到因式分解 $ p $ 作為 $ \prod p_i $ ; 然後找到 $ x_i $ 和 $ g^{x_i}\equiv y\pmod{p_i} $ 使用輔助算法來解決 DLP，也許是Pollard 的 rho和/或Pohlig-Helman。
我會假設 $ p_i $ 是不同的，這是原始問題中的情況。因此它們是互質的，並且由中國剩餘定理 $ g^x\equiv y\pmod p $ 相當於 $ \forall i, g^x\equiv y\pmod{p_i} $ .
費馬小定理告訴我們 $ g^{p_i-1}\equiv1\pmod{p_i} $ ， 自從 $ p_i $ 是一個不分裂的素數 $ g $ . 所以， $ g^x\equiv g^{x\bmod(p_i-1)}\pmod{p_i} $ . 因此找到就足夠了 $ x $ 這樣 $ \forall i,x\equiv x_i\pmod{p_i-1} $ （請參閱最後一節以獲得更好的選擇）。
問題是，模數 $ m_i=p_i-1 $ 不是互質的：首先，它們都可以被 $ 2 $ . 這可以防止以不同方式使用正常 CRT 來查找 $ x $ . 我們需要減少 $ m_i $ 為了使它們互質，同時保持它們的最小公倍數不變。
假設我們可以充分考慮 $ m_i $ : 我們收集每一個素數 $ q_j $ 在這些分解中，找到它的最大多重性 $ k_j $ （這是最大的 $ k_j $ 以便 $ q_j^{k_j} $ 劃分至少一個 $ m_i $ ）。那麼對於每個 $ q_j $ ，我們選擇一個（可能是幾個） $ m_i $ 那 $ q_j^{k_j} $ 分裂，我們彼此分裂 $ m_i $ 經過 $ q_j $ 盡可能多次。
注1：每次我們劃分一個 $ m_i $ 經過 $ q_j^{k_{j,i}} $ , 我們可以檢查 $ x_i\equiv x_j\pmod{q_j^{k_{k,j}}} $ ，否則得出無解的結論。
注2：我們可以避免完全因式分解 $ m_i $ 並使用最大公約數計算，但這有點涉及；看到這個。
如果 $ x\equiv x_i\pmod{p_i-1} $ ， 然後 $ x\equiv x_i\pmod{m_i} $ 持有減少 $ m_i $ . 如果我們在註 1 中進行檢查，則相反。我們現在可以找到合適的 $ x $ 使用正常 CRT，需要互質 $ m_i $ . 我們不需要重新計算 $ x_i $ , 但我們可以減少它們模 $ m_i $ .
如果我們沒有執行註釋 1 中的檢查，我們需要最終檢查 $ g^x\equiv y\pmod p $ .
另一個問題是 $ x\equiv x_i\pmod{p_i-1} $ 是充分但非必要條件 $ g^x\equiv g^{x_i}\pmod{p_i} $ 舉行。因此，如上應用的 CRT 可以找到一個 $ x $ 這不必要地比需要的大。解決這個問題的方法是初始化 $ m_i $ 以 $ g $ 模組 $ p_i $ ，即最小的正數 $ m_i $ 和 $ g^{m_i}\equiv1\pmod{p_i} $ . 這是一些除數 $ p_i-1 $ ， 不總是 $ p_i-1 $ 本身。