Revision history [back]
 | 1 | initial version |
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)
'0x17f3dadd767275ddd3b23f46723631778bf01dadaebb9a953cf068712457c010'
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
yQ = 0x17f3dadd767275ddd3b23f46723631778bf01dadaebb9a953cf068712457c010
Personal note: Some number theoreticians already knew why such experiences are called cryptography.
