GO Language ECDSA verify the valid signature to invalid

usermc2d 0
Viewed 138

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.

digital-signature elliptic-curve ecdsa cryptography go
1 Answers

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

usermc2d0
Related