Quote from: aplistir on May 08, 2019, 02:52:19 PM

Quote from: Trancefan on May 08, 2019, 01:16:46 PM

I know from reading another forum that a public key in bitcoin is a point P. To do P/2, you multiply 12 to P where 12 is the multiplicative inverse of 2 in Zn. It is an integer that can be found using the extended...

My question is how would I code this in python?

I see what you are trying to do

You can indeed halve a point, BUT, and it is a big BUT, halving a point does not work as you would expect.
Because halving an odd and an even "point" behave differently.

For example. Let us work in field of numbers mod 17. (Where multiplicative inverse of 2 is 9)
if you divide point 8 by 2 you get 4 as you would expect,
but if you divide 9 by 2 you will get 13 (which is 4+1/2, which is 4+9 )

Or more simply:
If you divide any even number you will end up half way between that number and 0 and if you divide any odd number you will end up half way between than number and 17

This example is with numbers mod 17, but fields with "points" work exactly the same way. All fields of the same order are isomorphic. (=the same)

When it comes to bitcoin and finding the private key from public key by dividing by 2 until you get to the generator G, in this example G=1. Which is what I assume you want to do Wink

Using the above example, lets try to find 1 by dividing 7 repeatedly by 2, (all calculations done mod 17)

Code:

7/2 mod 17=12
12/2=6
6/2=3
3/2=10
10/2=5
5/2=11
11/2=14
14/2=7
7/2=12
... and so on ...

In this case you will never get to one. With some other numbers you would of-course reach one, but dividing by 2 wont make it any faster than brute forcing

To sum up. dividing by 2 wont help you in getting the private key from the public key, unless you can also tell which point is "even" and which is "odd".

And how to code the point multiplication in python?
The easiest way is to use a free math program called sagemath. It uses python, but has all the required functions already in it. Sage understands, big numbers, elliptic curves, finite fields and so on. To multiple a point in sage is as easy as this: 123456*G
But first you have to tell it what curve you are using and what is your generator
Sage is easy to use, but you need to study it a bit before you can use it.

PS. You do not have to use Euclidean algorithm to find what is the multiplicative inverse of 2 in any finite field. 1/2 is always (n+1)/2, where "n" is the order of the curve (= number of points )

https://themonkspeaks.com/

jonsnow902611

Posts

Merits