0
$\begingroup$

Can I know just from a Bitcoin public key if the private key is odd or even?


[moderator note] That is, can we find parity of the private key from a secp256k1 public key?
For the original dump of digits, see here.

$\endgroup$
1
  • $\begingroup$ Note to the OP: questions consisting mostly of ciphertext are off-topic. $\endgroup$
    – fgrieu
    Nov 25 at 19:48
4
$\begingroup$

Can I know just from a Bitcoin public key if the private key is odd or even?

We hope you can't; if you can, then you can solve the discrete log problem, that is, find the entire private key.

In cryptographical terminology, we say that the lsbit of the private key is a "hard core" bit, as it is as hard to recover as the entire value.

How it is done is straight-forward (at least, in the nonprobabilistic case, where your 'find-the-lsbit' algorithm always returns the correct answer); it works as follows $\log(q)$ times:

  • Take the public key $Y$ and use your algorithm to find the lsbit of the private key; this gives us the lsbit of the private key $y$.

  • If that lsbit was a '1', then replace $Y := Y - G$; this has the effect of replacing $y$ with $y-1$

  • Then, replace $Y := [2^{-1}] Y$, that is, do a point multiplication with the inverse of 2 (which exists, because the curve has an odd order); this has the effect of replacing $y$ with $y/2$.

By doing this $\log(p)$ times, this reads off the bits of the private exponent in lsbit-first order; giving us the entire value.

$\endgroup$
1

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.