bdb
Newbie
Offline
Activity: 2
Merit: 0
|
|
January 04, 2016, 09:49:33 PM |
|
long time lurker; not much of a poster... With simple C code, on a single thread, my cpu gets ~20K keys/second. roughly broken down as: EC_POINT_add: 19808 ticks EC_POINT_point2oct: 120116 ticks sha256: 27840 ticks ripemd160: 3152 ticks Scanned 763188 keys in 40 seconds, 19079 keys/second i.e. as noted in this thread, the EC point conversion takes most of the time. This can be further optimised in several ways - ignore the Y component or as noted in the VanityGen code; batch up a set of results and use EC_POINTs_make_affine to simplify this operation. I then patched the VanityGen code to solve the same problem. This is only a very small mod. - set the initial private key = 1, rather than random - change the pattern matching [you could probably even use the existing one; but there is no need to convert to b58] BitcoinPuzzle roughly broken down as: EC_POINT_add: 5300 ticks EC_POINTs_make_affine 1193800 ticks [called once per 256 keys] i.e. 4663 ticks per key EC_POINT_point2oct: 2760 ticks sha256: 1216 ticks ripemd160: 1484 ticks [186.63 Kkey/s] VanityGen [167 Kkey/s] The saving on the EC point conversion can be seen, as can the better quality hash code used by OpenSSL compared to the code I was using. If I run this on all cores; I get ~1.4M keys/second. I've not tried the GPU version; but would expect comparable results to VanityGen generation. The VanityGen thread suggests that a reasonable GPU can do ~30Mkeys/second. Now, consider that the average time to find a key is half the search space. So, for a 40 bit key, the average search = 1/4 * 2^40 = 2.74877906944 x10^11 i.e. bits search_len rate time 25 8388608 1.4M 6 secs 40 274877906944 1.4M 196341 secs = 3.15 days 40 274877906944 30M 9163 secs = 2.5 hours 50 281474976710656 30M 9382500 secs = 109 days 51 562949953421312 30M 18765000 secs = 217 days
... I'm not going to be running for 200 days for $20 Burt, after generating the public key, it requires converting from elliptic curve coordinates to bytes. The operation is 'simply' X' = X/Z^2 - but that means a divide in the finite field. I *think* that make_affine step forces Z to be a constant for all the block that are affined, so this division only has to be done once per block. EC_POINT_point2oct actually calculates both X'= X/Z^2 and Y'=Y/Z^3; but as we are using a compressed key, we don't need the Y' term. I've not checked to see if this code gets optimised away properly; if not, it might save 10%.
|
|
|
|
|
|
|
|
|
The forum strives to allow free discussion of any ideas. All policies are built around this principle. This doesn't mean you can post garbage, though: posts should actually contain ideas, and these ideas should be argued reasonably.
|
|
|
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
|
|
|
|
werty98
Newbie
Offline
Activity: 8
Merit: 0
|
|
January 05, 2016, 06:47:23 AM |
|
long time lurker; not much of a poster...
Nice work! Unlike mining, this challenge won't get harder. If 1 BTC = 1,000,000 USD, which address will be cracked up to?
|
|
|
|
NorrisK
Legendary
Offline
Activity: 1946
Merit: 1007
|
|
January 05, 2016, 07:03:53 AM |
|
long time lurker; not much of a poster...
Nice work! Unlike mining, this challenge won't get harder. If 1 BTC = 1,000,000 USD, which address will be cracked up to? Without a clear pattern it will be quite hard to get far. It is basically like generating addresses with a certain entropy to them. I doubt we will get much further than the 50 range without additional info or significant calculating power.
|
|
|
|
Bulista (OP)
Member
Offline
Activity: 169
Merit: 23
|
|
January 05, 2016, 09:35:04 AM |
|
Would be great if someone could find out who did this transaction. We know that the funds came from this address: https://blockchain.info/address/173ujrhEVGqaZvPHXLqwXiSmPVMo225cqTIt's quite a big player, with transactions every day. Is this an exchange? Like someone was saying here before, the guy that holds those 256 addresses has now some power over us, if suddenly we see that the addresses from 50 to 256 are spent, we will all feel a bit scared, no? We wouldn't know if they were actually cracked (and this would raise some questions) or if it was an intentional transaction from the holder...
|
|
|
|
NorrisK
Legendary
Offline
Activity: 1946
Merit: 1007
|
|
January 05, 2016, 09:54:28 AM |
|
Would be great if someone could find out who did this transaction. We know that the funds came from this address: https://blockchain.info/address/173ujrhEVGqaZvPHXLqwXiSmPVMo225cqTIt's quite a big player, with transactions every day. Is this an exchange? Like someone was saying here before, the guy that holds those 256 addresses has now some power over us, if suddenly we see that the addresses from 50 to 256 are spent, we will all feel a bit scared, no? We wouldn't know if they were actually cracked (and this would raise some questions) or if it was an intentional transaction from the holder... Why would he spend them? If it was not his intention to male a puzzle like this, he would've moved them after the first coins were moved. Maybe you can try sending a message to that address, maybe well get a hint or something in return.
|
|
|
|
werty98
Newbie
Offline
Activity: 8
Merit: 0
|
|
January 05, 2016, 01:47:00 PM |
|
The first 20 addresses were spent in the same block with the puzzle transaction, surely by the author. Would the author be a miner? This also raises the question whether someone else rather than the author did cash out
|
|
|
|
|
BurtW
Legendary
Offline
Activity: 2646
Merit: 1131
All paid signature campaigns should be banned.
|
|
January 05, 2016, 02:10:53 PM |
|
amaclin,
Do you happen to know anything about the author of the trasaction?
Just curios.
|
Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
|
|
|
amaclin
Legendary
Offline
Activity: 1260
Merit: 1019
|
|
January 05, 2016, 03:19:50 PM |
|
Do you happen to know anything about the author of the trasaction? nothing.
|
|
|
|
Bulista (OP)
Member
Offline
Activity: 169
Merit: 23
|
|
January 06, 2016, 01:44:34 AM Last edit: January 06, 2016, 02:02:42 AM by Bulista |
|
I got an information from someone pointing out some interesting facts. Maybe there is a solution for a formula after all. If you look at the sequence: 13 7 821 49 76 224 467 etc. The values 1 and 8, suggest that the formula can be something like this: 2^n * x, where x is = 1 OR 2^n + x, where x is = 0 Position 0 has the value 1, which is 2^0*1 OR 2^0+0 Position 3 has the value 8, which is 2^3*1 OR 2^3+0 It means that the calculation of x for the positions 0 and 3 result in 0 or 1. Finding the formula for this "x" can be the holy grail of this puzzle. The source also pointed out this example: If you calculate the Prime Factor of 21 (Position 4), the result is 3 and 7. (these numbers are in the position 1 and 2). You can check the prime factor here: http://www.calculatorsoup.com/calculators/math/prime-factors.php
|
|
|
|
DannyHamilton
Legendary
Offline
Activity: 3388
Merit: 4616
|
|
January 06, 2016, 02:32:53 AM |
|
The values 1 and 8, suggest that the formula can be something like this:
2^n * x, where x is = 1 OR 2^n + x, where x is = 0
Value 1 is in the position 0, value 8 is in the position 3.
Position 0 has the value 1, which is 2^0*1 OR 2^0+0 Position 3 has the value 8, which is 2^3*1 OR 2^3+0
It means that the calculation of x for the positions 0 and 3 result in 0 or 1.
Lets see if that's right... Position 1 has the value of 3, which is 2 1*1 = 2 OR 2 1+0 = 2Hmm. That didn't work. Position 2 has the value of 7, which is 2 2*1 = 4 OR 2 2+0 = 4Hmm. That didn't work either. Position 4 has the value of 21, which is 2 4*1 = 16 OR 2 4+0 = 16Hmm. Still no good. Position 5 has the value of 49, which is 2 5*1 = 32 OR 2 5+0 = 32This isn't looking like it's going to work. Lets think about this logically. If (as many of us have presumed) the first key (position 0) is completely random in the range between 2 0 and 2 1-1 then all the possible values are 1 and, well, um, I guess that's it. Can't be anything else. If the third key is then completely random in the range between 2 3 and 2 4-1, then there are 4 possibilities 5, 6, 7, and 8. So there's a 25% chance of it being 8. If you just pick any 2 of the lower positions the possible values are so limited that it's pretty easy to imagine that you see patterns in the numbers. The problem is none of the patterns people seem think they see work out as soon as you add another position or two. If you're having to come up with a brand new "formula" to fit the data every time you add a position, then its important to consider the possibility that you are looking at random data and simply calculating a convoluted and useless formula that fits your current limited set and none of the rest of the set. The source also pointed out this example:
If you calculate the Prime Factor of 21 (Position 4), the result is 3 and 7. (these numbers are in the position 1 and 2).
Prime factors of 76 are 2 and 19 (which don't occur in any positions). Prime factors of 224 are 2 and 7. Now 7 was already used as a factor for 21, and 2 is a factor of 76 and doesn't occur in the list of positions. Prime factors of 467 are 467 and that's it. (467 is prime). If you like I can give you a formula that will work "perfectly" for 39 and 40 (mostly because 2 points define a line and it's pretty easy to create an equation for a line). It won't work for pretty much any others, but then all we have to do is figure out how to "tweak" the formula, right? If you like, I can give you a formula that will work "perfectly" for 38, 39, and 40 (mostly because 3 points define a parabola, and it's pretty easy to create an equation for a parabola). It won't work for pretty much any others, but then all we have to do is figure out how to "tweak" the formula, right? Here's a formula that I suspect will work EVERY time: Given zero based position n Private key k will always be: k = 2 n + x Where x will always be in the range between 0 and 2 nx will be different every time (and almost certainly random), but once you figure out x (through brute force) at any position, you'll have the private key at that position. Another way to look at it is that k will always be random but limited to a random number in the range: 2 n <= k < 2 n+1
|
|
|
|
BurtW
Legendary
Offline
Activity: 2646
Merit: 1131
All paid signature campaigns should be banned.
|
|
January 06, 2016, 02:47:30 AM |
|
Why stop at fitting 2, 3, 4, etc. Keys? Now that we know the first 40 private keys it would be very easy to enter all 40 keys and get a polynomial to perfectly fit all 40 keys. Unfortunately the function will not predict the 41st key.
|
Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
|
|
|
DannyHamilton
Legendary
Offline
Activity: 3388
Merit: 4616
|
|
January 06, 2016, 03:04:15 AM |
|
Unfortunately the function will not predict the 41st key.
No, but (depending on how you define "close") I'll bet I can get you close to the 41st key. Specifically, I'm nearly certain that I can find you a formula that will result in a value that is less than 2 n-1 * 0.5 (which I think would be 2 n-2) away from the actual private key. So for the 41st key I can get you a value that will be within 2 39 of the actual key (with a 50% chance that my value is actually within 2 38 and a 25% chance that my value is within 2 37). While I'm being truthful here, those who are aware of the ranges that the random numbers fall between will probably notice the obviousness in my statement.
|
|
|
|
Quickseller
Copper Member
Legendary
Offline
Activity: 2870
Merit: 2298
|
|
January 06, 2016, 05:58:16 AM |
|
Unfortunately the function will not predict the 41st key.
No, but (depending on how you define "close") I'll bet I can get you close to the 41st key. Specifically, I'm nearly certain that I can find you a formula that will result in a value that is less than 2 n-1 * 0.5 (which I think would be 2 n-2) away from the actual private key. So for the 41st key I can get you a value that will be within 2 39 of the actual key (with a 50% chance that my value is actually within 2 38 and a 25% chance that my value is within 2 37). While I'm being truthful here, those who are aware of the ranges that the random numbers fall between will probably notice the obviousness in my statement. Sure, all you need to do is calculate the midpoint of the potential values of the private key for the 41st key. I am not sure if this would get someone "close" to the 41st private key, although I do not think it matters if you are "close" because AFAIK, for private key n, you receive no benefit for knowing private key n+1, and there is no indication that you are only " +1" away from n. (BTW, I was able to accurately predict the principle behind my response without even reading anything except this post, although my specific response was only formulated after reading the entire thread......and having most of the formulas go way over my head).
--snip--
One thing I noticed:
The first address in the transaction is tagged on blockchain.info with "1st Bitcoin Address Compressed".
So probably this transaction was done by the Bitcoin devs? or even... satoshi?
That address links to a website that appears to be a Chinese version of directory.io (that has recently been taken offline).
|
|
|
|
Bulista (OP)
Member
Offline
Activity: 169
Merit: 23
|
|
January 06, 2016, 06:50:53 AM Last edit: January 06, 2016, 07:13:50 AM by Bulista |
|
The values 1 and 8, suggest that the formula can be something like this:
2^n * x, where x is = 1 OR 2^n + x, where x is = 0
Value 1 is in the position 0, value 8 is in the position 3.
Position 0 has the value 1, which is 2^0*1 OR 2^0+0 Position 3 has the value 8, which is 2^3*1 OR 2^3+0
It means that the calculation of x for the positions 0 and 3 result in 0 or 1.
Lets see if that's right... Position 1 has the value of 3, which is 2 1*1 = 2 OR 2 1+0 = 2Hmm. That didn't work. Position 2 has the value of 7, which is 2 2*1 = 4 OR 2 2+0 = 4Hmm. That didn't work either. Position 4 has the value of 21, which is 2 4*1 = 16 OR 2 4+0 = 16Hmm. Still no good. Position 5 has the value of 49, which is 2 5*1 = 32 OR 2 5+0 = 32This isn't looking like it's going to work. You didn't get the idea. I was also not getting it at first. Look: The values 1 and 8, suggest that the formula can be something like this:
2^n * x, where x is = 1 OR 2^n + x, where x is = 0
This means x = 1 or x = 0 for the positions 0 and 3 ( Only), it's just a superficial demonstration of the formula. Means that x is possibly some kind of formula (A giant one, with mods, logs, exponents and whatever, where n is also included) and when n is = 0, result is 1 and x is 1 or 0, when n is = 3 result is 8 and x is 1 or 0. Values of x for other positions can be also calculated easily, for example position 2: position 2: We know the result is 7, so 2^2 * x = 7 OR 2^2 + x = 7 Means that x is: x = 7 / (2^2) = 1.75 OR x = 7 - 2^2 = 3 That's why I said: Finding the formula for this "x" can be the holy grail of this puzzle.
About the prime factorization, could be part the solution for finding how this x is calculated.
|
|
|
|
werty98
Newbie
Offline
Activity: 8
Merit: 0
|
|
January 06, 2016, 07:50:20 AM |
|
Of course the n-th private key is always in the form 2^n + x; this is the whole point of this puzzle. The problem is there are 2^n possible values for x!
|
|
|
|
Bulista (OP)
Member
Offline
Activity: 169
Merit: 23
|
|
January 06, 2016, 10:46:00 AM |
|
Here are the results for the values we know given those 2 mentioned formulas: y = 2^n * x and so x = y / 2^n AND y = 2^n + x and so x = y - 2^n n | Known Results (y) | x = y / 2^n | x = y - 2^n | 0 | 1 | 1.00000000 | 0
| 1 | 3 | 1.50000000 | 1
| 2 | 7 | 1.75000000 | 3
| 3 | 8 | 1.00000000 | 0
| 4 | 21 | 1.31250000 | 5
| 5 | 49 | 1.53125000 | 17
| 6 | 76 | 1.18750000 | 12
| 7 | 224 | 1.75000000 | 96
| 8 | 467 | 1.82421875 | 211
| 9 | 514 | 1.00390625 | 2
| 10 | 1155 | 1.12792969 | 131
| 11 | 2683 | 1.31005859 | 635
| 12 | 5216 | 1.27343750 | 1120
| 13 | 10544 | 1.28710938 | 2352
| 14 | 26867 | 1.63983154 | 10483
| 15 | 51510 | 1.57196045 | 18742
| 16 | 95823 | 1.46214294 | 30287
| 17 | 198669 | 1.51572418 | 67597
| 18 | 357535 | 1.36388779 | 95391
| 19 | 863317 | 1.64664650 | 339029
| 20 | 1811764 | 1.72783279 | 763188
| 21 | 3007503 | 1.43408918 | 910351
| 22 | 5598802 | 1.33485842 | 1404498
| 23 | 14428676 | 1.72003222 | 6040068
| 24 | 33185509 | 1.97801048 | 16408293
| 25 | 54538862 | 1.62538475 | 20984430
| 26 | 111949941 | 1.66818412 | 44841077
| 27 | 227634408 | 1.69600850 | 93416680
| 28 | 400708894 | 1.49275696 | 132273438
| 29 | 1033162084 | 1.92441434 | 496291172
| 30 | 2102388551 | 1.95800192 | 1028646727
| 31 | 3093472814 | 1.44051053 | 945989166
| 32 | 7137437912 | 1.66181426 | 2842470616
| 33 | 14133072157 | 1.64530614 | 5543137565
| 34 | 20112871792 | 1.17072322 | 2933002608
| 35 | 42387769980 | 1.23364647 | 8028031612
| 36 | 100251560595 | 1.45885221 | 31532083859
| 37 | 146971536592 | 1.06935867 | 9532583120
| 38 | 323724968937 | 1.17770458 | 48847061993
| 39 | 1003651412950 | 1.82563129 | 453895599062
|
|
|
|
|
BurtW
Legendary
Offline
Activity: 2646
Merit: 1131
All paid signature campaigns should be banned.
|
|
January 06, 2016, 02:07:30 PM Last edit: January 06, 2016, 04:21:02 PM by BurtW |
|
Here are the results for the values we know given those 2 mentioned formulas: y = 2^n * x and so x = y / 2^n AND y = 2^n + x and so x = y - 2^n n | Known Results (y) | x = y / 2^n | x = y - 2^n | 0 | 1 | 1.00000000 | 0
| 1 | 3 | 1.50000000 | 1
| 2 | 7 | 1.75000000 | 3
| 3 | 8 | 1.00000000 | 0
| 4 | 21 | 1.31250000 | 5
| 5 | 49 | 1.53125000 | 17
| 6 | 76 | 1.18750000 | 12
| 7 | 224 | 1.75000000 | 96
| 8 | 467 | 1.82421875 | 211
| 9 | 514 | 1.00390625 | 2
| 10 | 1155 | 1.12792969 | 131
| 11 | 2683 | 1.31005859 | 635
| 12 | 5216 | 1.27343750 | 1120
| 13 | 10544 | 1.28710938 | 2352
| 14 | 26867 | 1.63983154 | 10483
| 15 | 51510 | 1.57196045 | 18742
| 16 | 95823 | 1.46214294 | 30287
| 17 | 198669 | 1.51572418 | 67597
| 18 | 357535 | 1.36388779 | 95391
| 19 | 863317 | 1.64664650 | 339029
| 20 | 1811764 | 1.72783279 | 763188
| 21 | 3007503 | 1.43408918 | 910351
| 22 | 5598802 | 1.33485842 | 1404498
| 23 | 14428676 | 1.72003222 | 6040068
| 24 | 33185509 | 1.97801048 | 16408293
| 25 | 54538862 | 1.62538475 | 20984430
| 26 | 111949941 | 1.66818412 | 44841077
| 27 | 227634408 | 1.69600850 | 93416680
| 28 | 400708894 | 1.49275696 | 132273438
| 29 | 1033162084 | 1.92441434 | 496291172
| 30 | 2102388551 | 1.95800192 | 1028646727
| 31 | 3093472814 | 1.44051053 | 945989166
| 32 | 7137437912 | 1.66181426 | 2842470616
| 33 | 14133072157 | 1.64530614 | 5543137565
| 34 | 20112871792 | 1.17072322 | 2933002608
| 35 | 42387769980 | 1.23364647 | 8028031612
| 36 | 100251560595 | 1.45885221 | 31532083859
| 37 | 146971536592 | 1.06935867 | 9532583120
| 38 | 323724968937 | 1.17770458 | 48847061993
| 39 | 1003651412950 | 1.82563129 | 453895599062
|
I think that what you have done is to pretty much prove it is random and there is no predictive formula.
|
Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
|
|
|
Bulista (OP)
Member
Offline
Activity: 169
Merit: 23
|
|
January 06, 2016, 02:54:58 PM Last edit: January 06, 2016, 03:12:00 PM by Bulista |
|
-snip-
I think that what you have done is to pretty much prove it is random and there is no predictive formula. I'm not sure. I got some infos that are getting me to believe that there is a possible formula behind it. I give you an example. I'm playing around by creating random formulas, and I get pretty much similar results. Yet they are predictable with a formula. All I use for inputs are 2 arrays, one with the current position and another with the sequential list of prime numbers. For example: Consider n = count, p = prime numbers, and y = sequence based on the formula 2^n + (n mod p) * Log(n+1, 2) <--- Random formula I invented. y / 2^p + 1 and y-2^p *-1 are similar formulas to what was shown before for the var x in the real sequence, their results also appear to be random... n | p | y = 2^n + (n mod p) * Log(n+1, 2) | y / 2^p + 1 | y-2^p *-1
| 0 | 2 | 1 | 1.25000000 | 3
| 1 | 3 | 3 | 1.37500000 | 5
| 2 | 5 | 7 | 1.22406016 | 25
| 3 | 7 | 14 | 1.10937500 | 114
| 4 | 11 | 25 | 1.01234752 | 2023
| 5 | 13 | 45 | 1.00548399 | 8147
| 6 | 17 | 81 | 1.00061679 | 130991
|
Yet this sequence is breakable with a simple formula. EDIT: this formula doesn't make any sense I know, just playing around
|
|
|
|
werty98
Newbie
Offline
Activity: 8
Merit: 0
|
|
January 06, 2016, 04:02:41 PM |
|
Maybe these random-like numbers came from hashing operations? For example: n-th key = truncate(SHA256(f((n-1)-th key))). It will be still hopeless if the process involves a strong passphrase though.
|
|
|
|
|