This message was too old and has been purged

[jaesyn]

I think you got it.  That is my understanding also.

Assuming for now 2⁴⁰ known keypairs all we need is an estimate for the average comparison time given that some of them will be a short quick comparison as you suggested and others will be very long, having to do full comparisons.

Then we can easily calculate how long, on average, to crack a key pair.

Is the assumption here is that you can find 2⁴⁰ keypairs all with the same lower 32-bits to use in a rainbow table? I think that task alone is equivalent to O(N).

[Supercomputing]

@Ritual

Evil-Knievel is attempting to implement a variation of Pollard's kangaroo algorithm. The best known implementation that I know of can be accessed from the link below:
http://eprint.iacr.org/2010/617.pdf


We need to use what is known as "distinguished points" to implement a parallel version of the algorithm, please see the above link. Evil-Knievel is focused on small intervals, which is what the above algorithm does.The only limitation with this approach is that you need to know beforehand, the search interval that contains the solution. I am afraid setting random traps (rendezvous points) is not going to work for a 256-bit prime field.

If the goal is to recover an ECDSA key as used in Bitcoin, then the best approach will be to study the Hidden Number Problem. I have successfully used it in a lab environment to recover some keys that would otherwise be almost impossible to recover through pure brute force methods. I will explain more on this subject later.
http://www.iacr.org/archive/crypto2009/56770333/56770333.pdf

[kjj]

This is a scam.  This has been known to be a scam since post #125, nearly a week ago now.  Why are you still talking about it?

There is no statistical project.  There are no rendezvous points.  There is no algorithm.  He isn't washing Pollard's jockstrap, much less trying to implement any actual math.  His script generates keys from a tiny, tiny keyspace, and then his "cracker" searches that same tiny keyspace.

Also, Ritual is almost certainly the same person as Evil-Knievel.  Re-read the whole thread and watch out for posts from both accounts that appear to be in the other character's voice.

Here's what's going on.  Evil-Knievel has pre-computed a couple points on the secp256k1 curve.  Specifically points where the exponent is of the form 2**N. (see 1,2)  He then wrote a program, the "cracker", that can search the area around those points.  If a Bitcoin key-pair lies close to one of those points, his program will find it.

This isn't dangerous.  It's improbable (~impossible) that any uniformly random Bitcoin key-pairs are weak to his pre-computed points.  The secp256k1 keyspace is, for all practical purposes, infinitely large.  It doesn't matter if Evil-Knievel had a gabillion-gajillion pre-computed points and all the computing power in the universe.  His approach still wouldn't crack a normal Bitcoin key-pair.

To me, having just read Evil-Knievel's thread, it sounds like he's insinuating that there is danger here.  He's insinuating that a uniformly random Bitcoin key-pair has a reasonable chance of being tractably close to one of his pre-computed points.  There is no reasonable chance of this, and his claims are ridiculous.  The thread should be closed as a scam, because he's asking for money on misleading premises.

If he has nothing to hide, why was his HTML generator obfuscated?  I'll help and de-obfuscate the generator for everyone.  Here's the algorithm:

Code:

Pick a random N, [128, 255].
Pick a random M, [1, 20000000].
Spit out 2**N - M as a private key.

See the problem?  He just needs to take a generated public key, add G to it ~20,000,000 until it matches one of the 128 pre-computed keys (which are of the form 2**N), and BAM the private key is "cracked".  This doesn't make Bitcoin weak.  It never will.  It's a rainbow table attack.  But mankind will never have enough computational and storage power to make rainbow tables work against secp256k1.

As for the bitprobing.com "project".  That's a load of bollocks.  If you don't believe what the experts have to say about ECDSA, that's fine.  But go learn group theory and number theory first, before asking the public to help run unsubstantiated "experiments."


I know these forums are intentionally soft-modded, and appreciate that to an extent.  But it's times like these I wish the forums were more aggressively moderated so that Evil-Knievel could just be banned for misleading and scamming people.


(1)  Actually, he fscked this up.  He interpretes the decimal result of 2**N as hexadecimal.
(2)  2**128 is 340282366920938463463374607431768211456.  Interpret that as a hexadecimal private key and you get a public key of 04864f29af3191e135f5c78499271961f2313110fb2a296bf072733475529da1fb4d5cef64d1212 a946775bfb2db5319fb618089ae8806d618f44d68d3bdb18650.  The least significant 32-bits of the X coordinate is 0x529da1fb.  That matches one of the constant in his script.  I assume the rest match similarly.

[itod]

This is a scam.  This has been known to be a scam since post #125, nearly a week ago now.  Why are you still talking about it?

Thanks for the info. We already know what his script is doing, and still discussing it because:

Option I: We are all the same person as Ritual & Evil-Knievel, or we are different persons but we are in this scam together;
Option II: We are sado-masochists who love to waist everyone's time and money;
Option III: There's something very interesting in Evil-Knievel ideas, and we would like to talk a bit about it.

Pick your choice.

[Supercomputing]

Also add that gmaxwell is willing to lose 50 BTCs because of this thread - it got my attention. Though very unlikely, but still possible that he may lose 50 BTCs.

[Ritual]

Also, Ritual is almost certainly the same person as Evil-Knievel.  Re-read the whole thread and watch out for posts from both accounts that appear to be in the other character's voice.

This is the second time some cretin has suggested this. Why not read my post history? And read EKs as well. Totally different boards, topics, interests. As I've stated before, I'm from Ireland. I'm not sure where EK is from, but it sure isn't here. Also, if you read the thread, you'll see that I have not always agreed with EK in it. And lastly, why in the world of sport would I ask for an explanation about this if I was him? If this is a scam, it's not in his interests to have any explanations which might show that?

So in short, kjj, if you don't like the thread, or if your tin-foil hat has slipped off, or nobody has come down to your basement with hot pockets for too long or whatever, then piss off.

Clear?

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

@kjj: There's always that one person ready to stir things up  In this thread, it's you!
Also, my project is no "scam" - the weak key generator (which was advertised as such) is a proof of concept to actually see that the program is able to crack private keys. People wan't to try, experiment, see results - that's why thy need keys that will show the "proof-of-concept" pretty quickly. But why am I telling you anyway, you seem to have no idea about anything that I was writing in this post.

I personally think YOU are the scam here

You are the scam, you are using FUD to push your product which doesn't clearly state what it is actually doing.

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

Noooo, now we must interrupt our scientific talk to argue with the trouble makers.

@gweedo: The program does exactly what it described here! If you still disagree then you certainly have not understood anything.
I would suggest going to university and attending some math classes.

I have a math degree and I understand your math. It is preying on FUD.

[Evil-Knievel]

This message was too old and has been purged

[Mitchell]

My housekeeper (and I think the trash collector too) have a math degree as well. Doesn't mean they understand anything though  .
Okay serously guys, how can I make this topic moderated to keep out those stress-makers?

You can't. You will have to lock this one, create a new topic and enable "Self-moderated" under "Additional Options...".

[gweedo]

My housekeeper (and I think the trash collector too) have a math degree as well. Doesn't mean they understand anything though  .

LMAO you have a house keeper, your mom doesn't count as a house keeper js. I have a math degree from an Ivy league school and I have been working on cryptographics for over 10yrs. I understand the bitcoin protocol and the code. Your code wasn't hard to follow and figure out. But you are using FUD to create a panic that you have found a flaw, and that is untrue. The flaw you found was with random generators not addresses.

[gweedo]

My housekeeper (and I think the trash collector too) have a math degree as well. Doesn't mean they understand anything though  .
Okay serously guys, how can I make this topic moderated to keep out those stress-makers?

You can't. You will have to lock this one, create a new topic and enable "Self-moderated" under "Additional Options...".

Don't tell him how to do it. If he is insulting the intelligence of other people let him use his mind and figure it out.

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

If he is insulting the intelligence of other people

.... which I do because you are insulting me as a scammer.

But you are a scammer...

To defraud; swindle.

You are defrauding people by saying that their is a flaw in bitcoin address which is untrue, so you are a scammer.

[Evil-Knievel]

This message was too old and has been purged

[gweedo]

You are defrauding people by saying that their is a flaw in bitcoin address which is untrue, so you are a scammer.

Please quote the posting where I said that. I think you are doing FUD here.
I recall that I wrote that certain addresses are a lot easier to crack if others.

Clearly I am making the FUD and plus you edited the OP heavy.

Price:
I am asking you 2 BTC for the whole package. It has taken me lots of time to research everything and implement it cleanly. And who knows, this tool is giving you good chances to get one of these lost 10 MILLION US$ accounts 

[Sukrim]

Nothing wrong there, though the chances are about as good as with vanitygen (maybe a bit faster, if you directly attack the key and don't have to compare addresses) so far.

[prezbo]

Nothing wrong there, though the chances are about as good as with vanitygen (maybe a bit faster, if you directly attack the key and don't have to compare addresses) so far.

It is significantly faster, because the algorithm needs O(sqrt(n)) (expected) operations where vanitygen needs O(n), however with the space size we're talking here sqrt makes practically no difference.
Basically the efficiency of this algorithm is on par with other general-dlp-solving algorithms, of which none practically works on this kind of space.