破解Diffie-Hellman的方法（小非素數）
我想知道如何打破 DH（小非素數）。假設我們不知道：
$ a $ : Alice 的私鑰
$ b $ : Bob 的私鑰
我們知道：
$ N $ : 非質數
$ p $ , $ q $ : $ N = p * q $ ( $ p $ 和 $ q $ 是質數）
$ g $ : 基礎
$ A $ : Alice 的公鑰
A = pow(g, a, N)$ B $ : Bob 的公鑰
B = pow(g, b, N)現在我們要計算
shared_secret = pow(A, b, N)或shared_secret = pow(B, a, N)如果我們想找到共享秘密，我們需要找到私鑰 $ a $ 或者 $ b $ 第一的。我們現在有 $ g^{a} \equiv A \bmod pq $
接著
$ {x_p} $ 和 $ g^{x_p} \equiv A \bmod p $
$ {x_q} $ 和 $ g^{x_q} \equiv A \bmod q $
接著
$ x_p \equiv x \bmod p-1 $
$ x_q \equiv x \bmod q-1 $
我知道在那之後我們需要使用中國提醒定理，但我不知道如何開始。有什麼建議麼？
如果我們想找到共享秘密，我們需要找到私鑰 $ a $ 或者 $ b $ 第一的
不，有兩個原因：
- $ a $ 不需要。_ 發現問題說明了什麼 $ x_p $ 和 $ x_q $ ，很容易計算出共享秘密約簡模 $ p $ , 和模 $ q $ ，然後使用直漢語提醒定理找到共享秘密。它告訴你什麼時候 $ p $ 和 $ q $ 是互質數（包括此處和 RSA 中的不同質數），並且 $ 0\le m<p,q $ ， 它擁有 $$ \begin{align} &m_p=m\bmod p\quad\text{and}\quad m_q=m\bmod q\ \iff&m=\left(\left(\left(q^{-1}\bmod p\right),(m_p-m_q)\right)\bmod p\right)q+m_q\end{align} $$
- 我們找不到 $ a $ 當然，因為可以有幾個等價的 $ a $ （就像有幾個等價的私人指數一樣 $ d $ 在 RSA 中）。我們能做到的最好的目標就是找到一份工作 $ a $ ，或最好的最小正工作 $ a $ .
提示如果我們想找到一個 $ a $ :
- 使用費馬小定理定義模方程 $ a $ , $ x_p $ 和 $ p $ ; 和一個類似的只涉及 $ a $ , $ x_q $ 和 $ q $ . 這個問題幾乎做到了，但是如果我們堅持如下所述的正確符號，則需要額外的括號來修正方程，並且相同的數量由兩個不同的字母表示，從而造成混淆。
- 然後解決 $ a $ 使用中國提醒定理的一個輕微變體，適用於模不是互質的情況：我們首先將其中一個模除以模的大公約數，相應地調整方程，然後回到直 CRT。
筆記： $ u\equiv v\pmod n $ 是一個符號，意思是 $ n $ 劃分 $ u-v $ , 對於某個整數 $ n>0 $ . 然而 $ v\bmod n $ 之前沒有左括號 $ \bmod $ 是唯一定義的整數 $ u $ 和 $ 0\le u<n $ 和 $ u\equiv v\pmod n $ . 和 $ v^{-1}\bmod n $ 是唯一定義的整數 $ u $ 和 $ 0\le u<n $ 和 $ u,v\equiv1\pmod n $ ， 假設 $ \gcd(v,n)=1 $ . 裸括號，運算符 $ \bmod $ 被理解為在添加左側的內容後進行評估（停在第一個 $ = $ )，但是當模數是和時最好使用顯式括號，如 $ u\bmod(n-1) $ . 另外最好避免 $ u\equiv v\bmod n $ 並使用
\pmod而不是\bmodif $ u\equiv v\pmod n $ 是指，或使用 $ u=v\bmod n $ 如果 $ 0\le u<n $ 另外暗示。