Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
"I find the source code utterly unenlightening" - Haha! I'd really like to vote that up two or three more times. How do you like the documentation and custom build system..... –  noloader Dec 26 '13 at 4:23
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
Makes perfect sense. Thank you! –  Zack Jun 5 '12 at 22:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.