Pollard's kangaroo ECDLP solver - page 104.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: Etar on June 12, 2020, 04:46:02 PM

Quote from: WanderingPhilospher on June 12, 2020, 04:15:01 PM

-snip-
Can you give details on how you are shifting? Interesting concept I'd like to learn more about. Thanks.

for ex. pazzle #79
pub 037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc
range 80000000000000000000:ffffffffffffffffffff
1step
sub 80000000000000000000 from pub >>033aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a0
and sub 80000000000000000000 from range>>new range 0:7fffffffffffffffffff
center of range it is 3fffffffffffffffffff
So again sub 3fffffffffffffffffff from pub>>02f65e6e18eab67f86287d565702468c2f30a303f22ebdcebe556c23d016350222
and sub 3fffffffffffffffffff from range>>new range 0:3fffffffffffffffffff

after key will be solved add 3fffffffffffffffffff and 80000000000000000000 to key.

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key

Etar

sr. member

Activity: 617

Merit: 312

Quote from: WanderingPhilospher on June 12, 2020, 04:15:01 PM

-snip-
Can you give details on how you are shifting? Interesting concept I'd like to learn more about. Thanks.

for ex. pazzle #79
pub 037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc
range 80000000000000000000:ffffffffffffffffffff
1step
sub 80000000000000000000 from pub >>033aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a0
and sub 80000000000000000000 from range>>new range 0:7fffffffffffffffffff
center of range it is 3fffffffffffffffffff
So again sub 3fffffffffffffffffff from pub>>02f65e6e18eab67f86287d565702468c2f30a303f22ebdcebe556c23d016350222
and sub 3fffffffffffffffffff from range>>new range 0:3fffffffffffffffffff

after key will be solved add 3fffffffffffffffffff and 80000000000000000000 to key.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: Etar on June 12, 2020, 04:07:22 PM

I think we can reduce the search range by 1 bit by shifting the initial range, and then shifting half the range.
For example, the 79bit puzzle is shifted to the 78bit range:

Code:

Start:0
Stop :3FFFFFFFFFFFFFFFFFFF
Range width: 2^78
[1405.94 MK/s][GPU 1405.94 MK/s][Count 2^38.90][Dead 0][06:55 (Avg 15:15)][481.5/608.4MB]
Key# 0 [1S]Pub:  0x02F65E6E18EAB67F86287D565702468C2F30A303F22EBDCEBE556C23D016350222
       Priv: 0x2A1A5C66DCC11B5AD181 + 0x3fffffffffffffffffff + 0x80000000000000000000 = 0xea1a5c66dcc11b5ad180

without shifting:

Code:

Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Range width: 2^79
[1380.42 MK/s][GPU 1380.42 MK/s][Count 2^40.59][Dead 0][22:35 (Avg 21:15)][1541.1/1932.8MB]
Key# 0 [1S]Pub:  0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
       Priv: 0xEA1A5C66DCC11B5AD180

As you can see time and count less with shifting.
If pubkey appear "under zero" after shifting it is not a matter you any way will found key.

Here is example were pubkey is "below zero"
random key 0xbc690499fb50bfde866b

Code:

Start:0
Stop :3FFFFFFFFFFFFFFFFFFF
Range width: 2^78
[1390.34 MK/s][GPU 1390.34 MK/s][Count 2^40.00][Dead 0][14:53 (Avg 15:26)][1027.3/1290.6MB]
Key# 0 [1S]Pub:  0x02996740F4755163FB167F7D06875B3F415CD7AB9E2F198DE66E1E7D082086E64F
       Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF489CA4C46C59DD9014C7AD + 0x3fffffffffffffffffff + 0x80000000000000000000 = 0xbc690499fb50bfde866b

without shifting:

Code:

Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Range width: 2^79
[1385.36 MK/s][GPU 1385.36 MK/s][Count 2^39.90][Dead 1][13:54 (Avg 21:10)][957.7/1203.7MB]
Key# 0 [1S]Pub:  0x02D48BBCB4370DA5F3CD5FBC25D1052C8BAC97953C65FB4F837A423320FAE88CB4
       Priv: 0xBC690499FB50BFDE866B

In last example without shifting little bit faster because pubkey was around the center of range.
Any way need few test..

Can you give details on how you are shifting? Interesting concept I'd like to learn more about. Thanks.

Etar

sr. member

Activity: 617

Merit: 312

I think we can reduce the search range by 1 bit by shifting the initial range, and then shifting half the range.
For example, the 79bit puzzle is shifted to the 78bit range:

Code:

Start:0
Stop :3FFFFFFFFFFFFFFFFFFF
Range width: 2^78
[1405.94 MK/s][GPU 1405.94 MK/s][Count 2^38.90][Dead 0][06:55 (Avg 15:15)][481.5/608.4MB]
Key# 0 [1S]Pub:  0x02F65E6E18EAB67F86287D565702468C2F30A303F22EBDCEBE556C23D016350222
       Priv: 0x2A1A5C66DCC11B5AD181 + 0x3fffffffffffffffffff + 0x80000000000000000000 = 0xea1a5c66dcc11b5ad180

without shifting:

Code:

Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Range width: 2^79
[1380.42 MK/s][GPU 1380.42 MK/s][Count 2^40.59][Dead 0][22:35 (Avg 21:15)][1541.1/1932.8MB]
Key# 0 [1S]Pub:  0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
       Priv: 0xEA1A5C66DCC11B5AD180

As you can see time and count less with shifting.
If pubkey appear "under zero" after shifting it is not a matter you any way will found key.

Here is example were pubkey is "below zero"
random key 0xbc690499fb50bfde866b

Code:

Start:0
Stop :3FFFFFFFFFFFFFFFFFFF
Range width: 2^78
[1390.34 MK/s][GPU 1390.34 MK/s][Count 2^40.00][Dead 0][14:53 (Avg 15:26)][1027.3/1290.6MB]
Key# 0 [1S]Pub:  0x02996740F4755163FB167F7D06875B3F415CD7AB9E2F198DE66E1E7D082086E64F
       Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF489CA4C46C59DD9014C7AD + 0x3fffffffffffffffffff + 0x80000000000000000000 = 0xbc690499fb50bfde866b

without shifting:

Code:

Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Range width: 2^79
[1385.36 MK/s][GPU 1385.36 MK/s][Count 2^39.90][Dead 1][13:54 (Avg 21:10)][957.7/1203.7MB]
Key# 0 [1S]Pub:  0x02D48BBCB4370DA5F3CD5FBC25D1052C8BAC97953C65FB4F837A423320FAE88CB4
       Priv: 0xBC690499FB50BFDE866B

In last example without shifting little bit faster because pubkey was around the center of range.
Any way need few test..

MrFreeDragon

sr. member

Activity: 443

Merit: 350

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

There are no fractional points. All points are integer. Your example with integer 7 divided by 2 is not the same in discrete group.
If you divide 7 by 2 you receive not 3.5, but you receive the following integer number:

invert(2) * 7 mod order = 57896044618658097711785492504343953926418782139537452191302581570759080747169 * 7 mod order = 57896044618658097711785492504343953926418782139537452191302581570759080747172

So, if you divide 7 by 2 you will receive number 57896044618658097711785492504343953926418782139537452191302581570759080747172 or 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a4 in hex, and it is NOT 3.5

If you double this number by module order, you will have your initial 7 number:

(0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a4 * 2) mod 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 = 7

The reason is easy. Numbers within the order are no infinite, they are limited to the order. That means they are repeating and could be considered as a wheel.

Imagine huge wheel with all integers from 0 to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (order-1) marked on it. So you can roll it forever for infinite numbers, but all the results will be only within the order, and only integers. Not fractional numbers.

Etar

sr. member

Activity: 617

Merit: 312

Quote from: brainless on June 12, 2020, 11:32:25 AM

-snip-
private key : CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBC88BE3EBBF6D4CFC99751870A691CDCf
pub k : 023ef1f322847965ee7f8d745af562e6507568fea5316b199f7349a2717021661d
92633671389852956338856788006950326282270051423259923506084130513214529195471

can you explaine calculation?
Seems like understand the same as devide.
7*(inverse(5)%n)

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

Merit: 312

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

Merit: 312

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

Merit: 312

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

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

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