52 Things: Number 35: Give the rough idea of Pollard rho, Pollard "kangaroo" and parallel Pollard rho attacks on ECDLP.
52件事：第35件：大致了解Pollard rho、Pollard“袋鼠”和平行的Pollard rho对ECDLP的攻击。 This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this blog post we discuss the Pollard rho, Pollard "kangaroo" and parallel Pollard rho attacks on ECDLP.这是一系列博客文章中的最新一篇，旨在解决“每个博士生都应该知道的52件事”做密码学：这是一组问题，旨在让博士生在第一年结束时了解他们应该知道什么。在这篇博客文章中，我们讨论了Pollard-rho、Pollard-“袋鼠”和平行的Pollard-rho对ECDLP的攻击。
Our aim is to solve the discrete logarithm problem, h = gx for any cyclic finite abelian group G. Thus, assuming that we have a cyclic group G = ⟨g⟩, which has prime order p, we want to find the value of x modulo p such that h = gx when we were also given an h ∈ G. The problem with the Baby-Step/Giant-Step method is that although its run time complexity is O(√p), it also requires O(√p) space. Hence, we are interested in replacing the large space requirement for a smaller space requirement, but maintain a time complexity of O(√p). This task can be achieved with the following algorithms. [1]
我们的目标是解决任何循环有限阿贝尔群g的离散对数问题，h=g x 。因此，假设我们有一个循环群g=⟨g⟩，它有素数阶p，我们想找到x模p的值，使得当我们也被赋予h∈g时，h=g x 。小步/大步方法的问题是，尽管它的运行时复杂度是O（√p），但它也需要O（√p）空间。因此，我们有兴趣用较小的空间需求取代较大的空间需求，但保持O（√p）的时间复杂性。这项任务可以通过以下算法来实现。1. 1. Pollard’s Rho Algorithm.
1.波拉德的Rho算法。 Let f : S → S be a random mapping between a set S and itself, n is the size of S. For a random value x0 ∈ S we compute xi+1 = f(xi) for i ≥ 0. Each step xi+1 = f(xi) is a deterministic function of the current position xi. The values x0, x1, x2, . . . are considered as a deterministic random walk.
设f:S→ S是集合S和其自身之间的随机映射，n是S的大小。对于随机值x 0 ∈S，我们计算x i+1 =f（x），其中i≥0。每个步骤x i+1 ＝f（x）是当前位置x的确定性函数。值x 0 、x#4、x 2 、。被认为是确定性随机游动。 Since S is finite we will eventually obtain xi = xj thus xi+1 = f(xi) = f(xj) = xj+1. Hence, the sequence x0, x1, x2, . . . , will eventually become cyclic (“pho” shape: ρ). Our goal is to find a collision in a random mapping like the one above, which means to find 2 values xi and xj with i≠j such that xi =xj.
由于S是有限的，我们最终将获得x=x，因此x i+1 =f（x）=f（x）=x j+1 。因此，序列x 0 ，x 1 ，x 2 ，最终会变成环状（“pho”形状：ρ）。我们的目标是在像上面这样的随机映射中找到碰撞，这意味着找到2个值x和x，其中i≠j，使得x=x。 To find a collision we use Floyd’s cycle finding algorithm: Given (x1,x2) we compute (x2,x4), then (x3,x6) and so on, i.e. given the pair (xi, x2i) we compute (xi+1,x2i+2) = (f(xi),f(f(x2i))) and we stop when we find xm = x2m. It is m=O(√ n).
为了找到碰撞，我们使用Floyd的循环查找算法：给定（x 1 ，x 2 ），我们计算（x 2 ，x 4 ），然后（x 3 ，x 6 ），以此类推，即给定对（x，x 2i ），计算（x i+1 ，x 2i+2 ）=（f（x），f（f（x 2i ））），当我们找到x m =x 2m 时停止。它是m=O（√n）。 For the discrete logarithm problem we partition group S into three sets S1,S2,S3. We assume that 1 ∈ S2, and define the following random walk on the group G, following random walk on the group G: xi+1 =f(xi)=h·xi when xi ∈S1, xi+1 =f(xi)=x2i when xi ∈S2, xi+1 =f(xi)=g·xi when xi ∈S3. We actually keep track of (xi, αi, bi) where αi+1 = αi when xi ∈ S1, αi+1 = 2αi (modn) when xi ∈ S2, αi+1 = αi+1(modn) when xi ∈ S3, and bi+1 = bi+1 (modn) when xi ∈ S1, bi+1 = 2bi (modn) xi ∈ S2, bi+1 = bi when xi ∈ S3
对于离散对数问题，我们将群S划分为三个集合S1S2S3。我们假设1 ∈ S2，并定义群G上的如下随机行走，群G上如下随机行走：当x∈S1时，x+1=f（x）=h·x，当xi∈S2时，x+1=f（x）=x2，当xi∈S3时，x+1=f（×）=G·x。我们实际上跟踪（x，α，b），其中当xi∈S1时α+1=αi，当xi∈S2时α+1=2α（modn），当xi∈S3时α+1=α+1（modn.
Starting with the triple (x0,α0,b0) = (1,0,0), then for all i we have logg(xi) = αi + bi logg(h) = αi + bix. Applying Floyd’s algorithm we are able to obtain a collision, thus find a value of m such that xm = x2m. This means that am + bmx = a2m + b2mx or (bm − b2m)x = a2m − am and if bm ≠ b2m, we obtain x = a2m−ambm−b2m(modn)
从三元组（x0，α0b0）=（100）开始，那么对于所有i，我们都有logg（x）=αi+bi logg（h）=αi+bx。应用Floyd算法，我们能够获得碰撞，从而找到m的值，使得xm=x2m。这意味着am+bmx=a2m+b2mx或（bm−b2m）x=a2m−am，如果bm ≠ b2m，我们得到x= a2m−ambm−b2m(modn)
Assuming that the sequence
假设序列x0,x1,x2,... is produced by a random mapping from
由随机映射生成G to itself, then the above algorithm will find the discrete logarithm in the expected time
则上述算法将在预期时间内找到离散对数O(√ n).
2) Pollard’s Kangaroo Method.
2） 波拉德的袋鼠法。 Pollard’s Kangaroo method is like the Rho method but it is particularly tuned to the situation where we know that the discrete logarithm lies in a certain interval x ∈ [a,...,b].
Pollard的Kangaroo方法类似于Rho方法，但它特别适用于我们知道离散对数位于某个区间x∈[a，…，b]的情况。 Let w = b − a be the length of the interval in which the discrete logarithm x is known to lie. We define a set S = {s0,...,sk−1} of integers in non-decreasing order and its mean m should be around N =√w. We usually choose si = 2i for 0 ≤ i < k (thus the mean of the set is m = 2kk) and also k ≈ 12 log2(w). The group is divided up to k sets Si, for i = 0, . . . , k − 1. We then define the deterministic random walk: xi+1=xi·gsj if xi∈S
设w=b−a是已知离散对数x所在区间的长度。我们定义了一个非递减整数集S={s0，…，sk−1}，其平均值m应在N=√w左右。对于0≤ij. We compute the deterministic random walk, starting from g0 = gb, by setting gi = gi−1 · gsj for i=1,...,N. We also set c0 =b and ci+1 =ci+sj (mod q). We store gN and notice that we have computed the discrete logarithm of gN with respect to g, which is cN =logg(gN)
我们从g0=gb开始，通过设置gi=g−1·gsj来计算确定性随机游动，其中i=1，。。。，N。我们还设置c0＝b和c+1＝c+sj（mod q）。我们存储gN，并注意到我们已经计算了gN相对于g的离散对数，即cN=logg（gN）.
Now we have to compute the second deterministic random walk starting from the unknown point in the interval x. We set h0 = h = gx and compute h i+1 = hi · gs′j . We also set d0 = 0 and di+1 = di +s′j (mod q). Notice that we have logg(hi) = x + d
现在我们必须计算从区间x中的未知点开始的第二个确定性随机游动。我们设置h0=h=gx，并计算h+1=hi·gsj。我们还设置d0=0和d+1=di+sj（modq）。注意，我们有logg（h）=x+di.
Hence, if the path of the hi meets the path of the gi then hi will carry on the path of the gi. We will then be able to find a value M where hM equals our stored point gN .
因此，如果hi的路径与gi的路径相遇，那么hi将继续g的路径。然后我们将能够找到一个值M，其中hM等于我们存储的点gN。
Thus, we will have cN = logg(gN) = logg(hM) = x+dM, and the solution to our discrete logarithm problem is given by x = cN − dM (mod q)
因此，我们将有cN=logg（gN）=logg（hM）=x+dM，并且我们的离散对数问题的解由x=cN−dM（mod q）给出.
If we do not get a collision then we can increase N and continue both walks in a similar manner until a collision does occur. The expected running time of this method is √w and the storage can be seen to be constant.
如果我们没有发生碰撞，那么我们可以增加N，并以类似的方式继续两次行走，直到发生碰撞。这种方法的预期运行时间是√w，并且可以看出存储是恒定的。
3) Parallel Pollard’s Rho Method.
3） 平行波拉德的Rho方法。
When we use random walk based techniques for solving discrete logarithm problems we often use a parallel Pollard's version. Assuming that we are given the discrete logarithm problem h = gx in a group G of prime order q, we first decide on an easily computable function H : G → {1 , . . . , k} (k is usually around 20) and then we define a set of multipliers mi. These are produced by generating random integers ai, bi ∈ [0, . . . , q − 1] and then setting mi=gaihb
当我们使用基于随机游动的技术来解决离散对数问题时，我们通常使用并行的Pollard版本。假设给定素数阶q的群G中的离散对数问题h=gx，我们首先决定一个易于计算的函数h:G→ {1，…，k}（k通常在20左右），然后我们定义了一组乘法器mi。这些乘法器是通过生成随机整数a，bi∈[0，…，q−1]，然后设置m=gahb产生的i.
To start the deterministic random walk we randomly pick s0, t0 ∈ [0, . . . , q − 1] and compute g0 =gs0ht0. The deterministic random walk is then defined on the triples (gi,si,ti) where gi+1 = gi · mH(gi), si+1 = si + aH(gi) (mod q), ti+1 = ti + bH(gi) (mod q).
为了开始确定性随机行走，我们随机选取s0，t0∈[0，…，q−1]，并计算g0=gs0h0。然后在三元组（gst）上定义确定性随机游动，其中g+1=gi·mH（g），s+1=si+aH（g。
Hence, for every gi we record the values of si and ti such that gi =gsih
因此，对于每个gi，我们记录si和ti的值，使得gi=gshti.
If we assume that we have m processors, then each processor can start a different deterministic random walk from a different starting position using the same algorithm in order to determine the next element in the walk. When two processors (or the same processor) meet an element of the group that has been seen before, then we obtain the equation gsi hti = gs′j ht′j from which for the discrete logarithm x can be solved.
如果我们假设我们有m个处理器，那么每个处理器可以使用相同的算法从不同的起始位置开始不同的确定性随机游动，以便确定游动中的下一个元素。当两个处理器（或同一个处理器）遇到以前见过的群的一个元素时，我们得到方程gsi hi=gsj hj，从中可以求解离散对数x。
We expect that after O(πq/2−−−−√/m) iterations of these parallel walks, a collision will be found and the discrete logarithm problem will be solved. However, this means that each processor needs to return every element in its computed deterministic random walk to a central server which then stores all the computed elements. This is highly inefficient due to large storage requirements, namely O(πq/2−−−−√).
我们预计，在这些平行行走的O（ πq/2−−−−√ /m）次迭代后，将发现碰撞，并解决离散对数问题。然而，这意味着每个处理器需要将其计算的确定性随机游动中的每个元素返回到中央服务器，然后中央服务器存储所有计算的元素。由于大的存储需求，即O（ πq/2−−−−√ ），这是非常低效的。
Moreover the storage can be reduced to any required value as follows: We define a function d on the group, d : G → {0, 1} such that d(g) = 1 around 1/2t of the time. The function d is often defined by returning d(g) = 1 if a certain subset of t of the bits representing g are set to zero for example. The elements in G for which d(g) = 1 will be called distinguished.
此外，存储可以减少到任何所需的值，如下所示：我们在群d:G上定义了一个函数d→ {0，1}使得d（g）＝1大约是时间的1/2t。例如，如果表示g的比特的t的某个子集被设置为零，则函数d通常通过返回d（g）＝1来定义。G中d（G）=1的元素将被称为可分辨元素。 It is only the distinguished group elements which are now transmitted back to the central server, which means that we expect the deterministic random walks to continue another 2t steps before a collision is detected between two deterministic random walks. Hence, the computing time now becomes O(πq/2−−−−√/m+2t) and storage becomes O(πq/2−−−−√/2t). Thus, storage can be reduced to any manageable amount, at the expense of a little extra computation.
现在只有可区分的组元素被传输回中央服务器，这意味着我们期望在检测到两个确定性随机行走之间的碰撞之前，确定性随机行走再继续2t步。因此，现在计算时间变为O（ πq/2−−−−√ /m+2），并且存储变为0（ πq/2−−−−√ /2）。因此，存储可以减少到任何可管理的量，而只需要一点额外的计算。 标签：xi,random,idea,Pollard,随机,rho,我们,gi From： https://www.cnblogs.com/3cH0-Nu1L/p/18107503