0
$\begingroup$

From observation, 32 bit public key values of opposite parities are either both valid, or both invalid.

[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], Err(InvalidPublicKey)
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], Err(InvalidPublicKey)
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], Ok(PublicKey(0100000000000000000000000000000000000000000000000000000000000000eea7767e580d75bc6fdd7f58d2a84c2614fb22586068db63b346c6e60af21842))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], Ok(PublicKey(010000000000000000000000000000000000000000000000000000000000000041548981a6f28a43902280a72d57b3d9eb04dda79f97249c4cb93919f50de7bd))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2], Ok(PublicKey(02000000000000000000000000000000000000000000000000000000000000005e53b85706861f511cdabb25a45f4c42e8fc5e0ad7985a9fe009bab227e7fb66))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2], Ok(PublicKey(0200000000000000000000000000000000000000000000000000000000000000d1a847a8f879e0aee32544da5ba0b3bd1703a1f52867a5601ff6454dd8180499))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3], Ok(PublicKey(0300000000000000000000000000000000000000000000000000000000000000e440b6608078ddf043f1a9d17a870ca2b46bbc25641a5fcbc7854f376accdcd0))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3], Ok(PublicKey(03000000000000000000000000000000000000000000000000000000000000004bbb499f7e87220fbc0e562e8578f35d4b9443da9be5a034387ab0c89533232f))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4], Ok(PublicKey(04000000000000000000000000000000000000000000000000000000000000009ceb4e974992fcbc84ba2d7cd3c0d5700ac3db8b1e0a1df501f0718dac3b71a6))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4], Ok(PublicKey(04000000000000000000000000000000000000000000000000000000000000009310b168b56d03437b45d2832c3f2a8ff53c2474e1f5e20afe0f8e7253c48e59))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5], Err(InvalidPublicKey)
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5], Err(InvalidPublicKey)
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6], Ok(PublicKey(0600000000000000000000000000000000000000000000000000000000000000409a3a87b750ff0d25a0e7b48677a1b55cb9adbb67b8f8d3ccbc9903830a412a))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6], Ok(PublicKey(0600000000000000000000000000000000000000000000000000000000000000ef61c57847af00f2da5f184b79885e4aa34652449847072c334366fc7cf5bed5))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7], Err(InvalidPublicKey)
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7], Err(InvalidPublicKey)
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8], Ok(PublicKey(0800000000000000000000000000000000000000000000000000000000000000def3761176795e46a6caba358e11d3aeb51e0f2f47f91fdb7bc8332811d0d0ca))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8], Ok(PublicKey(0800000000000000000000000000000000000000000000000000000000000000510889ee8886a1b9593545ca71ee2c514ae1f0d0b806e0248437ccd7ee2f2f35))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9], Err(InvalidPublicKey)
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9], Err(InvalidPublicKey)
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, a], Err(InvalidPublicKey)
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, a], Err(InvalidPublicKey)
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, b], Err(InvalidPublicKey)
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, b], Err(InvalidPublicKey)
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, c], Ok(PublicKey(0c00000000000000000000000000000000000000000000000000000000000000a480cf899faf4ab8b1ef858bcea2c7591ee5fdff77c9d31579fe363cb15ab044))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, c], Ok(PublicKey(0c000000000000000000000000000000000000000000000000000000000000008b7b30765f50b5474e107a74315d38a6e11a020088362cea8601c9c34ea54fbb))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, d], Ok(PublicKey(0d0000000000000000000000000000000000000000000000000000000000000014c3493037636b4dedc309613ca6ca977e5880a7288430a6f170c26d49f9ce2c))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, d], Ok(PublicKey(0d000000000000000000000000000000000000000000000000000000000000001b39b6cfc79c94b2123cf69ec359356881a77f58d77bcf590e8f3d92b60631d3))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, e], Ok(PublicKey(0e0000000000000000000000000000000000000000000000000000000000000090cde85f0ceac07511dba6a43d8b1d0c41742cee9b6530fdd329b2b9c0664a9d))
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, e], Ok(PublicKey(0e000000000000000000000000000000000000000000000000000000000000009f2e17a0f2153f8aee24595bc274e2f3be8bd311649acf022cd64d463f99b562))
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, f], Err(InvalidPublicKey)
[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, f], Err(InvalidPublicKey

Is there a relation between the private keys for public keys which only differ by parity?

$\endgroup$
  • 2
    $\begingroup$ secp256k1 is a Koblitz-restricted Weierstrass-form curve $y^2 = x^3 + 7$ over $F_p$ for a specified $p$ so iff $(x,y)$ is on the curve then $(x,-y) = (x,p-y)$ also is. Moreover these points are inverses in the curve group i.e. $(x,y)+(x,-y)=O$ thus their corresponding private keys are inverses in $Z_n^+$ i.e. for the canonical values $[1,n-1]$ the relationship is $d+d'=n$ $\endgroup$ – dave_thompson_085 Aug 2 at 1:12
  • $\begingroup$ @dave_thompson_085 So, if I have key pair, so I also know another keypair where the public key is identical, apart from the parity, and the private key is n - private key? If so, why do systems bother with odd parity and not just use private keys which generate even parity public keys, to eliminate these trivial duplicates? $\endgroup$ – fadedbee Aug 2 at 7:06
  • $\begingroup$ @kelalaka Obviously no-one can claim to have observed this for all key values. I just haven't found a counter-example in millions of tests. Apologies if I haven't used the correct terminology. $\endgroup$ – fadedbee Aug 2 at 7:08
  • 1
    $\begingroup$ Because that throw away one bit of keyspace for no benefit or reason. The goal of generating a keypair is to have a keypair to use, and keypairs with even and odd publickey y's are equally usable. If you can't break d then you can't break n-d either, and if you can break either then both are broken and unusable. Note however that Bernstein's x-only (Montgomery) ECDH method ignores all of y including its parity thus effectively using $\pm Q = (\pm d) \cdot G$ as keypairs. $\endgroup$ – dave_thompson_085 Aug 3 at 0:45
  • $\begingroup$ @dave_thompson_085 Thanks for your comments, if you turn them into an answer I'll accept them. (I still don't understand the value of having n and n-d in a system. It seems like each keypair has an equivalent keypair of opposite sign and parity, so that if you know one, you know the other. To me, and I'm very-likely wrong, it seems like the keyspace has already been halved by this symmetry.) $\endgroup$ – fadedbee Aug 3 at 5:42

Your Answer

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

Browse other questions tagged or ask your own question.