Baby-step/Giant-step是Dnaiel Shanks为解决DLP问题开发的算法。DLP问题已经是许多现代密码学的困难性基础。
首先，我们回顾DLP问题。
给定一个循环群\(G\)，\(G\)的阶是\(n\)，生成元是\(g\)。给定群中的一个元素\(h\),DLP问题就是找出\(x\)满足下面的条件：
\[h = g^x\]
现在我们回到Baby-step/Giant-step算法上。
因为\(n\)是一个群的阶，因此我们知道\(0 \leq x \leq n\)。因此我们写作：
\[x = i\lceil\sqrt{n}\rceil + j\]
，其中\(0 \le i,j \le \sqrt{n}\)。
因此DLP问题可以写作
\[ h = g^{i\lceil\sqrt{n}\rceil+j}\]
\[ h*(g^{-j}) = g^{i\lceil\sqrt{n}\rceil}\]
现在问题是找到这样的\(i,j\)使得它们满足上面的条件。
一种方法就是预先计算一个表\(\{g^{i\lceil\sqrt{n}\rceil}\}\)，其中\(0 \le i \le \sqrt{n}\)和\(g^{-1}\)。对给定的\(h\)，我们迭代\(j\)计算\(h*(g^{-1})^j\)最终使得
\[ g^{i\lceil \sqrt{n} \rceil} = h(g^{-1})^j = h(g^{-j}) \]
。
一旦匹配成功，我们就能构造\(x\)，使用：
\[x = i\lceil\sqrt{n}\rceil + j\]
。
这个算法的时间复杂度是\(O(\sqrt{n})\)。但是幸运的是，这不足以推翻整个密码学。
第三十四个知识点：描述攻击离散对数问题的baby-step/Giant-step方法
原文：https://www.cnblogs.com/zhuowangy2k/p/12245615.html