This message was too old and has been purged

EK: That's OK I think by now most of us have realised that you're a mathematician rather than a teacher

No offense, but you're operating at a level higher than alot of us on this thread. We need a baby-level explanation, particularly if you're asking 2 BTC for this!

Having said that, you seem to be intelligent, organised and energetic about it, which gives me faith.

Please don't take this as a criticism of any kind - I kinda consider you my last hope for the missus' wallet!

Rit.

What are the valid characters for a wallet password? Are specials allowed like "&%$!"?
I used to use alt-codes a lot to be a smarta**, like alt-255 which looks like a space, but isn't.
EDIT: found the list: (no zero, lowercase L, uppercase "oh", uppercase I)
“123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

EK, great explanation. I'm not clear on G though. Is it a fixed value?

Yes G is a constant in the specification Bitcoins uses.  From the specification:

So you are clever in your point selection in order to make your comparison a bit faster.  

The smaller you make the common bits the more collisions you will get that require a time consuming full comparison, the larger you make your common bits the more costly your initial comparison.  Somewhere between 2²⁵⁶ and 2⁸ bits lies an optimal number of bits given how much you want to spend on your FPGA or ASIC hardware.

I already granted you the comparison can be done is a clever way to speed it up a bit.

This still boils down to a brute force attack.  A clever brute force attack but a brute force attack never the less.

All you need are these two numbers:

The number of known points (2⁴⁰ in the example so far)

The amount of time needed (on average, given a clever implementation) to compare the result of the N = P + G calculation to all the known points.

I think we can bascially neglect the time it takes to calculate N = P + G but that does take some time to do.

Given these two numbers we can calculate the time needed to crack any key.  The notion of "weak keys" is silly and is just introducing "luck" into the equation for no reason.

Excuse if this is silly question because my understanding of this is very limited - but 2⁴⁰ is not a very big number, it's around 1 Terra. Since, to my understanding, Y coordinate is not very important because it is binary determined by the X coord and the sign +1/-1, there's only 32 bytes * 1 Terra = 32TB of data to check, which is well within range of todays disk arrays. This shouldn't be hard to check against, should it?

So, is this the correct explanation of the attack method:
- You need 2⁴⁰ X coordinates which have the 32 least significant bits matched to the X coord of the attacked public key, and all 2⁴⁰ with known private keys. That's what we've been doing in the other thread, collected 8 million of them in a few days
- You go through the sequence n*G, (n+1)*G, (n+2)*G ... (n+k)*G and check only those 32 bits for a match
- If you find a match, you check the X coord against the 32TB of data with known private keys
- If you find a match there you calculate found secret - k to get unknown private key
- If not you add 1 to k and repeat the process

Is this the correct attack vector? It looks too simple to me, I've must have misunderstood something.

Storage needed for the public keys:

257 bits, 256 for the X coordinate + one bit for the sign of the Y coordinate BUT the bottom 32 bits are the same for all keys so we really just need a total of 257 - 32 = 225 bits each

Storage needed for the private keys:  256 bits each

So realistically we still need 64 bytes to store each known key pair

2⁴⁰ * 64 bytes is exactly 64 binary terabytes of data that needs to be stored - no big deal by today's standards.

But, have you ever tried to read 64 Tibytes of information from a disk drive?  Be sure to use SSDs for this as HDDs will be too slow for the full comparison operation

I was only giving total storage requirements.

Yes, you put the public keys in about 32 Tb of SSD and the private keys on 32 Tb of HDD.  32 Tb of HDD is not that much in the grand scheme of cracking ECC so forget the tape.