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.
My questions:
- 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?