Author

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

member
Activity: 330
Merit: 34
June 13, 2020, 03:21:11 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
Sorry, I'm still not tracking. Where is *G in the above?

037e....  - (80000....*G) = 033aeb....
what are these?
hex: 80000000000000000000
dec: 604462909807314587353088
pubkey: 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be

let me clear you more
if pubkey in 80 bit, he is doing minus 79bit, and thinking next key will be in 79 bit, but its not exact, its probability
next could be in 79 bit, or 78 bit, depand on 80 bit key location, which you all dont know, location mean 80bit start, middle, or in near last area of under 80 bit, you love to play try it again and again
btw staudy my 8 month old post and 
my exact down bit proof here
https://bitcointalksearch.org/topic/m.54531996
just trying to understand the math a little better.
pub - start range * G(generator point) = new pub key
in his first example
(pub)7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc - (start range) 80000000000000000000 * G = (pub) 3aeb....

real: (pub)  7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc
G = 1 or in point pubkey is 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
hex 80000000000000000000 = pub 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be

now play in 2 forms
Real - G(pub)*hex =
Real - hex(pub) =
point to point minus
clear Huh??
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 13, 2020, 03:13:01 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
Sorry, I'm still not tracking. Where is *G in the above?

037e....  - (80000....*G) = 033aeb....
what are these?
hex: 80000000000000000000
dec: 604462909807314587353088
pubkey: 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be

let me clear you more
if pubkey in 80 bit, he is doing minus 79bit, and thinking next key will be in 79 bit, but its not exact, its probability
next could be in 79 bit, or 78 bit, depand on 80 bit key location, which you all dont know, location mean 80bit start, middle, or in near last area of under 80 bit, you love to play try it again and again
btw staudy my 8 month old post and 
my exact down bit proof here
https://bitcointalksearch.org/topic/m.54531996
just trying to understand the math a little better.
pub - start range * G(generator point) = new pub key
in his first example
(pub)7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc - (start range) 80000000000000000000 * G = (pub) 3aeb....
member
Activity: 330
Merit: 34
June 13, 2020, 03:08:55 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
Sorry, I'm still not tracking. Where is *G in the above?

037e....  - (80000....*G) = 033aeb....
what are these?
hex: 80000000000000000000
dec: 604462909807314587353088
pubkey: 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be

let me clear you more
if pubkey in 80 bit, he is doing minus 79bit, and thinking next key will be in 79 bit, but its not exact, its probability
next could be in 79 bit, or 78 bit, depand on 80 bit key location, which you all dont know, location mean 80bit start, middle, or in near last area of under 80 bit, you love to play try it again and again
btw staudy my 8 month old post and 
my exact down bit proof here
https://bitcointalksearch.org/topic/m.54531996
member
Activity: 255
Merit: 27
June 13, 2020, 03:04:00 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)
But it’s really possible to divide any public key into 10 without knowing the private one. But to divide by 3, 6, 7, 9, 14 .... is already more difficult.
member
Activity: 330
Merit: 34
June 13, 2020, 03:02:43 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
Sorry, I'm still not tracking. Where is *G in the above?

037e....  - (80000....*G) = 033aeb....
what are these?
hex: 80000000000000000000
dec: 604462909807314587353088
pubkey: 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be
member
Activity: 255
Merit: 27
June 13, 2020, 02:59:59 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)
Mathematical working according to the rules of mathematics of public keys (addition, subtraction, division, multiplication), you will always get the coordinates (public key) at the output, which will have the corresponding private key.

Another thing is that one public key can have several private keys. But this collision has not yet been proven.

full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 13, 2020, 02:55:58 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
Sorry, I'm still not tracking. Where is *G in the above?

037e....  - (80000....*G) = 033aeb....
what are these?
copper member
Activity: 205
Merit: 1
June 13, 2020, 02:47:24 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,625c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
Sorry, I'm still not tracking. Where is *G in the above?

037e....  - (80000....*G) = 033aeb....
copper member
Activity: 205
Merit: 1
June 13, 2020, 02:45:22 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,625c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9

What tool do you use to subtract coordinates? Share the code please.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 13, 2020, 02:02:35 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,625c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
Sorry, I'm still not tracking. Where is *G in the above?
sr. member
Activity: 617
Merit: 312
June 13, 2020, 01:30:55 AM

how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
037e....  - 80000....*G = 033aeb....
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,625c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 13, 2020, 01:25:56 AM

If pubkey appear "under zero" after shifting it is not a matter you any way will found key.

Don`t use this method yet.
For test range is 80000000000000000000:ffffffffffffffffffff
I generate random key very close to begin range.
0x9000000f000000300001
without shifting key was found. with shifting - no. I don`t understand why..
I don't understand how it's helpful since you must know the private key in advance. Example, for puzzle 115, you have to know it's private key before shifting it down, but if you already have the private key, why shift down?
sr. member
Activity: 617
Merit: 312
June 13, 2020, 01:23:11 AM

If pubkey appear "under zero" after shifting it is not a matter you any way will found key.

Don`t use this method yet.
For test range is 80000000000000000000:ffffffffffffffffffff
I generate random key very close to begin range.
0x9000000f000000300001
without shifting key was found. with shifting - no. I don`t understand why..
full member
Activity: 281
Merit: 114
June 12, 2020, 09:10:51 PM
For a change, this is current progress
jr. member
Activity: 30
Merit: 122
June 12, 2020, 09:04:50 PM
It's available here: https://github.com/brichard19/eclambda

Basically, start the server, use the jobsubmit program to submit the problem details (public key, key length, DP bits) to the server, and use the client to retrieve work from the server and submit results back to the server.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 12, 2020, 08:12:56 PM
Etar, if you are talking about 100 bitcoin challenge competition, all the addresses have the pattern: their 1st (big endian) bit always equals to '1'. You can see for every found private key and present it in binary format, and you can see that the 1st bit always '1' (i mean the 1st of unknown part, without leading zeros).

For example, the key for 80bit address was 0xEA1A5C66DCC11B5AD180, and it is in binary:
11101010000110100101110001100110110111001100000100011011010110101101000110000000

The 1st is '1'.

HardwareCollector absolutely right saying that 80bit address has 79bit search range. And this applies to any other key: n-bit address has (n-1) bit search range.
But every key in 80 bit range will have a "1" at the 80 bit marker, or else it would be a different bit. Turn that 1 into a 0 and if it's followed by a 1, then it's a 79 bit key.

The puzzle creator had to make the last bit always 1, otherwise it would be possible that two private keys would be in the same search range when doing a sequential brute-force search. Making the high bit 1 guarantees that the next puzzle will be 1 bit longer than the previous.
When's that new tool available?
jr. member
Activity: 30
Merit: 122
June 12, 2020, 07:59:38 PM
Etar, if you are talking about 100 bitcoin challenge competition, all the addresses have the pattern: their 1st (big endian) bit always equals to '1'. You can see for every found private key and present it in binary format, and you can see that the 1st bit always '1' (i mean the 1st of unknown part, without leading zeros).

For example, the key for 80bit address was 0xEA1A5C66DCC11B5AD180, and it is in binary:
11101010000110100101110001100110110111001100000100011011010110101101000110000000

The 1st is '1'.

HardwareCollector absolutely right saying that 80bit address has 79bit search range. And this applies to any other key: n-bit address has (n-1) bit search range.
But every key in 80 bit range will have a "1" at the 80 bit marker, or else it would be a different bit. Turn that 1 into a 0 and if it's followed by a 1, then it's a 79 bit key.

The puzzle creator had to make the last bit always 1, otherwise it would be possible that two private keys would be in the same search range when doing a sequential brute-force search. Making the high bit 1 guarantees that the next puzzle will be 1 bit longer than the previous.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 12, 2020, 07:37:23 PM
Etar, if you are talking about 100 bitcoin challenge competition, all the addresses have the pattern: their 1st (big endian) bit always equals to '1'. You can see for every found private key and present it in binary format, and you can see that the 1st bit always '1' (i mean the 1st of unknown part, without leading zeros).

For example, the key for 80bit address was 0xEA1A5C66DCC11B5AD180, and it is in binary:
11101010000110100101110001100110110111001100000100011011010110101101000110000000

The 1st is '1'.

HardwareCollector absolutely right saying that 80bit address has 79bit search range. And this applies to any other key: n-bit address has (n-1) bit search range.
But every key in 80 bit range will have a "1" at the 80 bit marker, or else it would be a different bit. Turn that 1 into a 0 and if it's followed by a 1, then it's a 79 bit key.
sr. member
Activity: 443
Merit: 350
June 12, 2020, 06:30:51 PM
Etar, if you are talking about 100 bitcoin challenge competition, all the addresses have the pattern: their 1st (big endian) bit always equals to '1'. You can see for every found private key and present it in binary format, and you can see that the 1st bit always '1' (i mean the 1st of unknown part, without leading zeros).

For example, the key for 80bit address was 0xEA1A5C66DCC11B5AD180, and it is in binary:
11101010000110100101110001100110110111001100000100011011010110101101000110000000

The 1st is '1'.

HardwareCollector absolutely right saying that 80bit address has 79bit search range. And this applies to any other key: n-bit address has (n-1) bit search range.
member
Activity: 144
Merit: 10
June 12, 2020, 05:30:00 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..
It’s an 80-bit private key challenge and because we know that the private key can only be expressed with 80 bits, we can immediately eliminate half of the search interval. Half of 2^80 is 2^79, so that’s why I call it 80-bit private key challenge with a 79-bit search interval. Same is true for the other private key challenges with exposed public keys in this series. You cannot reduce the search space any further without brute force.
Jump to: