Issue with Elliptic Curve over finite field division

Question

$G$ is the generator point, In spec256k1, I want to divide $5020G$ over $2$ which works and gives me a point where the scalar is $2510$. To do that I first find multiplicative inverse of $2$ which is

0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 

and use it to scale the point.

The issue is that it only works when the scalar of that point is an even number $(16, 32, 50, \dots)$, but if I divide $53G$ by $2$ it doesn't work and I get a random point on the curve.

Without knowing the scalar value ($53$) is there any solution to detect if a point is not divisible by $2$?

Answer 1

This is an answer to a not so clear question, it is posted in the hope that the information needed to set up the framework, the way it is given, may help in future questions.

So we are working with the bitcoin elliptic curve, which is usually called Secp256k1 (and not spec256k1 as in the question). Using sage, the situation is initialized as follows:

p = ZZ('0x FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F'
       .replace(' ', ''))
print(f"p = {p}")
print("Is p equal to 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 ?")
print(bool(p == 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1))

F = GF(p)
E = EllipticCurve(F, [0, 7])
n = ZZ('0x FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141')
print(f"n = {n}")
print(f"Is n prime? {n.is_prime()}")

N = ZZ((n+1)/2)
print("N = (n + 1)/2 has the following hex representation:")
print(hex(N))

Results:

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Is p equal to 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 ?
True
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Is n prime? True
N = (n + 1)/2 has the following hex representation:
0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1

The above 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 matches the given information from the question. So i am with a high guess in the right place. Store this $N$ for later use,

sage: N
57896044618658097711785492504343953926418782139537452191302581570759080747169

$$ N = 57896044618658097711785492504343953926418782139537452191302581570759080747169 \ . $$ Let us not say some words on the setting of the problem.

We are working with the set of points $P=(x,y)$, where $x,y$ are elements in the finite field $F=\Bbb F_p$ with $p=2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$ elements ($p$ is indeed prime), which satisfy the (affine) algebraic equation (of a Koblitz elliptic curve $E$) over $F$ $$ E\ :\qquad y^2 = x^3+7\ . $$ We also add the point $O$, the neutral element, it is satisfying the homogenized version of the above, $y^2z=x^3+7z^3$, and $O=[0:1:0]$ in $[x:y:z]$-coordinates. (Usually, we norm the $z$-component if $z\ne 0$.) This set is usually denoted by $E(F)$, the set of the $F$-rational points of the elliptic curve $E$.

The one bitcoin-published generator of the curve is "in compressed form":

G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

Again, the cryptographic information from loc. cit. comes as usual in a cryptic manner. This means that we take the above "hex number", without the white noise information 02 specifying what to do with the rest, write it as an integer, take it modulo $p$, (i.e. coerce / convert / project to an element in $F=\Bbb F_p=\Bbb Z/p$), obtain an element $x_G\in F$, that can be "lifted" (completed with a second component) to an element $$ (x_G,y_G)\in E(F)\subset F\times F\ . $$ Let us do so:

xG = F(ZZ('0x 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798'
         .replace(' ', '')))
G = -E.lift_x(xG)    # take the other lift...
yG = G[1]
print(f"xG = {hex(ZZ(xG))}")
print(f"yG = {hex(ZZ(yG))}")

This gives:

xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

and this is the generator. Note that:

sage: n*G
(0 : 1 : 0)
sage: n*G == E(0)
True

So $n$ times the generator is the neutral element $O$ for the addition of points on the elliptic curve $E$ / on its rational points $E(F)$. We can finally start the answer:

---

• Consider the point $P=5020G$. If we know that this point is computed as $5020G$, than taking "half of it" can be done by computing $Q=\left(\frac{5020}2\right)G=2510G$.

  Check: $2Q = 2\cdot(2510G)=(2\cdot2510)G=5020G=P$.

• Consider the same point $P=5020G$, but assume that the multiplier $5020$ is not known to some other person Eve, so Eve has only the point $P$. How can Eve construct some point $Q'$ with $2Q'=P$? Well, Eve may just compute $Q'=N\cdot P$, where $N$ is the stored number from above.

  Check: $2Q'=2(NP)=(2N)P=(n+1)P=nP+P=O+P=P$.

  In general, if for two points $Q,Q'$ we have $2Q=2Q'$, then $2(Q-Q')=0$, but the order of $E(F)$ is $n$, an odd number, so $(Q-Q')=0$ after multiplication with the "half", which is $N$. So $Q=Q'$. Code reproducing this:

    sage: P = 5020*G
    sage: Q1 = 2510*G
    sage: Q2 = N*P
    sage: print(f"Is Q1 equal to Q2? {bool(Q1 == Q2)}")
    Is Q1 equal to Q2? True
    sage: print(f"Is 2 Q1 equal to P? {bool(2*Q1 == P)}")
    Is 2 Q1 equal to P? True
    sage: print(f"Is 2 Q2 equal to P? {bool(2*Q2 == P)}")
    Is 2 Q2 equal to P? True
  

• What about taking the "half" of $R=53 G$? No problem, we multiply this point with $N$:

    sage: R = 53*G
    sage: R
    (109204401742901676102938274178210524270147101032576152349016621748734496666183 
      : 93562928090829704595527535353598406140745506107437687143296992058804640357878 
      : 1)
    sage: R_HALF = N*R
    sage: print(f"Is 2 R_HALF equal to R? {bool(2*R_HALF == R)}")
    Is 2 R_HALF equal to R? True
  

---

Note: See also my answer on the other Q&A site: asksage question 50288