Pages:
Author

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

sr. member
Activity: 462
Merit: 696
June 17, 2020, 09:36:41 AM
Jumps (the points) are the same, only their private keys are different;

So in practical, I let the old #115 DP as they are and for the new search #120 I use inv(32)*G instead of G ?
member
Activity: 330
Merit: 34
June 17, 2020, 09:23:10 AM
Hi,
I don't understand well how this can work ?
If you change G, the path will also differ as jumps are a function of the X value.

Jumps (the points) are the same, only their private keys are different;

instead of using, for example, 2543*G as jump, you use (2543*32)*G', where G' = inv(32)*G

in this way the points are the same and the paths are the same. The same interval

A = [1G, 2G...., (2^114 - 1)*G]

can be viewed as

B = [32*G', 2*32*G'...., 32*(2^114 - 1)*G']

and this interval is a subset of the interval

C = [1*G', 2*G', 3*G',...., (2^119 - 1)*G']

Note that C has the same number of elements of

D = [1*G, 2*G, ...., (2^119 - 1)*G]

but C != D.

To recap:  

A = B, A subset C
A subset D

What is the difference? Why using C instead of D?

The advantage is that the old DPs, that lie in A = B, lie in C too, but now they are uniformly spread out in C, while the same points are not uniformly spread out in D.

Now, P lies in the interval D, not in C, but P' = inv(32)*P does, and the private key of P' respect to G' is the same as the private key of P respect to G.

-----------------------------------------------------
Note:

C is not the original interval D = [0*G, 2*G, ...., (2^119 - 1)*G], C is a 'contraction' of D, on other hand the very original interval (where the real public key P lies) is E = [2^119 *G, ..., (2^120 - 1)*G].

Usually you shift E to D and P to P' = P - 2^119*G; note that it is like you changed G to G' = G - 2^119G.

Now I suggest to add another move:

move D to C and P' to P'' = inv(32)*P' ; I call this move a 'contraction', because I divide G by 32.

Actually you r saying upword in multiple mode
And i said long time ago downside multiple mode.

Upside *32 mean u still stand 1 part of 32 part
And down side u r stand for 32/1
So i know this stage of multiple pub keys you have 90% work n time savings.
Hope u will not understand. Other jean luc will leave everything and rush to develop multipub key search ver .
Bc after long junps in thinking he will come to this stage in last
Example i said
2 x 100 = 200
But he listening
2+2+2 till 200
2+3 till 200
2x2 x2 till 200

Hope u all moving slowly to multiple keys or multiple bits
But dont try to understand my words. As its from brainless
sr. member
Activity: 661
Merit: 250
June 17, 2020, 09:06:16 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.

Can you please let the #64 for normal guys not owning/renting tons of gpu ?
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 08:26:46 AM
Hi,
I don't understand well how this can work ?
If you change G, the path will also differ as jumps are a function of the X value.

Jumps (the points) are the same, only their private keys are different;

instead of using, for example, 2543*G as jump, you use (2543*32)*G', where G' = inv(32)*G

in this way the DP points are the same, the jumps are the same and all the old paths are the same too.

The same interval

A = [1G, 2G...., (2^114 - 1)*G]

can be viewed as

B = [32*G', 2*32*G'...., 32*(2^114 - 1)*G']

and this interval is a subset of the interval

C = [1*G', 2*G', 3*G',...., (2^119 - 1)*G']

Note that C has the same number of elements of

D = [1*G, 2*G, ...., (2^119 - 1)*G]

but C != D.

To recap:  

A = B, A subset C
A subset D

What is the difference? Why to work in C instead of D, since the old points in A are already in D?

The advantage is that the old DPs, that lie in A, are uniformly spread out in C, while the same points are not uniformly spread out in D.

Now, P lies in the interval D, not in C, but P' = inv(32)*P does, and the private key of P' respect to G' is the same as the private key of P respect to G.

-----------------------------------------------------
Note:

C is not the original interval D = [0*G, 2*G, ...., (2^119 - 1)*G], C is a 'contraction' of D, on other hand the very original interval (where the real public key P lies) is E = [2^119 *G, ..., (2^120 - 1)*G].

Usually you shift E to D and P to P' = P - 2^119*G.

Now I suggest to add another move:

move D to C and P' to P'' = inv(32)*P' ; I call this move a 'contraction', because I divide G by 32.
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 08:23:58 AM
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.

In the search of #64 you will find several points with x-coordinate with the leading 60 bits = 0. You could use them here as jumps to save space (or to use more jumps in the same space).  But in this way you can't reuse the old DPs.


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 think that a DP worth is equal to the length of the path you computed to find it.
 
If you find a DP with 25 bits = 0 after 2^27 steps, that point should be worth like 4 points, each with 25 bits = 0 and found after 2^25 steps. It is like a DP with 25 bits = 0 is equal to a DP with 27 bits = 0.

If you reuse only the DPs you found after 2^27 steps, you will have a better ratio "space occupied / chance to find a collision"
sr. member
Activity: 462
Merit: 696
June 17, 2020, 08:19:58 AM
Hi,
I don't understand well how this can work ?
If you change G, the path will also differ as jumps are a function of the X value.
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 05:26:57 AM
@JeanLuc can you add G to params in the next release? Thanks.
if someone wants to use the suggested arulbero method, then the parameter G must be changeable. (As i understand correct)

You would need to do these changes:

- a parameter 'reuse', to indicate that you want to reuse a DP file generated for a different search task, and the indication of the difference 'xbit'
*** xbit: current bit range -  previous bit range (for example, 119 bit - 114 bit = 5 bit)

- ** recompute all the previous private keys multiplying them by 2^xbit (for example, for all the 2^33.36 DPs found by Zielar,  each single privkey k -> k' = k*(2^5) )

- the point P needs to be converted in P' = inv(2^xbit) * P  (for example, P' = inv(2^5)*P)  

- the point G needs to be converted in G' = inv(2^xbit) * G  (for example, G' = inv(2^5)*G)


** this task is not strictly necessary, it is enough, once you have found a collision, to modify only the private key of the old DP involved in the collision, to retrieve the correct private key for P (remember that the points are the same); you could insert as parameter the public key of the previous search too, in this way you can avoid to transform all the old wild kangaroos in tame kangaroos, again you could do this transformation on the fly at the end, and only for the single wild kangaroo involved in the collision

*** you can use a xbit negative too, if current bit range < previous bit range, for example inv(2^-5) = 2^5; in this case all the old DPs have the new private keys (respect to G' = 32*G) that are 1/32 of the old private keys; on average only 1/32 of the old DPs will be available for the new search in the new interval; in this case you need to compute first the private keys of all old DPs in order to choose the correct ones; but in this case it would be simpler fetching directly the old DPs that lies in the new range too, without change G

member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
June 17, 2020, 04:27:41 AM
@JeanLuc make please option for save all dead kangaroo to .txt file in readable format ? This is needed information for understand mistake with ranges and -d param.


@JeanLuc and make please counting +/- dead kangaroo: [Dead 10] -> [Dead total: 10 ["+" 8, "-" 2 ]]

BR.




newbie
Activity: 17
Merit: 0
June 17, 2020, 04:13:01 AM

If you or someone who can program can work on sending hashtable to textfiles (like your export option configuration) then there would be no need for save files and merging, etc. If you give user option to export tame and wild files with any amount they wish (example 20 tame and 20 wild files), then no merging or saving. Just compare the different tame and wild files for a collision/solution. This also eliminates any RAM issues.

Once you know the structure of a workfile it is not difficult to work with this type of file. I have created a small script in python as an example, anyone can modify it to suit their needs

https://gist.github.com/PatatasFritas/a0409df4306fb1bb81f9a53e70151ddc
sr. member
Activity: 617
Merit: 312
June 17, 2020, 04:09:08 AM
@JeanLuc can you add G (Generator point) to params in the next release? Thanks.
if someone wants to use the suggested arulbero method, then the parameter G must be changeable. (As i understand correct)
full member
Activity: 141
Merit: 116
June 17, 2020, 03:54:25 AM
-snip-
...Here is server/client (source and compiled version) for bitcrack, you also need put cu or cl version of Bitcrack.exe to client folder https://drive.google.com/file/d/1pFTvBLwTDF4GZCyDpJHwnWqfuNeOT6Ik..


@Etar would you mind sharing the source code ?


Edit: Please disregard, I got it .

member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
June 17, 2020, 02:00:07 AM
I have a question, P = kG, k is in the range of [k1, k2], I am now solving for a public key, but I don’t know the range of [k1, k2], how should I use the kangaroo.exe program, or can I explain how Estimate the range of [k1, k2]?
There is no way to estimate the range. You would have to search range from 000000000000....1 to FFFFFFFFFFF...F (1 to 256)  which would be a really long time.
Is there any way to get other information from the public key, such as X coordinate?
yes, you can get x and y from pubkey.

Buddy, how to extract dead kangaroo parameters from work file or enower method ?
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 16, 2020, 10:58:45 PM
I have a question, P = kG, k is in the range of [k1, k2], I am now solving for a public key, but I don’t know the range of [k1, k2], how should I use the kangaroo.exe program, or can I explain how Estimate the range of [k1, k2]?
There is no way to estimate the range. You would have to search range from 000000000000....1 to FFFFFFFFFFF...F (1 to 256)  which would be a really long time.
Is there any way to get other information from the public key, such as X coordinate?
yes, you can get x and y from pubkey.
newbie
Activity: 14
Merit: 0
June 16, 2020, 09:05:01 PM
I have a question, P = kG, k is in the range of [k1, k2], I am now solving for a public key, but I don’t know the range of [k1, k2], how should I use the kangaroo.exe program, or can I explain how Estimate the range of [k1, k2]?
There is no way to estimate the range. You would have to search range from 000000000000....1 to FFFFFFFFFFF...F (1 to 256)  which would be a really long time.
Is there any way to get other information from the public key, such as X coordinate?
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 16, 2020, 08:53:32 PM
I have a question, P = kG, k is in the range of [k1, k2], I am now solving for a public key, but I don’t know the range of [k1, k2], how should I use the kangaroo.exe program, or can I explain how Estimate the range of [k1, k2]?
There is no way to estimate the range. You would have to search range from 000000000000....1 to FFFFFFFFFFF...F (1 to 256)  which would be a really long time.
newbie
Activity: 14
Merit: 0
June 16, 2020, 08:49:15 PM
I have a question, P = kG, k is in the range of [k1, k2], I am now solving for a public key, but I don’t know the range of [k1, k2], how should I use the kangaroo.exe program, or can I explain how Estimate the range of [k1, k2]?
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 16, 2020, 08:28:06 PM
Congratulations to Jean_Luc and zielar!

I have been thinking for several days about removing the hashtables from the joining process, and when I finally finish it I find that it had already been implemented by JeanLuc Cheesy

Now I have applied the same method to join several files in one process, reducing the total time quite a bit.
My approach is to read all the files in the directory at the same time in HASH_ENTRY loop.

Although my code works, it is still in testing and it is possible that it has some bug.


https://github.com/PatatasFritas/FriedKangaroo/blob/merge/Merge.cpp
If you or someone who can program can work on sending hashtable to textfiles (like your export option configuration) then there would be no need for save files and merging, etc. If you give user option to export tame and wild files with any amount they wish (example 20 tame and 20 wild files), then no merging or saving. Just compare the different tame and wild files for a collision/solution. This also eliminates any RAM issues.
newbie
Activity: 17
Merit: 0
June 16, 2020, 08:17:33 PM
Congratulations to Jean_Luc and zielar!

I have been thinking for several days about removing the hashtables from the joining process, and when I finally finish it I find that it had already been implemented by JeanLuc Cheesy

Now I have applied the same method to join several files in one process, reducing the total time quite a bit.
My approach is to read all the files in the directory at the same time in HASH_ENTRY loop.

Although my code works, it is still in testing and it is possible that it has some bug.


https://github.com/PatatasFritas/FriedKangaroo/blob/merge/Merge.cpp
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 16, 2020, 04:07:28 PM

@JeanLuc sorry about little offtop in your thread..
@WanderingPhilospher Here is server/client (source and compiled version) for bitcrack, you also need put cu or cl version of Bitcrack.exe to client folder https://drive.google.com/file/d/1pFTvBLwTDF4GZCyDpJHwnWqfuNeOT6Ik
before using app in big range made few test in small interval to make shure that you correct understand params.(-dp 3 means that the entire range will be divided into 2^3=8 subranges)
[/quote]
@Etar open up PMs please.
jr. member
Activity: 43
Merit: 1
June 16, 2020, 03:21:17 PM
@Etar thanks
Pages:
Jump to: