Ask Your Question

Revision history [back]

click to hide/show revision 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                                                                                                                                                                                               
sage: p.is_prime()                                                                                                                                                                                    

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 

(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 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()                                                                                                                                                                                      
sage: n.is_prime()                                                                                                                                                                                    

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                                                                                                                                                                                      
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                                                                                                                                                                                              
sage: yQ                                                                                                                                                                                              
sage: hex(xQ)                                                                                                                                                                                         
sage: hex(yQ)                                                                                                                                                                                         

All in one go:

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.