1

First, some background.

1. There are some coordinates x,y satisfying y^2(mod p)=x^3+7(mod p) on the Secp256k1 curve that do not correspond to a valid Bitcoin uncompressed publicKey of the form 04[x,y].

We can prove 1 using the random_point() function in Sage with unknown generator underE=EllipticCurve(GF(modi), [0,7]). If we get lucky, after a few trials Sage returns a point such as Q.

   Q=E.random_point()

   Q
   (B8F0170E293FCC9291BEE2665E9CA9B25D3B11810ED68D9EA0CB440D7064E4DA : 
    691AA44502212591132AA6F27582B78F9976998DE355C4EE5960DB05AC0A2A3 : 1)

Now we have:

   Qx=B8F0170E293FCC9291BEE2665E9CA9B25D3B11810ED68D9EA0CB440D7064E4DA
   Qy=691AA44502212591132AA6F27582B78F9976998DE355C4EE5960DB05AC0A2A3

We verify that Qy^2(mod p) = Qx^3+7 (mod p) is satisfied so we confirm that Q is a point on the Secp256k1 curve.

Next, we try to validate Q as an uncompressed Bitcoin publicKey:

04B8F0170E293FCC9291BEE2665E9CA9B25D3B11810ED68D9EA0CB440D7064E4DA691AA44502212591132AA6F27582B78F9976998DE355C4EE5960DB05AC0A2A3

We get: Q is not a valid publicKey.

Yet, checking the validity of the mirrored point -Q, returns a valid publicKey:

   -Qx=B8F0170E293FCC9291BEE2665E9CA9B25D3B11810ED68D9EA0CB440D7064E4DA
   -Qy=F96E55BBAFDDEDA6EECD5590D8A7D4870668966721CAA3B11A69F24EA53F598C

Valid publicKey for -Q:

04B8F0170E293FCC9291BEE2665E9CA9B25D3B11810ED68D9EA0CB440D7064E4DAF96E55BBAFDDEDA6EECD5590D8A7D4870668966721CAA3B11A69F24EA53F598C

Valid publicKey for -Q (hashed):

1A2gaiiKy91Pmx8EUcbT4Hd6JFZ3sQvUhM

Question:

Why not every [x,y] coordinate on the Secp256k1 curve corresponds to a valid uncompressed publicKey?

Note:

In this question, by validity I mean a set of EC coordinates (x,y) that can be hashed into a bitcoin uncompressed address. I am specifying uncompressed for obvious reasons. My question is detailed enough I hope to show that it's not referring to compressed Bitcoin addresses.

2

Both are valid public keys just that in the first case the uncompressed public key is not represented in a valid hexadecimal format. If you look closely, your Qy has 63 hexadecimal digits (so there is a 'half-byte'). Although hashing can be done in bit boundaries, most standard implementations out there do not support it. Just try to concatenate '0' at the start of the Qy to get Qy = 0691AA44502212591132AA6F27582B78F9976998DE355C4EE5960DB05AC0A2A3 so that you get a full byte. So now your uncompressed public key is 04B8F0170E293FCC9291BEE2665E9CA9B25D3B11810ED68D9EA0CB440D7064E4DA0691AA44502212591132AA6F27582B78F9976998DE355C4EE5960DB05AC0A2A3, which would hash to P2PKH address: 17Y1XJiC72f2kyJnzwBdkaPQEGgaD1aroR

  • Excellent! Thanks for your prompt answer. – RobertH Jul 15 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.