ECC 上的 Pohlig-Hellman 和 Shanks 算法

首先，對不起我的英語不是我的自然語言，其次，我希望我在正確的部分發帖。

所以讓我們解釋一下我的問題。

我正在嘗試實現基於橢圓曲線的 Pohlig-Hellman 算法，每次迭代都使用 Baby-Steps-Giant-Steps。

我的 Python 實現使用具有平滑素數模數的有限域曲線 $ N = 28533593*4339 $ .

隨著曲線： $ y^2 = x^3 + 521x + 1331 $ 上 $ \mathbb{F}_{26596586063} $

和發電機 $ G = (20197258757, 24233149744) $

從理論上講，如果我理解正確，Baby-Steps-Giant-Steps 階段中最糟糕的複雜性將是 $ \sqrt{4339} $ ， 正確的 ？

我的實現似乎有效（我有正確的解決方案），但我沒有正確的複雜性：Polhig-Hellman 問題減少似乎沒用，因為我與 Baby-Steps-Giant-Steps 單獨執行具有相同的複雜性。

當我嘗試求解離散對數時： $ H = xG $ ，我的實現執行複雜度為： $ O(\sqrt{x}) $ 大約。

我不明白我的錯誤，我很困惑……

感謝您的回答。

這是我的實現（在 Python 中）：

def baby_step_giant_step(curve, G, H, order):

   m = int(math.ceil(gmpy2.sqrt(order)))
   L = {}


   # Baby steps
   for j in range(0, m):
       P_tmp = curve.mul(j, G)
       L[str(P_tmp)] = j

   mG = curve.mul(m, G)

   # Giant steps
   for i in range(0, m):
       P_tmp = curve.mul(i, mG)
       if not P_tmp.isInf():
           P_tmp = ecc.Point(P_tmp.x, (-P_tmp.y) % curve.p)

       P = curve.add(H, P_tmp)

       index = str(P)

       if index in L:
           return (L[index] + i*m) % curve.p

   return None

# Solve the equation : G^x = H (mod curve.p)
def pohlig_hellman(curve, G, H):
   N = curve.p-1
   factors = decompose_order(N)
   x = 0


   for i in range(len(factors)):
       ni = factors[i][0]**(factors[i][1])
       tmp = N//ni
       G_prime = curve.mul(tmp, G)
       H_prime = curve.mul(tmp, H)

       # Now, use the Baby Step Giant Step algorithm to solve :
       # H_prime = x_prime*G_prime
       x_prime = baby_step_giant_step(curve, G_prime, H_prime, ni)
       while x_prime == None:
           order *= 2
           x_prime = baby_step_giant_step(curve, G_prime, H_prime, ni)

       # Use the CRT to solve the equation x_prime = x (mod ni)
       (gcd, x0, x1) = xgcd(ni, tmp)

       x += x_prime*x1*tmp

   return x % N

# (A, B, N)
curve = ecc.Curve(521, 1331, 26596586063)
G = ecc.Point(20197258757,24233149744)

H = curve.mul(523151, G)

x = pohlig_hellman(curve, G, H)
print("x = %s" % x)

PS：不要害怕 WHILE 循環，它只是為了調試目的。

雖然我無法執行腳本（也許是我的錯，我的 Python 技能充其量只是平庸），但讓我嘗試（稍微）詳細說明 fkraiem 的評論。

Pohlig-Hellman 的複雜性低於 BSGS 的複雜性（對於平滑階曲線），您確實是對的。但是，您的參數相對較小。看大的定義 $ O $ 符號，我們看到這條推理將忽略一些常數。也就是說，粗略地，複雜度 $ O(\sqrt{x}) $ 意味著有一些常數 $ c $ 這樣對於大參數，複雜性將是 $ \leq c\sqrt{x} $ . 然而，這只是關於大參數值的陳述，對於專門選擇的（小）參數沒有太大意義。例如，算法複雜的情況 $ O(t) $ 比複雜的算法慢 $ O(t^2) $ 對於特定的實例很容易實現。請注意，這裡的 small 和 large 的定義很大程度上取決於上下文。

話雖如此，我不確定這是否真的是這裡的問題。Iirc Pohlig-Hellman 對於小參數的表現並不差，BSGS 也沒有。也許你應該小心你如何衡量你的複雜性。是執行時間、曲線運算次數、場乘法次數等？可能存在一些與影響複雜性的算法無關的成本。

編輯： 好的，您的問題中有一些令人困惑的部分。讓我們把細節弄清楚。我們假設一條曲線 $ E:y^2=x^3+521x+1331 $ 在場上 $ \mathbb{F}_{26596586063} $ . 正如你所說，這條曲線上的點形成了一組秩序 $ N=28533593*4339 $ , 有一些發電機 $ G $ . 假設有一些 $ H\in E $ 這樣 $ H=\ell G $ 為了 $ \ell\in[1,..,N] $ . 我故意命名標量 $ \ell $ 與 $ x $ 避免與曲線變數混淆 $ x $ . 讓我們比較一下解決這個 DLP 的兩種方法（有點濫用符號）：

1. **BSGS：**在一組訂單上做 BSGS $ N $ 有復雜性 $ O(\sqrt{N}) $ 並將給我們 $ \ell\pmod{N} $ .
2. Pohlig-Hellman： 執行 PH 會將 DLP 分成四個部分。我們解決了四個具有各自複雜性的較小 DLP $ O(\sqrt{2}) $ , $ O(\sqrt{853}) $ , $ O(\sqrt{3593}) $ 和 $ O(\sqrt{4339}) $ （這些是你的 $ ni $ ’s), 得到 $ \ell\pmod{2} $ , $ \ell\pmod{853} $ , $ \ell\pmod{3593} $ 和 $ \ell\pmod{4339} $ . 然後我們使用 CRT 來恢復 $ \ell\pmod{N} $ . 因此我們有復雜性 $ O(\sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339}) $ 對於小型 DLP。請注意，我們忘記了實際減少到這些小訂單 DLP 的成本。

我們得出的結論是，對於 BSGS，我們的複雜性約為 $ \sqrt{N}\approx 163085 $ 而對於 Pohlig-Hellman 我們只有大約 $ \sqrt{2}+\sqrt{853}+\sqrt{3593}+\sqrt{4339}\approx 156 $ .

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