Pollard's kangaroo ECDLP solver - page 121.

brainless

member

Activity: 330

Merit: 34

Quote from: Etar on May 28, 2020, 07:18:50 AM

Quote from: brainless on May 28, 2020, 07:08:46 AM

-snip-
how much gpu's you have ?

now left 24x2080ti, around half GPU is out of race.

As say Turing, machine working we need only give him what he is undertsand..

could you try this for calc time about your 24 2080ti gpu for 100 bit
0314AA23C847D86CE1FCDC4B3E0524F741FDE2AC4B38B522ED2E3B77CF500D5718
and you can use client server or single system with gpuid 0,1,2,3 to 24 command
and just run and you will have estimate time, could update me your estimate time ?

Jean_Luc

sr. member

Activity: 462

Merit: 696

Published a new release with a faster merger.
Thanks to test it Wink

BitCrack

jr. member

Activity: 30

Merit: 122

Quote from: Etar on May 28, 2020, 06:53:13 AM

There seems to be some kind of mistake in this puzzle#110
A huge number of GPU capacities have already been spent and no one could find the key.
I checked the range borders with bsgs, there is no key there.
This was the only version why we could not find the key for so long.
But she is not true. The key is not near the edge.
Someone has an idea why we can’t find the key .. even with the possibility of 400 GPU?

I think folks are just being impeded by storage and network issues.

Etar

sr. member

Activity: 617

Merit: 312

Quote from: brainless on May 28, 2020, 07:08:46 AM

-snip-
how much gpu's you have ?

now left 24x2080ti, around half GPU is out of race.

As say Turing, machine working we need only give him what he is undertsand..

brainless

member

Activity: 330

Merit: 34

Quote from: Etar on May 28, 2020, 06:53:13 AM

There seems to be some kind of mistake in this puzzle#110
A huge number of GPU capacities have already been spent and no one could find the key.
I checked the range borders with bsgs, there is no key there.
This was the only version why we could not find the key for so long.
But she is not true. The key is not near the edge.
Someone has an idea why we can’t find the key .. even with the possibility of 400 GPU?

how much gpu's you have ?

Etar

sr. member

Activity: 617

Merit: 312

There seems to be some kind of mistake in this puzzle#110
A huge number of GPU capacities have already been spent and no one could find the key.
I checked the range borders with bsgs, there is no key there.
This was the only version why we could not find the key for so long.
But she is not true. The key is not near the edge.
Someone has an idea why we can’t find the key .. even with the possibility of 400 GPU?

Etar

sr. member

Activity: 617

Merit: 312

Quote from: WanderingPhilospher on May 27, 2020, 09:22:05 PM

With the new -wsplit option:

How are you using it?

The way I read, it saves an updated file let's say every -wi 60 seconds. Got it. I've tested it.

So the only way the key can be solved on the server side, is if a collision happens in the current, being worked on, reset/smaller hash table (the one that will be saved next)?

The server doesn't compare the different saved files for a collision, so one must merge the different saved working files to check for a collision.
If you have 10, 20, 30, 100, 1000 saved files over a period of days, weeks, months, are you manually merging the saved work files every so often?
The current merge option only allows the merge of 2 files at a time...manually merging could become an hourly task (depending on how many files you have being saved each minutes/hours.)

So you have a benefit in RAM but increases the amount of work you have to do in merging files?

Grabber and merger merge files in realtime, so i do not have any split files on server. Once file exist merger merge him with masterfile.
all what you need it is set -jobtime to value (wi/2*1000). If -wi set to 60, than you need -jobtime 30000, -jobtime in ms.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: Etar on May 27, 2020, 08:08:01 AM

@JeanLuc in next release if it possible fix please addiding date string to workfile before extention.
I mean i use file -w savework1.part but after saving got savework1.part_27May20_160341 should be savework1_27May20_160341.part I think. Thanks.

Edit:With -d 28, -wi 600, memory usage by server 10-20MB( it think -wsplit is great tools)

I recompiled a version that does similar to what you asked.

Simply changed the code in Backup.cpp

Code:

string fileName = workFile;
if(splitWorkfile)
//fileName = workFile + "_" + Timer::getTS();
fileName = Timer::getTS() + "_" + workFile;

works as described.

Instead of saving as savework1.part_27May20_160341, it saves as 27May20_160341_savework1.part

This way your .part extension is at the end of the file.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

With the new -wsplit option:

How are you using it?

The way I read, it saves an updated file let's say every -wi 60 seconds. Got it. I've tested it.

So the only way the key can be solved on the server side, is if a collision happens in the current, being worked on, reset/smaller hash table (the one that will be saved next)?

The server doesn't compare the different saved files for a collision, so one must merge the different saved working files to check for a collision.
If you have 10, 20, 30, 100, 1000 saved files over a period of days, weeks, months, are you manually merging the saved work files every so often?
The current merge option only allows the merge of 2 files at a time...manually merging could become an hourly task (depending on how many files you have being saved each minutes/hours.)

So you have a benefit in RAM but increases the amount of work you have to do in merging files?

Etar

sr. member

Activity: 617

Merit: 312

Quote from: zielar on May 27, 2020, 03:14:19 PM

You fell from heaven with this tool, man! Just tell me how to set -ext knowing that the latest release adds the ending without .part?

-ext you can set what ever you want, just it was a word in the name of small files.
Example. you have -w mysmallfile on server, when it will be save with -wsplit it will look like mysmallfile_27May20_232415
So you need set -ext like smallfile or small.. if only the grabbber could distinguish this file from others

patatasfritas

newbie

Activity: 17

Merit: 0

Quote from: MrFreeDragon on May 26, 2020, 01:50:48 PM

Jean_Luc, I want to look at the table which is saved to workfile. But as I understood, only 128bit are saved for X-coordinate and 126bit for distance (together with 1 bit for sign and 1 bit for kangaroo type).

Anyway, what is the easiest way to receive the whole table in txt format. I easily could read from binary file the head, dp, start/stop ranges, x/y coordinates for key. After that the hash table is saved with a lot of 0 bytes....
Can you just briefly describe the hash table structure which is saved to binary file?

if you still haven't managed to export the workfile, here are the changes I made to the code to export the DPs to txt.

The X-coord is 128+18 bits and distance 126bits. The X-coordinate could be re-generated from the distance if necessary.

https://github.com/PatatasFritas/FriedKangaroo/commit/1669df5f91ef2cc8a7619b21f66883fa164ab602

zielar

full member

Activity: 281

Merit: 114

Quote from: Etar on May 27, 2020, 02:38:25 PM

If someone wants to run a solver with small DPs, but the server’s resources don’t allow it, then you can use the -wsplit option,
which appears in version 1.7 of the solver.
But in any case, you must have a PC that can merge files. I just had such a problem.
Now I can safely merge files on my home PC. In order not to do it all manually, you need a grabber and a merger.
File grabber is launched on the server, merger is launched on the home PC.
Merger communicates with the grabber and requests files from him. The graber sends, if any, and then removes them from the server.
The merger, in turn, after receiving the file from the grabber, starts the merge process, during which it is possible to find the key, after merge temp file deleted.
Grabber gives files only to an authorized merger.
If it helps someone, archive with source codes, compiled programs and example .bat files: https://drive.google.com/file/d/1YB3tz_tkJWTilXMCm_3GIfKsODGzDTqi
As before, the sources under Purebasic.
mergeServer(grabber):

Code:

-pass >password for merger authorization
-port >listening port, where merger will be connect
-ext >by this extension, the grabber will search for files in the folder,
for ex. using -ext part, than you should start server with -w xxxx.part

mergeClient(merger):

Code:

-jobtime 60000>request a file from the grabber every 60s
-name >it is name of your merger, useless, just for stats
-pass >password for authorization(should be the same as in grabber)
-server >host:port grabber
-workfile >name of your masterfile
-merger >Kangaroo.exe by default

You fell from heaven with this tool, man! Just tell me how to set -ext knowing that the latest release adds the ending without .part?

Etar

sr. member

Activity: 617

Merit: 312

If someone wants to run a solver with small DPs, but the server’s resources don’t allow it, then you can use the -wsplit option,
which appears in version 1.7 of the solver.
But in any case, you must have a PC that can merge files. I just had such a problem.
Now I can safely merge files on my home PC. In order not to do it all manually, you need a grabber and a merger.
File grabber is launched on the server, merger is launched on the home PC.
Merger communicates with the grabber and requests files from him. The graber sends, if any, and then removes them from the server.
The merger, in turn, after receiving the file from the grabber, starts the merge process, during which it is possible to find the key, after merge temp file deleted.
Grabber gives files only to an authorized merger.
If it helps someone, archive with source codes, compiled programs and example .bat files: https://drive.google.com/file/d/1wQWLCRsYY2s4DH2OZHmyTMMxIPn8kdsz
Edit: fixed little memory leak at grabber side.

As before, the sources under Purebasic.
mergeServer(grabber):

Code:

-pass >password for merger authorization
-port >listening port, where merger will be connect
-ext >by this extension, the grabber will search for files in the folder,
for ex. using -ext part, than you should start server with -w xxxx.part

mergeClient(merger):

Code:

-jobtime 60000>request a file from the grabber every 60s
-name >it is name of your merger, useless, just for stats
-pass >password for authorization(should be the same as in grabber)
-server >host:port grabber
-workfile >name of your masterfile
-merger >Kangaroo.exe by default

Jean_Luc

sr. member

Activity: 462

Merit: 696

Quote from: Etar on May 27, 2020, 11:17:06 AM

I tested -wsplit in the 89bit range. Works perfet! Thanks JeanLuc.
Grabber take files from server and send to local PC, where merger merged this files with masterfile.
Key solved during merge after 32minutes on 2080ti. I did not wait until the key is solved on the server, enough that it was found through merge.

Many thanks for the test

I'm currently working on the merger trying to speed it up and decrease memory consumption.

Etar

sr. member

Activity: 617

Merit: 312

I tested -wsplit in the 89bit range. Works perfet! Thanks JeanLuc.
Grabber take files from server and send to local PC, where merger merged this files with masterfile.
Key solved during merge after 32minutes on 2080ti. I did not wait until the key is solved on the server, enough that it was found through merge.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 27, 2020, 10:29:59 AM

-snip-
Different private keys, different positions, different points, different public keys.

Ok, got it. It is the group axiom.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: MrFreeDragon on May 27, 2020, 10:14:14 AM

Quote from: arulbero on May 27, 2020, 09:50:46 AM

-snip-
1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)
-snip-

I know that EC collision is not proved as there is no example.
Yes, for each private key there is only 1 point, however not necessary that if we have n private key we will have n different points.

Simple example for the group of 10 elements:

Code:

Key Point
1 7
2 6
3 5
4 7
5 3
6 2
7 7
8 0
9 9
0 7

You can see that for each key (0..9) there is only one Point, i.e. we do not receive 2 or 3 or more points for each key. We have only one point. However key 1,4,7 and 0 lead to Point 7 (collision). For group of 10 elements it is easy to check.

However how could you be sure that for group with almost 2^256 elements for every private key we have the unique Point?

'Group' has a specific meaning in math, it is not a simple set of elements, moreover a group with a prime number of elements has the property to be cyclic, i. e. you can 'generate' each element using only one element of the group (but not zero) and using the operation of the group: adding it to itself: G, G+G=2*G, G+G+G=3*G, ..... it is like to assign a number, a scalar, a order to each element from the point of view of G.

In the secp256k1 the group is a group of points, a cyclic group, and each private key is the 'position' of each point from the point of view of G (a chosen point). Because it is cyclic, when you perform G, G+G=2*G, G+G+G=3*G, ...., you generate all the elements of the group before to return to G.

Different private keys, different positions, different points, different public keys.

If you apply the Fermat's little theorem in a additive group, a*(n+1) = a, a+a+a+a+a....+a=a and
(n+1)*G = G.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 27, 2020, 09:50:46 AM

-snip-
1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)
-snip-

I know that EC collision is not proved as there is no example.
Yes, for each private key there is only 1 point, however not necessary that if we have n private key we will have n different points.

Simple example for the group of 10 elements:

Code:

Key Point
1 7
2 6
3 5
4 7
5 3
6 2
7 7
8 0
9 9
0 7

You can see that for each key (0..9) there is only one Point, i.e. we do not receive 2 or 3 or more points for each key. We have only one point. However key 1,4,7 and 0 lead to Point 7 (collision). For group of 10 elements it is easy to check.

However how could you be sure that for group with almost 2^256 elements for every private key we have the unique Point?

BitCrack

jr. member

Activity: 30

Merit: 122

Quote from: arulbero on May 27, 2020, 09:50:46 AM

Quote from: MrFreeDragon on May 27, 2020, 09:23:59 AM

Quote from: arulbero on May 27, 2020, 07:40:30 AM

-snip-
There are about 2^256 points, then 2^255 different X-coordinates (k*G and -k*G have the same x-coordinate).
-snip-

Is this proved fact?

I mean why every private key leads to the unique X-coordinate? (except for symmetry point).
In other words, if k and (order-k) leads to x-coordinate Xk, how could we be sure that there are no other key m leads to Xk as well? (m differs from k and (order-k) )

Because it is proved that:

1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)

2) for each x-coordinate, the y-coordinate must fulfil this relation: y^2 = x^3 + 7 mod n;

each equation of the form y^2 = a has or 2 opposite solutions (+y and -y -> k*G / -k*G), or has no solution.

Therefor there can't be 3 different points with the same x-coordinate and with 3 different y-coordinate, because there are no 3 different y solutions for the equation y^2 = a mod n.

We know that there are exactly (n-1)/2 different x-coordinates (and (n-1)/3 different y-coordinates)

That's how the math works. The points on the curve form a group (https://en.wikipedia.org/wiki/Group_%28mathematics%29) and the point G is a generator of that group.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: MrFreeDragon on May 27, 2020, 09:23:59 AM

Quote from: arulbero on May 27, 2020, 07:40:30 AM

-snip-
There are about 2^256 points, then 2^255 different X-coordinates (k*G and -k*G have the same x-coordinate).
-snip-

Is this proved fact?

I mean why every private key leads to the unique X-coordinate? (except for symmetry point).
In other words, if k and (order-k) leads to x-coordinate Xk, how could we be sure that there are no other key m leads to Xk as well? (m differs from k and (order-k) )

Because it is proved that:

1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)

2) for each x-coordinate, the y-coordinate must fulfil this relation: y^2 = x^3 + 7 mod p;

each equation of the form y^2 = a mod p has or 2*** opposite solutions (+y and -y -> k*G / -k*G), or has no solution.

Therefor there can't be 3 different points with the same x-coordinate and with 3 different y-coordinates, because there are no 3 different y solutions for the equation y^2 = a mod p.

We know that there are exactly (n-1)/2 different x-coordinates (and (n-1)/3 different y-coordinates)

***EDIT:

according to the Fermat's "little theorem"

https://brilliant.org/wiki/fermats-little-theorem/

a^p = a, then a^(p+1) = a^2 mod p then a^(p+1)/4 = sqrt(a) mod p

(note: in the secp256k1 p = 3 mod 4 then p+1 = 4 mod 4)

if y = a^(p+1)/4 is the sqrt(a) then y = -(a^(p+1)/4) is the sqrt(a) too, i.e. to the power of 2 they both produce the same result, a, that in our case is X^3 + 7.

Topic: Pollard's kangaroo ECDLP solver - page 121. (Read 58667 times)