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.

From the ECDH demo here http://www-cs-students.stanford.edu/~tjw/jsbn/ecdh.html

If I generate a private key for alice I can get

P = 1175846487558108474218546536054752289210804601041

Which gives the following public key point.

X = 583857549063195252150226340830731484791130788759
Y = 1195037839477751118658084226553581900533276838164

For ECDSA public key compression the above coordinates would be prepended by 02 and the X coordinate would be used. So the compressed key for the above (based on X9.62) is...

02583857549063195252150226340830731484791130788759

If I only have the compressed key given above, how would I derive Y i.e. the uncompressed point.

share|improve this question
    
For ECDH you probably don't need to uncompress at all. For ECDSA you take the curve equation and solve for the unknown coordinate. The only tricky part is the square-root, which AFAIK can be solved by modular exponentiation. –  CodesInChaos Jun 28 '13 at 10:40
    
You need to uncompress for ECDH too: for computations on the curve points, you have to know both coordinates. What you don't need to do with ECDH is to disambiguate between Y and -Y because at the end of ECDH you only take the X coordinate; so you must do the square root, but there is no need to keep around the least significant bit of Y. For ECDSA, you need the complete decompression, including the least significant bit. –  Thomas Pornin Jun 28 '13 at 15:22
    
@ThomasPornin I didn't look into other curve shapes, but at least for Montgomery curves you don't need decompression for DH when you use x/z coordinates. –  CodesInChaos Jun 28 '13 at 21:42
add comment

1 Answer

up vote 3 down vote accepted

All points on an elliptic curve verify, by definition, the curve equation, usually written as $Y^2 = X^3 + aX + b$, with two given $a$ and $b$ parameters (these two parameters actually define the curve). So, if you know $X$, you can use the curve equation to recompute $Y^2$. A square root extraction will yield $Y$ or $-Y$. The compressed point format includes the least significant bit of $Y$ in the first byte (the first byte is 0x02 or 0x03, depending on that bit): this bit is enough to know whether you got $Y$ or $-Y$ with the square root, and adjust in consequence.

All computations above are done in the base field, i.e. (usually) the integers modulo a prime integer. See this for square root extraction modulo a prime.

share|improve this answer
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.