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

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.)

-

1 Answer

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.

-

Makes perfect sense.  Thank you! – Zack Jun 5 '12 at 22:36
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 9, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8917549252510071, "perplexity_flag": "middle"}