How to uncompress a single X9.62 compressed point on an ECDH P256 curve in Go?

Question

Golang's elliptical curve library can derive a secret key given a public coordinate with a X and Y value (uncompressed coordinates).

However, when the point given is a single value in X9.62 compressed form with a given y-bit, how do I uncompress it?

OpenSSL handles this scenario with this method:

https://github.com/openssl/openssl/blob/4e9b720e90ec154c9708139e96ec0ff8e2796c82/include/openssl/ec.h#L494

There also appears to be a similar question addressing the math involved, but not a best practice for Go, specifically:

https://crypto.stackexchange.com/questions/8914/ecdsa-compressed-public-key-point-back-to-uncompressed-public-key-point

How should this be done in Go?

Entomophagous

I guess somebody that understands the math needs to lift the implementation from a different ECC library. You ask for best practice, but I guess you're really asking for an implementation. – Sosna

Answer 1

As far as I know there is no point decompression function in the Go standard library (or the “x” packages), so you’d have to do it yourself (or find an existing implementation).

The implementation is not too difficult, although there are a couple of things to looks out for.

Basically, you need plug your X value into the curve equation Y2 = X3 + aX + b, and then determine which of the two roots you want using the sign bit. The tricky bit is remembering that all this needs to be done modulo the field prime of the group.

I find Go’s big integer package can be a bit odd to use sometimes, because it uses mutable values, but it does have a modular square root function which makes things a lot easier for us. The curve parameters are available in the crypto/elliptic package, although you need to know the a parameter is always -3 for these curves.

Assuming you have the compressed point as a []byte (with a leading 0x02 or 0x03) in compressed_bytes, the following should work. This is a pretty direct implementation of the equation, broken up with comments and lots of named variables to attempt to explain what’s going on. Have a look at the source of CurveParams.IsOnCurve for a slightly more efficient (and shorter) implementation. It’s basically the same up until the modular square root.

compressed_bytes := //...

// Split the sign byte from the rest
sign_byte := uint(compressed_bytes[0])
x_bytes := compressed_bytes[1:]

// Convert to big Int.
x := new(big.Int).SetBytes(x_bytes)

// We use 3 a couple of times
three := big.NewInt(3)

// and we need the curve params for P256
c := elliptic.P256().Params()

// The equation is y^2 = x^3 - 3x + b
// First, x^3, mod P
x_cubed := new(big.Int).Exp(x, three, c.P)

// Next, 3x, mod P
three_X := new(big.Int).Mul(x, three)
three_X.Mod(three_X, c.P)

// x^3 - 3x ...
y_squared := new(big.Int).Sub(x_cubed, three_X)

// ... + b mod P
y_squared.Add(y_squared, c.B)
y_squared.Mod(y_squared, c.P)

// Now we need to find the square root mod P.
// This is where Go's big int library redeems itself.
y := new(big.Int).ModSqrt(y_squared, c.P)
if y == nil {
    // If this happens then you're dealing with an invalid point.
    // Panic, return an error, whatever you want here.
}

// Finally, check if you have the correct root by comparing
// the low bit with the low bit of the sign byte. If it’s not
// the same you want -y mod P instead of y.
if y.Bit(0) != sign_byte & 1 {
    y.Neg(y)
    y.Mod(y, c.P)
}

// Now your y coordinate is in y, for all your ScalarMult needs.

Betthel

Great answer. It's a shame the question is so niche, so you haven't got the upvotes this deserves. – Heterodoxy

Answer 2

Things have improved in later Go versions. Now the method UnmarshalCompressed can be used. This was introduced with Go 1.15.

Example:

x,y := elliptic.UnmarshalCompressed(elliptic.P224(), compressed)

Bauman