4

Take a bitcoin public key (x, y) and its additive inverse (x, -y). How do you identify which is the positive point and which is the negative point?

Example

Private key 1 -> (x, y)

x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798L

y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

-y = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777L

Private key 2 -> (x, y)

x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5L

y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52aL

-y = 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705L

Private key 3 -> (x, y)

x = 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9L

y = 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672L

-y = 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bdL


Also, how can you identify which pub key is odd and which is even?

ex: private key 1 x,y is odd , private key 2 x,y is even

2
  • I don't understand the question. x and y here are elements of the finite field F_p in which there is not generally an unambiguous meaning of "odd" and "even" - every number is divisible by 2 with respect to the field multiplication. There is a similar issue with "positive" and "negative" since F_p is not an ordered field. Commented Sep 15, 2015 at 15:09
  • @NateEldredge, I think Prabu is looking to know whether or not the point was generated from a private key that is odd/even, not whether the resulting coordinates are odd/even.
    – morsecoder
    Commented Sep 15, 2015 at 16:00

2 Answers 2

5

There is no concrete determination that makes one 'y' value negative or not in an EC point. Feel free to make your own convention, like y-values <= than half of p are negative, and > half of p are positive. That's just a convention, though.

Related:


Also, how can you identify which pub key is odd and which is even?

ex: private key 1 x,y is odd , private key 2 x,y is even

You can't! Not without knowing the private key itself. If you could, you would be part of the way towards solving the discrete log problem.

3
  • Hi StephenM347, y-values <= than half of p are negative, and > half of p are positive, please can you explain this clear with some example
    – Prabu r
    Commented Sep 27, 2015 at 4:50
  • How would one break the discrete log problem by knowing whether the Y is positive, negative, odd, or even? Would it absolutely break the cryptography or just narrow the field search to find a private key?
    – Pedro
    Commented Jan 24, 2020 at 2:56
  • @PedroGonçalves Knowing whether the Y coordinate is odd or even is of course not a break of anything, because it's public information. Knowing whether the Y coordinate is "positive or negative" depends on how you define positive or negative (as stated in this answer, you can make up your own convention). IF you define it as "the corresponding private key is even/odd", then indeed knowing whether Y is positive or negative is trivially a security break (you're not supposed to be able to infer any information about the private key). Commented Apr 18, 2020 at 18:50
0

Let's look at this more formally.

Assume that there is a function lsbPriv(P) such that it returns the LSB of the private key k from the public key P = [k]G where G is the base point.

Now, we can use this function to determine all of the bits of the private key k as follows;

func DlogbyLSB(P)
  for i in range(1..256)
    x = lsbPriv(P)
    secretKey.append(x)
    if x == 0 then    ; test the bit
      P = [2^-1]P     ; i.e. we can divide `k` by `2` since the last bit is `0`
   else 
      P = [1]G        ; i.e. we substructed the bit `1` from the `k` and 
      P = [2^-1]P    ; now it is again divisible by `2`
   return secretKey

This is almost like the reverse of the double-and-add algorithm that computes the scalar multiplication on the Elliptic Curves.

So, with the help of the lsbPriv we can learn every bit of the private key k. In Cryptography we call this lsb bit as hard core predicate. As we can see, after the 256 calls, the lsbPriv reveals the key. So the lsbpriv is as hard as to recover all bits.

This also implies that if such lsbPriv function exists it is equal to solving the Dlog problem on the curve Secp256k. Currently, we know that is hard so there is no such lsbPriv function.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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