Pollard's kangaroo ECDLP solver - page 105.

brainless

member

Activity: 330

Merit: 34

Quote from: Etar on June 12, 2020, 10:42:53 AM

Quote from: mrxtraf on June 12, 2020, 10:16:50 AM

-snip-
interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?

i think that not all points have private key, maybe i am wrong
For example simple 7/5 it is (3ef1f322847965ee7f8d745af562e6507568fea5316b199f7349a2717021661d,b9a20bc3783777d2681f64d92740817f95b2c169c5db92ce0bab00efb36c0d74)
i don`t know if this result have private key.. (n+7)/5 give the same result as for ex. (n+3)/5 = 0x33333333333333333333333333333332f222f8faefdb533f265d461c29a47374
but 0x33333333333333333333333333333332f222f8faefdb533f265d461c29a47374 for (n+3)/5 is correct.
becouse if 1 have the same x-coordinate as n-1 so there only 2^255 points with unique x-coordinate. So there can be around 2^255 points that not have private key.(maybe Wink

)

private key : CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBC88BE3EBBF6D4CFC99751870A691CDCf
pub k : 023ef1f322847965ee7f8d745af562e6507568fea5316b199f7349a2717021661d
92633671389852956338856788006950326282270051423259923506084130513214529195471

brainless

member

Activity: 330

Merit: 34

Quote from: Etar on June 12, 2020, 10:42:53 AM

Quote from: mrxtraf on June 12, 2020, 10:16:50 AM

-snip-
interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?

i think that not all points have private key, maybe i am wrong
For example simple 7/5 it is (3ef1f322847965ee7f8d745af562e6507568fea5316b199f7349a2717021661d,b9a20bc3783777d2681f64d92740817f95b2c169c5db92ce0bab00efb36c0d74)
i don`t know if this result have private key.. (n+7)/5 give the same result as for ex. (n+3)/5 = 0x33333333333333333333333333333332f222f8faefdb533f265d461c29a47374
but 0x33333333333333333333333333333332f222f8faefdb533f265d461c29a47374 for (n+3)/5 is correct.
becouse if 1 have the same x-coordinate as n-1 so there only 2^255 points with unique x-coordinate. So there can be around 2^255 points that not have private key.(maybe Wink

)

each and every point have privatekey

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: mrxtraf on June 12, 2020, 10:16:50 AM

interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?

You can't.

Let P be a public key with unknown private key k (that means P = k*G)

By definition, you can get a public key Q such that 10*Q = P in this way:

Q = inv(10)*P = inv(10)*k*G

that's all you can have (if you don't know k, you don't know inv(10)*k neither)

Etar

sr. member

Activity: 642

Merit: 316

Quote from: mrxtraf on June 12, 2020, 10:16:50 AM

-snip-
interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?

i think that not all points have private key, maybe i am wrong
For example simple 7/5 it is (3ef1f322847965ee7f8d745af562e6507568fea5316b199f7349a2717021661d,b9a20bc3783777d2681f64d92740817f95b2c169c5db92ce0bab00efb36c0d74)
i don`t know if this result have private key.. (n+7)/5 give the same result as for ex. (n+3)/5 = 0x33333333333333333333333333333332f222f8faefdb533f265d461c29a47374
but 0x33333333333333333333333333333332f222f8faefdb533f265d461c29a47374 for (n+3)/5 is correct.
becouse if 1 have the same x-coordinate as n-1 so there only 2^255 points with unique x-coordinate. So there can be around 2^255 points that not have private key.(maybe Wink

)

mrxtraf

member

Activity: 255

Merit: 27

Quote from: arulbero on June 12, 2020, 08:26:03 AM

Quote from: mrxtraf on June 12, 2020, 07:42:58 AM

Quote from: brainless on June 12, 2020, 07:41:56 AM

Quote from: mrxtraf on June 12, 2020, 07:40:01 AM

Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001

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

Real privat key?

0.1 = 10^-1 mod n

inverse of a = a^(n-1) mod n

Code:

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

b=pow(10,n-1,n)
b
81054462466121336796499689506081535496986294995352433067823614199062713046036  <-- inverse of 10 mod n

hex(b)
0xb33333333333333333333333333333324f7a676e477fa35d0646756291bf9414  <-- inverse of 10 mod n

Verify:

Code:

b*10 % n
1

interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: mrxtraf on June 12, 2020, 07:42:58 AM

Quote from: brainless on June 12, 2020, 07:41:56 AM

Quote from: mrxtraf on June 12, 2020, 07:40:01 AM

Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001

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

Real privat key?

0.1 = 10^-1 mod n

inverse of a = a^(n-1) mod n

Code:

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

b=pow(10,n-1,n)
b
81054462466121336796499689506081535496986294995352433067823614199062713046036  <-- inverse of 10 mod n

hex(b)
0xb33333333333333333333333333333324f7a676e477fa35d0646756291bf9414  <-- inverse of 10 mod n

Verify:

Code:

b*10 % n
1

mrxtraf

member

Activity: 255

Merit: 27

Quote from: brainless on June 12, 2020, 07:41:56 AM

Quote from: mrxtraf on June 12, 2020, 07:40:01 AM

Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001

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

Real privat key?

brainless

member

Activity: 330

Merit: 34

Quote from: mrxtraf on June 12, 2020, 07:40:01 AM

Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001

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

mrxtraf

member

Activity: 255

Merit: 27

Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001

Etar

sr. member

Activity: 642

Merit: 316

Quote from: brainless on June 12, 2020, 07:28:54 AM

-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

brainless

member

Activity: 330

Merit: 34

Quote from: brainless on June 12, 2020, 07:24:32 AM

Quote from: Etar on June 12, 2020, 07:18:28 AM

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

brainless

member

Activity: 330

Merit: 34

Quote from: Etar on June 12, 2020, 07:18:28 AM

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

Etar

sr. member

Activity: 642

Merit: 316

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)

Jean_Luc

sr. member

Activity: 462

Merit: 701

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 Wink

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: arulbero on June 11, 2020, 04:10:52 PM

Quote from: Etar on June 11, 2020, 03:46:29 PM

Quote from: arulbero on June 11, 2020, 03:26:46 PM

-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

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: Etar on June 11, 2020, 03:46:29 PM

Quote from: arulbero on June 11, 2020, 03:26:46 PM

-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.

Etar

sr. member

Activity: 642

Merit: 316

Quote from: arulbero on June 11, 2020, 03:26:46 PM

-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

legendary

Activity: 1932

Merit: 2077

Quote from: Etar on June 11, 2020, 02:46:32 PM

Quote from: arulbero on June 11, 2020, 01:35:59 PM

-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:

Quote from: Etar on June 11, 2020, 02:46:32 PM

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.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: WanderingPhilospher on June 11, 2020, 02:06:48 PM

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.

Etar

sr. member

Activity: 642

Merit: 316

Quote from: arulbero on June 11, 2020, 01:35:59 PM

-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

Topic: Pollard's kangaroo ECDLP solver - page 105. (Read 59389 times)