Guys fyi 1024 is not div point in ecc, posting here, divideable magic digits for ecc, these will help you to decide bitrange to divide, use these magic ecc div numbers, for pollard kanagroo or other manual div
2 447 7572 564114 3 596 9536 752152 4 631 10096 1128228 6 894 14304 1504304 8 1192 15144 2256456 12 1262 20192 3008608 16 1788 28608 4512912 24 1893 30288 6017216 32 2384 40384 9025824 48 2524 60576 18051648 64 3576 94019 96 3786 121152 149 4768 188038 192 5048 282057 298 7152 376076
What the hell is a div point?
|
|
|
Is there any mathematical argument for this reduction? And what magic numbers are we talking about ![Cheesy](https://bitcointalk.org/Smileys/default/cheesy.gif) .
|
|
|
How about I give you a 120 bit public key and you give me exactly one 115 bit public key.
|
|
|
Can somebody please explain what the "brainless"-method is?
What is he adding and subtracting? WTF. Can somebody provide an example?
|
|
|
from fastecdsa import curve from fastecdsa.point import Point import bit
G = curve.secp256k1.G N = curve.secp256k1.q
def pub2point(pub_hex): x = int(pub_hex[2:66], 16) if len(pub_hex) < 70: y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2) else: y = int(pub_hex[66:], 16) return Point(x, y, curve=curve.secp256k1)
# This function makes all the downscaled pubkeys obtained from subtracting # numbers between 0 and divisor, before dividing the pubkeys by divisor. def shiftdown(pubkey, divisor, file, convert=True): Q = pub2point(pubkey) if convert else pubkey # k = 1/divisor k = pow(divisor, N - 2, N) for i in range(divisor): P = Q - (i * G) P = k * P if (P.y % 2 == 0): prefix = "02" else: prefix = "03" hx = hex(P.x)[2:].zfill(64) hy = hex(P.y)[2:].zfill(64) file.write(prefix+ " " + hx+"\n") # Writes compressed key to file file.write("\n") # Writes compressed key to file
with open("input.txt", "r") as f, open("output.txt", "w") as outf: line = f.readline().strip() while line != '': outf.write("original: " +line + "\n") shiftdown(line, pow(2,1), outf) line = f.readline().strip() input: 02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4 ..d13 is 4 and ...fe4 is 5 output: original: 02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13 02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413
original: 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4 03 5699b93fc6e1bd29e09a328d657a607b4155b61a6b5fcbedd7c12df7c67df8f5 02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 is 2 Because i know 4 is even, i know it has to be the first pubkey. Because i know 5 is odd, I know it has to be the second key. The problem is, that in bigger numbers, you can not determine if it is odd or even. See,if I add the pubkey of 3 original: 02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 -> pubkey of 3 02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413 -> not the halve 02 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 -> pubkey of 1
original: 02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13 -> pubkey of 4 02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 -> odd pubkey of 5 02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413 -> even pubkey of 3
original: 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4 -> pubkey of 5 03 5699b93fc6e1bd29e09a328d657a607b4155b61a6b5fcbedd7c12df7c67df8f5 -> not the halve 02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5-> pubkey of 2
You see... You can not determine from the halve if it is the correct one.
|
|
|
Also dont forget: The Problem we have is, that we don't know if the last bit is even or odd. If you know if the last bit is even or odd, you can crack any public key in no time.
How does this affect? Please explain in more detail.. You can always shift down a public key, aka halving a public key. You get two new public keys. But one is really halving and the other one is moving to the key middle range. E.g. You have the public key of 4 (binary represantation is 100). You halve it, and get the public key of 2 (10) and the public key of midrange - 2. You have the public key of 5 (binary representation is 101). You halve it, and get the public key of public key of midrange - 2 or 3 and 2 (binary 10). As you dont know the lowest bit, you can not determine which one of the pubkeys is the one you need. So you you have to take both and check them for the correct result.
|
|
|
ssxb
Your post makes not so much sense to me?!
How does brainless approach reduce the amount of public keys? Did you understand what he meant? Can you elaborate it further?
|
|
|
Also dont forget: The Problem we have is, that we don't know if the last bit is even or odd. If you know if the last bit is even or odd, you can crack any public key in no time.
|
|
|
@WanderingPhilosopher If you store it in a file, you can lookup the position. But is there a formula for shifting it up by knowing the position of the pubkey?
@fxsniper
Do you read? It is a memory tradeoff! If you bitshift a 256 bit key 128 bit you will have 2^128 keys to check in a range of 1-2^128. 2^128 is how many petabytes???
Please inform yourself about ECDLP. I invested last few weeks in my freetime to understand how it works and what to do.
|
|
|
for 40 bit it is 5 minutes.
With 300 MKey/s it will be for me 1 hour. 2^40 = 1,099511628×10¹² 1,099511628×10¹² keys / 300000000 keys/s = 3665,038759253 s = 61 minutes I suppose that if you don't know range of public key, you can't nothing.
Well. we are cracking this puzzle currently, right ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) . So as I wrote earlier, this bitshifting is a memory/processing performance tradeoff. The more you bitshift the more keys you have to check, till it is not practical anymore. So e.g. you could store 2^30 pubkeys into a bloom filter and need about 4 GB memory or 2 ^31 pubkeys and about 8 GB RAM or 2 ^32 pubkeys and about .... So if you would have 65 bits, you would bitshift it by the amount of pubkeys you can effectively store in your bloom filter. Lets say you can store 2 ^ 31 pubkeys in your bloom filter. Now you have only to generate the pubkeys and store them and crack them. Get the privatekey, shiftup and remove the first bits from the 65 bits of the pubkey and get a new shorter pubkey. Crack again like you did with the first bits. Shift up and remove the next bits. small amount of bits left, crack them. Now add privatekeys from the three rounds and voila you have the privatekey of the 65 bit in about an no time. Maybe not as fast as BSGS or Kangaroo, but still faster then BruteForce. Also BSGS is possible to crack multiple keys, Kangaroo currently can only crack one pubkey at a time, so totally useless for this bitshifting operation. because if it works, you are millionaire, and the question what are you doing on forum:D
lets say you want to crack 256 bit publickey. You could bitshift by lets say 30 bits. You would still need to bruteforce 226 bits.
|
|
|
I added also following to my original post So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.
Why will we have 31 public keys and not 32?
You will have 32 pubkeys, but from those 32 pubkeys only one will be in the desired range. The other 31 pubkeys will be all over the place, and thus being uninteresting.
|
|
|
You could give me your 40 bit public key. But cracking it is kind of waste of time, as I would need to do alot manually, you know...
But how to crack it: I would bit shift your public key by 65536 ( 2 ^ 16). I will then have 65536 pubkeys and one of them is in range 2 ^ 24. I will run it on BitCrack and get the key in 2 ^24. By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.
So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.
|
|
|
It doesnt matter if you know if it is even or odd. If you shiftdown you always get a solution for last bit being even and one for odd.
So if you divide by 32, you will have 31 publickeys which are out of your modified searchrange not leading to the solution and one which will be in the searched range.
|
|
|
This makes actually no sense, because the underlying principle is different. example: Puzzle 11 https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000483038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b halving the publickey: 03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d 03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 is the result, when the privatekey of puzzle 11 is even and 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d if the the privatekey of puzzle 11 is odd. 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is the correct one, as the privatekey of puzzle 11 is odd 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000241So if you do 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d + 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d, you get 038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b (untested, I guess you need also adding the Generatorpoint for + 1 as we do 241 + 241 + 1 = 483) So what is 03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 then? It is 241.5. 241.5 + 241.5 = 483 So, where do we find 241.5? https://privatekeys.pw/key/7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b1e5fHow did I find it? key middle range minus half of our privatekey: 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 - 0x241 => tada So from complexity of 11 bits, i just needed to check 10 bits now. If I divide by 32, I actually do what? 2 * 2 * 2 * 2 * 2 = 32 So we are halving the public key 5 times. This means, that when we do this on key 11, we get 32 keys, from where one of them has the correct endsequence of the private key. So we have to check all keys if they are in the range of 2^6. If we get one, than we know how the first 6 bits of the privatekey are. We can from here determine the last 5 bits easily. I am not interested in the other ranges, as i have now a total valid privatekey
|
|
|
When openSSL uses /dev/urandom, then even the last 5 digits will be random.
What is the benefit of calculating it in zones? And how is it possible to determine which PubKey is in which Zone?
|
|
|
Please describe what you are doing. I mean, we should invest calculation power on the premise, that your key is resulting in a solution. But till now, you are lacking the proof, that it makes sense.
And why dont you reduce it further and further?
|
|
|
How do you generate these pubkeys?
|
|
|
If I have the privatekey for your public key... why should i share it with you?
|
|
|
Does it have to be regex? Or can it be any other function?
|
|
|
Then sell your bitcoins and invest in land.
|
|
|
|