-1
$\begingroup$

I'm using ECDH over secp256k1 in multiple languages, and I saw something a little weird in the rust library I use.

After the point multiplication it changes y to 0x02 if it's even and to 0x03 if it's odd, and then it hashes the new y together with the regular x. Is this right? am I missing something?

https://source.that.world/source/libsecp256k1-rs/browse/master/src/ecdh.rs$25

Thanks, Elichai.

$\endgroup$
  • $\begingroup$ They seem to follow the same procedure as bitcoin does, and as this PHP implementation. Note that given $x$, $y$ is determined up to the symmetry over the $x$-axis, so determined up to the sign bit. $\endgroup$ – Ruben De Smet Jul 4 '18 at 15:33
3
$\begingroup$

For a point on the secp256k1 curve expressed in Cartesian coordinates, it holds that $y^2\equiv x^3+7\pmod p$, with prime $p\equiv3\pmod4$. There are thus two $y$ for any valid $x$. An $x$ is valid when $0\le x<p$ and $(x^3+7)^{(p-1)/2}\bmod p=1$, and the two possible $y$ are computable as $y_0=(x^3+7)^{(p+1)/4}\bmod p$ and $y_1=p-y_0$. A single one of $y_0$ or $y_1$ is even, the other is odd.

It follows that knowledge of $x$ with $(x^3+7)^{(p-1)/2}\bmod p=1$ and the parity of $y$ entirely defines a point on the curve (other than the group's neutral/point at infinity). Compressed (Cartesian) coordinates use this, and represent a point as a bytestring coding $x$ (big-endian over $\lceil(\log_2 p)/8\rceil=32$ bytes), prefixed by the byte 02 for even $y$ and the byte 03 for odd $y$. That format (among others) is standardized by ANS X9.62 (defining ECDSA) and SEC2, for public keys.

It is safe to use the above bytestring as the conventional representative of the point obtained by ECDH, and submitting it to a Key Derivation Function or hash. Practice varies, and using anything that includes $x$ (without or with $y$ in whole or in part) per some agreed-upon format is safe. ANS X9.63 (defining ECDH) and SEC2 unambiguously use $x$ only, coded as a fixed-width big-endian bytestring. That's safe enough and simple, thus good.

Footnote: Thomas Pornin's comment is a great answer.

$\endgroup$
  • 1
    $\begingroup$ Is this a standardised way for secp256k1 DH, or is SHA256(X) with X in canonical form just the de-facto standard? I felt that that was part of the original question. $\endgroup$ – Ruben De Smet Jul 4 '18 at 15:58
  • 2
    $\begingroup$ It's a "de facto" thing. Formally, ANSI X9.63 defines use of elliptic curve Diffie-Hellman, and the "shared secret" is obtained by hashing the X coordinate of the resulting point. The Bitcoin world, intent on doing things its own way with no regard for standards (after all, at its core, Bitcoin is an anarchist endeavour), decided to do things differently. Since Bitcoin is the main user of secp256k1, their way of doing things is a de facto standard. $\endgroup$ – Thomas Pornin Jul 4 '18 at 17:34

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.