I want to understand the Pollard kangaroo attack on elliptic curves. I found this Pollard's kangaroo attack on Elliptic Curve Groups Q/A pretty helpful, but not complete. The posts provides a pretty good algorithm for the attack:
def pollardKangaroo(P, Q, a, b, N): # Tame Kangaroo Iterations: xTame, yTame = 0, b * P for i in range(0,N): xTame += Hash(yTame) yTame += Hash(yTame) * P # yTame == (b + xTame) * P should be true # Wild Kangaroo Iterations: xWild, yWild = 0, Q wildLimit = b - a + xTame while xWild < wildLimit: xWild += Hash(yWild) yWild += Hash(yWild) * P if yWild == yTame: return b + xTame - xWild # No result was found: return None
I did the algorithm on paper and it worked. $P$ and $Q$ are the points in the ECDLP: $Q = n\cdot P$. $a$ and $b$ give the interval, in which the attack searches for $n$. So the algorithm can only succeed if $n \in [a,b]$. Now I got two problems: The hash-function and the parameter $N$ are not explained/defined.
- Is the hash-function just a semi-random generator and can be pretty simple (e.g. H(point) = x + y + 1)?
- How exactly is $N$ defined? What value should $N$ be? How does the value of $N$ affect the algorithm?