Pollard's kangaroo ECDLP solver - page 29.

_Counselor

member

Activity: 110

Merit: 61

Quote from: NotATether on September 30, 2021, 04:28:10 AM

Thanks for explaining this in concise terms.

Amazing how I thought this whole conjuncture was BS until someone actually came along with a proper demonstration.

The question now is how much more effective will this be vs. just dividing the keys?

i think these methods won't speed up 120 and further solution with Kangaroo or BSGS, because mathematically this is the same as dividing the original range to X parts and check them all for orginal pubkey.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: _Counselor on September 30, 2021, 03:17:26 AM

I'm already explained that all ranges will be X (X - divisor) times smaller than original range

Quote

FFFFFFFF / 33 = 7C1F07D
(45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a + 7C1F07D) = end of range

Thanks for explaining this in concise terms.

Amazing how I thought this whole conjuncture was BS until someone actually came along with a proper demonstration.

The question now is how much more effective will this be vs. just dividing the keys?

_Counselor

member

Activity: 110

Merit: 61

Quote from: NotATether on September 30, 2021, 01:53:31 AM

There is still one problem with this though, all the range beginnings are still much larger than the range end (assuming you're not simply adding length of #120 to it, if you're just dividing it by 33 or something it's guaranteed to be much smaller).

I'm already explained that all ranges will be X (X - divisor) times smaller than original range

Quote

FFFFFFFF / 33 = 7C1F07D
(45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a + 7C1F07D) = end of range

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: _Counselor on September 29, 2021, 09:53:29 AM

If we use 33 as divisor, than to determine beginning of each range you have to multiply numbers (1 .. 33) to inverse(33, secp256k1.p)
therefore you will get 33 possible ranges beginnings:

~snip

Size of the resulting ranges will be 33 times smaller than original, so you can calculate end of each range.
In our case WP searched this range:
3 45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a

To be honest, I don't know how and what exactly WP calculates, but that is main idea of such key reduction.

There is still one problem with this though, all the range beginnings are still much larger than the range end (assuming you're not simply adding length of #120 to it, if you're just dividing it by 33 or something it's guaranteed to be much smaller).

apvl

newbie

Activity: 4

Merit: 0

Quote from: a.a on September 29, 2021, 04:36:13 PM

@WP

What tool do you use for bruteforcing x point only search?

@apvl
You are kind of in the wrong thread if you ask about VanityBitCrack in the Kangaroo-Thread

ya aint wrong lol my b

a.a

member

Activity: 126

Merit: 36

@WP

What tool do you use for bruteforcing x point only search?

@apvl
You are kind of in the wrong thread if you ask about VanityBitCrack in the Kangaroo-Thread

apvl

newbie

Activity: 4

Merit: 0

So in turn is there a way to maximize the load of VanityGenBitcrack? currently only getting 123Mkeys/s

a.a

member

Activity: 126

Merit: 36

No, as they are different principles.

BitCrack gets a list of addresses and brute forces the privatekey. This means that if we have public keys, we can convert them to addresses and then bruteforce them in BitCrack, but we have the overhead of privatekey to public key to sha256 to ripemd160.
VanitySearch can as far as I know use directly the public keys so there is not that overhead, what we have in bitcrack to do the extra work of transforming the public key to the ripemd160
Kangaroo is not really bruteforcing the publickey but using a mathematical process to crack it.

So no, you can not mix them.

apvl

newbie

Activity: 4

Merit: 0

Would it be possible to combine Kangaroo algorithms with other programs such at Vanity or BitCrack. Currently running a VanitySearch
Number of CPU thread: 32
GPU: GPU #0 NVIDIA GeForce RTX 3050 Ti Laptop GPU (20x0 cores) Grid(160x128)
[952.00 Mkey/s][GPU 910.98 Mkey/s][Total 2^39.19][Prob 50.7%][60% in 00:03:15]
on BitCrack Roughly 600 Mkeys/s
Kangaroo is [563.76 MK/s][GPU 451.75 MK/s][Count 2^32.43][Dead 0][10s (Avg 33.6656y)

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: a.a on September 29, 2021, 10:53:45 AM

Quote from: WanderingPhilospher on September 29, 2021, 10:40:47 AM

Note: There will be at least 2 keys that will solve original pub key's private key, in every range.

Please elaborate.

After you did the division twice?

Or because you only search for the xPub and thats why there are two?

You will find 2 pubs in each range, regardless of how many times you divide or with what number you divide with, because yes, I am searching for xpoints only. But if you search for pub key, you will find at least one in every range.

Look at it like this, if you divide by 33, you will have 33 new pubkeys and 33 ranges. Each range will contain a pubkey; 33 = 33; 33/33=1

a.a

member

Activity: 126

Merit: 36

Quote from: WanderingPhilospher on September 29, 2021, 10:40:47 AM

Note: There will be at least 2 keys that will solve original pub key's private key, in every range.

Please elaborate.

After you did the division twice?

Or because you only search for the xPub and thats why there are two?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: _Counselor on September 29, 2021, 10:37:49 AM

Quote from: a.a on September 29, 2021, 10:24:57 AM

3 x 45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a = beginning of the range
then ffffffff divided by 33 + begin of the range marks the end of the range?

FFFFFFFF / 33 = 7C1F07D
(45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a + 7C1F07D) = end of range

and if you search all 33 ranges, one of it will contains the key which you got when divided target key by 33.

Counselor, our methods are close...same concept/principle.

Note: There will be at least 2 keys that will solve original pub key's private key, in every range.

_Counselor

member

Activity: 110

Merit: 61

Quote from: a.a on September 29, 2021, 10:24:57 AM

3 x 45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a = beginning of the range
then ffffffff divided by 33 + begin of the range marks the end of the range?

FFFFFFFF / 33 = 7C1F07D
(45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a + 7C1F07D) = end of range

and if you search all 33 ranges, one of it will contains the key which you got when divided target key by 33.

a.a

member

Activity: 126

Merit: 36

Soooo

3 x 45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a = beginning of the range
then ffffffff divided by 33 + begin of the range marks the end of the range?

_Counselor

member

Activity: 110

Merit: 61

Quote from: a.a on September 29, 2021, 09:30:38 AM

@Counselor
Well, you have to know the range, were you assume the privatekey. So how do you determine that range?

How do you know to search in D1745D1745D1745D1745D1745D1745D06A31FA8E3252B1A53FDAAA73xxxxxxxxxxxxxxxx?

If we use 33 as divisor, than to determine beginning of each range you have to multiply numbers (1 .. 33) to inverse(33, secp256k1.p)
therefore you will get 33 possible ranges beginnings:

Code:

1 6c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b265d174433
2 d9364d9364d9364d9364d9364d9364d9364d9364d9364d9364d9364cba2e8866
3 45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a
4 b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9a745d149d
5 1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1d1745ca1
6 8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e82e8ba0d4
7 f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0e8ba2e507
8 64d9364d9364d9364d9364d9364d9364d9364d9364d9364d9364d935e8ba2d0b
9 d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745c45d1713e
10 3e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83a2e8b942
11 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa9fffffd75
12 1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d15d174579
13 83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f7ba2e89ac
14 f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1e1745cddf
15 5d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745745d15e3
16 c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26bd1745a16
17 364d9364d9364d9364d9364d9364d9364d9364d9364d9364d9364d932e8ba21a
18 a2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8b98ba2e64d
19 f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0e8ba2e51
20 7c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f0745d17284
21 e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2da2e8b6b7
22 55555555555555555555555555555555555555555555555555555554fffffebb
23 c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07b5d1742ee
24 2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2ba2e8af2
25 9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c91745cf25
26 7c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f07c1f0745d1729
27 745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d16d1745b5c
28 e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83e0f83d2e8b9f8f
29 4d9364d9364d9364d9364d9364d9364d9364d9364d9364d9364d93648ba2e793
30 ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ae8ba2bc6
31 26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b26c9b245d173ca
32 9364d9364d9364d9364d9364d9364d9364d9364d9364d9364d9364d8a2e8b7fd
33 1

Size of the resulting ranges will be 33 times smaller than original, so you can calculate end of each range.
In our case WP searched this range:
3 45d1745d1745d1745d1745d1745d1745d1745d1745d1745d1745d1741745d06a

To be honest, I don't know how and what exactly WP calculates, but that is main idea of such key reduction.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote

I dont know how you determine the other range?!

Quote

So how do you determine that range?

brainless stated it in one of his posts, how to calculate the exact range of all pubkeys generated by a divisor. That was one main point of my tests, to see if this was true/what he said was true, instead of saying it's bs or creates larger range to search.

brainless words:

Quote

my answer were no random, and exact in all 256bit range, and what is exact location, i explain about how to calc exact range

Quote

Pollard Rho implementation

I have no such program. I either use kangaroo, bsgs, or xpoint only search

a.a

member

Activity: 126

Merit: 36

@ssxb
The problem is, that you say "Well I know a secret, but I wont tell you the whole secret. I just say, that when you know something everybody knows, you will understand it". And than ... nothing. Just write what your "secret" is or just let it be...

@WP
I apologize, I misread that you set the range to that small one, but you wrote clearly that you chose another range, where you clearly knew it was twice there. Still... I dont know how you determine the other range?!
Does your Pollard Rho implementation can process multiple targets at once?

@Counselor
Well, you have to know the range, were you assume the privatekey. So how do you determine that range?

How do you know to search in D1745D1745D1745D1745D1745D1745D06A31FA8E3252B1A53FDAAA73xxxxxxxxxxxxxxxx?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: ssxb on September 29, 2021, 09:21:00 AM

Quote from: WanderingPhilospher on September 29, 2021, 08:23:41 AM

Quote from: a.a on September 29, 2021, 08:18:12 AM

Would you please stop spamming ssxb?
Super annoying.

spamming? lol...if merely saying/doing what he has said/done to others is "spamming" then I guess the meat is in the can...so be fair and tell him not to "spam" others. My first reply to ssxb is labeled spamming lol...

you and a.a have no idea what you guys are doing , in fun i reveal some real engineering shit but no one picked the point , i guess enough is enough i will go other way ~ chill the soda out

says the person who was asking brainless for all insights just a short while ago. glad to know you have everything figured out. if you can't follow/understand the point of my tests, then you ssxb, have no idea what you are doing. enjoy your soda...WP

ssxb

jr. member

Activity: 81

Merit: 2

Quote from: WanderingPhilospher on September 29, 2021, 08:23:41 AM

Quote from: a.a on September 29, 2021, 08:18:12 AM

Would you please stop spamming ssxb?
Super annoying.

spamming? lol...if merely saying/doing what he has said/done to others is "spamming" then I guess the meat is in the can...so be fair and tell him not to "spam" others. My first reply to ssxb is labeled spamming lol...

you and a.a have no idea what you guys are doing , in fun i reveal some real engineering shit but no one picked the point , i guess enough is enough i will go other way ~ chill the soda out

_Counselor

member

Activity: 110

Merit: 61

Quote from: a.a on September 29, 2021, 09:10:41 AM

You set the range 1:ffffffff and you get a private key D1745D1745D1745D1745D1745D1745D06A31FA8E3252B1A53FDAAA7335FF288C

D1745D1745D1745D1745D1745D1745D06A31FA8E3252B1A53FDAAA7335FF288C is bigger than ffffffff.

Atleast in my math world Wink

what does the size of the key have to do with it, if to find it you need to search a range 33 times less than the original, for example

from D1745D1745D1745D1745D1745D1745D06A31FA8E3252B1A53FDAAA7300000000 to D1745D1745D1745D1745D1745D1745D06A31FA8E3252B1A53FDAAA75FFFFFFF

Topic: Pollard's kangaroo ECDLP solver - page 29. (Read 59436 times)