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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Note to the OP: questions consisting mostly of ciphertext are off-topic. $\endgroup$– fgrieu ♦Commented Nov 25, 2021 at 19:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ drawing attention to a followup question: crypto.stackexchange.com/questions/96349/… $\endgroup$ Commented Nov 28, 2021 at 14:54