# ECDSA Compressed public key point back to uncompressed public key point

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.

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