# multiply the point by 2^-1 (mod n)

Public key x and y == Double(Half of the Public key x and y) how to code this in sage math how to get coordinate x
x = f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 y = 388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672

edit retag close merge delete

I don't understand your question, can you rephrase it? What is happening to x and what is happening to y? What is n? Halving and then doubling sounds like it would do nothing.

( 2020-03-18 10:09:39 -0600 )edit

Sort by » oldest newest most voted

This is a rather cryptic question, but i guess i could guess the setting and the answer...

We are performing elliptic curve cryptography (EC). We are using the Bitcoin EC over the Koblitz curve named secp256k1 which has the equation $$y^2=x^3+7\ ,$$ and it is defined over the finite field with $p$ elements, where $p$ is given often by its hex string representation.

sage: p_string = 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F'
sage: p = ZZ( '0x' + p_string.replace(' ', '') )
sage: p
115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: p.is_prime()
True


If this prime p is declared, we can also associate the elliptic curve

sage: E = EllipticCurve( GF(p), [0, 7] )
sage: E
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size
115792089237316195423570985008687907853269984665640564039457584007908834671663


(Result was manually broken.)

The order of this curve, i.e. the order of the finite group of $\Bbb F_p$-rational points of $E$, is hard to compute, but the wiki page https://en.bitcoin.it/wiki/Secp256k1 is giving it to us for free:

sage: n_string = 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'
sage: n = ZZ( '0x' + n_string.replace(' ', '') )
sage: n.factor()
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: n.is_prime()
True


Now we will consider a random point on $E$, test if the order is "killing it":

sage: P = E.random_point()
sage: xP, yP = P.xy()
sage: print( f"xP = {xP}\nyP = {yP}" )
xP = 62433494688810490710184746376136664879440363064558608268184229054491693401589
yP = 99181992444807813146634000210860529358070091479642650161488200640388188617917
sage: n*P
(0 : 1 : 0)


Yes, so far so good. Now we come back to the OP, and consider that point.

xP = '0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9'
yP = '0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672'
P = E.point( (xP, yP) )


Sage is accepting the above line, which also checks that the point with the above coordinates is on the curve.

Now the question wants the "half point", $$Q = \frac 12 \cdot P\ .$$ To get it, we first get the "integer version" of $1/2$ by computing $1/2$ modulo the prime $n$. This is:

sage: half_mod_n = 1 / GF(n)(2)
sage: half_mod_n
57896044618658097711785492504343953926418782139537452191302581570759080747169
sage: half_mod_n.parent()
Finite Field of size 115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: half_mod_n = ZZ(half_mod_n)
sage: half_mod_n.parent()
Integer Ring


Now we can finally build $Q$, which is "half $P$" on the EC $E$:

sage: Q = half_mod_n * P
sage: xQ, yQ = Q.xy()
sage: xQ
89636686429439908262420422079980100111093242688153882571369946125714247242771
sage: yQ
10834049905482024808827094233028503931704324296739647619935835709590451240976
sage: hex(xQ)
'0xc62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413'
sage: hex(yQ)


All in one go:

p = ZZ( '0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F'.replace( ' ', '' ) )
n = ZZ( '0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'.replace( ' ', '' ) )
E = EllipticCurve(GF(p), [0, 7])

xP = '0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9'
yP = '0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672'

P = E.point( (xP, yP) )
half_mod_n = ZZ( GF(n)(1/2) )

Q = half_mod_n * P
xQ, yQ = Q.xy()
print( f"xQ = {hex(xQ)}\nyQ = {hex(yQ)}" )


Copy+pasted into the sage interpreter it gives:

xQ = 0xc62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413


Personal note: Some number theoreticians already knew why such experiences are called cryptography.

more