brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning]

[Etar]

0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED8 87AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
1 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
in  6285s

04A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD3E48440249D6B C78BC928AA52B1921E9690EBA823CBC7F3AF54B3707E6A73F34
2 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eb5abc43bebad3207
in  5720s

0404A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3BD05357CAF834 0CB041B1D46C5BB6B88CD9859A083B0804EF63D498B29D31DD1
3 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e5698aaab6cac52b3
in  2923s

040B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D1D18283AF4955 6CF33E1EA71A16B2D0E31EE7179D88BE7F6AA0A7C5498E5D97F
4 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e59c839258c2ad7a0
in  2884s

04837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493E46726DE04352 832790FD1C99D9DDC2EE8A96E50CAD4DCC3AF1BFB82D51F2494
5 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e765fb411e63b92b9
in  3820s

040ECDB6359D41D2FD37628C718DDA9BE30E65801A88A00C3C5BDF36E7EE6ADBBAD71A2A535FCB5 4D56913E7F37D8103BA33ED6441D019D0922AC363FCC792C29A
6 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e7d0e6081c7e0e865
in  3851s

0422DD52FCFA3A4384F0AFF199D019E481D335923D8C00BADAD42FFFC80AF8FCF038F139D652842 243FC841E7C5B3E477D901F88C5AB0B88EE13D80080E413F2ED
7 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ec737344ca673ce28
in  6434s

04DB4F1B249406B8BD662F78CBA46F5E90E20FE27FC69D0FBAA2F06E6E50E536695DF83B68FD0F3 96BB9BFCF6D4FE312F32A43CF3FA1FE0F81DF70C877593B64E0
8 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e38160da9ebeaecd7
in  1777s

043BD0330D7381917F8860F1949ACBCCFDC7863422EEE2B6DB7EDD551850196687528B6D2BC0AA7 A5855D168B26C6BAF9DDCD04B585D42C7B9913F60421716D37A
9 key 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e79d808cab1decf8d
in 3884s

[bigvito19]

Where is the program or is this person trying to sell it as usual?

[Etar]

Where is the program or is this person trying to sell it as usual?

Nobody sells anything here.
Here is a discussion about how speed is measured.

[NotATether]

All the same, I will not publish the source code.

Will you at least tell us why you don't want to publish the source code?

[MrFreeDragon]

Etar, I write it one more time: you just OVERestimate your actual power.

You use "square root method", but count the whole range. It is not correct.
Your example with 5 rooms x 200 people each and only one David among them: if you ask the whole room you perform ONLY one operation, but not 200 operations. Yes, it is better not to ask every person in every room, but ask once per room. This is efficient way. But it does not mean that you actually ask everybody. This will be overestimation.

Most famous Square root methods:
- Baby-step Gian-step
- Pollard's Rho algorithm
- Pollard's kangaroo algorithm

Have a look this link as well: https://www.embeddedrelated.com/showarticle/1093.php

[Etar]

Etar, I write it one more time: you just OVERestimate your actual power.

You use "square root method", but count the whole range. It is not correct.
Your example with 5 rooms x 200 people each and only one David among them: if you ask the whole room you perform ONLY one operation, but not 200 operations. Yes, it is better not to ask every person in every room, but ask once per room. This is efficient way. But it does not mean that you actually ask everybody. This will be overestimation.

Most famous Square root methods:
- Baby-step Gian-step
- Pollard's Rho algorithm
- Pollard's kangaroo algorithm

Have a look this link as well: https://www.embeddedrelated.com/showarticle/1093.php

You guys are so smart here, I even feel awkward.
Then answer me 3 simple questions:
#1 Question .
Let's imagine and take for the fact that I have a RAM for storing 2 ^ 255 public keys
And I make a table of baby steps by this size.
Those  it’s enough for me to take 2 Giant steps to break the entire range 2 ^ 256 in 1second.
What speed will I have in that case? If you answer 2hashes/s. I will call the orderlies and  will laugh for a long time. 

#2 Question .
For example, I have a very small table of baby's steps. Let it be 10 values. And I take 100 giant steps per second. What speed will be in this case?

#3 Question .
There are 2 factories that produce cars. The first factory does everything .. from wheels to the trunk and engine. And the second one does only large-assembly cars. The first plant will produce 100 cars per month. The second is also 100 cars.
Those due to the fact that the second factory does not make a car from atoms, but of large parts, we can’t say that it makes 100 cars a month? 

[odolvlobo]

Congratulations on finding those private keys. They are correct. I  am impressed. However, ...

You guys are so smart here, I even feel awkward.
Then answer me 3 simple questions:
#1 Question .
Let's imagine and take for the fact that I have a RAM for storing 2 ^ 255 public keys
And I make a table of baby steps by this size.
Those  it’s enough for me to take 2 Giant steps to break the entire range 2 ^ 256 in 1second.
What speed will I have in that case? If you answer 2hashes/s. I will call the orderlies and  will laugh for a long time.  

#2 Question .
For example, I have a very small table of baby's steps. Let it be 10 values. And I take 100 giant steps per second. What speed will be in this case?

#3 Question .
There are 2 factories that produce cars. The first factory does everything .. from wheels to the trunk and engine. And the second one does only large-assembly cars. The first plant will produce 100 cars per month. The second is also 100 cars.
Those due to the fact that the second factory does not make a car from atoms, but of large parts, we can’t say that it makes 100 cars a month?  

You are not doing  2.2 PH/s. You aren't even doing hashes.

The problem here is with your terminology:

• You aren't hashing, so you are using the wrong unit.
• You aren't being clear on what you are measuring.

#1 The "speed" 1 one key per second.
#2 The "speed" is 100 steps per second.
#3 Yes

[Jean_Luc]

@etar
The BSGS algotrithm has a complexity in time and in memory.
You can have time in O(sqrt(n)) and memory in O(sqrt(n)). n is the search space size.
But you can also have time in O(1) and memory in O(n)
If you have n memory available and memory already filled, it makes no sense to give a key rate.

[Etar]

Congratulations on finding those private keys. They are correct. I  am impressed. However, ...

Totaly i found 8 keys in a day and have few hours to the end of day. 9 keys in a day.
And i spent about 30-40 minutes on each new public key to prepare the data
But probably I will find 1 more key maximum.
I have question about the formula O (sqrt (n)), it means that the time spent is equal to (sqrt (n)) for the range from 1 to n
so if for example n=64 than to break this range i need time sqrt (n) = 8s ?

[Jean_Luc]

O(sqrt(n)) in time means that you need to perform sqrt(n) group operations (addition here) in the worst case.

If you have n=2^64 (like the above problem), you need to perform sqrt(n) = 2^32 EC additions but to achieve this you also need to store in memory 2^32 "baby steps" and perform 2^32 additions to fill the memory. In total, 2*sqrt(n) group operation (worst case). If you have less memory, of course, you will have to perform more operations, O(sqrt(n)) is the best time/memory tradeoff for this method.

I don't know your code but to solve the 16 keys given by odolvlobo, yon can fill only once the memory and then process the 16 keys.

[Etar]

Let's decide what kind of algorithm I came up with, and which of the known ones it looks like.

Step by step how I do bruteforce:

For example, we need to find the private key from known the public key: 0x68d552d7a9d3fcd453fa080f7e9f3ff5536a287b058c9fe72ebbf3dbc1ec4caab7d1c060acd4a 0b57b6edd70d283fbba557c62e87b31eaff6f615732fe4f675d

We need to make hashtable, for example, we will have a table of 10 values of X-coordinates
First we need make variable ADDPUBG that equil table size but represent this value like point on curve.
ADDPUBG  = tablesize = 10 = 0xa0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7893aba425419b c27a3b6c7e693a24c696f794c2ed877a1593cbee53b037368d7

After that we can fill hashtable:
Add Gpoint to  public key 0x68d552d7a9d3fcd453fa080f7e9f3ff5536a287b058c9fe72ebbf3dbc1ec4caab7d1c060acd4a 0b57b6edd70d283fbba557c62e87b31eaff6f615732fe4f675d
and we get new point 0xcb1e2f09dbff52b977bcf9b5820823dfc89f1621efb1e0f009246542edb2459479eea84c69408 3e4cd06d7c13ca35ca2494d374871f6bd31327c1651d941efe4
Cut only X-coordinat 0xcb1e2f09dbff52b977bcf9b5820823dfc89f1621efb1e0f009246542edb24594 and set to the table
Then Add 2G to 0x68d552d7a9d3fcd453fa080f7e9f3ff5536a287b058c9fe72ebbf3dbc1ec4caab7d1c060acd4a 0b57b6edd70d283fbba557c62e87b31eaff6f615732fe4f675d
Cut only X-coordinat  and set to the table until it is full.

After that we sort hashtable to use binarysearch in the shortest time!

With the table finished now we take the starting private key with which we start brute force. let it be 0x01
Now we need to get the public key from the start key. It is 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Now in the cycle we checks our x-coordinat of start public key with the keys in the table using binary search.
if we not found key we can add to start public key table size ADDPUBG  (ofcourse via addplt method)
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
+
0xa0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7893aba425419b c27a3b6c7e693a24c696f794c2ed877a1593cbee53b037368d7
=
0x774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cbd984a032eb6b5 e190243dd56d7b7b365372db1e2dff9d6a8301d74c9c953c61b

And so on, until the starting public key becomes equal to one of the hash tables.

I don’t know what famous algorithm suits mine. Because I use a sorted table.
Can you tell me?

[Jean_Luc]

Read this, page 7:
https://www.math.u-bordeaux.fr/~aenge/ecc2015/documents/galbraith.pdf

[Etar]

Read this, page 7:
https://www.math.u-bordeaux.fr/~aenge/ecc2015/documents/galbraith.pdf

So I came up with an existing one BSGS algorithm? 

[Jean_Luc]

Yes

[Etar]

@odolvlobo i have a question.
You gave me public keys whose private keys are in the range 8000000000000000:ffffffffffffffff
So those you previously brute force this range.
if you have all keys in this range why you do not take transaction #63 from bitcoin pazle?

[Fortuna33]

@Etar , anyway good work!
Could you send pm to me?

[MrFreeDragon]

Dear moderators, how do you think, could you remove malware warning from this post?
Question by question, actually we understood that the TC just created "the wheel" but did not know that this wheel was already known to the community.

Instead of walking by foot Etar used the wheel and could go faster and longer, so declared this high speed. However received the negative feedback for this: gmaxwell Reference - Physically impossible claims about key cracking performance, probably trying to trick people into running malware.

It is grandiosely if Etar came to this method (already known) by himself. Just wow!

[Jean_Luc]

That isn't impressive at all and wouldn't prove your claim.  Because you fix a range, you could simply have a table of 2^31 entries (1G, 2G, 3G) based on X-only, you step by twice the size of your table, checking only the X to get a positive and negative offset, and find the match in one hour at a terribly slow rate of 1.2 million keys a second.

gmaxwell posted this method in the beginning of this topic, (an optimized version using negation), without a starting offset in that case but easy to add one.
It took 3 pages to etar to understand. BSGS is quite a very simple and intuitive algorithm and there are plenty of possible optimizations to speed it up.
gmaxwell is right, according to the "attracting" title of this topic and to the refusal of Etar to post his code, to add this warning.

[MrFreeDragon]

That isn't impressive at all and wouldn't prove your claim.  Because you fix a range, you could simply have a table of 2^31 entries (1G, 2G, 3G) based on X-only, you step by twice the size of your table, checking only the X to get a positive and negative offset, and find the match in one hour at a terribly slow rate of 1.2 million keys a second.

gmaxwell posted this method in the beginning oh this topics, (an optimized version using negation), without a starting offset in that case but easy to add one.
It took 3 pages to etar to understand. BSGS is quite a very simple and intuitive algorithm and there are plenty of possible optimizations to speed up it.
gmaxwell is right, according to the "attracting" title of this post and to the refus of Etar to post his code, to add this warning.

Ok, noted. Agree.

[Etar]

Yes

No. This is not  BSGS algorithm.
because:
 - baby-step giant-step is a "meet in the middle" algorithm!
 - BSGS  algoritm has a limit on N due to memory lack!
So BSGS can`t be launched with n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
My algorithm can be run with any amount of memory, the amount of memory will only affect the size of the subgroup.
Compare https://bitcointalk.org/index.php?topic=5238719.msg54191839#msg54191839
BSGS  algorithm subtracts mP from Q unlike mine which adds mG to start point.
->>>
I create a table of public keys that are in front of a known public key.
And after that I am incrementing by the size of the tables to the starting public key.
Those the algorithm rather catches up than meets in the middle.
So we can say that there is something from the BSGS algorithm, but this is not it. (I think).