4 ms·

Fun timing: I just implemented, purely for fun, EC curve public key recovery from signed message in Clojure, using both "regular" maths (and the Java crypto Bou

Fun timing: I just implemented, purely for fun, EC curve public key recovery from signed message in Clojure, using both "regular" maths (and the Java crypto BouncyCastle library) and then handcoded jacobian maths (I did it only for secp256k1 but I take it works with many curves). Took me quite some head scratching to get working but it was nice when it eventually worked. Tiny nitpick: "Hence, when compressing a point, an additional byte of data is used to distinguish the correct y-coordinate.". It's actually only one additional bit of data that is needed, not a full byte: all you need is the parity of the y-coordinate. Even though that one bit is often encoded in a full byte it's not always so: for example Ethereum, for a very long time, used transactions where the y-coordinate parity was encoded as a single bit, along with the "chain ID" (now with the latest protocols they're encoding the parity in a full byte, which is either 0x00 or 0x01). It's really a tiny nitpick but there you go.

drexlspivey 5y ago
You don’t even need the one bit, you can try both points and only one will be on the curve. The new Schnorr Signatures in Bitcoin are encoded in 32 bytes (just the X coordinate)
- TacticalCoder 5y ago
  > you can try both points and only one will be on the curve. Hmmm. You "decompress" the compressed key (a compressed key is one only transmitted using its x coordinate) and when you decompress, you can have two points on the secp256k1 curve (these are the "two solutions" TFA mentions): which is precisely why you pass the parity bit to get the correct one. There are two points are are going to validate y * 2 = x * 3 + 7 (mod p). So they're both on the curve right? Now all the Bitcoin/Ethereum docs says that the parity is there to speed up computation: I took it they meant by that that of the two potentially valid public keys, only one shall have fund of them and that's easy to verify. And only the one with funds on it can actually do anything. So I do agree that you don't technically even need that one bit (it only speeds up computation) however I do disagree that only one point will be on the curve (for both y and -y (aka P - y) will be on the curve).
  - drexlspivey 5y ago
    You are right, after re-reading BIP340 they decompress the X coordinate and they always pick the even Y coordinate to break ambiguity.

drexlspivey 5y ago

You don’t even need the one bit, you can try both points and only one will be on the curve. The new Schnorr Signatures in Bitcoin are encoded in 32 bytes (just the X coordinate)

TacticalCoder 5y ago
> you can try both points and only one will be on the curve. Hmmm. You "decompress" the compressed key (a compressed key is one only transmitted using its x coordinate) and when you decompress, you can have two points on the secp256k1 curve (these are the "two solutions" TFA mentions): which is precisely why you pass the parity bit to get the correct one. There are two points are are going to validate y * 2 = x * 3 + 7 (mod p). So they're both on the curve right? Now all the Bitcoin/Ethereum docs says that the parity is there to speed up computation: I took it they meant by that that of the two potentially valid public keys, only one shall have fund of them and that's easy to verify. And only the one with funds on it can actually do anything. So I do agree that you don't technically even need that one bit (it only speeds up computation) however I do disagree that only one point will be on the curve (for both y and -y (aka P - y) will be on the curve).
- drexlspivey 5y ago
  You are right, after re-reading BIP340 they decompress the X coordinate and they always pick the even Y coordinate to break ambiguity.