Re: Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo
Quote
Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.
This doesn't make sense to me. Why would you need the same point in the database. I don't see how this is useful.
Well a DP entry has a key (hash or whatever) and a value (distance from base point).
If the DP hash matches, you can compute for two possible values for each distance, because the collision may have happened on either the odd or even Y coord.
So, a 4-way match instead of just one. For tames, you know the distance, so you can compute both key values. For wilds, you can similarly consider the distance as being on the left or right side of the interval, so they can both be used as a potential match. It all checks out.
I still do not get why you have to store both, tame or wild, or both, all 4 DPs, a 4-way match as you said. Or just going back to the original statement, why it makes sense to store both, "...then you basically have two DPs found instead of one".
The kicker is, if you found one, you know that you have found both. They are the same value +/-. So I do not know why one would save both in a table.
Let us say we are searching for private key 0x15, public key 02352bbf4a4cdd12564f93fa332ce333301d9ad40271f8107181340aef25be59d5 at DP 0.
I have a tame that landed on private key (point) 0x16, point and distance stored:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC : 16
Let's say we had a tame land on the + and the -; right or left side, etc. of private key (point) 0x1, or fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140; the point and distance stored would be:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC : 1
or if you program in some wacky kind of way, it would be stored as:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC : fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140
Now you can jumble up the table and add some kind of switch that lets you know if it is right/left +/-, or have your solver code check both +/-, but I would never store the same exact points, for tames nor wilds. Just one for me
