Topic: Public Key Division - Number Theore - page 2. (Read 643 times)

Hmm, i dont know if i agree with this statement. When you create 1 million key with the help of subtracting the public key, You have like created a million clones of the targeted public key, and with that, you increase the chance. When you find 1 of the 1 million pubkey, you get back to the original key. So the chances is higher. And so is very similar to dividing.

@digaran, you are fucking smart with coming up with this idea, but it still wont help us a lot finding the targeted priviate key.

Teach me more tips like that though!  

Isn't kangaroo doing division to decrease the search time? As long as you are dividing +n key, you can even reach G itself.

---

Since you don't know anything about the private key, the easiest way is to guess the last digit and if it's even, at least you can divide by 2 for sure.
And if you are dealing with prime numbers, look at N of secp256k1, if you just subtract 1 from it you can divide it by dozens of already known divisor numbers.
Anyways for now the puzzle #125 has been solved, it's  time to focus on the next one #130, we'd either find it or die trying, right? 🤣

Use MinGW software to create a Unix build environment in Windows, and run it from there. It doesn't have any external dependencies.


It's like having a spectrum of a numerical range that extremes from 0 to your maximum value 2^N.

0 |----------------| 2^N

Division cuts that spectrum into two lengths, so that there are 2^(N-M) keys remaining on the left, and then on the right there are 2^M possible remainders there may be that should be tried for each of the keys on the left.

               2^(M-N)
0 |-----------|----| 2^N

Since reminders have to be tried for all remaining keys, the total search space is these two values multiplied together: 2^M * 2^(N-M) = 2^(M+N-M) = 2^N. Exactly the same range as before.

So no, key division does not decrease search time.

Thanks for answer everyone,

After doing researches, I found a decent ecctools that does public key math made and developed by Alberto

https://github.com/albertobsd/ecctools

However, it's made for ubuntu, and i have Windows operating system. Can anyone help me compile the tools for windows?

I'll be grateful

Thanks

You can generate 2^20 keys, based on some 120-bit key, and then one of them will have only 100 bits. But you won't know which one, and you will have to check all of them, so it won't solve anything.

Wouldn't it possible to reduce 120 bits to 100 bits?

For the targeted public key below: 0233709eb11e0d4439a729f21c2c443dedb727528229713f0065721ba8fa46f00e

You can multiply or divide by any number, it doesn't matter.

You won't reduce anything by using division. You are in a finite field, so you can always divide your key by any number, and you will always reach a valid result. If you have 1234 as your key, and divide it by 1000, you will get "1.234" key, so you will end up in fractions, just they will be expressed as large, 256-bit numbers.

It doesn't matter. You can divide a key equal to 31337 by 127, and then you will just get a fraction 31337/127, expressed as some 256-bit number.

For each and every key, you can multiply or divide it by any other key, in the whole range from 1 to N-1, and you will always get some valid key as a result.

Thanks for your answer,

Why do you divide by 2 though? Why not like 1000 or any larger number? (for more reducing). Seems dividing is just as complicated as bruteforcing a whole key. It can reduce range, but it can mess it up also. And what if a PubKey is a prime? Lol then, there is no way to divide it, correct?

Multiply your public key by this key
7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
Key above is N/2, or 0.5 and if you for example multiply 4 by 0.5 you'd get 2, this is a simple operation.
There is also a java calculator on github, https://github.com/MrMaxweII/Secp256k1-Calculator
You can put public key and select division then put 2 and divide or any other number you like.

About dividing you should know, every single even public key has an odd pair we call it inverse key, aka 02 and 03.

If the pub key starts with 02 and it's private key ends with 1, 3, 5, 7, 9 the inverse key must end with 2, 4, 6, 8, 0.

Now let us practice :

Our target pub key :
03f42cde25a364c9764a4c60f762337c0a1a9d27805c89b59bc845e18a93db4ac9

It's private key :
00000000000000000000000000000000000000002880422a1ab3e513482869b2
 Decimal ( 12534455350639729112533985714 ) ends with 4 so it is even.

Inverse pub key :
02f42cde25a364c9764a4c60f762337c0a1a9d27805c89b59bc845e18a93db4ac9

It's private key :
fffffffffffffffffffffffffffffffebaaedce686c85e11a51e7979880dd78f
Decimal (  115792089237316195423570985008687907852837564279062369927254523412405627508623  ) ends with 3 so it is odd.

Now it doesn't matter which one of the pub keys you are dividing, it will divide the even one because there is no fraction in ECC.

If we divide our target pub by 2 we will see :
0312d8734901f0f88e3b396c4fa66454543cd8837bbb31ea177cc19b99a8a79ed1
Private key :
0000000000000000000000000000000000000000144021150d59f289a41434d9
Decimal (  6267227675319864556266992857  )
Inverse pub :
0212d8734901f0f88e3b396c4fa66454543cd8837bbb31ea177cc19b99a8a79ed1
Private key :
fffffffffffffffffffffffffffffffebaaedce69b087f26b2786c032c220c68
Decimal (  115792089237316195423570985008687907852837564279068637154929843276961894501480  )

Then if you try to divide this
0312d8734901f0f88e3b396c4fa66454543cd8837bbb31ea177cc19b99a8a79ed1
Or the -n aka 02 version of it, doesn't matter which one since both will give you the same result which is :
0222db101c46b9d0f52e30f1be2565c67a9e75d3104fda0b75fcbec3fae320b88d
Private key :
7fffffffffffffffffffffffffffffff5d576e734d843f93593c360196110634
Decimal (  57896044618658097711785492504343953926418782139534318577464921638480947250740  )
Inverse key :
0322db101c46b9d0f52e30f1be2565c67a9e75d3104fda0b75fcbec3fae320b88d
Private key :
7fffffffffffffffffffffffffffffff5d576e7361c460a86696288b3a253b0d
Decimal (  57896044618658097711785492504343953926418782139540585805140241503037214243597  )

So, tell me, are we close to our target or did we just distanced ourselves from target by 2^255 difference? If you had more questions, happy to answer if I know the answer.😉

Hi,

We all (hopefully) have heard about the current ongoing-puzzle that was recently increased its prize by 10x and which is still not all solved for long time.

Since I'm very interesting in math and dealing with big numbers, I would love to get to learn about dividing public keys. I will mainly focus for the next possible puzzle (#125) which has its public key revealed.

Puzzle #125:

Since public key for puzzle #125 is revealed, we can do many things with it so we can try to slightly reduce the targeted range by XXX amount.

I already know Addition, Subtraction, and striding public keys, but weirdly i haven't managed to know how to divide public keys in the correct way.

Can you help me give me an detailed example of dividing public key into lower ranges, and if possible which tools is needed for the process?

What could be the advantages and disadvantages of dividing public keys? Is it a problem if the divided public key has a decimal in it? I think if i understood correctly, the newly divided keys could be invalid and could lead to infinity if its wrongly divided (Correct me, if I'm wrong).

Thanks to all, and Goodluck hunting!