Topic: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] - page 10. (Read 3490 times)

So I came up with an existing one BSGS algorithm? 

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

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?

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.

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 ?

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

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


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

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? 

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

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

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

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

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

This is well know since the beginning of elliptic curve usage in crypto.
But we count the number of group operation really performed (not the size of the range divided by time).

For instance in my BTCollider which use the DP method (also in O(sqrt(n))), I get 27.9 Mips (GeForce GTX 1050 Ti) for 80bit collision search. That means that I really compute 27.9M group operation and hash per second. It solves 80bit collision in 14h30 (in average). Note that in that case, it have to compute an EC mult for each group operation.

https://github.com/JeanLucPons/BTCCollider

About speed, read above. Yes, an algorithm is used that minimizes the use of resources. But this does not mean that they do not need to be taken into calculation of speed. The total number of keys that are processed will not decrease. It’s just that they are processed by comparison, not by adding a point.

I did not write that CPU can do 2.2 P operations of addiding points/s i say 2.2Ph/s mean 2.2Pkeys/s. This mean that CPU can brutforce range of 2.2*10^15 points in 1/s
if range is 1000 points and you check this range in 1seconds than you can say that speed is 1000points/s no matter how you do that whith comparsation or addiding or in other way!

So you have use this algorithm which is in O(sqrt(n)) for both memory and time where n is the size of the range.
Starting with an offset does not prevent to use this algorithm.
That means that the key rate (or group operation) you announced is wrong.
Do not waste time in solving the above problem, solving it will just prove that you have correctly implemented this known algorithm.

As i understand all of this public keys is in range of private keys:
from
 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
to
0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff

ok i will try to do this.

Yesterday, I read in detail about the giant baby steps algorithm.
I had heard about him before, but did not delve into the gist of it.
This algorithm is very similar to the one I use.
I just thought that I was the first one to think of this, but it turns out that something similar was invented before))
You can delete the topic if you want. All the same, I will not publish the source code.

10¹⁵ checks/s for 1 day is 8.64x10¹⁹ (4AF0A763BB1C00000₁₆) checks. If you can actually do that, you should  be able to check all private keys between

0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000

and

0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff

in less than 6 hours.

But, I'll give you a whole day to find the private keys for these 16 public keys. The private keys are randomly distributed in the above range. If you can do that, I'll be impressed. I don't think that you can find 4.

Perhaps, but quite a few times people have shown up with "cracking" tools that turned out to be a scam. It's a pretty standard MO. In particular several of the more recent ones have setup making these seemingly pointless "advertising posts" then nailing people who PM them, e.g. by sending them the software privately where other people can't call it out for being malware.  I guess they feel better about robbing people because they imagine they're robbing other thieves.