Can the public key be derived from the private key? [closed]

Question

The calculation/formula i use in deriving a public key from the private key without importing any module in python3 script involves the following steps:

1. Define the parameters of the secp256k1 elliptic curve:

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

2. Initialize the variables:

Qx = Gx
Qy = Gy

3. Define the private key:

private_key = 0x000000000000000000000000000000000000000000000000000000000000000f

4. Perform the scalar multiplication using double-and-add algorithm:

for bit in bin(private_key)[3:]:
    # Perform point doubling on the elliptic curve
    # Calculate the slope
    s = (3 * Qx**2 + a) * pow(2 * Qy, -1, p) % p

    # Calculate the new point coordinates
    Rx = (s**2 - 2 * Qx) % p
    Ry = (s * (Qx - Rx) - Qy) % p

    # print every calculated points
    print ('\n[1]\nQx =',Qx,'\nQy =',Qy,'\nRx =',Rx,'\nRy =',Ry)

    Qx = Rx
    Qy = Ry

    if bit == '1':
        # Perform point addition on the elliptic curve
        # Calculate the slope
        s = (Qy - Gy) * pow(Qx - Gx, -1, p) % p

        # Calculate the new point coordinates
        Rx = (s**2 - Qx - Gx) % p
        Ry = (s * (Qx - Rx) - Qy) % p

        # print every calculated points
        print ('\n[2]\nQx =',Qx,'\nQy =',Qy,'\nRx =',Rx,'\nRy =',Ry)

        Qx = Rx
        Qy = Ry

5. Initialize the variables:

x = Qx
y = Qy

6. Convert x and y coordinate to hex:

public_key_hex = '04' + format(x, '064x') + format(y, '064x')

7. Print results:

print ("\nPublic key (uncompressed) =", public_key_hex)

The complete/formated python3 script as follow:

# Define the parameters of the elliptic curve
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# Perform scalar multiplication on the elliptic curve
# Initialize the variables
Qx = Gx
Qy = Gy

private_key = 0x000000000000000000000000000000000000000000000000000000000000000f
print('\nExample = 3a6859fcfc9bb02981897c2d5bcb0ca1ded0c2eac4e89304411709615aea1420')
private_key = int('0x' + input('[Key]: '), 16)

# Perform the scalar multiplication using double-and-add algorithm
for bit in bin(private_key)[3:]:
    # Perform point doubling on the elliptic curve
    # Calculate the slope
    s = (3 * Qx**2 + a) * pow(2 * Qy, -1, p) % p

    # Calculate the new point coordinates
    Rx = (s**2 - 2 * Qx) % p
    Ry = (s * (Qx - Rx) - Qy) % p

    # print every calculated points
        print ('\n[2]\nQx =',Qx,'\nQy =',Qy,'\nRx =',Rx,'\nRy =',Ry)
    
    Qx = Rx
    Qy = Ry

    if bit == '1':
        # Perform point addition on the elliptic curve
        # Calculate the slope
        s = (Qy - Gy) * pow(Qx - Gx, -1, p) % p

        # Calculate the new point coordinates
        Rx = (s**2 - Qx - Gx) % p
        Ry = (s * (Qx - Rx) - Qy) % p
    
        # print every calculated points
        print ('\n[2]\nQx =',Qx,'\nQy =',Qy,'\nRx =',Rx,'\nRy =',Ry)
        

        Qx = Rx
        Qy = Ry

# Initialize the variables
x = Qx
y = Qy

# Convert coordinate to Hex
public_key_hex = '04' + format(x, '064x') + format(y, '064x')

# Print results
print ("\nPublic key (uncompressed) =", public_key_hex)

In the given Python script the main calculation used are as follow:

s = (3 * Qx**2) * pow(Qy*2, -1, p) % p
Rx = (s**2 - Qx*2) % p
Ry = (s * (Qx - Rx) - Qy) % p

s = (Qy - Gy) * pow(Qx - Gx, -1, p) % p
Rx = (s**2 - Qx - Gx) % p
Ry = (s * (Qx - Rx) - Qy) % p

Based on my understanding these calculations are used to derive the public key from the private key. If someone was able to reverse each calculations would they be able to obtain each bits of the binary representation of the private key then concentrate all the bits together then add a 0 or 1 to the beginning of the binary representation then convert it to decimal to obtain the private key?

This is because the Python script converts the private key to binary then removes the first bit then perform the above series of calculations for each bit in order to obtain the public key.

Could someone confirm if my understanding is correct?

Please answers should be base on the body of the question not the topic.

Answer 1

For the inverting the private key from public key, we have a well defined problem; the discrete logarithm problem; namely,

• given $P$ over a prime curve $E(\mathbb{F}_p)$ with the generator $G$, find $x$ such that $P= [x]G$ .

There are many works for speeding the discrete logarithm;

• Baby-step-Giant-Step which has $\mathcal{O}(\sqrt{p})$-time and $\mathcal{O}(\sqrt{p})$-space complexity.
• Pohlig–Hellman algorithm is useful especially if the order of the group is a smooth integer. This is based on the on the Floyd's cycle-finding algorithm. This is not the case for Secp255k1 since the order is prime.
• Pollard's kangaroo algorithm. This is a range based algorithm, given in a range $[a,b]$ it can find the discrete log in $\mathcal{O}(\sqrt{b-a})$-time.

Currently best achievement for Secp256k1 is performed with parallel Pollard's kangaroo. Best record can achieve 112-bit.

If you where to run the script and input a private key it will print the points calculated in the process of deriving the public key. Now take any of the calculated points (𝑅𝑥,𝑅𝑦) and indicate([2] or [1]) if it was derived using point doubling or point addition formula and I'll reverse the calculation the give you the value of 𝑄𝑥 and 𝑄𝑦 that was used in deriving the new points 𝑅𝑥 𝑅𝑦 (Deleted comment)

The obtaining the public key from the private key $k$ and base point $G$ is calculated as $P = [k]G$, this is scalar multiplication and means add $G$ itself $k$-times ( consider integer value of $k$).

$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$

This is a very long method and we have better alternatives like double-and-add method^* ( if $k$ is integer than it takes roughly $\lfloor \log_2{k}\rfloor+1 $-time.)

let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s
let temp = P # track doubled P val
for bit in bits: 
    if bit == 1:            
        res = res + temp # point add
    temp = temp + temp # double
return res

Now, this speeds up the calculation, and notice that it is depending on the value of bits of the $k$. Actually, this is not good since can cause side channel attacks. We use double-and-add method to demonstrate the problem. Notice two points;

1. There is always doubling
2. There can be point addition only if the current bit value of $k$ is 1.

So, for every bit of the key;

• we may return back to either only doubled case or added and doubled case.

• There is no test value for the reversing, i.e. how to determine that it was only double or add-and-double.

• So one needs to use a tree structure to follow the the cases. Can we see where is is going?

• For every step, we need to branch and this is exactly, two branch.

• In the final, the tree will have depth $n$ where $n$ is the number of bits of $k$, possible values on the tree and $2^n$ leaves.

• This is exactly same as the number of the bits of the key that needed to determine.

Now, one faces two problems;

1. One cannot store such tree since you need around $2^{256}$ storage for Secp256k1, and
2. One cannot compute such tree since you need reach $2^{256}$ computing power for Secp256k1. The best available one, the bitcoin miners can reach $2^{93}$ in a year, so you still need $2^{163}$ year to achieve this.

Well, on the other hand Pollard's $\rho$ has complexity around $\mathcal{O}(\sqrt{p})$, where $p$ is the size of the group generated by the $G$. This is far better than above.

---

_{^*Similar arguments can make for the Montgomery and Joyce ladder, too.}