How does DJB's nistp224 manage to fit compressed points into 224 bits?

Question

DJB's nistp224 program purports to be an implementation of elliptic curve Diffie-Hellman relative to the standard NIST P-224 elliptic curve.

To the best of my understanding, ECDH relative to this curve should produce 225-bit public messages (compressed points consisting of a 224-bit x-coordinate and a 1-bit y-coordinate), which require 29 bytes to encode (in SEC1 format). Yet somehow nistp224 manages to produce 28-byte messages, which are therefore one bit short.

How does it do this? I find the source code utterly unenlightening.

(Rationale for question: It sure would be nice if I could shave a byte off my messages on the wire.)

Answer 1

That's because you can do ECDH by exchanging only the X coordinates of your public value; as long as the shared secret depends only on the x coordinate, everything works out.

Here's the fundamental property of elliptic curves that makes this work, the x coordinate of $nP$ is only a function of the x coordinate of $P$ (and $n$); it does not depend on the y coordinate of $P$.

So, if the two sides select their secret values as $a$ and $b$, they both compute $aG$ and $bG$. They then exchange the x-coordinates of those points to the other. What both sides can do is then compute the x-coordinate of $a(bG) = b(aG) = (ab)G$. This x-coordinate is the same value on both sides. Now, neither side knows the y-coordinate of the common point; however, the x-coordinate is sufficient for a shared secret.