如何在Go中的ECDH P256曲线上解压缩单个X9.62压缩点？

Question

Golang的椭圆曲线库可以在给定具有X和Y值(未压缩坐标)的公共坐标的情况下导出秘密密钥.

但是,当给定的点是具有给定y位的X9.62压缩形式的单个值时,如何解压缩它？

OpenSSL使用此方法处理此方案:

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

似乎还有一个类似的问题涉及数学,但不是Go的最佳实践,具体来说:

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

怎么在Go中完成？

Answer 1

据我所知,Go标准库(或"x"包)中没有任何解压缩功能,所以你必须自己做(或找到现有的实现).

虽然有一些事情需要注意,但实施并不太难.

基本上,您需要将您的X值插入曲线方程,然后使用符号位确定您想要的两个根中的哪一个.棘手的一点是要记住所有这些都需要以模块的字段填充为模.Y2 = X3 + aX + b

我发现Go的大整数包有时可能有点奇怪,因为它使用了可变值,但它确实有一个模块化的平方根函数,这使我们的事情变得更加容易.虽然您需要知道参数总是针对这些曲线,但曲线参数在crypto/elliptic包中可用.a-3

假设您将压缩点作为[]byte(带有前导0x02或0x03)in compressed_bytes,则以下内容应该有效.这是一个非常直接的方程实现,用注释和许多命名变量分解,试图解释发生了什么.查看CurveParams.IsOnCurve稍微更有效(和更短)的实现的来源.直到模块化平方根才基本相同.

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.