第三十五个知识点：给针对ECDLP问题的Pollard rho，Pollard "Kangaroo"，parallel Pollard rho攻击的一个粗略的描述
我们的目标是对任意一个有限循环阿贝尔群\(G\)，解决离散对数问题\(h = g^x\)。问题进行详细描述，给定一个循环群\(G = <g>\)，\(G\)的阶是素数\(p\)，给定\(G\)中元素\(h\)，我们需要找到这样的\(x\)使得\(h = g^x\)成立。我们使用上一篇中的方法进行计算时，时间复杂度是\(O(\sqrt{n})\)，但是这个算法也需要\(O(\sqrt{p})\)的时间复杂度。因此，我们对使用使用更小的空间有了需求。这个任务被算法[1]实现了。
1.Pollard's Rho Algorithm
让\(f:S \rightarrow S\)是一个\(S\)到它自身的映射。\(S\)的大小是\(n\)。对于一个随机的值\(x_0 \in S\)，对于每个\(i \ge 0\)，我们计算\(x_{i+1} = f(x_i)\)。对于每一步来说\(x_{i+1} = f(x_i)\)都是一个确定的函数，我们就得到了一个确定的随机序列\(x_0,x_1,x_2...\)。
因为\(S\)是有限的，我们最终会得到\(x_i=x_j\)因此\(x_{i+1} = f(x_i) = f(x_j) = x_{j+1}\)。因此，序列\(x_0,x_1,x_2...\)将变成一个循环。我们的目标是在上述的序列中找到一个碰撞，就是找到\(i,j\)使得\(i \neq j\)并且\(x_i = x_j\)。
为了寻找一个碰撞，我们使用Floyd's发现算法，给定\((x_1,x_2)\)，我们计算\((x_2,x_4)\)，然后是\((x_3,x_6)\)等等。例如给定\((x_i,x_{2i})\)，我们就可以计算\((x_{i+1},x_{2i+2}) = (f(x_i),f(f(x_{2i}))))\)。当我们发现的时候我们有\(x_m = x_{2m}\)。此时\(m = O(\sqrt{n})\)。(这里计算出来的是当\(f\)为完全随机函数而算出的时间复杂度。)
对于离散对数问题，我们将群\(S\)人为划分成三个组\(S_1,S_2,S_3\)。我们假设\(1 \in S_2\)，然后定义下面的随机序列
\begin{aligned}
Q+R_i,R_i \in S_1 \\
2R_i,R_i \in S_2\\
P+R_i,R_i \in S_3
\end{aligned}
\right.\]
\begin{aligned}
a_i,R_i \in S_1 \\
2a_i \mod N ,R_i \in S_2 \\
a_i + 1, R_i \in S_3
\end{aligned}
\right.\]
\begin{aligned}
b_i+1,R_i \in S_1 \\
2b_i \mod N ,R_i \in S_2 \\
b_i, R_i \in S_3
\end{aligned}
\right.\]
然后我们初始化参数\((x_0,a_0,b_0)=(1,0,0)\)，我们知道对所有的\(i\)，我们有\(log_g(x_i)=a_i+b_i\)，\(log_g(h)=a_i+b_ix\)。使用Floyd's算法，我们能找到\(x_m = x_{2m}\)。这样我们就计算出了\(x = \frac{a_{2m}-a_m}{b_m-b_{2m} \mod n}\)。
我们精确的计算，如果\(f\)是完全随机的，那么时间复杂度的期望是\(O(\sqrt{n})\)。
2.Pollard's Kangaroo Method
Pollard's Kangaroo 算法和Rho算法类似，但是它更适合我们知道\(x\)在一定范围，即\(x \in [a,b]\)。
让w = b-a是区间的长度。我们定义一个集合\(S = \{s_0,...s_{k-1}\}\)是一个非降序的序列。这意味着m的值在\(N = \sqrt{w}\)附近。我们通常选择\(s_i = 2^i,0\le i <k\)。因此\(m = 2^k/k，k = 1/2*log_2(m)\)。群被分成了k个子集。我们定义一个随机的序列\(x_{i+1} = x_ig^{s_j},x_i \in S_i\)。
我们计算出确定的随机序列，从\(g_0 = g^b\)
[1] http://www.cs.bris.ac.uk/~nigel/Crypto_Book/book.ps (pages 208 - 214)