DJB\'s nistp224 program purports to be an implementation of elliptic curve Diffi

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

Explanation / 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.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.