Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 99. (Read 58630 times)

member
Activity: 330
Merit: 34
June 16, 2020, 09:06:58 AM
If we attack #64, we will try all priv key one by one, compute the HASH160 until we get a match.
With few mods, the vanitySearch engine can do that. Kangaroo is not usefull here.
For one by one bitcrack could work too. Even peoples created group pool for find 64. Like client server sharing
sr. member
Activity: 462
Merit: 696
June 16, 2020, 08:57:51 AM
If we attack #64, we will try all priv key one by one, compute the HASH160 until we get a match.
With few mods, the vanitySearch engine can do that. Kangaroo is not usefull here.
newbie
Activity: 25
Merit: 0
June 16, 2020, 08:49:04 AM
Yes thanks for this tip Smiley
I'm building a map to compute with accuracy the DP overhead as I didn't yet managed to get the correct analytical expression but only the 2 asymptote (0 and infinity)
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.


hello Jean_Luc, how to attaque #64 with kangoroos or the VanitySearch engine without public key ?
jr. member
Activity: 47
Merit: 13
June 16, 2020, 08:29:37 AM
We (me and zielar) solved #115 after ~2^33.36 DP (DP25) (More than 300GB of DP). I do not know exactly how long the run takes due to unwanted interruption.
Cheesy

Congratulations
did you forget to send some satoshi to
1FoundByJLPKangaroo111Bht3rtyBav8


And there it is!  Cheesy

The satoshi to 1FoundByJLPKangaroo111Bht3rtyBav8  Grin Wink

Congrats again  Smiley
member
Activity: 330
Merit: 34
June 16, 2020, 08:27:38 AM
Yes thanks for this tip Smiley
I'm building a map to compute with accuracy the DP overhead as I didn't yet managed to get the correct analytical expression but only the 2 asymptote (0 and infinity)
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.

private key for 115 ?
sr. member
Activity: 462
Merit: 696
June 16, 2020, 08:10:13 AM
Yes thanks for this tip Smiley
I'm building a map to compute with accuracy the DP overhead as I didn't yet managed to get the correct analytical expression but only the 2 asymptote (0 and infinity)
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.
legendary
Activity: 1932
Merit: 2077
June 16, 2020, 08:00:34 AM

You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1])


Yes you're right.
I ve forgotten that the start range was shifted to zero. shame on me Smiley
It will help to solve #120. Wink


Instead of 2^61 steps, you need to compute (2^60 - 2^58.36) steps for tame + 2^60 for wild. If you spread the old DPs like I have suggested you in a previous post.

It would be convenient to start with only wild (for the first 2^58.36 steps) and then continue with wild and tame, but with many machines it should be not simple to do this.

You can save in this way about 15.8% of the work.

An other way it could be: you know that you have already DPs in [1,2^114-1], then you generate tame only in the [2^114, 2^119-1] space --> you have enough DP's (2^33.36) already in the first 1/32.

In the first case you should use 300GB * 2^2.5 = 1700 GB, in the second case I guess you need more RAM and more time.
sr. member
Activity: 462
Merit: 696
June 16, 2020, 07:41:50 AM
my Question you misunderstand
example i have 2 pubkeys in 115bit range, 1 key found, for 2nd key how i can use that work file for find in less time, ??

You can simply merge the files, but at the moment the "trapped wild" are not yet handled, you will take benefit only from tame.
This will be done in a future release as we will need it for solving #120.
sr. member
Activity: 617
Merit: 312
June 16, 2020, 07:40:55 AM

second interval[/u]  = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,....,27,28,29,30,31]  (5 bit)
you want to find P = 11*G, you know only that the P lies in this interval

instead of searching P in the second interval [1*G, 2*G, ...., 31*G]

you search P'=inv(4)*P (a different point) in the

third interval [1*G', 2*G', ......, 31*G']  (that contains the first interval but not at the beginning + P')

The old DPs are now: 8*G' and 20*G' (same points, different private keys). All the points of the first interval are now in the third one too.

The private key of P' = 11, in fact 11*G' = 11*inv(4)*G --> P = 4*P' = 4*11*inv(4)*G = 11*G

Perfect explanation. Thanks!
member
Activity: 330
Merit: 34
June 16, 2020, 07:27:30 AM

You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1])


Yes you're right.
I ve forgotten that the start range was shifted to zero. shame on me Smiley
It will help to solve #120. Wink

my Question you misunderstand
example i have 2 pubkeys in 115bit range, 1 key found, for 2nd key how i can use that work file for find in less time, ??
sr. member
Activity: 462
Merit: 696
June 16, 2020, 07:17:24 AM

You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1])


Yes you're right.
I ve forgotten that the start range was shifted to zero. shame on me Smiley
It will help to solve #120. Wink
legendary
Activity: 1932
Merit: 2077
June 16, 2020, 06:44:56 AM
-snip-
You can (see here -> https://bitcointalksearch.org/topic/m.54546770, it is enough to map the new task [1, 2^119 - 1] to the previous one [1, 2^114 - 1]) but it's not worth it.
-snip-
i think all DPs from previous work will be in the left 1/32 part of interval(in the begining).
If you just multiply DPs by 32 then  they will be just points not DPs becouse they will not have leading zeros.
If i wrong can you explaine in very small range how transform DP by 32 times and do not loose leading zeros? Thanks.

No, you don't transform the old DPs, you change only their private keys (changing the generator G). The same for the old jumps. The only point you change is P, the public key for which you are looking the private key.

Instead of multiplying the old points by 32 you divide (= multiply by inv(32)) the new public point P -> P'=inv(32)*P.

If P lies in the [1, 2^119 - 1] interval, then P' lies in the

[1/32, ...., 31/32, 1, 33/32, ....., 2, ......3, .......4, ................., 2^114 -1/32] interval.

Note that the private keys of the old DPs are 'integer'. In this way you spread the old DPs uniformly in a set x32 bigger. This interval contains all the previous points [1,2,3,..., 2^114-1], but not at the beginning!

You can change now the private keys changing the generator, G -> G' = inv(32)*G:

[1, .........,31, 32, 33, .........2*32,..........3*32, .............., 4*32,.................32*2^114 - 1]

the private keys of the old DPs have become all multiplies of 32.

If for example a DP has private key = 78543 respect of G, it has private key = 32*78543 respect of G', the point remains the same (same x-coordinate), you have changed only the point G.

The private key of P' respect of G' is the same private key of P respect of G.  

------------------------------------------------------------------------------------------------------------------

Example:

first interval = [1,2,3,4,5,6,7]  (3 bit)
DPs  = 2*G, 5*G

second interval
 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,....,27,28,29,30,31]  (5 bit)
you want to find P = 11*G, you know only that the P lies in this interval

instead of searching P in the second interval [1*G, 2*G, ...., 31*G]

you search P'=inv(4)*P (a different point) in a

third interval [1*G', 2*G', ......, 31*G']  (that contains the first interval but not at the beginning + P')

The old DPs are now: 8*G' and 20*G' (same points, different private keys). All the points of the first interval are now in the third one too.

The private key of P' = 11, in fact 11*G' = 11*inv(4)*G --> P = 4*P' = 4*11*inv(4)*G = 11*G
sr. member
Activity: 617
Merit: 312
June 16, 2020, 06:26:48 AM
-snip-
You can (see here -> https://bitcointalksearch.org/topic/m.54546770, it is enough to map the new task [1, 2^119 - 1] to the previous one [1, 2^114 - 1]) but it's not worth it.
-snip-
i think all DPs from previous work will be in the left 1/32 part of interval(in the begining).
If you just multiply DPs by 32 then  they will be just points not DPs becouse they will not have leading zeros.
If i wrong can you explaine in very small range how transform DP by 32 times and do not loose leading zeros? Thanks.
legendary
Activity: 1932
Merit: 2077
June 16, 2020, 05:19:51 AM
Unfortunately I don't see how to reuse the work file on a different range.
This work file is for [2^114,2^115-1]

If you translate the kangaroos, the paths will differ so you have to redo all the job.

You can (see here -> https://bitcointalksearch.org/topic/m.54546770, it is enough to map the new task [1, 2^119 - 1] to the previous one [1, 2^114 - 1]) but it's not worth it.

You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs are in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P is in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1])

In theory, to have 50% to get a collision in the #120 search, if you reuse the 300GB of DPs you need to do other 2^61.70 steps (only wild).

If you restart instead from scratch, you need to do about 2^61 steps.
member
Activity: 330
Merit: 34
June 16, 2020, 04:51:06 AM
Unfortunately I don't see how to reuse the work file on a different range.
This work file is for [2^114,2^115-1].

If you translate the kangaroos, the paths will differ so you have to redo all the job.

There was an interesting question in a previous message of this topic:
Why paths are important and why not adding DP without computing paths ?

Using only DP:
It is like drawing a random number in a reduced space N/2^dpbit so time to solve will be O( sqrt(N/2^dpbit) )
However, it is true, that you can reach a DP faster in this way by computing consecutive points.

Using paths:
It is like drawing a bunch of 2^dpbit random points at each DP, so time to solve is O( sqrt(N)/2^dpbit )
The "gain" using path is 2^dpbit while without paths, the "gain" is only sqrt(2^dpbit)

So even if reaching a DP without path is faster, the gain is not enough to beat path.

" I don't see how to reuse the work file on a different range.
This work file is for [2^114,2^115-1]."

no different range, same range [2^114,2^115-1] and pubkey of this same range too, then ?
in short if an other pubkey is of range [2^114,2^115-1] as workfile already for this[2^114,2^115-1] range
sr. member
Activity: 462
Merit: 696
June 16, 2020, 04:41:37 AM
Unfortunately I don't see how to reuse the work file on a different range.
This work file is for [2^114,2^115-1].

If you translate the kangaroos, the paths will differ so you have to redo all the job.

There was an interesting question in a previous message of this topic:
Why paths are important and why not adding DP without computing paths ?

Using only DP:
It is like drawing a random number in a reduced space N/2^dpbit so time to solve will be O( sqrt(N/2^dpbit) )
However, it is true, that you can reach a DP faster in this way by computing consecutive points.

Using paths:
It is like drawing a bunch of 2^dpbit random points at each DP, so time to solve is O( sqrt(N)/2^dpbit )
The "gain" using path is 2^dpbit while without paths, the "gain" is only sqrt(2^dpbit)

So even if reaching a DP without path is faster, the gain is not enough to beat path.
newbie
Activity: 43
Merit: 0
June 16, 2020, 04:33:56 AM
All the other mortals are spectators at the show created by Zielar and Jean Luc. I like the show. The show must go on Smiley
member
Activity: 330
Merit: 34
June 16, 2020, 04:18:13 AM
Congratulations for breaking the World Record too. Good job  Smiley

The last world record was 112 bits, right? Huh

Thanks Wink

The world record on standard architecture was also 114 bit but on a 114 bit field. Here we have solved a 114bit key on a 256bit field. So yes, we broke the world record on classic architecture Cheesy

The world record on FPGA is 117.25 bit, it was done using up to 576 FPGA during 6 months.
With our architecture, we expect 2 months on 256 V100 to solve #120 (119bit keys), we will see if we will attack it.

Yes I will send the satoshi to 1FoundByJLPKangaroo... but before I'm waiting Zielar who is offline at the moment.
We will publish the private in a while when altcoin will also be moved.

as now you have work file for 115 bit, can we apply an other 115 bit pubkey for check inside your 300gb workfile, and what aspected time to find solution ?
sr. member
Activity: 462
Merit: 696
June 16, 2020, 03:17:02 AM
Congratulations for breaking the World Record too. Good job  Smiley

The last world record was 112 bits, right? Huh

Thanks Wink

The world record on standard architecture was also 114 bit but on a 114 bit field. Here we have solved a 114bit key on a 256bit field. So yes, we broke the world record on classic architecture Cheesy

The world record on FPGA is 117.25 bit, it was done using up to 576 FPGA during 6 months.
With our architecture, we expect 2 months on 256 V100 to solve #120 (119bit keys), we will see if we will attack it.

Yes I will send the satoshi to 1FoundByJLPKangaroo... but before I'm waiting Zielar who is offline at the moment.
We will publish the private in a while when altcoin will also be moved.
member
Activity: 330
Merit: 34
June 16, 2020, 03:12:59 AM
We (me and zielar) solved #115 after ~2^33.36 DP (DP25) (More than 300GB of DP). I do not know exactly how long the run takes due to unwanted interruption.
Cheesy

Congratulations
did you forget to send some satoshi to
1FoundByJLPKangaroo111Bht3rtyBav8

Pages:
Jump to: