Half of any bitcoin (crypto) public key - (public key half) in Python

[Trancefan]

I know from reading another forum that a public key in bitcoin is a point P. To do P2, 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 Euclidean algorithm and is 57896044618658097711785492504343953926418782139537452191302581570759080747169 in the case of secp256k1.
2^-1 (mod n) = 57896044618658097711785492504343953926418782139537452191302581570759080747169


2 * 57896044618658097711785492504343953926418782139537452191302581570759080747169 = 1 (mod n)

Multiplying a point by this number will "half" the point.

My question is how would I code this in python?

[1715302621]

1715302621

[aplistir]

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  
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 )

[Trancefan]

The forum I got the information on is https://bitcointalk.org/index.php?topic=4455904.0

[aplistir]

The forum I got the information on is https://bitcointalk.org/index.php?topic=4455904.0

Thanks for the link

What it says is true. You can get "half" of a public key.

But What I wrote above is also correct. The "half" can be half way towards zero, or half way to max value depending if the point is "odd" or "even" 

[Trancefan]

2 * 57896044618658097711785492504343953926418782139537452191302581570759080747169 = 1 (mod n)

Multiplying a point by this number will "half" the point.

How do I multiply a point by the number?
private key 3

x =  f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
y =  388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672

half of the above public key is 1 given below

x =  79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y =  483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

How to half to multiply  f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 to get to 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798?

[DaCryptoRaccoon]

You are talking of exploiting the ECDSA signatures?

If you have the values you can use something like this.

Code:

#!/usr/bin/env python

import bitcoin
import hashlib
import random

def ecdsa_sign_k(z, d, k):
    r, y = bitcoin.fast_multiply(bitcoin.G, k)
    s = bitcoin.inv(k, bitcoin.N) * (z + r*d) % bitcoin.N
    v, r, s = 27+((y % 2) ^ (0 if s * 2 < bitcoin.N else 1)), r, s if s * 2 < bitcoin.N else bitcoin.N - s
    return v, r, s

# Generate secret key & the corresponding public key and address
sk = random.SystemRandom().randrange(1, bitcoin.N)
Q = bitcoin.fast_multiply(bitcoin.G, sk);

# Sign 2 differents messages with same k
signing_k = random.SystemRandom().randrange(1, bitcoin.N)
z1 = bitcoin.hash_to_int(hashlib.sha256('first_message').hexdigest())
z2 = bitcoin.hash_to_int(hashlib.sha256('second_message').hexdigest())
v1, r1, s1 = ecdsa_sign_k(z1, sk, signing_k)
v2, r2, s2 = ecdsa_sign_k(z2, sk, signing_k)
assert r1 == r2
print('+ R used   = {:x}'.format(r1))

# Calculate k candidates
k_candidates = [
    (z1 - z2) * bitcoin.inv(s1 - s2, bitcoin.N) % bitcoin.N,
    (z1 - z2) * bitcoin.inv(s1 + s2, bitcoin.N) % bitcoin.N
]
for k in k_candidates:
    priv_key = (s1 * k - z1) * bitcoin.inv(r1, bitcoin.N) % bitcoin.N
    if bitcoin.fast_multiply(bitcoin.G, priv_key) == Q:
        print('+ Calc key = {0}'.format( priv_key ))
        break
else:
    print('An unknown error occured.')