GO语言中，如何将有效的签名验证为无效的签名？

huangapple
go评论84阅读模式
英文:

GO Language ECDSA verify the valid signature to invalid

问题

我在我的C++程序中编写了ECDSA函数。当我在C++的ECDSA验证函数中测试我的签名时，它能正常工作，但并非所有的测试都能在GO语言中通过。

因此，我尝试将我的公钥（来自C++）导出为GO语言中的十六进制字符串缓冲区（33字节）。然后，我使用ellipitc.UnmarshalCompressed在GO程序中检索我的公钥。后来，我发现当公钥是通过使用标量乘法从私钥生成时，解组的公钥的Y坐标不同。我在下面放置了代码。

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"log"
	"math/big"
	"os"
)

func main() {

	/* UnmarshalCompressed public key from C++ buffer (hex string) */
	publicKeyBufferFromCplusplus, err := hex.DecodeString("02d36b0e521ca9a28cd6f2ddc56dc0973215702f6f67ed0670b9bc9a98c28d473b")
	if err != nil {
		fmt.Println("Unable to convert hex to byte. ", err)
	}
	pk := new(ecdsa.PublicKey)
	pk.Curve = elliptic.P256()
	pk.X, pk.Y = elliptic.UnmarshalCompressed(elliptic.P256(), publicKeyBufferFromCplusplus[:])

	/* Generate the key pair in GO, using the private key (as decimal) from C++ */
	expect_sk := new(ecdsa.PrivateKey)
	expect_sk.D, _ = new(big.Int).SetString("50228957095953179898827503463423289296009712707225507368245266147079499081684", 10)
	expect_sk.PublicKey.Curve = elliptic.P256()
	expect_sk.PublicKey.X, expect_sk.PublicKey.Y = expect_sk.PublicKey.Curve.ScalarBaseMult(expect_sk.D.Bytes())
	expect_pk := expect_sk.PublicKey

	/* compare the two public keys, the X coordinate is the same, but Y is different */
	fmt.Printf("pk_x:\t\t%d\n", pk.X)
	fmt.Printf("expect pk_x:\t%d\n\n", expect_pk.X)
	fmt.Printf("pk_y:\t\t%d\n", pk.Y)
	fmt.Printf("expect pk_y:\t%d\n", expect_pk.Y)

}

这是终端的结果：

pk_x:           95627162525183504786576659676808415919520991299985517290103803735976207796027
expect pk_x:    95627162525183504786576659676808415919520991299985517290103803735976207796027

pk_y:           106312815215663533204607583749797836088594130128596587441436180287153537381066
expect pk_y:    9479273994692715558089863199609737441492013286693726754097451021713560472885

请注意，差异在于Y坐标，而X坐标是相同的。

  [1]: https://pkg.go.dev/crypto/elliptic#UnmarshalCompressed
英文:

I coded the ECDSA functions in my C++ program. When I test my signature it works fine in my C++ ECDSA verify function, but not every test pass on the GO language.

Therefore, I tried to export my public key (from my C++) as hex string of buffer (33 bytes) to GO Language. Then, I use ellipitc.UnmarshalCompressed to retrieve my public key on GO program. Later, I found that the Unmarshal public key has different Y-coordinate when the public key is generated from the secret key using Scalar Multiplication. I have put the code below.

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"log"
	"math/big"
	"os"
)    
func main() {

	/* UnmarshalCompressed public key from C++ buffer (hex string) */
	publicKeyBufferFromCplusplus, err := hex.DecodeString("02d36b0e521ca9a28cd6f2ddc56dc0973215702f6f67ed0670b9bc9a98c28d473b")
	if err != nil {
		fmt.Println("Unable to convert hex to byte. ", err)
	}
	pk := new(ecdsa.PublicKey)
	pk.Curve = elliptic.P256()
	pk.X, pk.Y = elliptic.UnmarshalCompressed(elliptic.P256(), publicKeyBufferFromCplusplus[:])

	/* Generate the key pair in GO, using the private key (as decimal) from C++ */
	expect_sk := new(ecdsa.PrivateKey)
	expect_sk.D, _ = new(big.Int).SetString("50228957095953179898827503463423289296009712707225507368245266147079499081684", 10)
	expect_sk.PublicKey.Curve = elliptic.P256()
	expect_sk.PublicKey.X, expect_sk.PublicKey.Y = expect_sk.PublicKey.Curve.ScalarBaseMult(expect_sk.D.Bytes())
	expect_pk := expect_sk.PublicKey

	/* compare the two public keys, the X coordinate is the same, but Y is different */
	fmt.Printf("pk_x:\t\t%d\n", pk.X)
	fmt.Printf("expect pk_x:\t%d\n\n", expect_pk.X)
	fmt.Printf("pk_y:\t\t%d\n", pk.Y)
	fmt.Printf("expect pk_y:\t%d\n", expect_pk.Y)

}

Here's the result from the terminal

pk_x:           95627162525183504786576659676808415919520991299985517290103803735976207796027
expect pk_x:    95627162525183504786576659676808415919520991299985517290103803735976207796027

pk_y:           106312815215663533204607583749797836088594130128596587441436180287153537381066
expect pk_y:    9479273994692715558089863199609737441492013286693726754097451021713560472885

Please note that the difference is the Y-coordinate, where the X-coordinate is the same.

答案1

得分: 0

更新：

我发现我的C++椭圆曲线库在将公钥（点）压缩（编组）为SEC 1，版本2.0，第2.3.3节形式时存在一个错误。一些点的第一个字节错误（从奇数变为偶数，或从偶数变为奇数）。

1*G     GO缓冲区：0x036b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296     C++缓冲区：0x026b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
2*G     GO缓冲区：0x037cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978     C++缓冲区：0x037cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978
3*G     GO缓冲区：0x025ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c     C++缓冲区：0x035ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c
4*G     GO缓冲区：0x02e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852     C++缓冲区：0x02e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852
5*G     GO缓冲区：0x0251590b7a515140d2d784c85608668fdfef8c82fd1f5be52421554a0dc3d033ed     C++缓冲区：0x0251590b7a515140d2d784c85608668fdfef8c82fd1f5be52421554a0dc3d033ed
6*G     GO缓冲区：0x02b01a172a76a4602c92d3242cb897dde3024c740debb215b4c6b0aae93c2291a9     C++缓冲区：0x03b01a172a76a4602c92d3242cb897dde3024c740debb215b4c6b0aae93c2291a9
7*G     GO缓冲区：0x028e533b6fa0bf7b4625bb30667c01fb607ef9f8b8a80fef5b300628703187b2a3     C++缓冲区：0x038e533b6fa0bf7b4625bb30667c01fb607ef9f8b8a80fef5b300628703187b2a3
8*G     GO缓冲区：0x0262d9779dbee9b0534042742d3ab54cadc1d238980fce97dbb4dd9dc1db6fb393     C++缓冲区：0x0362d9779dbee9b0534042742d3ab54cadc1d238980fce97dbb4dd9dc1db6fb393
9*G     GO缓冲区：0x02ea68d7b6fedf0b71878938d51d71f8729e0acb8c2c6df8b3d79e8a4b90949ee0     C++缓冲区：0x02ea68d7b6fedf0b71878938d51d71f8729e0acb8c2c6df8b3d79e8a4b90949ee0

因此，一些公钥（点）以{x，-y}的形式导出，而不是{x，y}。

原文

椭圆曲线（EC）公钥遵循高效密码标准（SEC），SEC 1：椭圆曲线密码第2.3.3节中的椭圆曲线点到八进制字符串的转换。

以压缩形式（字节）表示的公钥的第一个字节为0x02，如果y坐标为偶数。否则，为0x03，如果y坐标为奇数。

根据数学推导，给定一个x坐标

y^2 = x^3 + ax + b (mod p)

上述方程有两个解，(x, y)和(x, -y)，因为y^2 = (-y)^2

此外，-y等于(p - y)，因为它是模素数p的整数域。

由于p是素数且p！=2，p是奇数。那么，如果y是奇数，则**-y**（或**(p-y)**）是偶数，反之亦然。

ECDSA验证算法不需要公钥的y坐标，因为它只需要x坐标。因此，在检查签名元组**{r，s}**时，我将使用具有相同x坐标但不同y坐标（从奇数翻转为偶数或反之亦然）的公钥进行检查。我真的不知道为什么GO语言的ECDSA包只允许两个y坐标值中的一个。

以下是我的代码示例。假设我有一个压缩的公钥作为缓冲区publicKeyBuffer[:]

然后，我可以使用Unmarshal将其解组为x坐标和y坐标

    pk := new(ecdsa.PublicKey)
    pk.Curve = elliptic.P256()    
    pk.X, pk.Y = elliptic.UnmarshalCompressed(elliptic.P256(), publicKeyBuffer[:])

我们可以检查签名元组{r，s}是否有效

valid := ecdsa.Verify(pk, hash[:], r, s)

如果签名无效，即valid == false，尝试将pk.Y值更改为其对应值。有两种简单的方法可以做到这一点。

第一种方法是，将公钥缓冲区的第一个字节从0x02更改为0x03，或者反之亦然。可以通过将第一个字节与0x01（即1）进行XOR来实现这一点。

    valid = ecdsa.Verify(pk, hash[:], r, s)

    /* 第一种方法 */
	if !valid {
		publicKeyBuffer[0] ^= 1 // 将公钥缓冲区的y坐标从0x02更改为0x03（或反之亦然）
		pk.X, pk.Y = elliptic.UnmarshalCompressed(elliptic.P256(), publicKeyBuffer[:])
		valid = ecdsa.Verify(pk, hash[:], r, s)
	}
    fmt.Println("签名验证结果：", valid)

第二种方法是，将y坐标更改为其（p-y）值，即将其更改为（-y）

    valid = ecdsa.Verify(pk, hash[:], r, s)

	/* 第二种方法 */
	if !valid {
		pk.Y = new(big.Int).Sub(pk.Curve.Params().P, pk.Y) // 用（-y）替换y坐标pk.Y，注意。(-y)等于（p - y）
		valid = ecdsa.Verify(pk, hash[:], r, s)
	}
	fmt.Println("签名验证结果：", valid)

如果签名仍然无效，则与公钥解组无关。

附注：我不知道为什么GO ECDSA语言只允许公钥的另一个y坐标值

英文:

Update:

I found that my C++ Elliptic curve library has a bug when compressing (marshal) the public key (points) into SEC 1, Version 2.0, Section 2.3.3 form. Some points have the first byte wrong (from odd to even, or even to odd).

1*G     GO buffer: 0x036b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296     C++ buffer: 0x026b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
2*G     GO buffer: 0x037cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978     C++ buffer: 0x037cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978
3*G     GO buffer: 0x025ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c     C++ buffer: 0x035ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c
4*G     GO buffer: 0x02e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852     C++ buffer: 0x02e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852
5*G     GO buffer: 0x0251590b7a515140d2d784c85608668fdfef8c82fd1f5be52421554a0dc3d033ed     C++ buffer: 0x0251590b7a515140d2d784c85608668fdfef8c82fd1f5be52421554a0dc3d033ed
6*G     GO buffer: 0x02b01a172a76a4602c92d3242cb897dde3024c740debb215b4c6b0aae93c2291a9     C++ buffer: 0x03b01a172a76a4602c92d3242cb897dde3024c740debb215b4c6b0aae93c2291a9
7*G     GO buffer: 0x028e533b6fa0bf7b4625bb30667c01fb607ef9f8b8a80fef5b300628703187b2a3     C++ buffer: 0x038e533b6fa0bf7b4625bb30667c01fb607ef9f8b8a80fef5b300628703187b2a3
8*G     GO buffer: 0x0262d9779dbee9b0534042742d3ab54cadc1d238980fce97dbb4dd9dc1db6fb393     C++ buffer: 0x0362d9779dbee9b0534042742d3ab54cadc1d238980fce97dbb4dd9dc1db6fb393
9*G     GO buffer: 0x02ea68d7b6fedf0b71878938d51d71f8729e0acb8c2c6df8b3d79e8a4b90949ee0     C++ buffer: 0x02ea68d7b6fedf0b71878938d51d71f8729e0acb8c2c6df8b3d79e8a4b90949ee0

Therefore, some of the public keys (points) are exported as {x,-y} instead of {x,y}

Original

The Elliptic Curve (EC) public key follows the Standards for Efficient Cryptography (SEC), SEC 1: Elliptic Curve Cryptography in section 2.3.3 Elliptic-Curve-Point-to-Octet-String Conversion.

The public key in compressed form (as bytes) has the first byte as 0x02 if the y-coordinate is even. Otherwise, 0x03 if the y-coordinate is odd.

Mathematically, given only an x-coordinate

y^2 = x^3 + ax + b (mod p)

There are two solutions to the equation above, (x, y) and (x, -y) since y^2 = (-y)^2

In addition, -y is equal to (p - y) since it's a field of integers modulo prime p.

Since p is prime and p!=2, p is odd. Then, if y is odd, then -y (or (p-y)) is even, and vice versa.

The ECDSA verification algorithm does not require the y-coordinate of the public key since it requires only the x-coordinate of it. Therefore, when I check the signature tuple {r,s}, I will check it against with the public key which same x-coordinate, but different y-coordinate (flip from odd to even or vice-versa). I don't really know why GO Language ECDSA package allows only one of two y-coordinate value.

Here's my code sample below.
Let's say I have a compressed public key as a buffer publicKeyBuffer[:]

Then I can Unmarshal it to get the x-coordinate and y-coordinate

    pk := new(ecdsa.PublicKey)
    pk.Curve = elliptic.P256()    
    pk.X, pk.Y = elliptic.UnmarshalCompressed(elliptic.P256(), publicKeyBuffer[:])

We can check if the signature tuple {r,s} is valid or not

valid := ecdsa.Verify(pk, hash[:], r, s)

If the signature is invalid i.e. valid == false try changing the pk.Y value to its counterpart. You can do so in two simple ways.

The first way, you change the first byte of the public key buffer from either 0x02 to 0x03 or vice versa. You can achieve this by doing XOR first byte with 0x01 (simply 1).

    valid = ecdsa.Verify(pk, hash[:], r, s)

    /* The 1st way */
	if !valid {
		publicKeyBuffer[0] ^= 1 // change the y-coordinate by switching 0x02 to 0x03 (or vice versa) of public key buffer
		pk.X, pk.Y = elliptic.UnmarshalCompressed(elliptic.P256(), publicKeyBuffer[:])
		valid = ecdsa.Verify(pk, hash[:], r, s)
	}
    fmt.Println("signature verified:", valid)

In the 2nd way, we change the y-coordinate to its (p-y) value i.e., change it to (-y)

    valid = ecdsa.Verify(pk, hash[:], r, s)

	/* The 2nd way */
	if !valid {
		pk.Y = new(big.Int).Sub(pk.Curve.Params().P, pk.Y) // replace y-coordinate pk.Y with (-y), Note. (-y) is equal (p - y)
		valid = ecdsa.Verify(pk, hash[:], r, s)
	}
	fmt.Println("signature verified:", valid)

If the signature is still invalid, then it's not about the public key Unmarshal.

P.S. I don't know why the GO ECDSA Language does not allow the other y-coordinate value of the public key

huangapple
  • 本文由 发表于 2022年9月15日 01:57:09
  • 转载请务必保留本文链接：https://go.coder-hub.com/73721296.html
  • cryptography
  • digital-signature
  • ecdsa
  • elliptic-curve
  • go
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定