Bitcoin Forum
December 15, 2024, 06:13:27 AM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 4 5 6 7 8 9 10 11 [12]  All
  Print  
Author Topic: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning]  (Read 3501 times)
arulbero
Legendary
*
Offline Offline

Activity: 1954
Merit: 2101


View Profile
April 30, 2020, 04:08:59 PM
Last edit: April 30, 2020, 04:35:10 PM by arulbero
Merited by fillippone (2), ABCbits (1)
 #221

Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.

The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.

In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.

In other words : an interval of this type has only 2**(n-1) different x coordinates.
Jean_Luc
Sr. Member
****
Offline Offline

Activity: 462
Merit: 701


View Profile
April 30, 2020, 04:35:06 PM
Last edit: April 30, 2020, 05:35:01 PM by Jean_Luc
 #222

Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.

The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.

Yes i have to investigate, I already tested several things without improving things.
Translating tame is like translating wild in the opposite direction.
May be a brownian motion can be interesting (having positive and negative jump).

Why it was faster with 32 jumps for him? Do you have the exaplanation?

Probably cache usage.

Also nice things you added:
Expected operations: 2^37.15
Expected RAM: 1419.0MB


Edit:
Formula exposed above and for the memory , expected operation*sizeof(hash entry)/2^dp
arulbero
Legendary
*
Offline Offline

Activity: 1954
Merit: 2101


View Profile
April 30, 2020, 04:46:36 PM
Last edit: May 01, 2020, 05:16:16 AM by arulbero
 #223

Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.

The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.

Yes i have to investigate, I already tested several things without improving things.
Translating tame is like translating wild in the opposite direction.

No. I meant: translate tame and wild. Not only tame. In a interval with 2^n points but only 2^(n-1) coordinates 'x' (instead of 2^n) to increase the probability to have a collision. If you do the same number of steps in a half space (from coordinates x point of view), the chance should be higher. Half number of x coordinates, half DP, same number of steps, more chance.

Like I said before, a tame kangaroo and a wild kangaroo in this scenario collide not only if they fall in the same position but if they fall in 2 different positions (but symetric respect of the center of the interval) as well.

If you instead translate this interval in any other position of the curve, when a tame kangaroo and a wild kangaroo fall in 2 positions symetric respect of the center of the interval, your current algorithm doesn't detect a collision, simply because it can't know (without more computation) the x coordinate of the symetric point (respect of (a+b)/2 * G) of any DP that lies in the hashtable (and a symetric point of a DP generally is not a DP)

May be a brownian motion can be interesting (having positive and negative jump).

My idea goes a little in that direction too, cause the jumps are always positive but the points generated go in both direction, exploiting the symetrie of the curve.

Example:

when a sequence starts from -k*G (negative part):

-k*G, (-k + 2^17)*G, (-k +2^17 + 2^3)*G, ....  forth -->

but in this way you have too (for free) the x coordinates of :

+k*G, (+k - 2^17)*G, (+k- 2^17 - 2^3)*G, ....       <-- back

the movement is like this:

             zero point
(-->                            <--)         extreme:  -k*G, k*G
   (-->                    <--)              extreme:   (-k+2^17)*G,  -(-k+2^17)*G
          (-->   <--)                        extreme:   (-k+2^17+2^3)*G,  -(-k+2^17+2^3)*G



when a sequence starts/arrives in the positive part:

k*G, (k + 2^8)*G, (k +2^8 + 2^31)*G, ....  forth -->
-k*G, (-k - 2^8)*G, (-k -2^8 - 2^31)*G, ....   <-- back

                zero point
           <-- (        )-->                        extreme:  -k*G, k*G
       <--(                  )-->                   extreme:   -(k+2^8)*G,  (k+2^8)*G
  <--(                            )-->              extreme:   -(k+2^8+2^31)*G,  (k+2^8+2^31)*G

HardwareCollector
Member
**
Offline Offline

Activity: 144
Merit: 10


View Profile
April 30, 2020, 06:55:43 PM
Merited by Halab (2), arulbero (2), ABCbits (1), Husna QA (1)
 #224

Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.

The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.

In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.

In other words : an interval of this type has only 2**(n-1) different x coordinates.

I am not following the logic here. What is missing is, how will the paths converge after both the tame and the wild reach the same x-coordinate, assuming that it is the symmetry point?
HardwareCollector
Member
**
Offline Offline

Activity: 144
Merit: 10


View Profile
April 30, 2020, 07:03:08 PM
Merited by nullius (1)
 #225

@Jean_Luc

Please start a new thread for your Pollard Kangaroo implementation discussion.  Smiley
arulbero
Legendary
*
Offline Offline

Activity: 1954
Merit: 2101


View Profile
April 30, 2020, 07:50:08 PM
Last edit: May 01, 2020, 05:26:38 AM by arulbero
 #226

Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.

The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.

In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.

In other words : an interval of this type has only 2**(n-1) different x coordinates.

I am not following the logic here. What is missing is, how will the paths converge after both the tame and the wild reach the same x-coordinate, assuming that it is the symmetry point?

Good point!


It is enough to modify slightly the way we generate the next jump:

+ jP[tamePosi.x % n]*G if y > p/2,  - jP[tamePosi.x % n]*G is y <p/2

(then I will indicate 'y' if y > p/2, '-y' if y < p/2)


in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision

The tame and the wild will go on with 2 specular paths:

Q -> Q + k*G -> Q + k*G -r*G ->  ... -> DP
(x,y)    (x1,-y1)          (x2,y2)              (x0, y0)

-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y)  (x1,y1)         (x2, -y2)              (x0, -y0)

until they reach 2 symetric DP, for both of which we know the private key.


May be a brownian motion can be interesting (having positive and negative jump).

I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.
Jean_Luc
Sr. Member
****
Offline Offline

Activity: 462
Merit: 701


View Profile
May 01, 2020, 05:45:47 AM
 #227

I opened a new thread.
https://bitcointalk.org/index.php?topic=5244940.0
Pages: « 1 2 3 4 5 6 7 8 9 10 11 [12]  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!