知道指數在一定範圍內是否有助於解決離散對數？

給定：

$ c=g^i \bmod P $

$ g $ 具有組大小的組生成器 $ \varphi(P) $

$ g,P,\varphi(P) $ ,c 被攻擊者

知道 他想知道 $ i $ .

現在攻擊者也知道了 $ j,k $ 和 $ j<i<k $

$ k-j $ 太大而無法全部計算，但它比組大小要小得多。

這方面的知識 $ i $ 幫助攻擊者？

可以調整基本的嬰兒步巨步算法以利用這些資訊。以下算法採用 $ \Theta(!\sqrt{k-j}) $ 組操作。

1. 讓 $ h:=c\cdot g^{-j-1} $ , 等於 $ g^{i-j-1} $ .
2. 選擇一些整數 $ m\geq\sqrt{k-j-1} $ .
3. 初始化一個空的查找表 $ T $ .
4. 對所有人 $ 0\leq a<m $ , 計算 $ g^{ma} $ 並儲存 $ T[g^{ma}]:=a $ .
5. 對所有人 $ 0\leq b<m $ , 計算 $ g^{-b}h $ 並檢查是否 $ g^{-b}h $ 在 $ T $ . 找到匹配項時，返回 $ j+1+m\cdot T[g^{-b}h]+b $ .

請注意，這幾乎完全是標準的 BSGS 算法，除了替換未知指數 $ i $ 經過 $ i-j-1 $ 在步驟 1 中並在步驟 5 中相應地調整輸出。

---

正確性：如果算法返回一些東西，它必須是形式 $ r=j+1+m\alpha+\beta $ 和 $ 0\leq\alpha,\beta<m $ 和 $ T[g^{-\beta}h]=T[g^{m\alpha}] $ . 這意味著 $$ g^r = g^{j+1+m\alpha+\beta} = g^{j+1-\beta+(i-j-1)+\beta} = g^i \text, $$ 因此 $ r=i $ （模的順序 $ g $ ).

完整性：讓 $ b:=(i-j-1)\bmod m $ 和 $ a:=(i-j-1-b)/m $ . 這些值在範圍內 $ 0\leq a,b<m $ 並滿足 $ -b+i-j-1=ma $ ，因此將由算法找到。

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