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

Question

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

但是，当给定的点是具有给定 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值进入曲线方程Y<sup>2</sup> = X<sup>3</sup> + aX + b ，然后使用符号位确定您想要的两个根中的哪一个。棘手的一点是要记住所有这些都需要对组的场质数取模。

我找到了 Go’s big integer package有时使用起来有点奇怪，因为它使用可变值，但它确实有一个 modular square root function这让我们的事情变得容易多了。 crypto/elliptic package 中提供了曲线参数, 虽然你需要知道 a参数始终为 -3对于这些曲线。

假设您将压缩点设为 []byte (以 0x02 或 0x03 开头)在 compressed_bytes 中, following should work .这是等式的一个非常直接的实现，用注释和许多命名变量分解，试图解释发生了什么。查看 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.