英文:
How to uncompress a single X9.62 compressed point on an ECDH P256 curve in Go?
问题
Golang的椭圆曲线库可以根据具有X和Y值(未压缩坐标)的公共坐标派生出一个秘密密钥。
然而,当给定的点是以X9.62压缩形式表示的单个值,并带有给定的y位时,我该如何解压缩它?
OpenSSL使用以下方法处理这种情况:
还有一个类似的问题涉及到所涉及的数学问题,但没有针对Go的最佳实践:
在Go中应该如何处理这个问题?
英文:
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:
There also appears to be a similar question addressing the math involved, but not a best practice for Go, specifically:
How should this be done in Go?
答案1
得分: 16
据我所知,Go标准库(或者“x”包)中没有点解压缩函数,所以你需要自己实现(或者找到一个现有的实现)。
实现并不太难,尽管有一些需要注意的地方。
基本上,你需要将你的X
值插入到曲线方程Y^2 = X^3 + aX + b
中,然后使用符号位确定你想要的两个根中的哪一个。棘手的地方在于记住所有这些操作都需要在群的有限域素数模下进行。
我发现Go的大整数包有时候使用起来有点奇怪,因为它使用可变值,但它确实有一个模平方根函数,这对我们来说非常方便。曲线参数可以在crypto/elliptic
包中找到,尽管你需要知道这些曲线的a
参数始终为-3
。
假设你将压缩的点表示为[]byte
(带有前导的0x02
或0x03
)存储在compressed_bytes
中,下面的代码应该可以工作。这是一个相当直接的实现,通过注释和大量的命名变量来解释正在发生的事情。查看CurveParams.IsOnCurve
的源代码可以找到一个稍微更高效(更短)的实现。它基本上与模平方根之前的部分相同。
compressed_bytes := //...
// 将符号字节与其余部分分离
sign_byte := uint(compressed_bytes[0])
x_bytes := compressed_bytes[1:]
// 转换为大整数
x := new(big.Int).SetBytes(x_bytes)
// 我们会多次使用3
three := big.NewInt(3)
// 我们需要P256的曲线参数
c := elliptic.P256().Params()
// 方程为y^2 = x^3 - 3x + b
// 首先计算x^3,模P
x_cubed := new(big.Int).Exp(x, three, c.P)
// 接下来计算3x,模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 模P
y_squared.Add(y_squared, c.B)
y_squared.Mod(y_squared, c.P)
// 现在我们需要找到模P的平方根。
// 这就是Go的大整数库派上用场的地方。
y := new(big.Int).ModSqrt(y_squared, c.P)
if y == nil {
// 如果发生这种情况,说明你处理的是一个无效的点。
// 在这里可以抛出异常、返回错误,或者采取其他操作。
}
// 最后,通过比较低位与符号字节的低位来检查是否有正确的根。
// 如果不相同,你需要取-y mod P而不是y。
if y.Bit(0) != sign_byte & 1 {
y.Neg(y)
y.Mod(y, c.P)
}
// 现在你的y坐标在y中,可以用于所有的ScalarMult需求。
希望对你有帮助!
英文:
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 <code>Y<sup>2</sup> = X<sup>3</sup> + aX + b</code>, 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.
答案2
得分: 1
在后续的Go版本中,情况有所改善。现在可以使用方法UnmarshalCompressed。这是在Go 1.15中引入的。
示例:
x, y := elliptic.UnmarshalCompressed(elliptic.P224(), compressed)
英文:
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)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论