Pohlig Hellman 和小型亞群攻擊
在學習Curve25519 時，我在第 3 章中讀到了小型子群攻擊。到目前為止，我知道，您需要一個帶有小型子群的點來進行這種攻擊。Curve25519 有一個素數基點，因此它是有抵抗力的。我的問題是：這麼小的亞群攻擊是如何起作用的？能給我舉個例子？
現在我也有點迷茫了。我知道Pohling Hellman 攻擊。當橢圓曲線的域階不是素數時，您可以使用此攻擊（您也可以將它與素數域一起使用，但它沒有用）。它是如何工作的：是 $ E $ 一條橢圓曲線 $ F_p $ . 是 $ p = f_1 \cdot f_2 \cdot … \cdot f_n $ 因式分解。是 $ xP = Q $ 離散對數。現在您可以使用中國剩餘定理來求解以下方程組： $ x \cdot (p/f_1)P = (p/f_1)Q $ , $ x \cdot (p/f_2)P = (p/f_2)Q $ , … , $ x \cdot (p/f_n)P = (p/f_n)Q $ . 所以這可以用來通過只知道公鑰來計算私鑰。我的問題：我認為這兩種攻擊是相關的。但我不明白怎麼做。你能給我解釋一下嗎？
Pohlig-Hellman 算法將離散對數從一組複合階減少為素數階的子組。例如，有一條橢圓曲線和一個點 $ P $ 其階數為複合整數 $ q = p_1 \cdot p_2 $ ，我們想找到 $ k $ 這樣 $ Q = [k]P $ 對於給定的點 $ Q $ . 那麼，由於 $ [p_2]P $ 是一個程序問題 $ p_1 $ . 讓 $$ Q_2 = [p_2] Q,\quad \text{and} \quad P_2 = [p_2]P, $$ 現在我們有了 $ Q_2 = [k\bmod p_1] P_2 $ . 然後可以使用通用離散對數算法來獲得 $ k\bmod p_1 $ .
和 $ Q_1 = [p_1]Q $ 和 $ P_1 = [p_1]P $ ， 我們獲得 $ k\bmod p_2 $ 並且可以使用中國剩餘定理得到 $ k $ . 那麼，安全性主要取決於分解中的最大素數 $ q $ . 這就是為什麼點誰的順序 $ q $ 是一個大素數被選中。
在小子群攻擊中，想法是使計算發生在一個小階點而不是一個階數為大素數的點上。通常，密碼學中的標準化曲線具有順序 $ q\cdot h $ 在哪裡 $ q $ 是一個大素數並且 $ h $ 一般很小。原則是攻擊者，而不是發送程序點 $ q $ , 發送一個點 $ P $ 有秩序的 $ h $ （例如在 Diffie-Hellman 密鑰交換中）。然後計算一個秘密值 $ k $ 將會 $ Q = [k]P $ ， 但是由於 $ P $ 有訂單 $ h $ , 最多有 $ h $ 可能的值 $ Q $ .
在 Diffie-Hellman 密鑰交換中，它的工作原理如下：攻擊者發送 $ P $ 對 Alice 的小訂單，而不是其有效的公共點。愛麗絲計算 $ Q = [k]P $ 認為這一點 $ Q $ 是共享秘密，她從中派生出一個對稱密鑰來加密通信。因為只有幾個可能的值 $ Q $ , 只有幾個可能的鍵。攻擊者一一嚐試，直到解密正確。在這種情況下，他學會了 $ k \bmod h $ .
當橢圓曲線的域階不是素數時，您可以使用此攻擊（您也可以將它與素數域一起使用，但它沒有用）。它是如何工作的：是 $ E $ 一條橢圓曲線 $ F_p $ . 是 $ p = f_1 \cdot f_2 \cdot \ldots \cdot f_n $ 因式分解。
為了澄清起見，在密碼學中，橢圓曲線是在有限域上定義的，並且有限域的階數要麼是素數 $ p $ 或素數的冪 $ p^\ell $ . 該值不是曲線的階數。曲線的階數非常接近它，但通常是不同的。