is it possible to calculate the difference between 2 public keys of secp256k1

Question

I am inquiring about the feasibility of calculating the point difference between two distinct secp256k1 elliptic curve points. Given the nature of secp256k1, which is widely used in cryptographic applications such as blockchain technology, I am interested in understanding the process and potential challenges involved in determining the point difference between these specific curve points.

Could you please provide a detailed explanation of the mathematical and computational methods that can be employed for such a calculation, along with any relevant considerations or limitations?

For example:

Pub_key_A= 02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 
    (private key is 2)
pub_key_B= 2c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
(private key is 3)

The deference between 2 points is 1; I need the difference in number of points between point A and B.

Code that I tried:

import ecdsa

# Convert hexadecimal public keys to bytes
public_key1_hex = "02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5"
public_key2_hex = "02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9"

public_key1_bytes = bytes.fromhex(public_key1_hex)
public_key2_bytes = bytes.fromhex(public_key2_hex)

# Create ecdsa.VerifyingKey objects for the first and second public keys
vk1 = ecdsa.VerifyingKey.from_string(public_key1_bytes, curve=ecdsa.SECP256k1)
vk2 = ecdsa.VerifyingKey.from_string(public_key2_bytes, curve=ecdsa.SECP256k1)

# Get the generator point of the elliptic curve
generator_point = ecdsa.SECP256k1.generator

# Calculate the inverse of vk2's public key point
vk2_inverse_point = generator_point - vk2.pubkey.point

# Calculate the difference between the public key points
difference_point = vk1.pubkey.point + vk2_inverse_point

# Convert the difference point to hexadecimal
difference_hex = "04" + difference_point.x().to_bytes(32, byteorder="big").hex() + difference_point.y().to_bytes(32, byteorder="big").hex()

print("Difference between public key points:", difference_hex)

Answer 1

What you need depends on what you mean by 'point difference'.

What your code appears to be attempting to do is compute the point $X$ such that $X + K2 = K1$. That is easy to do ($X = K1 + (-K2)$, or $X = K1 - K2$), and your code almost does it, except:

# Calculate the inverse of vk2's public key point
vk2_inverse_point = generator_point - k2.pubkey.point

Here's your problem: $G - K2$ is not the inverse of $K2$. You might try:

vk2_inverse_point = -k2.pubkey.point

That is, the library you're using probably has 'point negation' (which you call inversion) built it - it's actually quite simple to do on the library side.

On the other hand, you also write:

example: Pub_key_A= 02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 (private key is 2) pub_key_B= 02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 (private key is 3) the deference between 2 points is 1 i need the difference in Number of points between point A and B

If, given the public keys $aG$ and $bG$, you want the integer $a-b$, well, we hope that's a hard problem. If it is not, you can easily find private keys from public keys - given the public key $aG$, we can:

• pick an arbitrary $b$
• compute $bG$
• with $aG, bG$, we use that method to recover $a-b$;
• add back $b$ and that gives us the private key $a$.

Answer 2

The problem is: for $K_1$ and $K_2$ on secp256k1 given by their (compressed) coordinates, find the integer $d$ with $-n/2<d<n/2$ such that $d\,G+K_1=K_2$ (where $n$ is the 256-bit prime order of secp256k1).

If $d$ is extremely close to $0$ (to the point that it's feasible to perform $|d|$ point additions, which includes the example since $d=1$) then it's possible to find $d$ by trying incremental values

• if $K_1:=K_2$, output $0$ and stop.
• set $K:=K_1-K_2$, $P:=G$, $d:=1$
• while $x_P\ne x_K$
  • set $P:=P+G$ and $d:=d+1$
• if $y_P\ne y_K$
  • set $d:=-d$
• output $d$

The operations involving elliptic curve points (capital letters) are detailed there.

---

For $d$ still very close to $0$ (when it's feasible to perform $2\sqrt{|d|}$ point additions and store the $x$ coordinates of half the results), the Baby Step / Giant Step algorithm solves the problem. I think there are algorithms (Pollard's rho or/and Pollard's lambda) that use much less memory and distribute better, at the cost of slightly more computations on average and being probabilistic.

However, if $K_1$ and $K_2$ are independently chosen and at least one is (uniformly) random, then $d$ is (uniformly) random in $\bigl[-\left\lfloor n/2\right\rfloor,\left\lfloor n/2\right\rfloor\bigr]$, and the task is as infeasible as finding the private key for a random point $K$ on secp256k1.

---

Thus it's unreasonable to attempt anything like the above unless we know something about what $K_1$ and $K_2$ are, and said something is such that the solution $d$ is likely to be small.