Pollard's kangaroo ECDLP solver

[WanderingPhilospher]

If any of you are working on #115 or #120 or # any above that, by yourself, you're just wasting power.

Jean Luc's knowledge, with Zielar's unlimited GPUs through his work...YOU can't compete. Especially if Jean Luc is making changes to increase chances of Zielar finding the puzzle.

You can't compete. Not with Kangaroo. You'll have to get creative and try random other options.

It's like everyone has GPU power but no one wants to link up and send DPs to common server, or get together and agree on a specific DP to share work files, etc.

I'd rather have 10% of 1.15 BTC versus 0%.

I'm still in the chase, but not strictly with Kangaroo. I offered up my work files, at DP 30 or 31. They are just sitting in file, no longer being used. I'm down to DP 12, with creative works.

We also get lots of troubles handling large workfiles (above 200GB) so I created a partitioned work file system (available on github) , an integrity workfile checker.

Told you 

[WanderingPhilospher]

How long are your GPUs working on #115?

If #110 was solved for 2 days, so with the same speed and the same luck you need 2days * sqrt(2^5) = 2 days * 5.66 ~ 11.3 days for #115. So, yes, if you started on 1 June, the estimated completion date 11-12 June  

For #110 you was very close to sqrt(n) operations, but not the average 2*sqrt(n). That means that probably you should wait another 11-12 days to be close to the average and 50% probability to find the key.

EDIT:
I doubt you will find the #115 key tomorrow. Much more likely at the end of June, or mid July. But not tomorrow.

We almost reached 50% probability yesterday (~8 days of run, ~2^33 DP, DP25) but unfortunately everything was shutdown due to a storm
Fortunately the workfiles has been preserved but we have to restart clients and servers to recover from crash.
As there was no kangaroo backup we will get a DP overhead by restarting the work.
I don't know if Zielar restarted the GPUs, yesterday he was a bit nervous
We also get lots of troubles handling large workfiles (above 200GB) so I created a partitioned work file system (available on github) , an integrity workfile checker. We manage to re-merge all worfiles in ~24H.
The current release is tagged 1.10(unstable) but should work.
Hope it will go better now...

I've told you...build a comparer. No issues with overhead or large workfiles or 24 hour merging. I've built a homemade one and am able to run any DP without any RAM or merging issues. But I'm not a programmer and know a better one can be built.

[Etar]

Anybody think about using bsgs algo but with DP?
bsgs  fast but have a problem due to memory usage. maybe using DP can solve this issues?

[WanderingPhilospher]

Anybody think about using bsgs algo but with DP?
bsgs  fast but have a problem due to memory usage. maybe using DP can solve this issues?

Extremely fast, it gets through a FFFFFFFFFFF range in 2 seconds total. Including step build time. Only uses 600Mb.

I thought about how to implement it differently. Use DP or build the table on harddrive and when giants start stepping compare back to the saved table. After so long, save the giant file with previously created file, and continue with giant step.

[arulbero]

Anybody think about using bsgs algo but with DP?
bsgs  fast but have a problem due to memory usage. maybe using DP can solve this issues?

Extremely fast, it gets through a FFFFFFFFFFF range in 2 seconds total. Including step build time. Only uses 600Mb.

I thought about how to implement it differently. Use DP or build the table on harddrive and when giants start stepping compare back to the saved table. After so long, save the giant file with previously created file, and continue with giant step.

How do you use DPs with BSGS?

[WanderingPhilospher]

Anybody think about using bsgs algo but with DP?
bsgs  fast but have a problem due to memory usage. maybe using DP can solve this issues?

Extremely fast, it gets through a FFFFFFFFFFF range in 2 seconds total. Including step build time. Only uses 600Mb.

I thought about how to implement it differently. Use DP or build the table on harddrive and when giants start stepping compare back to the saved table. After so long, save the giant file with previously created file, and continue with giant step.

How do you use DPs with BSGS?

I don't...Etar was pondering if it could be done. I just added some of the thoughts I have had because the speed is insane and it's a 100% solver.

[WanderingPhilospher]

What are your thoughts...

For this Kangaroo ECDLP solver, if RAM was not an issue, what is the optimal DP setting?

Would lower always be better? Small DP means you have to find more DPs.

Expected group operations remains the same no matter how you adjust the DP, right?

So what is the optimal DP setting if RAM is not an issue?

[Etar]

-snip-
How do you use DPs with BSGS?

First fill baby steps, but not each point put to table but only DP and distance
when you reach last DP you will get final distance.
Doubled distance it will be Giant steps.
Before GS you need to find 2 DP (+/-) for known pubkey, compare with hashtable this DP
if not success sub GS from pubkey and repeat..

In ex. i generate random pubkey b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82bbfbb9d25748a27 92fcac6ec1b892db592556534f1b6155a37804522d1ff2194
private key is 0xA0300879 in range 2^32
I set DPsize=8, and maxDP in table around 262144
when i fill baby steps i get 262346 DPs
It is very small hashtable ofcourse it is just for test..
In this case i should make 20 giant steps to find key.
Total add point op was 6981.

Code:

DPSIZE   :8
MASK     :ff00000000000000000000000000000000000000000000000000000000000000
TOTAL DPs:262144
STARTx:79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
STARTy:483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
FINDx :b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82
FINDy :bbfbb9d25748a2792fcac6ec1b892db592556534f1b6155a37804522d1ff2194
100.1%
TOTAL DPs  :262346
AVEDIST    :256
TABLE SIZE :0000000000000000000000000000000000000000000000000000000004000001
SUB POINTx:930224dc7b052d55216cd197b65997a703e4864ed12ef2f65018a5c8d815dde7
SUB POINTy:392b293eb3eb8d6597f659938411eb241d9ebb59209eeddb308e09b7dd5bf9ea
JUMP..20
+FIND!!!>>00000000000000000000000000000000000000000000000000000000A0300879
HASH DISTANCE:3147960
PRE DISTANCE:2684354600
DISTANCE:103
POINTx:b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82
POINTy:bbfbb9d25748a2792fcac6ec1b892db592556534f1b6155a37804522d1ff2194
op 6981

the same with 2^40 range

Code:

DPSIZE   :8
MASK     :ff00000000000000000000000000000000000000000000000000000000000000
TOTAL DPs:1048576
STARTx:79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
STARTy:483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
FINDx :d25841ae281aad4c516463fe69553b6f9526ef39692b7a5a483d30fee7a3bc22
FINDy :0ab386a9f0985ba4718c827250789cc5e7fc0852800521bb725e05dddc9a4bc2
100.0%
TOTAL DPs  :1048354
AVEDIST    :256
TABLE SIZE :0000000000000000000000000000000000000000000000000000000010000001
SUB POINTx:2d0ea198923cdaf6c8e38f2f7595912a19efb1e78a6c0ce793863da8b4312e3c
SUB POINTy:f61fb584f1753d923951f4af8b26d9e96b572283c3f12c15971f6699bc74362b
JUMP..1315
+FIND!!!>>000000000000000000000000000000000000000000000000000000A4530846E5
HASH DISTANCE:217563888
PRE DISTANCE:705985251910
DISTANCE:113
POINTx:d25841ae281aad4c516463fe69553b6f9526ef39692b7a5a483d30fee7a3bc22
POINTy:0ab386a9f0985ba4718c827250789cc5e7fc0852800521bb725e05dddc9a4bc2
op 530970

[arulbero]

For this Kangaroo ECDLP solver, if RAM was not an issue, what is the optimal DP setting?

Would lower always be better? Small DP means you have to find more DPs.

Expected group operations remains the same no matter how you adjust the DP, right?

So what is the optimal DP setting if RAM is not an issue?

If the RAM was not a issue, it would be better to use a low DP, because high DP means long time between a collision and its detection, especially if you use many kangaroos in parallel.  

But not too low, with DP = 0 ** you would have the minimum number of steps, but the generation of the the start points is much slower than the generation of the other points of the path. Let's say that the cost of generating a start point is about x50 the cost of generating the next point with a single jump, with an average length of 10k points (about 2^13) you should have a good value. Then DP = 12 / 13 / 14, not more.

** A note: if you use equivalence classes with DP = 0, you need only sqrt(2).sqrt(N) steps, this is the expected group operations.

[arulbero]

-snip-
How do you use DPs with BSGS?

First fill baby steps, but not each point put to table but only DP and distance
when you reach last DP you will get final distance.
Doubled distance it will be Giant steps.
Before GS you need to find 2 DP (+/-) for known pubkey, compare with hashtable this DP
if not success sub GS from pubkey and repeat..

But in this way you find the private key at 100%?

EDIT:

In ex. i generate random pubkey b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82bbfbb9d25748a27 92fcac6ec1b892db592556534f1b6155a37804522d1ff2194
private key is 0xA0300879 in range 2^32
I set DPsize=8, and maxDP in table around 262144
when i fill baby steps i get 262346 DPs
It is very small hashtable ofcourse it is just for test..
In this case i should make 20 giant steps to find key.
Total add point op was 6981.

With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.

[Etar]

-snip-
With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.

you can use what ever you want amount of DPs, but less amount of DP then more GS you need.
here is 16k DPs

Code:

DPSIZE   :8
MASK     :ff00000000000000000000000000000000000000000000000000000000000000
TOTAL DPs:16384
STARTx:79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
STARTy:483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
FINDx :225e0e43997fb77b83ef7e61a7be88d2851b09da3e36615c0a2d7e06f06b4517
FINDy :cb488adc7c5ba9f4bf0ccf48e0adc7bd2fb2b1488ed42c9cd14a5762be5017dd
101.1%
TOTAL DPs  :16567
AVEDIST    :253
TABLE SIZE :00000000000000000000000000000000000000000000000000000000003fffff
SUB POINTx:045685b52a932ee1f2638b9ea3b075f8be2ecd902e14bb7eb1ff0c24c22bbcc5
SUB POINTy:672f0bb37150ac5427d93df317fcb2b2798251581f4966f067f59291b1413b5c
JUMP..142
HASH DISTANCE:3177180
PRE DISTANCE:1191182052
DISTANCE:159
POINTx:225e0e43997fb77b83ef7e61a7be88d2851b09da3e36615c0a2d7e06f06b4517
POINTy:cb488adc7c5ba9f4bf0ccf48e0adc7bd2fb2b1488ed42c9cd14a5762be5017dd
+FIND!!!>>0000000000000000000000000000000000000000000000000000000046CF8369
op 57909

[arulbero]

-snip-
With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.

you can use what ever you want amount of DPs, but less amount of DP then more GS you need.
here is 16k DPs

The goal is to use less RAM than classic BSGS.

Let's say we want to find a key in 120 bit range.
With the classic BSGS you need 2^60 BS (huge amount of RAM) and 2^60 GS.

With BSGS + (DP = 10):

2^50 BABYSTEPS  + on average 2^59 GIANTSTEPS * 2^10 = 2^69 steps.

Then less RAM but more steps.

With BSGS + (DP = 10):

if you want to use more BABYSTEPS:

2^80 BABYSTEPS  + on average 2^29 GIANTSTEPS * 2^10 = 2^80 steps + 2^39 GIANTSTEPS.

The advantage is that you can precompute this 2^80 BABYSTEPS, but you don't have space to store them.

[COBRAS]

-snip-
With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.

you can use what ever you want amount of DPs, but less amount of DP then more GS you need.
here is 16k DPs

The goal is to use less RAM than classic BSGS.

Let's say we want to find a key in 120 bit range.
With the classic BSGS you need 2^60 BS (huge amount of RAM) and 2^60 GS.

With BSGS + (DP = 10):

2^50 BABYSTEPS  + on average 2^59 GIANTSTEPS * 2^10 = 2^69 steps.

Then less RAM but more steps.

With BSGS + (DP = 10):

if you want to use more BABYSTEPS:

2^80 BABYSTEPS  + on average 2^29 GIANTSTEPS * 2^10 = 2^80 steps + 2^39 GIANTSTEPS.

The advantage is that you can precompute this 2^80 BABYSTEPS, but you don't have space to store them.

Jean_Luc BSGS support only 2^32 max BABYSTEP

[Jean_Luc]

New release 1.10 available:

    Added -wcheck option (Check workfile integrity)
    Added partitioned work file
    Merger performance increase

https://github.com/JeanLucPons/Kangaroo/releases

Thanks for testing

[Etar]

Interesting thing this elliptic curve..
I didn’t think that there are even fractional points on the curve
For ex. if 7/2=3.5

Code:

(5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)
/2=
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)

and if double this point it will be again 7
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
+
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
=
(5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)

[brainless]

Interesting thing this elliptic curve..
I didn’t think that there are even fractional points on the curve
For ex. if 7/2=3.5

Code:

(5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)
/2=
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)

and if double this point it will be again 7
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
+
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
=
(5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)

3.5 would be in real figure
57896044618658097711785492504343953926418782139537452191302581570759080747172
hex:  7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A4
pubkey: 04592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b03172dd2e1d26c23 3337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d

its common practice

[brainless]

Interesting thing this elliptic curve..
I didn’t think that there are even fractional points on the curve
For ex. if 7/2=3.5

Code:

(5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)
/2=
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)

and if double this point it will be again 7
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
+
(592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
=
(5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)

3.5 would be in real figure
57896044618658097711785492504343953926418782139537452191302581570759080747172
hex:  7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A4
pubkey: 04592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b03172dd2e1d26c23 3337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d

its common practice

both odd and even fractional points are exist, you only need to calc it, as i can do it

[Etar]

-snip-
both odd and even fractional points are exist, you only need to calc it, as i can do it

Can you explain  how you calculate 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A4 ?
edit: solved (n+7)/2

[mrxtraf]

Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001 

[brainless]

Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001 

for 0.1
a = 1/3
b = a/2
result = 0.1